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

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

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

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

уже имеется приближение решения задачи и пусть каким-либо методом мы нашли направление , в котором будем искать новое приближение решения . Тогда , где удовлетворяет условиям Вольфе:

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

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

[править | править код]

Другой вариант условий Вольфе, который предполагает, что новое приближение лежит в окрестности локального минимума функции :

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

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

то

где

.

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

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

Литература

[править | править код]
  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.