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

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

Описание

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

$\underset{x}{\min }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)\le f(x_k)+c_1{\alpha }_k\mathrm{\nabla }{f}_k^T{p}_k,$

$\mathrm{\nabla }f(x_k+{\alpha }_k{p}_k{)}^T{p}_k\ge c_2\mathrm{\nabla }{f}_k^T{p}_k$

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

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

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

$f(x_k+{\alpha }_k{p}_k)\le f(x_k)+c_1{\alpha }_k\mathrm{\nabla }{f}_k^T{p}_k,$

$|\mathrm{\nabla }f(x_k+{\alpha }_k{p}_k{)}^T{p}_k|\le c_2|\mathrm{\nabla }{f}_k^T{p}_k|$

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

Свойства

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

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

то

$\sum _{k\ge 0}{\cos }^2{\theta }_k||\mathrm{\nabla }{f}_k|{|}^2<\mathrm{\infty },$

где

$\cos {\theta }_k=-\frac{\mathrm{\nabla }{f}_k^T{p}_k}{||\mathrm{\nabla }{f}_k||||p_k||}$.

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

${\cos }^2{\theta }_k||\mathrm{\nabla }{f}_k|{|}^2\to 0$ при $k\to \mathrm{\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.