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

В непринужденной минимизация проблема, Условия Вульфа представляют собой набор неравенств для выполнения неточный линейный поиск, особенно в квазиньютоновские методы, впервые опубликовано Филип Вулф в 1969 г.^[1][2]

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

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

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

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

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

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

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

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

${\displaystyle {\begin{aligned}{\textbf {i)}}&\quad 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}),\\[6pt]{\textbf {ii)}}&\quad {-\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}),\end{aligned}}}$

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

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

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

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

${\displaystyle {\textbf {iii)}}\quad {\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) вместе образуют так называемые сильные условия Вульфа, и сила ${\displaystyle \alpha _{k}}$ лежать рядом с критическая точка из ${\displaystyle \varphi }$.

Обоснование

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

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

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

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

Комментарии

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

Смотрите также

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

Рекомендации

1. Вулф, П. (1969). «Условия сходимости методов восхождения». SIAM Обзор. 11 (2): 226–000. Дои:10.1137/1011036. JSTOR  2028111.
2. Вулф, П. (1971). «Условия сходимости методов восхождения. II: Некоторые исправления». SIAM Обзор. 13 (2): 185–000. Дои:10.1137/1013035.
3. Нокедаль, Хорхе; Райт, Стивен (1999). Численная оптимизация. п. 38.
4. Армийо, Ларри (1966). «Минимизация функций, имеющих липшицевы первые частные производные». Pacific J. Math. 16 (1): 1–3. Дои:10.2140 / pjm.1966.16.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.