Детерминированная глобальная оптимизация - Deterministic global optimization
Детерминированная глобальная оптимизация - это ветвь численной оптимизации, которая фокусируется на поиске глобальных решений задачи оптимизации, обеспечивая при этом теоретические гарантии того, что заявленное решение действительно является глобальным в пределах некоторого предопределенного допуска. Термин «детерминированная глобальная оптимизация» обычно относится к методам полной или строгой (см. Ниже) оптимизации. Строгие методы сходятся к глобальному оптимуму за конечное время. Детерминированные методы глобальной оптимизации обычно используются, когда необходимо найти глобальное решение (т.е. когда единственное естественное состояние, описываемое математической моделью, является глобальным минимумом проблемы оптимизации), когда чрезвычайно сложно найти возможное решение, или просто, когда пользователь желает найти наилучшее возможное решение проблемы.
Обзор
Neumaier классифицировал методы глобальной оптимизации на четыре категории в зависимости от степени их строгости, с которой они приближаются к оптимуму, следующим образом:
- Неполный метод использует умные интуитивные эвристики для поиска , но не имеет гарантий , если поиск застревает в локальном минимуме
- Асимптотически полный метод достигает глобального минимума с уверенностью или , по крайней мере , с вероятностью единица , если разрешено работать бесконечно долго, но не имеет средств , чтобы знать , когда глобальный Минимизатор был найден.
- Полный метод достигает глобальный минимум с уверенностью, предполагая , что точные расчеты и бесконечно долго во время выполнения, и знает , что за конечное время, приближенный глобальный Минимизатор был найден (в пределах заданных допусков).
- Строгий метод достигает глобальный минимум с уверенностью и в пределах заданных допусков даже при наличии ошибок округления, за исключением близких к вырожденным случаям, когда допуски могут быть превышены.
Детерминированные методы глобальной оптимизации обычно относятся к двум последним категориям. Обратите внимание, что создание строгой части программного обеспечения чрезвычайно сложно, поскольку процесс требует, чтобы все зависимости также были строго закодированы.
Детерминированные методы глобальной оптимизации требуют способов строгого ограничения значений функций по областям пространства. Можно сказать, что основное различие между детерминированными и недетерминированными методами в этом контексте заключается в том, что первые выполняют вычисления по областям пространства решений, а вторые - по отдельным точкам. Это делается либо путем использования определенных функциональных форм (например, релаксации Маккормика), либо с использованием интервального анализа для работы с более общими функциональными формами. В любом случае требуется ограничение, поэтому детерминированные методы глобальной оптимизации не могут дать строгий результат при работе с кодом черного ящика , если этот код явно не написан, чтобы также возвращать границы функций. По этой причине проблемы детерминированной глобальной оптимизации обычно представляются с помощью вычислительного графа , поскольку легко перегрузить все операторы, так что результирующие значения функций или производные дают интервальные (а не скалярные) результаты.
Классы детерминированных задач глобальной оптимизации
Задачи линейного программирования (ЛП)
Задачи линейного программирования - это очень желательная формулировка любой практической задачи. Причина в том, что с появлением алгоритмов внутренней точки стало возможно эффективно решать очень большие задачи (включающие сотни тысяч или даже миллионы переменных) до глобальной оптимальности. Задачи оптимизации линейного программирования строго подпадают под категорию детерминированной глобальной оптимизации.
Смешанно-целочисленные задачи линейного программирования (MILP)
Подобно задачам линейного программирования, MILP очень важны при решении моделей принятия решений. Эффективные алгоритмы для решения сложных задач этого типа известны и доступны в виде решателей, таких как CPLEX или Gurobi .
Проблемы нелинейного программирования (НЛП)
Задачи нелинейного программирования чрезвычайно сложны при детерминированной глобальной оптимизации. Порядок величины, которую современный решатель может обработать за разумное время, составляет примерно от 100 до нескольких сотен нелинейных переменных. На момент написания этой статьи не существовало параллельных решателей для детерминированного решения NLP, что объясняет разрыв в сложности между детерминированным LP и NLP-программированием.
Смешанно-целочисленные задачи нелинейного программирования (MINLP)
Детерминированное решение задачи MINLP может оказаться даже более сложной задачей, чем их аналоги по НЛП. Обычно используются такие методы, как целочисленные сокращения или разветвление задачи по ее целочисленным переменным (что создает подзадачи НЛП, которые, в свою очередь, могут быть решены детерминированно).
Методы нулевого порядка
Методы нулевого порядка состоят из методов, которые используют интервальную арифметику нулевого порядка . Типичным примером является деление интервала пополам.
Методы первого порядка
Методы первого порядка состоят из методов, которые используют информацию первого порядка, например, интервальные градиенты или интервальные наклоны.
Методы второго порядка
Методы второго порядка используют информацию второго порядка, обычно границы собственных значений, полученные из интервальных матриц Гессе . Одной из наиболее общих методологий второго порядка для решения задач общего типа является алгоритм αΒΒ .
Детерминированные решатели глобальной оптимизации
- АНТИГОНА : Алгоритмы непрерывной / целочисленной глобальной оптимизации нелинейных уравнений). Это проприетарное программное обеспечение, доступное через ANTIGONE, платформу моделирования GAMS .
- БАРОН : BARON доступен под AIMMS , AMPL и ГАМС моделирования языка и на NEOS Server. Это проприетарное программное обеспечение
- Couenne : Convex Over and Under ENvelopes for Nonlinear Estimation (Couenne) - это библиотека с открытым исходным кодом.
- EAGO : Easy-Advanced Global Optimization (EAGO) - решатель с открытым исходным кодом на Julia (язык программирования) . Он разработан Университетом Коннектикута.
- LINDO (линейный, интерактивный и дискретный оптимизатор) включает возможности глобальной оптимизации.
- MAiNGO: алгоритм на основе Маккормика для смешанной целочисленной нелинейной глобальной оптимизации (MAiNGO) - это пакет C ++ с MPI и распараллеливанием openMP, предоставляемый с открытым исходным кодом под Eclipse Public License - v 2.0.
- Octeract Engine - это запатентованный решатель с возможностями распараллеливания. Он разработан и лицензирован Octeract.
- SCIP : SCIP - это набор решателей оптимизации с открытым исходным кодом, который, среди прочего, решает смешанное целочисленное нелинейное программирование (MINLP).