Глобальная оптимизация с помощью escape функций

Обновлено: 05.07.2024

Неделя 3: Оптимизация и матричные разложения

Градиент и оптимизация гладких функций

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

Оптимизация негладких функций

КонспектМетоды оптимизации: оптимизация негладких функций, метод имитации отжига, генетические алгоритмы, метод Нелдера-Мида

Assignment Оптимизация в Python: глобальная оптимизация и оптимизация негладкой функции

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

В ННГУ им. Н.И. Лобачевского разработан (в рамках единого подхода) ряд эффективных алгоритмов глобальной оптимизации; все они вошли в программную систему Globalizer.

Основными особенностями разработанных методов являются:

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

Лежащий в основе разработанной программной системы Globalizer информационно-статистический алгоритм глобального поиска (АГП) превосходит многие известные методы аналогичного назначения. Для иллюстрации на рис. 1 изображены линии уровня двумерной многоэкстремальной функции и отмечены точки поисковых испытаний, выполненных АГП (рис. 1(а), 130 испытаний) и методом DIRECT (рис. 1(б), 269 испытаний) до достижения заданной точности.

Результаты сравнения АГП с некоторыми другими алгоритмами (метод ломаных, метод Кушнера, одношаговый байесовский метод) приведены на рис. 2. Сравнение алгоритмов проводилось при решении серии случайно генерируемых задач многоэкстремальных задач. Результат представлен операционной характеристикой P(k), характеризующей долю задач серии, для которых в ходе k шагов поиска имели место попадания точек поисковых испытаний в заданную окрестность решения.

Рис. 2. Операционные характеристики алгоритмов

Детерминированная глобальная оптимизация - это ветвь численной оптимизации, которая фокусируется на поиске глобальных решений задачи оптимизации, обеспечивая при этом теоретические гарантии того, что заявленное решение действительно является глобальным в пределах некоторого предопределенного допуска. Термин «детерминированная глобальная оптимизация» обычно относится к методам полной или строгой (см. Ниже) оптимизации. Строгие методы сходятся к глобальному оптимуму за конечное время. Детерминированные методы глобальной оптимизации обычно используются, когда необходимо найти глобальное решение (т.е. когда единственное естественное состояние, описываемое математической моделью, является глобальным минимумом проблемы оптимизации), когда чрезвычайно сложно найти возможное решение, или просто, когда пользователь желает найти наилучшее возможное решение проблемы.

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

СОДЕРЖАНИЕ

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

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

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

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

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

Сноски

Классы детерминированных задач глобальной оптимизации

Задачи линейного программирования (ЛП)

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

Смешанно-целочисленные задачи линейного программирования (MILP)

Подобно задачам линейного программирования, MILP очень важны при решении моделей принятия решений. Эффективные алгоритмы для решения сложных задач этого типа известны и доступны в виде решателей, таких как CPLEX или Gurobi .

Проблемы нелинейного программирования (НЛП)

Задачи нелинейного программирования чрезвычайно сложны при детерминированной глобальной оптимизации. Порядок величины, которую современный решатель может обработать за разумное время, составляет примерно от 100 до нескольких сотен нелинейных переменных. На момент написания этой статьи не существовало параллельных решателей для детерминированного решения NLP, что объясняет разрыв в сложности между детерминированным LP и NLP-программированием.

Смешанно-целочисленные задачи нелинейного программирования (MINLP)

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

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

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

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

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

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

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

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

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

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

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

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

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

Обзор

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

Неполный метод использует умные интуитивные эвристики для поиска , но не имеет гарантий , если поиск застревает в локальном минимуме
Асимптотически полный метод достигает глобального минимума с уверенностью или , по крайней мере , с вероятностью единица , если разрешено работать бесконечно долго, но не имеет средств , чтобы знать , когда глобальный Минимизатор был найден.
Полный метод достигает глобальный минимум с уверенностью, предполагая , что точные расчеты и бесконечно долго во время выполнения, и знает , что за конечное время, приближенный глобальный Минимизатор был найден (в пределах заданных допусков).
Строгий метод достигает глобальный минимум с уверенностью и в пределах заданных допусков даже при наличии ошибок округления, за исключением близких к вырожденным случаям, когда допуски могут быть превышены.

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

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

Методы первого порядка

Методы первого порядка состоят из методов, которые используют информацию первого порядка, например, интервальные градиенты или интервальные наклоны.

Общая теория

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

Lim k → ∞ ∫ Ω ж ( Икс ) м ( k ) ( Икс ) d Икс знак равно ж * , куда м ( k ) ( Икс ) знак равно е - k ж ( Икс ) ∫ Ω е - k ж ( Икс ) d Икс ; \ int _ е (х) м ^ (х) \, \ mathrm х = е ^ ,

где - -мерная мера Лебега множества минимизаторов . И если не постоянна , то монотонная связь μ ( Икс * ) )> п Икс * ∈ Ω \ in \ Omega> ж Ω

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

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

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

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

ж ( у ) ⩾ ж ( Икс ) + ∇ ж ( Икс ) ( у - Икс ) , ∀ Икс , у ∈ D ;

\ forall x, y \ in D;>

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

Методы второго порядка

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

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

Учитывая, возможно, нелинейную и невыпуклую непрерывную функцию с глобальными минимумами и набор всех глобальных минимизаторов в , стандартная задача минимизации может быть задана как ж : Ω ⊂ р п → р ^ \ to \ mathbb > ж * > Икс * > Ω

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

Методы нулевого порядка

Методы нулевого порядка состоят из методов, которые используют интервальную арифметику нулевого порядка . Типичным примером является деление интервала пополам.

Читайте также: