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

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

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

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

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

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

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

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

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

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

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

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

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

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

то

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

где

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

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

${\displaystyle \cos ^{2}\theta _{k}||\nabla f_{k}||^{2}\rightarrow 0}$ при ${\displaystyle 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.