Первичный порядок меры оптимальности

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

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

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

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

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

The 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.$

Смысл оптимальности первого порядка в этом случае сложнее, чем для задач без ограничений. Определение основано на условиях Каруша-Куна-Такера (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 или |<reservedrangesplaceholder2> (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.

Ограниченные методом наименьших квадратов и Trust-Region-Reflective Решателей

Для решателей методом наименьших квадратов и алгоритмов, отражающих доверительные области, в задачах с одними только границами мера оптимальности первого порядка является максимальной по i _{|<reservedrangesplaceholder4>*<reservedrangesplaceholder3>|}. Здесь gi является i -м компонентом градиента, x является текущей точкой, и

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

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

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