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

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

Обзор

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

БАРОН: BARON доступен под ЦЕЛИ, AMPL, и GAMS язык моделирования и на сервере NEOS.^[6] Это проприетарное программное обеспечение ^[7]
Couenne: Convex Over and Under ENvelopes for Nonlinear Estimation (Couenne) - это библиотека с открытым исходным кодом. ^[8]
ЕАГО: Простая расширенная глобальная оптимизация (EAGO) ^[9] решатель с открытым исходным кодом в Юля (язык программирования). Он разработан Университетом Коннектикута.^[10]
LINDO (Линейный, интерактивный и дискретный оптимизатор) включает возможности глобальной оптимизации.^[11]
MAiNGO: алгоритм на основе Маккормика для смешанно-целочисленной нелинейной глобальной оптимизации (MAiNGO) ^[12] - это пакет C ++ с распараллеливанием MPI и openMP, предоставляемый с открытым исходным кодом. ^[13] под Eclipse Public License - v 2.0.
Octeract Engine - это запатентованный решатель с возможностями распараллеливания. Он разработан и лицензирован Octeract. ^[14]
SCIP: SCIP - это пакет решателей оптимизации с открытым исходным кодом, который, среди прочего, решает смешанное целочисленное нелинейное программирование (MINLP). ^[15]