Условия Вольфе

Условия Вольфе — в теории оптимизации набор условий, которые используются в алгоритме приближенного поиска вдоль направления, в алгоритме Бройдена — Флетчера — Гольдфарба — Шанно (BFGS). Впервые опубликованы Филипом Вольфе в 1969 году.

Описание

Пусть решается задача минимизации

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

уже имеется приближение решения задачи $x_{k}$ и пусть каким-либо методом мы нашли направление $p_{k}$, в котором будем искать новое приближение решения $x_{k+1}$. Тогда $x_{k+1}=x_{k}+\alpha _{k}p_{k}$, где $\alpha _{k}$ удовлетворяет условиям Вольфе:

$f(x_{k}+\alpha _{k}p_{k})\leq f(x_{k})+c_{1}\alpha _{k}\nabla f_{k}^{T}p_{k},$

$\nabla f(x_{k}+\alpha _{k}p_{k})^{T}p_{k}\geq c_{2}\nabla f_{k}^{T}p_{k}$

Константы выбираются следующим образом: $0<c_{1}<c_{2}<1$. Обычно константа $c_{1}$ выбирается достаточно маленькой (в окрестности 0), что означает, что функция после совершения шага должна уменьшиться, в то время как $c_{2}$ выбирается значительно большей (в окрестности 1), что, в свою очередь, означает, что проекция градиента в новом приближении должна либо изменить направление, либо уменьшиться.

Усиленные условия Вольфе

Другой вариант условий Вольфе, который предполагает, что новое приближение лежит в окрестности локального минимума функции $\phi (\alpha )=f(x_{k}+\alpha p_{k})$:

$f(x_{k}+\alpha _{k}p_{k})\leq f(x_{k})+c_{1}\alpha _{k}\nabla f_{k}^{T}p_{k},$

$|\nabla f(x_{k}+\alpha _{k}p_{k})^{T}p_{k}|\leq c_{2}|\nabla f_{k}^{T}p_{k}|$

Первое неравенство оставлено таким же, как и в условиях Вольфе, а второе изменено таким образом, чтобы проекция градиента должна уменьшиться по модулю. Таким образом исключаются точки, которые находятся далеко от стационарных точек функции $\phi$. Константы подбираются так же, как и в условиях Вольфе.

Свойства

Можно показать, что если $p_{k}$ — направление убывания ограниченной снизу и непрерывно дифференциируемой функции $f$, каждый шаг $\alpha _{k}$ удовлетворяет условиям Вольфе, а градиент функции $f$ непрерывен по Липшицу:

$\forall x,{\tilde {x}}\in N\quad ||\nabla f(x)-\nabla f({\tilde {x}})||\leq L||x-{\tilde {x}}||,$

то

$\sum _{k\geq 0}\cos ^{2}\theta _{k}||\nabla f_{k}||^{2}<\infty ,$

где

$\cos \theta _{k}=-{\frac {\nabla f_{k}^{T}p_{k}}{||\nabla f_{k}||||p_{k}||}}$.

Отсюда следует, что

$\cos ^{2}\theta _{k}||\nabla f_{k}||^{2}\rightarrow 0$ при $k\rightarrow \infty$, что означает, что алгоритм сходится.

Литература

1. Nocedal J., Wright S. Numerical optimization, series in operations research and financial engineering //Springer, New York. – 2006.
2. Wolfe P. Convergence conditions for ascent methods //Siam Review. – 1969. – Т. 11. – №. 2. – С. 226-235.
3. Wolfe P. Convergence conditions for ascent methods. II: Some corrections //SIAM review. – 1971. – Т. 13. – №. 2. – С. 185-188.