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

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

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

${\ Displaystyle \ мин _ {х} е (\ mathbf {х})}$

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

${\ Displaystyle \ мин _ {\ альфа} е (\ 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}}}$

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

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

Обозначим одномерную функцию, ограниченную направлением, как . Условия Вульфа могут привести к значению длины шага, не близкому к минимизатору . Если мы изменим условие кривизны на следующее,${\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 |}}$

затем я) и III) вместе образуют так называемые сильные условия Wolfe , а силы лежат близко к критической точке в .${\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}$

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

Комментарии [ редактировать ]

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

См. Также [ править ]

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

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