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

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

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

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

то есть поиск и глобальный минимизатор в ; где – (не обязательно выпуклый) компакт, определяемый неравенствами . $f^{*}$ $X^{*}$ $\Омега$ ${\ displaystyle 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 Geyer, (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). Байесовский подход к глобальной оптимизации: теория и приложения. Клювер Академик.

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

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