9、强 Wolfe 线搜索下一般性收敛定理

本文给出在强 $~\rm{Wolfe}~$ 线搜索下一般性收敛性定理，由戴彧虹，韩继业，刘光辉，孙德峰，阴红霞和袁亚湘 $^{[1]}$ 提出，这些人都是运筹学领域的大家。而且这个定理本身也非常有用，是对充分下降条件的弱化，因为这里仅仅需要下降条件即可。

1、引言

共轭梯度法是求解无约束优化问题常用的方法
$\min_{x\in\mathbb{R}^n}~f(x)\tag{1}$
其一般的迭代格式为
$x_{k+1}=x_k+\alpha_k d_k\tag{2}$
$d_k=\begin{cases}-g_k,&k=1,\\-g_k+\beta_k d_{k-1},&k\ge2,\end{cases}\tag{3}$
其中 $~\beta_k~$ 是参数。不同的 $~\beta_k~$ 决定不同的共轭梯度法。
我们考虑推广的 Wolfe 线搜素，其条件为
$f(x_k)-f(x_k+\alpha_kd_k)\ge -\rho\alpha_kg_k^T d_k\tag{5}$
$\sigma_1g_k^T d_k\le g(x_k+\alpha_k d_k)^T d_k\le-\sigma_2g_k^T d_k\tag{6}$
其中参数 $~0<\rho<\sigma_1<1~$ 以及 $~0\le\sigma_2<1~$ 。显然，如果 $~\sigma_1=\sigma_2~$ ，则上述搜素条件就是强 $\rm{Wolfe}$ 线搜索。

2、收敛性定理

定理：设目标函数 $~f(x)~$ 有界，导数 $~\rm{Lipschitz}~$ 条件。考虑一般的共轭梯度法 (2) 和 (3)，其中 $~\alpha_k~$ 满足 (5) 和 (6)， $~d_k~$ 满足
$g_k^T d_k<0,~~\forall~k\ge 1$
如果
$\sum_{k=1}^{\infty}\frac{\Vert g_k\Vert^t}{\Vert d_k\Vert^2}=\infty$
对某常数 $~t\in [0,4]~$ 成立，则方法在下述意义下全局收敛：
$\lim\inf\Vert g_k\Vert=0$
证明：由 (3) 知，对 $~k\ge 2~$ 有
$d_k+g_k=\beta_k d_{k-1}$
对上式两端取模平方移项，得
$\Vert d_k\Vert^2=\beta_k^2\Vert d_{k-1}\Vert^2-\Vert g_k\Vert^2-2g_k^T d_k$
因为 $~g_k^T d_k<0~$ ，故有
$\Vert d_k\Vert^2\ge\beta_k^2\Vert d_{k-1}\Vert^2-\Vert g_k\Vert^2\tag{7}$
由 (3) 式可以推出
$g_k^T d_k-\beta_k g_k^T d_{k-1}=-\Vert g_k\Vert^2\tag{8}$
令 $~c=\left\{\sigma_1,\sigma_2\right\}~$ ，由 (6) 和 (8) 得
$\vert g_k^T d_k\vert+c\vert\beta_k\vert\vert g_{k-1}^T d_{k-1}\vert\ge\Vert g_k\Vert^2$
利用上式和 Cauchy-Schwarz 不等式知
$(g_k^T d_k)^2+\beta^2(g_{k-1}^T d_{k-1})^2\ge c_1\Vert g_k\Vert^4\tag{9}$
其中 $~c_1=\frac{1}{(1+c)^2}>0~$ 为常数，结合 (7) 和 (9)，便得
$\begin{align} &\frac{(g_k^T d_k)^2}{\Vert d_k\Vert^2}+\frac{(g_{k-1}^T d_{k-1})^2}{\Vert d_{k-1}\Vert^2}\\ =&\frac{1}{\Vert d_k\Vert^2}[(g_k^T d_k)^2+\frac{\Vert d_k\Vert^2}{\Vert d_{k-1}\Vert^2}(g_{k-1}^T d_{k-1})^2]\\ \ge &\frac{1}{\Vert d_k\Vert^2}[(g_k^T d_k)^2+\beta_k^2(g_{k-1}^T d_{k-1})^2-\frac{(g_{k-1}^T d_{k-1})^2}{\Vert d_{k-1}\Vert^2}\Vert g_k\Vert^2]\\ \ge&\frac{1}{\Vert d_k\Vert^2}[c_1\Vert g_k\Vert^4-\frac{(g_{k-1}^T d_{k-1})^2}{\Vert d_{k-1}\Vert^2}\Vert g_k\Vert^2] \end{align}\tag{10}$
若定理结论不真，则存在常数 $~\gamma>0~$ ，使得
$\Vert g_k\Vert\ge \gamma,~~\forall~k\ge 1\tag{11}$
另外，从 $\rm{Zoutendijk}$ 条件可知
$\lim_{k\rightarrow\infty}\frac{g_k^T d_k}{\Vert d_k\Vert}=0\tag{12}$
利用 $(10),(11),(12)$ 知，对充分大的 $~k~$ 都有
$\frac{(g_k^T d_k)^2}{\Vert d_k\Vert^2}+\frac{(g_{k-1}^T d_{k-1})^2}{\Vert d_{k-1}\Vert^2}\ge\frac{c_1}{2}\frac{\Vert g_k\Vert^4}{\Vert d_k\Vert^2}$
由 $~\rm{Zoutendijk}~$ 条件可知
$\sum_{k\ge 1}\frac{\Vert g_k\Vert^4}{\Vert d_k\Vert^2}<\infty\tag{13}$
利用 (11) 式，对于 $~t\in [0,4]~$ ，有
$\Vert g_k\Vert^{t-4}\le\gamma^{t-4}\tag{14}$
利用 (13) 和 (14) 式，就有
$\sum_{k\ge 1}\frac{\Vert g_k\Vert^t}{\Vert d_k\Vert^2}<\infty$
这与题目条件所矛盾，故假设不成立，则命题得证。

推论：设目标函数 $~f(x)~$ 有界，导数 $~\rm{Lipschitz}~$ 条件。考虑一般的共轭梯度法 (2) 和 (3)，其中 $~\alpha_k~$ 满足 (5) 和 (6)， $~d_k~$ 满足
$g_k^T d_k<0,~~\forall~k\ge 1$
如果
$\sum_{k=1}^{\infty}\frac{\vert g_k^T d_k \vert^r}{\Vert d_k\Vert^2}=\infty$
对某常数 $~r\in [0,2]~$ 成立，则方法在下述意义下全局收敛：
$\lim\inf\Vert g_k\Vert=0$
证明：分情况讨论
(1) 若 $~\vert g_k^T d_k\vert\in [0,1]~$ ，对于 $~t\in[0,2]~$ ，有 $~\vert g_k^T d_k\vert^t\le 1~$ ，则
$\sum_{k=1}^{\infty}\frac{1}{\Vert d_k\Vert^2}=\infty$
显然和定理矛盾，故结论成立。
(2) 若 $~\vert g_k^T d_k\vert>1~$ ，对于 $~t\in[0,2]~$ ，有 $~\vert g_k^T d_k\vert^t\le (g_k^T d_k)^2$ ，则
$\vert g_k^T d_k\vert^r\le 1+(g_k^T d_k)^2$
于是
$\sum_{k\ge 1}\frac{1}{\Vert d_k\Vert^2}\ge\sum_{k\ge1}\frac{\vert g_k^T d_k\vert^r}{\Vert d_k\Vert^2}-\sum_{k\ge 1}\frac{(g_k^T d_k)^2}{\Vert d_k\Vert^2}$
利用 $\rm{Zoutendijk}$ 条件和题目条件知
$\sum_{k=1}^{\infty}\frac{1}{\Vert d_k\Vert^2}=\infty$
显然和定理矛盾，故结论成立。从而引理得证。

3、结束语

上述定理为共轭梯度法的收敛性分析提供了一个强有力的工具，令 $~t=0~$ ，则由上面定理可以看出，只要 $~\Vert d_k\Vert^2~$ 最多线性增长，即
$\Vert d_k\Vert^2\le \eta_1+\eta_2k$
则方法必然全局收敛。

参考文献
[1] Dai Y H, Han J Y, Liu G H, Sun D F, Yin H X, Yuan Y X. Convergence properties of nonlinear conjuagte gadient methods, SIAM Journal of Optimization, 2000, 10: 345-358.
[2] 戴彧虹. 非线性共轭梯度法[M]. 科学出版社, 2000.