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

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

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

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

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

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

Приложения

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

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

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

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

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

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

Методы секущей плоскости

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

Методы ветвей и границ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Косвенная оптимизация IOSO на основе самоорганизации
Байесовская оптимизация — стратегия последовательного проектирования для глобальной оптимизации функций «черного ящика» с использованием байесовской статистики. ^[9]

См. также

Сноски

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

Ссылки

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

Р. Хорст, Х. Тай, Глобальная оптимизация: детерминистические подходы , Springer, 1996.
Р. Хорст, П. М. Пардалос и Н. В. Тоай, Введение в глобальную оптимизацию , второе издание. Академическое издательство Клувер, 2000.
А. Ноймайер, Полный поиск в непрерывной глобальной оптимизации и удовлетворении ограничений, стр. 271–369 в: Acta Numerica 2004 (ред. А. Изерлес), Cambridge University Press, 2004.
М. Монжо, Х. Карсенти, В. Рузе и Ж.-Б. Хириарт-Уррути, Сравнение общедоступного программного обеспечения для глобальной оптимизации черного ящика . Методы оптимизации и программное обеспечение 13 (3), стр. 203–226, 2000.
Дж. Д. Пинтер, Глобальная оптимизация в действии: непрерывная и липшицевая оптимизация: алгоритмы, реализации и приложения . Kluwer Academic Publishers, Дордрехт, 1996. В настоящее время распространяется Springer Science and Business Media, Нью-Йорк. В этой книге также обсуждаются стохастические методы глобальной оптимизации.
Л. Жолен, М. Киффер, О. Дидрит, Э. Уолтер (2001). Прикладной интервальный анализ. Берлин: Шпрингер.
Э. Р. Хансен (1992), Глобальная оптимизация с использованием интервального анализа, Марсель Деккер, Нью-Йорк.

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

Киркпатрик, С.; Гелатт, CD; Векки, член парламента (13 мая 1983 г.). «Оптимизация путем моделирования отжига». Наука . 220 (4598). Американская ассоциация содействия развитию науки (AAAS): 671–680. Бибкод : 1983Sci...220..671K . дои : 10.1126/science.220.4598.671 . ISSN 0036-8075 . ПМИД 17813860 . S2CID 205939 .

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

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

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

А. Жиглявский . Теория глобального случайного поиска. Математика и ее приложения. Академическое издательство Клювер. 1991.
Хамахер, К. (2006). «Адаптация в стохастической туннельной глобальной оптимизации сложных потенциальных энергетических ландшафтов». Письма по еврофизике (EPL) . 74 (6). Издательство ИОП: 944–950. Бибкод : 2006EL.....74..944H . дои : 10.1209/epl/i2006-10058-0 . ISSN 0295-5075 . S2CID 250761754 .
Хамахер, К.; Венцель, В. (1 января 1999 г.). «Масштабирование алгоритмов стохастической минимизации в идеальной воронке». Физический обзор E . 59 (1): 938–941. arXiv : физика/9810035 . Бибкод : 1999PhRvE..59..938H . дои : 10.1103/physreve.59.938 . ISSN 1063-651X . S2CID 119096368 .
Венцель, В.; Хамахер, К. (12 апреля 1999 г.). «Стохастический туннельный подход для глобальной минимизации сложных потенциальных энергетических ландшафтов». Письма о физических отзывах . 82 (15). Американское физическое общество (APS): 3003–3007. arXiv : физика/9903008 . Бибкод : 1999PhRvL..82.3003W . дои : 10.1103/physrevlett.82.3003 . ISSN 0031-9007 . S2CID 5113626 .

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

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

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

Чжицзюнь Ву. Схема эффективного преобразования энергии как особый подход к глобальной оптимизации с применением к молекулярной конформации . Технический отчет, Аргоннская национальная лаборатория, Иллинойс (США), ноябрь 1996 г.

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

Хамахер, Кей (2005). «О стохастической глобальной оптимизации одномерных функций». Физика А: Статистическая механика и ее приложения . 354 . Эльзевир Б.В.: 547–557. Бибкод : 2005PhyA..354..547H . дои : 10.1016/j.physa.2005.02.028 . ISSN 0378-4371 .

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

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

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

[2] CJ Гейер, (1991) в «Вычислительной науке и статистике» , Труды 23-го симпозиума по интерфейсу, Американская статистическая ассоциация, Нью-Йорк, стр. 156.

[3] Марко Фальчиони и Майкл В. Дим (1999). «Смещенная схема Монте-Карло для решения структуры цеолита». Дж. Хим. Физ . 110 (3): 1754–1766. arXiv : cond-mat/9809085 . Бибкод : 1999JChPh.110.1754F . дои : 10.1063/1.477812 . S2CID 13963102 .

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

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

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

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]