Войти
Детерминированная глобальная оптимизация - это ветвь численной оптимизации, которая фокусируется на поиске глобальных решений задачи оптимизации, обеспечивая теоретические гарантии того, что заявленное решение действительно является глобальным в пределах некоторый предопределенный допуск. Термин «детерминированная глобальная оптимизация» обычно относится к методам полной или строгой (см. Ниже) оптимизации. Строгие методы сходятся к глобальному оптимуму за конечное время. Детерминированные методы глобальной оптимизации обычно используются, когда необходимо найти глобальное решение (т.е. когда единственное естественное состояние, описываемое математической моделью, является глобальным минимумом задачи оптимизации), когда чрезвычайно сложно найти возможное решение, или просто, когда пользователь желает найти наилучшее возможное решение проблемы.
Neumaier классифицировал методы глобальной оптимизации по четырем категориям в зависимости от степени их строгости, с которой они приближаются к оптимуму, следующим образом:
Детерминированные методы глобальной оптимизации обычно относятся к двум последним категориям. Обратите внимание, что создание строгой части программного обеспечения чрезвычайно сложно, поскольку процесс требует, чтобы все зависимости также были строго закодированы.
Детерминированные методы глобальной оптимизации требуют способов строго ограничивать значения функций по областям пространства. Можно сказать, что основное различие между детерминированными и недетерминированными методами в этом контексте заключается в том, что первые выполняют вычисления по областям пространства решений, а вторые - по отдельным точкам. Это делается либо путем использования определенных функциональных форм (например, релаксации Маккормика), либо с помощью интервального анализа для работы с более общими функциональными формами. В любом случае требуется ограничение, поэтому детерминированные методы глобальной оптимизации не могут дать строгий результат при работе с кодом черного ящика, если этот код явно не написан так, чтобы также возвращать границы функций. По этой причине проблемы в детерминированной глобальной оптимизации обычно представляются с помощью вычислительного графа , так как все операторы легко перегрузить, так что результирующие значения функций или производные дают интервал (а не скаляр) полученные результаты.
Задачи линейного программирования - это очень желательная формулировка любой практической задачи. Причина в том, что с появлением алгоритмов внутренней точки стало возможно эффективно решать очень большие задачи (включающие сотни тысяч или даже миллионы переменных) до глобальной оптимальности. Задачи оптимизации линейного программирования строго подпадают под категорию детерминированной глобальной оптимизации.
Подобно задачам линейного программирования, MILP очень важны при решении моделей принятия решений. Эффективные алгоритмы для решения сложных задач этого типа известны и доступны в виде решателей, таких как CPLEX или Gurobi.
Задачи нелинейного программирования чрезвычайно сложны при детерминированной глобальной оптимизации. Порядок величины, которую современный решатель может обработать за разумное время, составляет примерно от 100 до нескольких сотен нелинейных переменных. На момент написания этой статьи не существовало параллельных решателей для детерминированного решения NLP, что объясняет разрыв в сложности между детерминированным LP и NLP-программированием.
Детерминированное решение задачи MINLP может быть даже более сложной задачей, чем их аналоги НЛП. Обычно используются такие методы, как целочисленные сокращения или разветвление задачи по ее целочисленным переменным (тем самым создавая подзадачи НЛП, которые, в свою очередь, могут быть решены детерминированно).
Методы нулевого порядка состоят из методов, которые используют интервальную арифметику нулевого порядка . Типичным примером является деление интервала пополам.
Методы первого порядка состоят из методов, которые используют информацию первого порядка, например, интервальные градиенты или интервальные наклоны.
Методы второго порядка используют информацию второго порядка, обычно границы собственных значений, полученные из интервалов матриц Гессе. Одной из наиболее общих методологий второго порядка для решения задач общего типа является алгоритм αΒΒ.
