Оптимальность первого порядка является мерой того, насколько точка x близка к оптимальной. Большинство решателей Optimization Toolbox™ используют эту меру, хотя она имеет разные определения для различных алгоритмов. Оптимальность первого порядка является необходимым условием, но она не является достаточным условием. Другими словами:
Мера оптимальности первого порядка должна быть равна нулю как минимум.
Точка с оптимальностью первого порядка, равной нулю, не обязательно является минимальной.
Общие сведения об оптимальности первого порядка см. в разделах Nocedal и Wright [31]. Сведения о мерах оптимальности первого порядка для решателей панели инструментов оптимизации см. в разделах Неограниченная оптимальность, Теория ограниченной оптимальности и Ограниченная оптимальность в форме решателя.
OptimalityTolerance допуск относится к измерению оптимальности первого порядка. Как правило, если мера оптимальности первого порядка меньше OptimalityTolerance, итерации решателя заканчиваются.
Некоторые решатели или алгоритмы используют относительную оптимальность первого порядка в качестве критерия остановки. Итерации решателя заканчиваются, если измерение оптимальности первого порядка не превышает λ раз OptimalityTolerance, где λ - либо:
Норма бесконечности (максимальная) градиента целевой функции при x0
Норма бесконечности (максимум) входных данных решателя, например f или b в linprog или H в quadprog
Относительная мера пытается учесть масштаб проблемы. Умножение целевой функции на очень большое или малое число не изменяет условие остановки для критерия относительной остановки, но изменяет его для немасштабированного.
Решатели с расширенным состоянием сообщений выхода в деталях критериев остановки, когда они используют относительную оптимальность первого порядка.
Для гладкой задачи без ограничений,
),
мерой оптимальности первого порядка является норма бесконечности (означающая максимальное абсолютное значение) ∇f (x), которая является:
x) ‖ ∞.
Эта мера оптимальности основана на привычном для гладкой функции условии достижения минимума: её градиент должен быть равен нулю. Для неограниченных проблем, когда измерение оптимальности первого порядка почти равно нулю, целевая функция имеет градиент почти равен нулю, так что целевая функция может быть близка к минимуму. Если мера оптимальности первого порядка не мала, целевая функция не минимальна.
В этом разделе обобщена теория, лежащая в основе определения меры оптимальности первого порядка для ограниченных задач. Определение, используемое в функциях панели инструментов оптимизации, находится в разделе Ограниченная оптимальность в форме решателя.
Для задачи с гладким ограничением пусть g и h - векторные функции, представляющие все ограничения неравенства и равенства соответственно (означающие связанные, линейные и нелинейные ограничения):
) = 0.
Смысл оптимальности первого порядка в данном случае более сложен, чем для неограниченных задач. Определение основано на условиях Каруша-Куна-Такера (ККТ). Условия KKT аналогичны условию, при котором градиент должен быть нулевым, как минимум, модифицированным с учетом ограничений. Разница в том, что условия KKT выдерживают проблемы с ограничениями.
Условия KKT используют вспомогательную функцию Лагранжа:
| +∑λh,ihi (x). | (1) |
Условия KKT:
| = 0, | (2) |
| ∀i, | (3) |
| =0,λg,i≥0. | (4) |
Мера оптимальности, связанная с уравнением 2,
| +∑λh,i∇hh,i (x) ‖. | (5) |
| ‖, | (6) |
Комбинированное измерение оптимальности является максимумом значений, вычисленных в уравнении 5 и уравнении 6. Решатели, принимающие функции нелинейных ограничений, сообщают о нарушениях ограничений g (x ) > 0 или | h ( x) | > 0 какConstraintTolerance нарушения. См. раздел Допуски и критерии остановки.
Большинство решателей панели инструментов с ограничениями разделяют расчет измерения оптимальности первого порядка на границы, линейные функции и нелинейные функции. Мера является максимальной из следующих двух норм, которые соответствуют уравнению 5 и уравнению 6:
| (7) |
| |λineqnonlin,i→ ‖, | (8) |
где норма векторов в уравнении 7 и уравнении 8 является бесконечной нормой (максимальной). Подстрочные индексы множителей Лагранжа соответствуют структурам множителей Лагранжа решателя. См. раздел Структуры множителей Лагранжа. Суммирование в уравнении 7 находится в диапазоне по всем ограничениям. Если граница равна ±Inf, этот член не ограничен, поэтому он не является частью суммирования.
Для некоторых крупномасштабных задач с только линейными равенствами мера оптимальности первого порядка является нормой бесконечности спроецированного градиента. Другими словами, мера оптимальности первого порядка - это размер градиента, проецируемого на нулевое пространство Aeq.
Для решателей наименьших квадратов и алгоритмов, отражающих область доверия, в задачах только с границами мера оптимальности первого порядка является максимальной над i | vi * gi |. Здесь gi - i-я составляющая градиента, x - текущая точка, и
.
Если xi находится на границе, vi равно нулю. Если xi не находится на границе, то в точке минимизации градиент gi должен быть равен нулю. Поэтому мера оптимальности первого порядка должна быть равна нулю в точке минимизации.