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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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