Оптимальность первого порядка является мерой того, как близко точка x к оптимальному. Большинство решателей Optimization Toolbox™ использует эту меру, хотя она имеет различные определения для различных алгоритмов. Оптимальность первого порядка является необходимым условием, но это не достаточное условие. Другими словами:
Мера оптимальности первого порядка должна быть нулем как минимум.
Точка с равной нулю оптимальностью первого порядка является не обязательно минимумом.
Для получения общей информации об оптимальности первого порядка, смотрите Носедэла и Райта [31]. Для специфических особенностей о мерах оптимальности первого порядка для решателей Optimization Toolbox смотрите Неограниченную Оптимальность, Ограниченную Теорию Оптимальности и Ограниченную Оптимальность в Форме Решателя.
OptimalityTolerance
допуск относится к мере оптимальности первого порядка. Как правило, если мера оптимальности первого порядка меньше OptimalityTolerance
, завершение итераций решателя.
Некоторые решатели или алгоритмы используют оптимальность первого порядка relative в качестве останавливающегося критерия. Завершение итераций решателя, если мера оптимальности первого порядка меньше времен μ OptimalityTolerance
, где μ также:
Норма по бесконечности (максимум) градиента целевой функции при x0
Норма по бесконечности (максимум) входных параметров к решателю, таких как f
или b
\in linprog
или H
\in quadprog
Относительная мера пытается с учетом шкалы проблемы. Умножение целевой функции очень большим или маленьким номером не изменяет останавливающееся условие для относительного критерия остановки, но действительно изменяет его для немасштабированного.
Решатели с расширенным состоянием выходных сообщений, в деталях критерия остановки, когда они используют относительную оптимальность первого порядка.
Для сглаженной неограниченной проблемы,
мера оптимальности первого порядка является нормой по бесконечности (значение максимального абсолютного значения) ∇f (x), который является:
Эта мера оптимальности основана на знакомом условии для сглаженной функции, чтобы достигнуть минимума: его градиент должен быть нулем. Для неограниченных проблем, когда мера оптимальности первого порядка является почти нулем, целевая функция имеет градиент, почти обнуляют, таким образом, целевая функция могла быть около минимума. Если мера оптимальности первого порядка не мала, целевая функция не минимальна.
Этот раздел обобщает теорию позади определения меры оптимальности первого порядка для ограниченных проблем. Определение, как используется в функциях Optimization Toolbox находится в Ограниченной Оптимальности в Форме Решателя.
Для сглаженной ограниченной проблемы позвольте g и h быть вектор-функциями, представляющими все ограничения неравенства и ограничения равенства соответственно (значение связанных, линейных, и нелинейных ограничений):
Значение оптимальности первого порядка в этом случае является более комплексным, чем для неограниченных проблем. Определение основано на условиях Karush-Kuhn-Tucker (KKT). Условия KKT походят на условие, что градиент должен быть нулем как минимум, измененный, чтобы принять ограничения во внимание. Различие - то, что условия KKT содержат для ограниченных проблем.
Условия KKT используют вспомогательную лагранжевую функцию:
(1) |
Условия KKT:
(2) |
(3) |
(4) |
Мера оптимальности, сопоставленная уравнением 2,
(5) |
(6) |
Объединенная мера оптимальности является максимумом значений, вычисленных в уравнении 5 и уравнении 6. Решатели, которые принимают нелинейные ограничительные нарушения ограничений отчета функций g (x) > 0 или |h (x) | > 0 как ConstraintTolerance
нарушения. Смотрите Допуски и Критерий остановки.
Большинство ограниченных решателей тулбокса разделяет свое вычисление меры оптимальности первого порядка в границы, линейные функции и нелинейные функции. Мерой является максимум следующих двух норм, которые соответствуют уравнению 5 и уравнению 6:
(7) |
(8) |
где норма векторов в уравнении 7 и уравнении 8 является нормой по бесконечности (максимум). Индексы на множителях Лагранжа соответствуют структурам множителя Лагранжа решателя. Смотрите Структуры множителя Лагранжа. Суммирование в уравнении 7 передвигается на все ограничения. Если связанным является ±Inf
, тот термин не ограничивается, таким образом, это не часть суммирования.
Для некоторых крупномасштабных проблем только с линейными равенствами мера оптимальности первого порядка является нормой по бесконечности спроектированного градиента. Другими словами, мера оптимальности первого порядка является размером градиента, спроектированного на пустой пробел Aeq
.
Для решателей наименьших квадратов и доверительной области отражающие алгоритмы, в проблемах с одними только границами, мера оптимальности первого порядка является максимумом по i |vi*gi |. Здесь gi является i th компонент градиента, x является текущей точкой, и
Если xi в связанном, vi является нулем. Если xi не в связанном, то при минимизации указывают градиент, gi должен быть нулем. Поэтому мера оптимальности первого порядка должна быть нулем в точке минимизации.