Глобальная оптимизация - Global optimization

Глобальная оптимизация это филиал Прикладная математика и числовой анализ который пытается найти глобальный минимумы или максимумы функции или набора функций на данном наборе. Обычно это описывается как проблема минимизации, потому что максимизация действительной функции ${ displaystyle g (x)}$ эквивалентно минимизации функции ${ Displaystyle е (х): = (- 1) cdot g (x)}$ .

Для возможной нелинейной и невыпуклой непрерывной функции ${ displaystyle f: Omega subset mathbb {R} ^ {n} to mathbb {R}}$ с глобальными минимумами ${ displaystyle f ^ {*}}$ и набор всех глобальных минимизаторов ${ displaystyle X ^ {*}}$ в ${ displaystyle Omega}$ , стандартная задача минимизации может быть записана как

{ Displaystyle мин _ {х в Omega} е (х),}

то есть найти ${ displaystyle f ^ {*}}$ и глобальный минимизатор в ${ displaystyle X ^ {*}}$ ; куда ${ displaystyle Omega}$ является (не обязательно выпуклым) компактным множеством, определяемым неравенствами ${ Displaystyle g_ {я} (х) geqslant 0, я = 1, ldots, r}$ .

Глобальная оптимизация отличается от локальной оптимизации тем, что нацелена на поиск минимума или максимума по заданному набору, а не на поиск местный минимумы или максимумы. Найти произвольный локальный минимум относительно просто с помощью классических локальная оптимизация методы. Найти глобальный минимум функции гораздо сложнее: аналитические методы часто не применимы, а использование стратегий численного решения часто приводит к очень сложным проблемам.

Общая теория

Недавний подход к проблеме глобальной оптимизации заключается в следующем: минимальное распределение .^[1] В этой работе связь между любой непрерывной функцией ${ displaystyle f}$ на компакте ${ displaystyle Omega subset mathbb {R} ^ {n}}$ и его глобальные минимумы ${ displaystyle f ^ {*}}$ было строго установлено. Как типичный случай, следует, что

{ Displaystyle lim _ {к к infty} int _ { Omega} е (х) м ^ {(к)} (х) , mathrm {d} х = е ^ {*}, ~ ~ { textrm {where}} ~~ m ^ {(k)} (x) = { frac {e ^ {- kf (x)}} { int _ { Omega} e ^ {- kf (x )} , mathrm {d} x}};}

тем временем,

{ displaystyle lim _ {k to infty} m ^ {(k)} (x) = left {{ begin {array} {cl} { frac {1} { mu (X ^ { *})}}, & x in X ^ {*}, 0, & x in Omega -X ^ {*}, end {array}} right.}

куда ${ displaystyle mu (X ^ {*})}$ это ${ displaystyle n}$ -мерная мера Лебега множества минимизаторов ${ displaystyle X ^ {*} in Omega}$ . И если ${ displaystyle f}$ не постоянна на ${ displaystyle Omega}$ , монотонное отношение

{ Displaystyle int _ { Omega} f (x) m ^ {(k)} (x) , mathrm {d} x> int _ { Omega} f (x) m ^ {(k + Дельта k)} (x) , mathrm {d} x> f ^ {*}}

относится ко всем ${ Displaystyle к в mathbb {R}}$ и ${ displaystyle Delta k> 0}$ , что подразумевает серию монотонных отношений сдерживания, и одна из них, например,

{ displaystyle Omega supset D_ {f} ^ {(k)} supset D_ {f} ^ {(k + Delta k)} supset X ^ {*}, { text {где}} D_ {f } ^ {(k)} = left {x in Omega: f (x) leqslant int _ { Omega} f (t) m ^ {(k)} (t) , mathrm { d} t right }.}

И мы определяем минимальное распределение быть слабым пределом ${ displaystyle m_ {f, Omega}}$ так что личность

{ Displaystyle int _ { Omega} m_ {f, Omega} (x) varphi (x) , mathrm {d} x = lim _ {k to infty} int _ { Omega } m ^ {(k)} (x) varphi (x) , mathrm {d} x}

выполняется для любой гладкой функции ${ displaystyle varphi}$ с компактной опорой в ${ displaystyle Omega}$ . Вот два непосредственных свойства ${ displaystyle m_ {f, Omega}}$ :

(1)

{ displaystyle m_ {f, Omega}}

удовлетворяет личность

{ displaystyle int _ { Omega} m_ {f, Omega} (x) , mathrm {d} x = 1}

.

(2) Если

{ displaystyle f}

продолжается на

{ displaystyle Omega}

, тогда

{ displaystyle f ^ {*} = int _ { Omega} f (x) m_ {f, Omega} (x) , mathrm {d} x}

.

Для сравнения: хорошо известная связь между любой дифференцируемой выпуклой функцией и ее минимумом строго устанавливается градиентом. Если ${ displaystyle f}$ дифференцируема на выпуклом множестве ${ displaystyle D}$ , тогда ${ displaystyle f}$ выпукло тогда и только тогда, когда

{ Displaystyle f (y) geqslant f (x) + nabla f (x) (y-x), ~~ forall x, y in D;}

таким образом, ${ Displaystyle набла е (х ^ {*}) = 0}$ подразумевает, что ${ Displaystyle f (y) geqslant f (x ^ {*})}$ относится ко всем ${ displaystyle y in D}$ , т.е. ${ displaystyle x ^ {*}}$ является глобальным минимизатором ${ displaystyle f}$ на ${ displaystyle D}$ .

Приложения

Типичные примеры приложений глобальной оптимизации включают:

Прогноз структуры белка (минимизировать функцию энергия / свободная энергия)
Вычислительная филогенетика (например, минимизировать количество преобразований символов в дереве)
Проблема коммивояжера и конструкция электрической схемы (минимизировать длину пути)
Химическая инженерия (например, анализируя Энергия Гиббса )
Проверка безопасности, техника безопасности (например, механических конструкций, зданий)
Анализ наихудшего случая
Математические задачи (например, Гипотеза Кеплера )
Проблемы упаковки объектов (проектирования конфигурации)
Отправная точка нескольких молекулярная динамика Моделирование состоит из начальной оптимизации энергии моделируемой системы.
Спиновые очки
Калибровка модели распространения радиоволн и многих других моделей в науке и технике
Подгонка кривой подобно нелинейный метод наименьших квадратов анализ и другие обобщения, используемые при подгонке параметров модели к экспериментальным данным в химии, физике, биологии, экономике, финансах, медицине, астрономии, инженерии.

Детерминированные методы

Наиболее успешные общие точные стратегии:

Внутреннее и внешнее приближение

В обеих этих стратегиях множество, по которому должна быть оптимизирована функция, аппроксимируется многогранниками. Во внутреннем приближении многогранники содержатся в множестве, а во внешнем приближении многогранники содержат множество.

Режущие методы

В плоскостной метод общий термин для методов оптимизации, которые итеративно уточняют возможный набор или целевая функция с помощью линейных неравенств, называемых порезы. Такие процедуры широко используются для поиска целое число решения для смешанное целочисленное линейное программирование (MILP), а также для решения общих, не обязательно дифференцируемых выпуклая оптимизация проблемы. Использование режущих плоскостей для решения MILP было введено Ральф Э. Гомори и Вацлав Хваталь.

Методы ветвления и привязки

Ветвь и переплет (BB или же B & B) является алгоритм парадигма дизайна для дискретный и комбинаторная оптимизация проблемы. Алгоритм ветвей и границ состоит из систематического перечисления возможных решений с помощью поиск в пространстве состояний: набор возможных решений рассматривается как формирующий укоренившееся дерево с полным набором в корень. Алгоритм исследует ветви этого дерева, которые представляют собой подмножества множества решений. Перед тем, как перечислить возможные решения ветви, ветвь проверяется по верхней и нижней оценкам. границы на оптимальном решении и отбрасывается, если оно не может дать лучшего решения, чем лучшее, найденное алгоритмом на данный момент.

Интервальные методы

Интервальная арифметика, интервальная математика, интервальный анализ, или же интервальное вычисление, это метод, разработанный математиками с 1950-х по 1960-е гг. как подход к оценке ошибки округления и погрешности измерения в математическое вычисление и таким образом развивая численные методы дающие надежные результаты. Интервальная арифметика помогает находить надежные и гарантированные решения уравнений и задач оптимизации.

Методы, основанные на реальной алгебраической геометрии

Реальная алгебра - это часть алгебры, имеющая отношение к реальной алгебраической (и полуалгебраической) геометрии. В основном это связано с изучением упорядоченные поля и заказанные кольца (особенно реальные закрытые поля ) и их приложения к изучению положительные полиномы и суммы квадратов многочленов. Его можно использовать в выпуклая оптимизация

Стохастические методы

Существует несколько точных или неточных алгоритмов на основе Монте-Карло:

Прямой отбор проб Монте-Карло

В этом методе случайное моделирование используется для поиска приближенного решения.

Пример: задача коммивояжера это то, что называется обычной задачей оптимизации. То есть все факты (расстояния между каждой точкой назначения), необходимые для определения оптимального пути, по которому следует следовать, известны с уверенностью, и цель состоит в том, чтобы просмотреть возможные варианты путешествия, чтобы найти путь с наименьшим общим расстоянием. Однако давайте предположим, что вместо того, чтобы минимизировать общее расстояние, пройденное для посещения каждого желаемого пункта назначения, мы хотели минимизировать общее время, необходимое для достижения каждого пункта назначения. Это выходит за рамки обычной оптимизации, поскольку время в пути по своей сути неопределенно (пробки, время суток и т. Д.). В результате, чтобы определить наш оптимальный путь, мы хотели бы использовать моделирование - оптимизацию, чтобы сначала понять диапазон потенциального времени, которое может потребоваться, чтобы перейти от одной точки к другой (представленной в данном случае распределением вероятностей, а не конкретным расстоянием). а затем оптимизировать наши решения о поездках, чтобы определить лучший путь, по которому следует идти, с учетом этой неопределенности.

Стохастическое туннелирование

Стохастическое туннелирование (STUN) - это подход к глобальной оптимизации, основанный на Метод Монте-Карло -отбор проб функции, которая должна быть объективно минимизирована, в которой функция нелинейно преобразуется, чтобы упростить туннелирование между областями, содержащими минимумы функции. Более простое туннелирование позволяет быстрее исследовать пространство для образца и быстрее найти хорошее решение.

Параллельный отпуск

Параллельный отпуск, также известный как обмен репликами выборка MCMC, это симуляция метод, направленный на улучшение динамических свойств Метод Монте-Карло моделирование физических систем и Цепь Маркова Монте-Карло (MCMC) методы отбора проб в более общем плане. Метод обмена репликами был первоначально разработан Свендсеном,^[2] затем продлен Гейером^[3] и позже разработан, среди прочего, Джорджио Паризи.,^[4]^[5]Сугита и Окамото сформулировали молекулярная динамика вариант параллельного отпуска:^[6] это обычно известно как молекулярная динамика с обменом реплик или REMD.

По сути, один запускается N копии системы, инициализированные случайным образом, при разных температурах. Затем, исходя из критерия Метрополиса, происходит обмен конфигурациями при разных температурах. Идея этого метода состоит в том, чтобы сделать конфигурации при высоких температурах доступными для моделирования при низких температурах и наоборот. Это приводит к очень надежному ансамблю, который способен отобрать как низкоэнергетические, так и высокоэнергетические конфигурации. Таким образом, термодинамические свойства, такие как удельная теплоемкость, которая обычно плохо вычисляется в каноническом ансамбле, может быть вычислена с большой точностью.

Эвристика и метаэвристика

Главная страница: Метаэвристический

Другие подходы включают эвристические стратегии для поиска в пространстве поиска более или менее интеллектуальным способом, в том числе:

Оптимизация колонии муравьев (ACO)
Имитация отжига, обобщенная вероятностная метаэвристика
Табу поиск, расширение местный поиск способный выйти из локальных минимумов
Эволюционные алгоритмы (например., генетические алгоритмы и стратегии эволюции )
Дифференциальная эволюция, метод, который оптимизирует проблема итеративно пытаясь улучшить возможное решение в отношении данной меры качества
Алгоритмы оптимизации на основе роя (например., оптимизация роя частиц, социальная когнитивная оптимизация, оптимизация нескольких роев и оптимизация колонии муравьев )
Меметические алгоритмы, совмещая глобальные и локальные стратегии поиска
Реактивная поисковая оптимизация (т.е. интеграция подсимвольных методов машинного обучения в поисковую эвристику)
Постепенная оптимизация, метод, который пытается решить сложную проблему оптимизации, сначала решая значительно упрощенную задачу, и постепенно преобразовывая эту проблему (при оптимизации), пока она не станет эквивалентной сложной задаче оптимизации.^[7]^[8]^[9]

Подходы на основе методологии поверхности реагирования

IOSO Косвенная оптимизация на основе самоорганизации
Байесовская оптимизация, последовательная стратегия проектирования для глобальных оптимизация функций черного ящика с использованием Байесовская статистика^[10]

Смотрите также

Сноски

^ Сяопэн Луо (2018). «Минимальное распределение для глобальной оптимизации». arXiv:1812.03457. Цитировать журнал требует | журнал = (помощь)
^ Свендсен Р. Х. и Ван Дж. С. (1986) Реплика Монте-Карло моделирования спиновых стекол Physical Review Letters 57: 2607–2609
^ К. Дж. Гейер, (1991) в Вычислительная техника и статистика, Материалы 23-го симпозиума по интерфейсу, Американская статистическая ассоциация, Нью-Йорк, с. 156.
^ Марко Фальчони и Майкл В. Дим (1999). «Смещенная схема Монте-Карло для решения структуры цеолита». J. Chem. Phys. 110 (3): 1754–1766. arXiv:cond-mat / 9809085. Bibcode:1999ЖЧФ.110.1754Ф. Дои:10.1063/1.477812.
^ Дэвид Дж. Эрл и Майкл В. Дим (2005) «Параллельная закалка: теория, приложения и новые перспективы», Phys. Chem. Chem. Phys., 7, 3910
^ Ю. Сугита и Ю. Окамото (1999). «Реплико-обменный молекулярно-динамический метод сворачивания белков». Письма по химической физике. 314 (1–2): 141–151. Bibcode:1999CPL ... 314..141S. Дои:10.1016 / S0009-2614 (99) 01123-9.
^ Такер, Нил; Кутс, Тим (1996). «Методы постепенной невыпуклости и оптимизации с несколькими разрешениями». Видение через оптимизацию.
^ Блейк, Эндрю; Зиссерман, Эндрю (1987). Визуальная реконструкция. MIT Press. ISBN 0-262-02271-0.^{[страница нужна ]}
^ Хоссейн Мобахи, Джон В. Фишер III. О связи между продолжением гауссовских гомотопий и выпуклыми оболочками, В конспектах лекций по информатике (EMMCVPR 2015), Springer, 2015.
^ Йонас Моцкус (2013). Байесовский подход к глобальной оптимизации: теория и приложения. Kluwer Academic.

внешняя ссылка

[1] Сяопэн Луо (2018). «Минимальное распределение для глобальной оптимизации». arXiv:1812.03457. Цитировать журнал требует | журнал = (помощь)

[2] Свендсен Р. Х. и Ван Дж. С. (1986) Реплика Монте-Карло моделирования спиновых стекол Physical Review Letters 57: 2607–2609

[3] К. Дж. Гейер, (1991) в Вычислительная техника и статистика, Материалы 23-го симпозиума по интерфейсу, Американская статистическая ассоциация, Нью-Йорк, с. 156.

[4] Марко Фальчони и Майкл В. Дим (1999). «Смещенная схема Монте-Карло для решения структуры цеолита». J. Chem. Phys. 110 (3): 1754–1766. arXiv:cond-mat / 9809085. Bibcode:1999ЖЧФ.110.1754Ф. Дои:10.1063/1.477812.

[5] Дэвид Дж. Эрл и Майкл В. Дим (2005) «Параллельная закалка: теория, приложения и новые перспективы», Phys. Chem. Chem. Phys., 7, 3910

[6] Ю. Сугита и Ю. Окамото (1999). «Реплико-обменный молекулярно-динамический метод сворачивания белков». Письма по химической физике. 314 (1–2): 141–151. Bibcode:1999CPL ... 314..141S. Дои:10.1016 / S0009-2614 (99) 01123-9.

[7] Такер, Нил; Кутс, Тим (1996). «Методы постепенной невыпуклости и оптимизации с несколькими разрешениями». Видение через оптимизацию.

[8] Блейк, Эндрю; Зиссерман, Эндрю (1987). Визуальная реконструкция. MIT Press. ISBN 0-262-02271-0.^{[страница нужна ]}

[mobahi2015-9] Хоссейн Мобахи, Джон В. Фишер III. О связи между продолжением гауссовских гомотопий и выпуклыми оболочками, В конспектах лекций по информатике (EMMCVPR 2015), Springer, 2015.

[10] Йонас Моцкус (2013). Байесовский подход к глобальной оптимизации: теория и приложения. Kluwer Academic.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Программное обеспечение для математической оптимизации
Форматы данных	Mathematica MPS нл соль
Моделирование инструменты	ЦЕЛИ AMPL APMonitor Затмение -CLP GEKKO GAMS GNU MathProg Прыгать LINDO OPL Mathematica OptimJ PuLP Pyomo ТОМЛАБ Экспресс-Мозель ZIMPL
LP, MILP^∗ решатели	APOPT^∗ АНТИГОНА^∗ Artelys Knitro^∗ BCP^∗ CLP CBC^∗ CPLEX^∗ FortMP^∗ GCG^∗ GLPK / GLPSOL^∗ Гуроби^∗ LINDO^∗ Lp_solve LOQO Mathematica МИНОС MINTO^∗ МОСЕК^∗ SCIP^∗ SoPlex Octeract Engine^∗ СИМФОНИЯ^∗ Xpress-Optimizer^∗
QP, MIQP^∗ решатели	APOPT^∗ АНТИГОНА^∗ Artelys Knitro^∗ CBC^∗ CLP CPLEX^∗ FortMP^∗ Гуроби^∗ IPOPT LINDO^∗ Mathematica МИНОС МОСЕК^∗ Octeract Engine^∗ SCIP^∗ Xpress-Optimizer^∗
QCP, MIQCP^∗ решатели	APOPT^∗ АНТИГОНА^∗ Artelys Knitro^∗ CPLEX^∗ Гуроби^∗ IPOPT LINDO^∗ Mathematica МИНОС МОСЕК^∗ SCIP^∗ Octeract Engine^∗ Xpress-Optimizer^∗ Xpress-SLP^∗
SOCP, MISOCP^∗ решатели	Artelys Knitro^∗ CPLEX^∗ Гуроби^∗ LINDO^∗ LOQO Mathematica МОСЕК^∗ SCIP^∗ Xpress-Optimizer^∗
SDP, MISDP^∗ решатели	Mathematica МОСЕК
НЛП, MINLP^∗ решатели	АОА^∗ APOPT^∗ АНТИГОНА^∗ Artelys Knitro^∗ БАРОН^∗ Couenne^∗ Библиотека галахад IPOPT LINDO^∗ LOQO MIDACO^∗ МИНОС NLPQLP НПСОЛ SCIP^∗ СНОПТ^∗ Octeract Engine^∗ WORHP Xpress-SLP^∗
ИДТИ решатели	АНТИГОНА^∗ БАРОН Couenne^∗ Mathematica LINDO SCIP Octeract Engine
CP решатели	Комета Оптимизатор CPLEX CP Gecode Mathematica JaCoP
Метаэвристический решатели	OptaPlanner
Список программ оптимизации Сравнение программ оптимизации