Условия Вульфа

неограниченной минимизации В задаче условия Вульфа представляют собой набор неравенств для выполнения неточного поиска прямой , особенно в квазиньютоновских методах , впервые опубликованных Филипом Вулфом в 1969 году.

Идея этих методов состоит в том, чтобы найти

$$\min _{x}f(\mathbf {x} )$$

для некоторого гладкого $f\colon \mathbb {R} ^{n}\to \mathbb {R}$. Каждый шаг часто предполагает приближенное решение подзадачи.

$$\min _{\alpha }f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})$$

где $\mathbf {x} _{k}$ это лучшее предположение на данный момент, $\mathbf {p} _{k}\in \mathbb {R} ^{n}$ это направление поиска, и $\alpha \in \mathbb {R}$ это длина шага.

Неточные поиски строк обеспечивают эффективный способ вычисления приемлемой длины шага. $\alpha$ это уменьшает целевую функцию «достаточно», а не минимизирует целевую функцию по $\alpha \in \mathbb {R} ^{+}$ точно. Алгоритм поиска строки может использовать условия Вульфа в качестве требования для любого угаданного значения. $\alpha$, прежде чем найти новое направление поиска $\mathbf {p} _{k}$.

Правило Армихо и кривизна

Длина шага $\alpha _{k}$ Говорят, что он удовлетворяет условиям Вульфа , ограниченным направлением $\mathbf {p} _{k}$, если выполняются следующие два неравенства:

1. $f(\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k})\leq f(\mathbf {x} _{k})+c_{1}\alpha _{k}\mathbf {p} _{k}^{\mathrm {T} }\nabla f(\mathbf {x} _{k}),$
2. ${-\mathbf {p} }_{k}^{\mathrm {T} }\nabla f(\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k})\leq -c_{2}\mathbf {p} _{k}^{\mathrm {T} }\nabla f(\mathbf {x} _{k}),$

с $0<c_{1}<c_{2}<1$. (При рассмотрении условия (ii) напомним, что для того, чтобы убедиться в том, что $\mathbf {p} _{k}$ это направление спуска, мы имеем $\mathbf {p} _{k}^{\mathrm {T} }\nabla f(\mathbf {x} _{k})<0$, как и в случае градиентного спуска , где $\mathbf {p} _{k}=-\nabla f(\mathbf {x} _{k})$, или Ньютона–Рафсона , где $\mathbf {p} _{k}=-\mathbf {H} ^{-1}\nabla f(\mathbf {x} _{k})$ с $\mathbf {H}$ положительно определенный.)

$c_{1}$ обычно выбирается довольно небольшим, в то время как $c_{2}$ намного больше; Нокедал и Райт приводят примеры значений $c_{1}=10^{-4}$ и $c_{2}=0.9$ для методов Ньютона или квазиньютона и $c_{2}=0.1$ для метода нелинейного сопряженного градиента . Неравенство i) известно как правило Армихо . и ii) как условие кривизны ; и) обеспечивает соблюдение длины шага $\alpha _{k}$ уменьшается $f$ «достаточно», и ii) гарантирует, что наклон достаточно уменьшен. Условия i) и ii) можно интерпретировать как обеспечивающие соответственно верхнюю и нижнюю границу допустимых значений длины шага.

Сильное условие Вульфа на кривизне

Обозначим одномерную функцию $\varphi$ ограничено направлением $\mathbf {p} _{k}$ как $\varphi (\alpha )=f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})$. Условия Вульфа могут привести к значению длины шага, которое не близко к минимизатору $\varphi$. Если мы изменим условие кривизны следующим образом:

3. ${\big |}\mathbf {p} _{k}^{\mathrm {T} }\nabla f(\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}){\big |}\leq c_{2}{\big |}\mathbf {p} _{k}^{\mathrm {T} }\nabla f(\mathbf {x} _{k}){\big |}$

тогда i) и iii) вместе образуют так называемые сильные условия Вульфа и заставляют $\alpha _{k}$ находиться вблизи критической точки $\varphi$.

Обоснование

Основная причина наложения условий Вульфа в алгоритме оптимизации, где $\mathbf {x} _{k+1}=\mathbf {x} _{k}+\alpha \mathbf {p} _{k}$ заключается в обеспечении сходимости градиента к нулю. В частности, если косинус угла между $\mathbf {p} _{k}$ и градиент,

$$\cos \theta _{k}={\frac {\nabla f(\mathbf {x} _{k})^{\mathrm {T} }\mathbf {p} _{k}}{\|\nabla f(\mathbf {x} _{k})\|\|\mathbf {p} _{k}\|}}$$

отделено от нуля и выполнены условия i) и ii), то $\nabla f(\mathbf {x} _{k})\rightarrow 0$.

Дополнительная мотивация в случае квазиньютоновского метода заключается в том, что если $\mathbf {p} _{k}=-B_{k}^{-1}\nabla f(\mathbf {x} _{k})$, где матрица $B_{k}$ обновляется по формуле BFGS или DFP , то если $B_{k}$ положительно определен ii) подразумевает $B_{k+1}$ также положительно определена.

Комментарии

Условия Вульфа сложнее, чем условия Армихо, и алгоритм градиентного спуска, основанный на условии Армихо, имеет лучшую теоретическую гарантию, чем алгоритм, основанный на условиях Вульфа (см. разделы «Верхняя граница скорости обучения» и «Теоретическая гарантия»). в статье Поиск по строке с возвратом ).

См. также

• Поиск строки с возвратом

Дальнейшее чтение

• «Методы поиска строк». Численная оптимизация . Серия Springer по исследованию операций и финансовой инженерии. 2006. стр. 30–32. дои : 10.1007/978-0-387-40065-5_3 . ISBN  978-0-387-30303-1 .
• «Квазиньютоновские методы». Численная оптимизация . Серия Springer по исследованию операций и финансовой инженерии. 2006. стр. 135–163. дои : 10.1007/978-0-387-40065-5_6 . ISBN  978-0-387-30303-1 .