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

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

Описание

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

[math]\displaystyle{ \min_x f(x), }[/math]

уже имеется приближение решения задачи [math]\displaystyle{ x_k }[/math] и пусть каким-либо методом мы нашли направление [math]\displaystyle{ p_k }[/math], в котором будем искать новое приближение решения [math]\displaystyle{ x_{k + 1} }[/math]. Тогда [math]\displaystyle{ x_{k + 1} = x_k + \alpha_k p_k }[/math], где [math]\displaystyle{ \alpha_k }[/math] удовлетворяет условиям Вольфе:

[math]\displaystyle{ f(x_k + \alpha_k p_k) \leq f(x_k) + c_1 \alpha_k \nabla f_k^T p_k, }[/math]

[math]\displaystyle{ \nabla f(x_k + \alpha_k p_k)^T p_k \geq c_2 \nabla f_k^T p_k }[/math]

Константы выбираются следующим образом: [math]\displaystyle{ 0 \lt c_1 \lt c_2 \lt 1 }[/math]. Обычно константа [math]\displaystyle{ c_1 }[/math] выбирается достаточно маленькой (в окрестности 0), что означает, что функция после совершения шага должна уменьшиться, в то время как [math]\displaystyle{ c_2 }[/math] выбирается значительно большей (в окрестности 1), что, в свою очередь, означает, что проекция градиента в новом приближении должна либо изменить направление, либо уменьшиться.

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

Другой вариант условий Вольфе, который предполагает, что новое приближение лежит в окрестности локального минимума функции [math]\displaystyle{ \phi(\alpha) = f(x_k + \alpha p_k) }[/math]:

[math]\displaystyle{ f(x_k + \alpha_k p_k) \leq f(x_k) + c_1 \alpha_k \nabla f_k^T p_k, }[/math]

[math]\displaystyle{ |\nabla f(x_k + \alpha_k p_k)^T p_k| \leq c_2 |\nabla f_k^T p_k| }[/math]

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

Свойства

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

[math]\displaystyle{ \forall x, \tilde{x} \in N\quad||\nabla f(x) - \nabla f(\tilde{x})||\leq L || x - \tilde{x}||, }[/math]

то

[math]\displaystyle{ \sum_{k \geq 0} \cos^2 \theta_k ||\nabla f_k||^2 \lt \infty, }[/math]

где

[math]\displaystyle{ \cos \theta_k = - \frac{\nabla f_k^T p_k}{||\nabla f_k|| ||p_k||} }[/math].

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

[math]\displaystyle{ \cos^2 \theta_k ||\nabla f_k||^2 \rightarrow 0 }[/math] при [math]\displaystyle{ k \rightarrow \infty }[/math], что означает, что алгоритм сходится.

Литература

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.