Детерминированная глобальная оптимизация — это ветвь исследования операций, фокусирующаяся на поиске глобального решения задачи оптимизации, предоставляя при этом теоретические гарантии того, что найденное решение действительно является глобальным в пределах заданной погрешности. Термин «детерминированная глобальная оптимизация» относится обычно к полным или строгим (см. ниже) методам оптимизации. Строгие методы сходятся к глобальному оптимуму за конечное время. Методы детерминированной глобальной оптимизации обычно используются, когда необходимо найти глобальное решение (например, когда единственное естественное состояние, описываемое математической моделью, является глобальным минимумом оптимизационной задачи), когда чрезвычайно трудно найти допустимое решение, или просто когда пользователь желает найти наилучшее возможное решение проблемы.
Обзор Ноймайер разделил методы глобальной оптимизации на четыре категории, исходя из строгости их подхода к достижению оптимума:
Неполный метод использует интуитивные эвристики для поиска, но не имеет механизмов защиты, если поиск застревает в локальном минимуме. Асимптотически полный метод гарантированно достигает глобального минимума или, по крайней мере, с вероятностью единица, если ему позволено работать неограниченно долго, но не имеет средств для определения момента нахождения глобального минимума. Полный метод гарантированно достигает глобального минимума при условии точных вычислений и неограниченного времени выполнения, и после конечного времени знает, что был найден приближённый глобальный минимум (в пределах заданных допусков). Строгий метод гарантированно достигает глобального минимума и в пределах заданных допусков даже при наличии ошибок округления, за исключением почти вырожденных случаев, когда допуски могут быть превышены.
Методы детерминированной глобальной оптимизации обычно относятся к последним двум категориям. Заметим, что создание строгого программного обеспечения крайне сложно, поскольку этот процесс требует, чтобы все зависимости также были закодированы строго.
Методы детерминированной глобальной оптимизации требуют способов строго ограничить значения функции в областях пространства. Можно сказать, что основное различие между детерминированными и недетерминированными методами в этом контексте заключается в том, что первые выполняют вычисления по областям пространства решений, тогда как вторые выполняют вычисления по отдельным точкам. Это достигается либо использованием конкретных функциональных форм (например, релаксаций МакКормика), или использованием интервального анализа для работы с более общими функциональными формами. В любом случае требуется ограничение, поэтому методы детерминированной глобальной оптимизации не могут дать строгий результат при работе с чёрным ящиком кода, если только этот код явно не написан для возврата границ функции. По этой причине задачи детерминированной глобальной оптимизации часто представляются с использованием графа вычислений, поскольку легко перегрузить все операторы таким образом, чтобы результирующие значения функций или производные давали интервальные (а не скалярные) результаты..
Классы задач детерминированной глобальной оптимизации Задачи линейного программирования Задачи линейного программирования являются очень желательной формой для решения любой практической проблемы. Причина в том, что с появлением алгоритмов внутренней точки стало возможным эффективно решать очень большие задачи (включающие сотни тысяч или даже миллионы переменных) с достижением глобальной оптимальности. Задачи оптимизации линейного программирования строго относятся к категории детерминированной глобальной оптимизации.
Задачи смешанного программирования Подобно задачам линейного программирования, задачи смешанного целочисленного программирования очень важны при решении моделей принятия решений. Известны эффективные алгоритмы для решения сложных задач такого типа, и они доступны в виде программ, таких как CPLEX.
Задачи нелинейного программирования Задачи нелинейного программирования представляют собой чрезвычайно сложную проблему в детерминированной глобальной оптимизации. Современное программное обеспечение способно обрабатывать в разумные сроки до нескольких сотен нелинейных переменных. На данный момент не существует систем параллельного решения для задач детерминированного нелинейного программирования, что объясняет разрыв в сложности между детерминированным линейным и нелинейным программированием.
Задачи смешанного целочисленного нелинейного программирования Даже более сложной проблемой является решение с гарантированным результатом нелинейной задачи в целых числах. Для таких задач часто применяются техники, такие как отсекающие плоскости или метод ветвей и границ на целочисленных переменных, что приводит к созданию подзадач нелинейного программирования, которые можно решить детерминированно.
Методы нулевого порядка Методы нулевого порядка состоят из методов, которые используют интервальную арифметику нулевого порядка. Типичным примером является деление интервала пополам.
Методы первого порядка Методы первого порядка состоят из методов, которые используют информацию первого порядка, например, интервальные градиенты или интервальные наклоны.
Методы второго порядка Методы второго порядка используют информацию второго порядка, обычно границы собственных значений, полученные из интервальных матриц Гессе. Одним из наиболее общих методов второго порядка для решения задач общего типа является алгоритм .
Программные средства решения детерминированных задач глобальной оптимизации : Algorithms for coNTinuous / Integer Global Optimization of Nonlinear Equations) (Алгоритмы для непрерывной/целочисленной глобальной оптимизации нелинейных уравнений). Это проприетарное программное обеспечение, доступное на платформе моделирования . : BARON доступен в системах , AMPL, в языке моделирования и на сервере NEOS Server. Это проприетарное программное обеспечение. : Convex Over and Under ENvelopes for Nonlinear Estimation (Выпуклые верхняя и нижняя оболочки для нелинейной оценки) — это библиотека программ с открытым исходным кодом EAGO: Easy-Advanced Global Optimization (Простая и продвинутая глобальная оптимизация) — это пакет программ с открытым исходным кодом на языке Julia. Пакет разработан Коннектикутским университетом. (Linear, Interactive, and Discrete Optimizer = Линейный, Интерактивный и Дискретный Оптимизатор) включает возможности глобальной оптимизации. MAiNGO: Основанный на методе Маккормика пакет решения задач смешанной нелинейной глобальной оптимизации на языке C++ с интерфейсами распараллеливания MPI и openMP, распространяемый с открытым исходным кодом под лицензией Eclipse Public License — v 2.0. является проприетарным пакетом программ для решения задач оптимизации с возможностями распараллеливания. Он разработан и лицензирован компанией Octeract. : SCIP — это пакет программ с открытым исходным кодом для решения задач оптимизации, который, помимо прочего, решает задачи смешанного целочисленного нелинейного программирования.
Примечания
Литература
Категория:Теория оптимизации