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

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

Обзор

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

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

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

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

Классы детерминированных

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

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

линейного программирования (MILP

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

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

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

нелинейного программирования (MINLP

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

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

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

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

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

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

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

оптимизации

• АНТИГОНА : Алгоритмы непрерывной/целочисленной глобальной оптимизации нелинейных уравнений). Это запатентованное программное обеспечение, доступное через ANTIGONE, платформу моделирования GAMS .

• BARON : BARON доступен на AIMMS , AMPL и GAMS языках моделирования и на сервере NEOS. Это проприетарное программное обеспечение
• Куэнн : Выпуклые верхние и нижние конверты для нелинейной оценки (Куэнн) — это библиотека с открытым исходным кодом.
• EAGO: Простая глобальная оптимизация (EAGO) — решатель с открытым исходным кодом на Julia (языке программирования) . Он разработан Университетом Коннектикута.
• LINDO (линейный, интерактивный и дискретный оптимизатор) включает возможности глобальной оптимизации.
• MAiNGO: Алгоритм смешанно-целочисленной нелинейной глобальной оптимизации на основе Маккормика (MAiNGO) представляет собой пакет C++ с распараллеливанием MPI и openMP, предоставляемый с открытым исходным кодом. под общественной лицензией Eclipse — v 2.0.
• Octeract Engine — это собственный решатель с возможностями распараллеливания. Он разработан и лицензирован Octeract.
• SCIP : SCIP — это набор решателей оптимизации с открытым исходным кодом, который, среди прочего, решает смешанное целочисленное нелинейное программирование (MINLP).