14、PRP 共轭梯度法与精确线搜索

本文将介绍 PRP 共轭梯度法，我们又进入崭新的一页。方法的全局收敛性证明会有点难，所以在 1969 年提出 PRP 共轭梯度法，却在 1992 年才证明其全局收敛性。

1、引言

PRP 共轭梯度法是由 Polak 和 Ribiere $^{[1]}$ 和 Polyak $^{[2]}$ 在 1969 年独立提出的一种非线性共轭梯度法，这种方法具有如下形式：
$x_{k+1}=x_k+\alpha_k d_k,\tag{1}$
$d_k=\begin{cases} -g_k,\quad & k=1,\\ -g_k+\beta_k d_k, &k\ge 2,\end{cases}\tag{2}$
其中参数 $~\beta_k~$ 由以下公式计算：
$\beta_k^{PRP}=\frac{g_k^T(g_k-g_{k-1})}{\Vert g_{k-1}\Vert^2}.\tag{3}$
PRP 共轭梯度法的全程为 Polak-Pibiere-Polyak 共轭梯度法，以后我们只说其简称。
PRP 共轭梯度法是目前认为数值表现最好的共轭梯度法之一。当算法产生一个小步长时，由 PRP 方法定义的搜索方向 $~d_k~$ 自动地靠近负梯度方向，从而有效地避免 FR 共轭梯度法可能连续产生小步长的缺点。基于此， Powell 在文献 ${[3]}$ 中证明了当步长 $~x_k=x_{k+1}-x_k~$ 趋于零时 PRP 方法的全局收敛性。利用文献 ${[4]}$ 中的结果即知采取精确线搜索的 PRP 方法对一致凸函数的全局收敛性。但是对于一般非凸函数，Powell 在文献 ${[5]}$ 中举出了三维反列，表明即使按 $~\rm{Curry}~$ 原则选取步长因子，即取 $~\alpha_k~$ 为一维函数 $\phi_k(\alpha)=\left\{f(x_k+\alpha d_k):\alpha>0\right\}$ 的第一个极小点，PRP 方法可能在六点附近循环，而其中任意一点都不是目标函数的稳定点。

2、精确线搜索下 PRP 方法的性质

如果采取精确线搜索，即
$\alpha_k=\arg\min_{\alpha>0} f(x_k+\alpha d_k)\tag{4}$
则有以下关系式
$\Vert d_k\Vert=\sec\theta_k\Vert g_k\Vert.\tag{5}$
$\beta_{k+1}\Vert d_k\Vert=\tan\theta_{k+1}\Vert g_{k+1}\Vert.\tag{6}$
利用 (3) 式。显然有
$\beta_{k+1}\le\frac{\Vert g_{k+1}\Vert\Vert g_{k+1}-g_k\Vert}{\Vert g_k\Vert^2}.\tag{7}$
利用 (5)、(6) 和 (7)，有
$\tan\theta_{k+1}\le\frac{\sec\theta_k\Vert g_{k+1}-g_k\Vert}{\Vert g_k\Vert}.\tag{8}$
故如果 $~\theta_k\rightarrow\frac{\pi}{2}~$ ，并且导致步长 $~s_k=x_{k+1}-x_k~$ 非常小，以及 $~\Vert g_{k+1}-g_k\Vert<<\Vert g_k\Vert~$ ，则由 (8) 式可知，
$\tan\theta_{k+1}<<\sec\theta_k\tag{9}$
从而下一步的搜素方向 $~d_{k+1}~$ 将自动靠近负梯度方向 $~-g_{k+1}~$ 。可见 PRP 方法当产生一个小步长时，具有自动地接近最速下降法的优点，从而有效地避免 FR 方法可能连续产生小步长的缺陷。到目前为止， PRP 方法仍被认为是数值表现最好的共轭梯度法之一。

定理 1：设目标函数 $~f(x)~$ 下方有界，导数 $~\rm{Lipschitz}~$ 连续，考虑 PRP 共轭梯度法 (1)-(3)，其中步长因子 $~\alpha_k~$ 由精确线搜索 (4) 求出，如果当 $~k\rightarrow\infty~$ ， $\Vert s_k\Vert\rightarrow 0~$ ，则必有
$\lim\inf\Vert g_k\Vert=0.\tag{10}$
证明：设定理不真，则存在常数 $~\gamma>0~$ ，使得
$\Vert g_k\Vert\ge\gamma,~~\forall~k\ge 1\tag{11}$
由导数的 $~\rm{LIpschitz}~$ 连续性和步长 $~\Vert s_k\Vert~$ 趋于零知，存在正整数 $~m~$ ，使得
$\Vert g_{k+1}-g_k\Vert\le\frac{\gamma}{2}\tag{12}$
对所有的 $~k\ge m~$ 成立。注意对所有的 $~\theta_k\in[0,\frac{\pi}{2})~$ ，有
$\sec\theta_k\le 1+\tan\theta_k\tag{13}$
可以由 (8)、(12) 和 (13) 推出
$\begin{align}\tan\theta_k&\le\frac{1}{2}+\frac{1}{4}+\dots+(\frac{1}{2})^{k+1-m}(1+\tan\theta_m)\\ &\le1+\tan\theta_m~~,\forall~k\ge m.\end{align}\tag{14}$
故搜索方向 $~d_k~$ 与负梯度方向 $~-g_k~$ 的夹角总小于某个小于 $~\frac{\pi}{2}~$ 的角度。由 $~\rm{Zoutendijk}~$ 条件可知， $\Vert g_k\Vert\rightarrow 0~$ 。这与 (11) 相矛盾，从而 (10) 成立。

若 $~\alpha_k~$ 满足精确线搜索 (4)，或满足
$f(x_k+\alpha_k d_k)\le f(x_k)+\rho\alpha_k g_k^T d_k.\tag{15}$
袁亚湘 $^{[4]}$ 对一致凸函数给出了如下函数下降量的估计式：
$f_k-f(x_k+s_k)\ge c\Vert s_k\Vert^2.\tag{16}$
其中 $~c>0~$ 为常数。故当 $~k\rightarrow\infty~$ ，必有 $~\Vert s_k\Vert\rightarrow 0~$ ，于是由 定理 1 可知，采取精确线搜索的 PRP 方法对一致凸函数是全局收敛的。

定理 2：设目标函数 $~f(x)~$ 为一致凸函数，即存在常数 $~\eta>0~$ ，使得
$(x-y)^T(\nabla f(x)-\nabla f(y))\ge \eta\Vert x-y\Vert^2\tag{17}$
对任何 $~x,y\in\mathbb{R}^n~$ 均成立，考虑 PRP 方法 (1)-(3)，其中步长因子 $~\alpha_k~$ 由精确线搜索 (4) 求出，则必有 (10) 成立。

3、参考文献

[1] Polak E, Ribière G. Note surla convergence de directions conjugèes[J]. Rev Francaise Informat Recherche Operationelle, 1969, 3(16): 35--43.
[2] Polyak B T. The conjugate gradient method in extreme problems[J]. USSR Computational Mathematic and Mathematical Physics, 1969, 9(4): 94--112.
[3] Powell M J D. Restart procedures of the conjugate gradient method[J]. Math Program, 1977, 2: 241-254.
[4] 袁亚湘, 孙文喻. 最优化理论与方法[M].
[5] Powell M J D. Nonconvex minimization calculations and the conjugate gradient method. in: Lecture Notes in Mathematics vol 1066, Berlin: Springer-Verlag, 1984, 122~141.

14、PRP 共轭梯度法与精确线搜索