Мера оптимальности первого порядка

Что такое мера оптимальности первого порядка?

Оптимальность первого порядка является мерой того, как близко точка x к оптимальному. Большинство решателей Optimization Toolbox™ использует эту меру, хотя она имеет различные определения для различных алгоритмов. Оптимальность первого порядка является необходимым условием, но это не достаточное условие. Другими словами:

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

Для получения общей информации об оптимальности первого порядка, смотрите Носедэла и Райта [31]. Для специфических особенностей о мерах оптимальности первого порядка для решателей Optimization Toolbox смотрите Неограниченную Оптимальность, Ограниченную Теорию Оптимальности и Ограниченную Оптимальность в Форме Решателя.

Остановка правил, связанных с оптимальностью первого порядка

OptimalityTolerance допуск относится к мере оптимальности первого порядка. Как правило, если мера оптимальности первого порядка меньше OptimalityTolerance, завершение итераций решателя.

Некоторые решатели или алгоритмы используют оптимальность первого порядка relative в качестве останавливающегося критерия. Завершение итераций решателя, если мера оптимальности первого порядка меньше времен μ OptimalityTolerance, где μ также:

Норма по бесконечности (максимум) градиента целевой функции при x0
Норма по бесконечности (максимум) входных параметров к решателю, таких как f или b в linprog или H в quadprog

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

Решатели с расширенным состоянием выходных сообщений, в деталях критерия остановки, когда они используют относительную оптимальность первого порядка.

Неограниченная оптимальность

Для сглаженной неограниченной проблемы,

$\min_{x} f (x),$

мера оптимальности первого порядка является нормой по бесконечности (значение максимального абсолютного значения) ∇f (x), который является:

$first-order optimality measure = \max_{i} | {(\nabla f (x))}_{i} | = {‖ \nabla f (x) ‖}_{\infty} .$

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

Ограниченная теория оптимальности

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

Для сглаженной ограниченной проблемы позвольте g и h быть вектор-функциями, представляющими все ограничения неравенства и ограничения равенства соответственно (значение связанных, линейных, и нелинейных ограничений):

$\min_{x} f (x) при ограничениях g (x) \leq 0, h (x) = 0.$

Значение оптимальности первого порядка в этом случае является более комплексным, чем для неограниченных проблем. Определение основано на условиях Karush-Kuhn-Tucker (KKT). Условия KKT походят на условие, что градиент должен быть нулем как минимум, измененный, чтобы принять ограничения во внимание. Различие - то, что условия KKT содержат для ограниченных проблем.

Условия KKT используют вспомогательную лагранжевую функцию:

L (x, λ) = f (x) + \sum λ_{g, i} g_{i} (x) + \sum λ_{h, i} h_{i} (x) .

(1)

Векторный λ, который является конкатенацией _λg и _λh, является вектором множителей Лагранжа. Его длина является общим количеством ограничений.

Условия KKT:

\nabla_{x} L (x, λ) = 0,

(2)

λ_{g, i} g_{i} (x) = 0 \forall i,

(3)

{\begin{matrix} g (x) \leq 0, \\ h (x) = 0, \\ λ_{g, i} \geq 0. \end{matrix}

(4)

Решатели не используют эти три выражения в уравнении 4 в вычислении меры оптимальности.

Мера оптимальности, сопоставленная уравнением 2,

‖ \nabla_{x} L (x, λ ‖ = ‖ \nabla f (x) + \sum λ_{g, i} \nabla g_{i} (x) + \sum λ_{h, i} \nabla h_{h, i} (x) ‖ .

(5)

Мера оптимальности, сопоставленная уравнением 3,

‖ \vec{λ_{g} g} (x) ‖,

(6)

где норма в уравнении 6 средних норм по бесконечности (максимум) вектора

\vec{λ_{g, i} g_{i}} (x)

Объединенная мера оптимальности является максимумом значений, вычисленных в уравнении 5 и уравнении 6. Решатели, которые принимают нелинейные ограничительные нарушения ограничений отчета функций g (x) > 0 или |h (x) | > 0 как ConstraintTolerance нарушения. Смотрите Допуски и Критерий остановки.

Ограниченная оптимальность в форме решателя

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

\begin{array}{l} ‖ \nabla_{x} L (x, λ ‖ = ‖ \nabla f (x) + A^{T} λ_{i n e q l i n} + A e q^{T} λ_{e q l i n} \\ + \sum λ_{i n e q n o n l i n, i} \nabla c_{i} (x) + \sum λ_{e q n o n l i n, i} \nabla c e q_{i} (x) ‖, \end{array}

(7)

‖ \vec{| l_{i} - x_{i} | λ_{l o w e r, i}}, \vec{| x_{i} - u_{i} | λ_{u p p e r, i}}, \vec{| {(A x - b)}_{i} | λ_{i n e q l i n, i}}, \vec{| c_{i} (x) | λ_{i n e q n o n l i n, i}} ‖,

(8)

где норма векторов в уравнении 7 и уравнении 8 является нормой по бесконечности (максимум). Индексы на множителях Лагранжа соответствуют структурам множителя Лагранжа решателя. Смотрите Структуры множителя Лагранжа. Суммирование в уравнении 7 передвигается на все ограничения. Если связанным является ±Inf, тот термин не ограничивается, таким образом, это не часть суммирования.

Линейные равенства только

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

Ограниченные наименьшие квадраты и доверительная область отражающие решатели

Для решателей наименьших квадратов и доверительной области отражающие алгоритмы, в проблемах с одними только границами, мера оптимальности первого порядка является максимумом по i _|vi*_gi |. Здесь _gi является i th компонент градиента, x является текущей точкой, и

$v_{i} = {\begin{array}{l} | x_{i} - b_{i} | & если отрицательный градиент указывает на связанный b_{i} \\ 1 & в противном случае . \end{array}$

Если _xi в связанном, _vi является нулем. Если _xi не в связанном, то при минимизации указывают градиент_{, gi} должен быть нулем. Поэтому мера оптимальности первого порядка должна быть нулем в точке минимизации.

Документация