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

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

ОписаниеПравить

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

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

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

$f(x_k+{\mathrm{\alpha <!--\; \alpha \; -->}}_k{p}_k)\le <!--\; \le \; -->f(x_k)+c_1{\mathrm{\alpha <!--\; \alpha \; -->}}_k\mathrm{\nabla <!--\; \nabla \; -->}{f}_k^T{p}_k,$$f(x_{k}+\alpha _{k}p_{k})\leq f(x_{k})+c_{1}\alpha _{k}\nabla f_{k}^{T}p_{k},$ 

$\mathrm{\nabla <!--\; \nabla \; -->}f(x_k+{\mathrm{\alpha <!--\; \alpha \; -->}}_k{p}_k{)}^T{p}_k\ge <!--\; \ge \; -->c_2\mathrm{\nabla <!--\; \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$$c_{1}$  выбирается достаточно маленькой (в окрестности 0), что означает, что функция после совершения шага должна уменьшиться, в то время как $c_2$$c_{2}$  выбирается значительно большей (в окрестности 1), что, в свою очередь, означает, что проекция градиента в новом приближении должна либо изменить направление, либо уменьшиться.

Усиленные условия ВольфеПравить

Другой вариант условий Вольфе, который предполагает, что новое приближение лежит в окрестности локального минимума функции $\mathrm{\varphi <!--\; \varphi \; -->}(\mathrm{\alpha <!--\; \alpha \; -->})=f(x_k+\mathrm{\alpha <!--\; \alpha \; -->}{p}_k)$$\phi (\alpha )=f(x_{k}+\alpha p_{k})$ :

$f(x_k+{\mathrm{\alpha <!--\; \alpha \; -->}}_k{p}_k)\le <!--\; \le \; -->f(x_k)+c_1{\mathrm{\alpha <!--\; \alpha \; -->}}_k\mathrm{\nabla <!--\; \nabla \; -->}{f}_k^T{p}_k,$$f(x_{k}+\alpha _{k}p_{k})\leq f(x_{k})+c_{1}\alpha _{k}\nabla f_{k}^{T}p_{k},$ 

$|\mathrm{\nabla <!--\; \nabla \; -->}f(x_k+{\mathrm{\alpha <!--\; \alpha \; -->}}_k{p}_k{)}^T{p}_k|\le <!--\; \le \; -->c_2|\mathrm{\nabla <!--\; \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}|$ 

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

СвойстваПравить

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

$\mathrm{\forall <!--\; \forall \; -->}x,\stackrel{~<!--\; ~\; -->}{x}\in <!--\; \in \; -->N||\mathrm{\nabla <!--\; \nabla \; -->}f(x)-<!--\; -\; -->\mathrm{\nabla <!--\; \nabla \; -->}f(\stackrel{~<!--\; ~\; -->}{x})||\le <!--\; \le \; -->L||x-<!--\; -\; -->\stackrel{~<!--\; ~\; -->}{x}||,$$\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 <!--\; \; -->{\mathrm{\theta <!--\; \theta \; -->}}_k=-<!--\; -\; -->\frac{\mathrm{\nabla <!--\; \nabla \; -->}{f}_k^T{p}_k}{||\mathrm{\nabla <!--\; \nabla \; -->}{f}_k||||p_k||}$$\cos \theta _{k}=-{\frac {\nabla f_{k}^{T}p_{k}}{||\nabla f_{k}||||p_{k}||}}$ .

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

${\cos }^2<!--\; \; -->{\mathrm{\theta <!--\; \theta \; -->}}_k||\mathrm{\nabla <!--\; \nabla \; -->}{f}_k|{|}^2\to <!--\; \to \; -->0$$\cos ^{2}\theta _{k}||\nabla f_{k}||^{2}\rightarrow 0$  при $k\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}$$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.