Условия Вольфе (Rvlkfnx Fkl,sy)

Условия Вольфе — в теории оптимизации набор условий, которые используются в алгоритме приближенного поиска вдоль направления, в алгоритме Бройдена — Флетчера — Гольдфарба — Шанно (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

, что означает, что алгоритм сходится.

Литература

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