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

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

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

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

${\displaystyle \min _{x\in \Omega }f(x),}$

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

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

Общая теория [ править ]

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

${\displaystyle \lim _{k\to \infty }\int _{\Omega }f(x)m^{(k)}(x)\,\mathrm {d} x=f^{*},~~{\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+\Delta k)}(x)\,\mathrm {d} x>f^{*}}$

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

${\displaystyle \Omega \supset D_{f}^{(k)}\supset D_{f}^{(k+\Delta k)}\supset X^{*},{\text{ where }}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;}$

таким образом, означает, что выполняется для всех , т. е. является глобальным минимизатором on .${\displaystyle \nabla f(x^{*})=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)
• Имитация отжига , обобщенная вероятностная метаэвристика.
• Табу-поиск , расширение локального поиска, способное выходить из локальных минимумов
• Эволюционные алгоритмы (например, генетические алгоритмы и стратегии эволюции )
• Дифференциальная эволюция , метод, который оптимизирует проблему, итеративно пытаясь улучшить возможное решение с учетом заданного показателя качества.
• Swarm на основе алгоритмы оптимизации (например, оптимизация хся частиц , социальная когнитивный оптимизация , оптимизация мульти-рой и оптимизация колонии муравьев )
• Меметические алгоритмы , сочетающие стратегии глобального и локального поиска
• Реактивная поисковая оптимизация (т.е. интеграция субсимвольных методов машинного обучения в поисковую эвристику)
• Поэтапная оптимизация - метод, который пытается решить сложную проблему оптимизации, сначала решая значительно упрощенную задачу, и постепенно преобразовывая эту проблему (при оптимизации), пока она не станет эквивалентной сложной задаче оптимизации. ^{[7] [8] [9]}

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

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

См. Также [ править ]

• Детерминированная глобальная оптимизация
• Многопрофильная оптимизация дизайна
• Многокритериальная оптимизация
• Оптимизация (математика)

Сноски [ править ]

Ссылки [ править ]

Внешние ссылки [ править ]

• Страница А. Ноймайера о глобальной оптимизации
• Введение в глобальную оптимизацию Л. Либерти
• Бесплатная электронная книга Томаса Вайса