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

Глобальная оптимизация - это раздел прикладной математики и численного анализа, который пытается найти глобальные минимумы или максимумы функции или набора функций на заданном наборе. Это обычно описывается как проблема минимизации, потому что максимизация действительной функции эквивалентна минимизации функции .

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

то есть поиск и глобальный минимизатор в ; где - (не обязательно выпуклый) компакт, определяемый неравенствами .

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

Общая теория

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

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

где - -мерная мера Лебега множества минимизаторов . И если не постоянна , то монотонная связь

выполняется для всех и , что подразумевает серию монотонных отношений сдерживания, и одним из них является, например,

И мы определяем минимальное распределение как слабый предел такой, что тождество

выполняется для любой гладкой функции с компактным носителем в . Вот два непосредственных свойства :

(1) удовлетворяет тождеству .
(2) Если непрерывно , то .

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

таким образом, означает, что выполняется для всех , т. е. является глобальным минимизатором on .

Приложения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основная статья : Метаэвристика

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

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

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

Сноски

использованная литература

Детерминированная глобальная оптимизация:

Для имитации отжига:

  • Киркпатрик, S .; Gelatt, CD; Векки, депутат (13 мая 1983 г.). «Оптимизация путем имитации отжига». Наука . Американская ассоциация развития науки (AAAS). 220 (4598): 671–680. DOI : 10.1126 / science.220.4598.671 . ISSN  0036-8075 . PMID  17813860 .

Для реактивной поисковой оптимизации:

  • Роберто Баттити , М. Брунато и Ф. Маскиа, Реактивный поиск и интеллектуальная оптимизация, Серия исследований операций / интерфейсов компьютерных наук, Том. 45, Springer, ноябрь 2008 г. ISBN  978-0-387-09623-0

Для стохастических методов:

  • А. Жиглявский . Теория глобального случайного поиска. Математика и ее приложения. Kluwer Academic Publishers. 1991 г.
  • Хамахер, К. (2006). «Адаптация в стохастической туннельной глобальной оптимизации сложных ландшафтов потенциальной энергии». Письма Europhysics (EPL) . IOP Publishing. 74 (6): 944–950. DOI : 10,1209 / EPL / i2006-10058-0 . ISSN  0295-5075 .
  • Hamacher, K .; Венцель, В. (1999-01-01). «Масштабируемое поведение алгоритмов стохастической минимизации в идеальном ландшафте воронки». Physical Review E . 59 (1): 938–941. arXiv : физика / 9810035 . DOI : 10.1103 / physreve.59.938 . ISSN  1063-651X .
  • Wenzel, W .; Хамахер, К. (1999-04-12). "Стохастический туннельный подход для глобальной минимизации сложных потенциальных энергетических ландшафтов". Письма с физическим обзором . Американское физическое общество (APS). 82 (15): 3003–3007. arXiv : физика / 9903008 . DOI : 10.1103 / physrevlett.82.3003 . ISSN  0031-9007 .

Для параллельного отпуска:

  • Хансманн, Ульрих HE (1997). «Алгоритм параллельного темперирования для конформационных исследований биологических молекул». Письма по химической физике . Elsevier BV. 281 (1–3): 140–150. arXiv : физика / 9710041 . DOI : 10.1016 / s0009-2614 (97) 01198-6 . ISSN  0009-2614 .

Для методов продолжения:

Для общих соображений о размерности области определения целевой функции:

  • Хамахер, Кей (2005). «О стохастической глобальной оптимизации одномерных функций». Physica A: Статистическая механика и ее приложения . Elsevier BV. 354 : 547–557. DOI : 10.1016 / j.physa.2005.02.028 . ISSN  0378-4371 .

Для стратегий, позволяющих сравнивать детерминированные и стохастические методы глобальной оптимизации.

внешние ссылки