16、PRP 共轭梯度法与 Grippo-Lucidi 线搜索

在 $~(15)~$ 节，我们证明了 $~\rm{PRP}^{+}~$ 方法的收敛性。然而，即使 $~f(x)~$ 是一致凸函数，参数 $~\beta_k^{PRP}~$ 也可能非负。在 $~(14)~$ 节，我们知道采取精确线搜索的 $~\rm{PRP}~$ 方法对于一致凸函数的全局收敛性。于是， $\rm{Grippo}~$ 和 $~\rm{Lucidi}^{[1]}~$ 致力于寻找这样的一种线搜索，以确保原始 $~\rm{PRP}~$ 方法的收敛性。他们提出了一种 $~\rm{Armijo}~$ 线搜索，并证明了在该线搜索下，原始 $~\rm{PRP}~$ 方法对一般非凸函数的收敛性。

1、引言

PRP 共轭梯度法是由 Polak 和 Ribiere 和 Polyak 在 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}$
$\rm{Grippo}~$ 和 $~\rm{Lucidi}~$ 提出的线搜索与下述条件密切相关：
$f(x_{k+1})\le f(x_k)-\rho\alpha_k^2\Vert d_k\Vert^2,\tag{4}$
其中 $~\rho>0~$ 为常数。线搜索条件 $~(4)~$ 由 $~\rm{Leone}~$ 等学者在考虑无约束优化的无导数方法时引入的，详见文献 ${[2]}$ ，与下式相比
$f(x_{k+1})\le f(x_k)+\rho\alpha_k g_k^T d_k,\tag{5}$
相比， $(4)$ 当 $~\alpha\Vert d_k\Vert~$ 大时，要求目标函数有较大的下降量，而当 $~\alpha\Vert d_k\Vert~$ 小时， $(4)$ 比 $(5)$ 更容易满足。
具体地，给定常数 $~\tau>0,\lambda\in(0,1)~$ ， $\rm{Grippo}$ 和 $\rm{Lucidi}$ 的线搜索的基本思想是计算
$\alpha_k=\max\left\{\lambda^j\frac{\tau\vert g_k^T d_k\vert}{\Vert d_k\Vert^2};j=0,1,\dots\right\},\tag{6}$
使得 $~x_{k+1}=x_k+\alpha_k d_k~$ 和 $~d_{k+1}=-g_{k+1}+\beta_k^{PRP}d_k~$ 满足 $(4)$ 以及
$-c_2\Vert g_{k+1}^T d_{k+1}\Vert^2\le g_{k+1}^Td_{k+1}\le -c_1\Vert g_{k+1}\Vert^2,\tag{7}$
其中 $~0<c_1<1<c_2~$ 为事先给定的常数。下述引理表明，当 $~f(x)~$ 满足一定条件时，确实存在这样的步长因子 $~\alpha_k~$ ，使得 $(4)$ 和 $(7)$ 成立，而且这样的步长因子 $~\alpha_k~$ 不会太小。

2、收敛性分析

引理 1： 设函数 $~f(x)~$ 下方有界，导数 $~\rm{Lipschitz}~$ 连续可微。考虑 $~\rm{PRP}~$ 方法 $~(1)-(3)~$ ，其中步长因子 $~\alpha_k~$ 由 $\rm{Grippo}$ 和 $\rm{Lucidi}$ 线搜索确定。则对于每个 $~k~$ ，必存在这样的 $~\alpha_k>0~$ ，使得线搜索条件 $(4)$ 和 $(7)$ 成立。进一步地，存在常数 $~c>0~$ ，使得
$\alpha_k\ge c\frac{\vert g_k^T d_k\vert}{\Vert d_k\Vert^2}\tag{8}$
对所有 $~k\ge 1~$ 成立。
$\color{red}{此处我们想对上式给出两种证明方法}$

$\color{red}{证法~ 1：}$ 因为 $~d_1=-g_1~$ ，故
$-c_2\Vert g_k\Vert^2\le g_k^T d_k\le-c_1\Vert g_k\Vert^2.\tag{9}$
对 $~k=1~$ 成立。设 $~(9)~$ 对某 $~k\ge 1~$ 成立。对任意的 $~\alpha_k~$ ，定义 $~x_{k+1}=x_k+\alpha_k d_k~$ 和 $~d_{k+1}=-g_{k+1}+\beta_k^{PRP}d_k~$ ，记
$c_3=\frac{\min(1-c_1,c_2-1)}{L c_2}>0\tag{10}$
利用 $~\rm{Lipschitz}~$ 连续和归纳假设，对任意的 $~\alpha_k\in (0,c_3\frac{\vert g_k^T d_k\vert}{\Vert d_k\Vert^2})~$ ，
$\begin{align}\vert g_{k+1}^T d_{k+1}+\Vert g_{k+1}\Vert^2\vert&\le\vert \beta_{k+1}^{PRP}\vert\vert g_{k+1}^T d_k\vert\\ &\le\Vert g_{k+1}\Vert^2\frac{\Vert g_{k+1}-g_k\Vert\Vert d_k\Vert}{\Vert g_k\Vert^2}\\ &\le\Vert g_{k+1}\Vert^2\frac{L\alpha_k \Vert d_k\Vert^2}{\Vert g_k\Vert^2}\\ &\le\min\left\{1-c_1,c_2-1\right\}\Vert g_{k+1}\Vert^2 \end{align}\tag{11}$
故有
$-c_2\Vert g_{k+}\Vert^2\le g_{k+}^T d_{k+1}\le-c_1\Vert g_{k+1}\Vert^2,$
$\forall~\alpha_k\in(0,c_3\frac{\vert g_k^T d_k\vert}{\Vert d_k\Vert^2})\tag{12}$
另一方面，由中值定理及导数的 $~\rm{Lipschitz}~$ 连续性知
$\begin{align}f(x_{k+1})-f(x_k)&=\int_0^1g(x_k+t\alpha_k d_k)^T(\alpha_k d_k)\rm{d}\\ &=\alpha_k g_k^T d_k+\int_0^1[g(x_k+t\alpha_k d_k)-g_k]^T(\alpha_k d_k)\rm{dt}\\ &\le\alpha_k g_k^T d_k+\frac{1}{2}L\alpha_k^2\Vert d_k\Vert^2\end{align}\tag{13}$
于是
$f(x_{k+1})-f(x_k)\le-\rho\alpha_k^2\Vert d_k\Vert^2,~~\forall~\alpha_k\in(0,\frac{2}{L+2\rho}\frac{\vert g_k^T d_k\vert}{\Vert d_k\Vert^2}).\tag{14}$
由 $~(13)~$ 和 $~(14)~$ 知，存在这样的 $~\alpha_k~$ ，使得 $~(4)~$ 和 $~(7)~$ 成立，而且 $~(8)~$ 对
$c=\left\{\tau,c_3,\frac{2}{L+2\rho}\right\}\tag{15}$
成立。由归纳法， $(8)~$ 对所有的 $~k\ge 1~$ 成立。

$\color{red}{证法~ 2：}$ 首先分两种情况： $\alpha_k=\tau\frac{\vert g_k^T d_k\vert}{\Vert d_k\Vert^2}$ 和 $\alpha_k<\tau\frac{\vert g_k^T d_k\vert}{\Vert d_k\Vert^2}$
第一种情况易得
$\alpha_k\ge c\frac{\vert g_k^T d_k\vert}{\Vert d_k\Vert^2}\tag{16}$
现设 $~\alpha_k<\tau\frac{\vert g_k^T d_k\vert}{\Vert d_k\Vert^2}~$ ，因此 $~\frac{\alpha_k}{\lambda}~$ 不满足 $~(4)~$ 和 $~(7)~$ 。首先，假设 $~\frac{\alpha_k}{\lambda}~$ 不满足线搜索条件 $~(4)~$ ，则
$f(x_k+\frac{\alpha_k}{\lambda})>f(x_k)-\rho\alpha_k^2\Vert d_k\Vert^2.\tag{17}$
另一方面，由中值定理及导数的 $~\rm{Lipschitz}~$ 连续性知
$\begin{align}f(x_{k}+\frac{\alpha_k}{\lambda}d_k)-f(x_k)&=f(x_k)+\frac{\alpha_k}{\lambda}g(z_k)^T d_k\\ &=f(x_k)+\frac{\alpha_k}{\lambda}g_k^T d_k+\frac{\alpha_k}{\lambda}(g(z_k)^T d_k-g_k^Td_k)\\ &\le f(x_k)+\frac{\alpha_k}{\lambda} g_k^T d_k+(\frac{\alpha_k}{\lambda})^2L\Vert d_k\Vert^2 \end{align}\tag{18}$
其中 $~z_k=x_k+\lambda_k\frac{\alpha_k}{\lambda}d_k,~\lambda_k\in(0,1)~$ ，由 $~(17)~$ 和 $~(18)~$ 得
$\alpha_k>\frac{\rho}{\rho+L}\frac{\vert g_k^T d_k\vert}{\Vert d_k\Vert^2}.\tag{19}$
另外，假设 $~\frac{\alpha_k}{\lambda}~$ 不满足线搜索条件 $~(7)~$ ，则下面的不等式至少有一个成立
$g(w_k)^T(-g(w_k)+\beta_{k+1}d_k)>-c_1\Vert g(w_k)\Vert^2.\tag{20}$
$g(w_k)^T(-g(w_k)+\beta_{k+1}d_k)<-c_2\Vert g(w_k)\Vert^2.\tag{21}$
其中 $~w_k=x_k+\frac{\alpha_k}{\lambda}d_k~$
由 $~(20)~$ 和 $~\rm{Lipschitz}~$ 得
$\begin{align}-c_1\Vert g(w_k)\Vert^2&<-\Vert g(w_k)\Vert^2+\vert\beta_{k+1}\vert\vert g(w_k)^T d_k\vert\\ &\le-\Vert g(w_k)\Vert^2+\frac{\Vert g(w_k)\Vert\Vert g(w_k)-g_k\Vert}{\Vert g_k\Vert}\vert g(w-k)^T d_k\vert\\ &\le-\Vert g(w_k)\Vert^2+\Vert g(w_k)\Vert^2\frac{\Vert g(w_k)-g_k\Vert}{\Vert g_k\Vert^2}\Vert d_k\Vert\\ &\le -\Vert g(w_k)\Vert^2+\frac{L\frac{\alpha_k}{\lambda}\Vert d_k\Vert^2}{\Vert g_k\Vert^2}\Vert g(w_k)\Vert^2\end{align}\tag{22}$
由 $~(23)~$ 可得
$\alpha_k\ge\frac{\lambda(1-c_1)\Vert g_k\Vert^2}{L\Vert d_k\Vert^2}\tag{23}$
由 $~(21)~$ 和 $~\rm{Lipschitz}~$ 得
$\begin{align}-c_2\Vert g(w_k)\Vert^2&>-\Vert g(w_k)\Vert^2+\vert\beta_{k+1}\vert\vert g(w_k)^T d_k\vert\\ &\ge-\Vert g(w_k)\Vert^2-\frac{\Vert g(w_k)\Vert\Vert g(w_k)-g_k\Vert}{\Vert g_k\Vert}\vert g(w_k)^T d_k\vert\\ &\ge-\Vert g(w_k)\Vert^2-\Vert g(w_k)\Vert^2\frac{\Vert g(w_k)-g_k\Vert}{\Vert g_k\Vert^2}\Vert d_k\Vert\\ &\ge -\Vert g(w_k)\Vert^2-\frac{L\frac{\alpha_k}{\lambda}\Vert d_k\Vert^2}{\Vert g_k\Vert^2}\Vert g(w_k)\Vert^2\end{align}\tag{24}$
由 $~(24)~$ 可得
$\alpha_k\ge\frac{\lambda(c_2-1)\Vert g_k\Vert^2}{L\Vert d_k\Vert^2}\tag{25}$
$\color{red}{其实最开始我们应该按照数学归纳法证明一下，假定下式成立}$
$-c_2\Vert g_k\Vert^2\le g_k^T d_k\le -c_1\Vert g_k\Vert^2\tag{26}$
即有
$\vert g_k^T d_k\vert\le c_2\Vert g_k\Vert^2\tag{27}$
则 $~(23)~$ 进一步有
$\alpha_k\ge \frac{\lambda (1-c_1)\vert g_k^T d_k\vert}{Lc_2\Vert d_k\Vert^2}\tag{28}$
则 $~(25)~$ 进一步有
$\alpha_k\ge \frac{\lambda (c_2-1)\vert g_k^T d_k\vert}{Lc_2\Vert d_k\Vert^2}\tag{29}$
结合 $~(6)~$ ， $~(19)~$ ， $~(28)~$ 和 $~(29)~$ ，我们可令
$c=\min\left\{\tau,\frac{\rho}{\rho + L},\frac{\lambda(1-c_1)}{L c_2},\frac{\lambda(c_2-1)}{L c_2}\right\}\tag{30}$
$\color{red}{从而引理得证}$

利用 $~(4)~$ 和 $~(8)~$ 两式可知，每步的函数值下降量具有量级 $~\frac{(g_k^T d_k)^2}{\Vert d_k\Vert^2}~$ 。因此，当目标函数 $~f(x)~$ 有下界时， $\rm{Zoutendijk}~$ 条件成立。
$\sum_{k\ge 1}\frac{(g_k^T d_k)^2}{\Vert d_k\Vert^2}<\infty\tag{31}$
利用 $~(31)~$ 以及
$\alpha_k\le\tau\frac{\vert g_k^T d_k\vert}{\Vert d_k\Vert^2}\tag{32}$
可以证明原始 $~\rm{PRP}~$ 方法在 $~\rm{Grippo-Lucidi}~$ 的线搜索下全局收敛性，而且为强收敛。

定理 2：设目标函数 $~f(x)~$ 下方有界，导数 $~\rm{Lipschitz}~$ 连续可微。考虑 $~\rm{PRP}~$ 方法 $~(1)-(3)~$ ，其中步长因子 $~\alpha_k~$ 由 $~\rm{Grippo-Lucidi}~$ 的线搜索确定，则方法在下述意义下全局收敛：
$\lim_{k\rightarrow\infty}\Vert g_k\Vert=0\tag{33}$
证明：用直接法：由 $~(2),(3),(7),(32)~$ 和导数的 $~\rm{Lipschitz}~$ 连续性、知
$\begin{align}\Vert d_k\Vert&\le\Vert g_k\Vert+\vert \beta_k^{PRP}\vert\Vert d_{k-1}\Vert\\ &\le\Vert g_k\Vert(1+\frac{\Vert g_k-g_{k-1}\Vert\Vert d_{k-1}\Vert}{\Vert g_{k-1}\Vert^2})\\ &\le\Vert g_k\Vert(1+\frac{L \alpha_{k-1}\Vert d_{k-1}\Vert^2}{\Vert g_{k-1}\Vert^2})\\ &\le\Vert g_k\Vert(1+\frac{\tau L \vert g_{k-1}^T d_{k-1}\vert}{\Vert g_{k-1}\Vert^2})\\ &\le(1+c_2\tau L)\Vert g_k\Vert\end{align}\tag{33}$
于是，利用 $~(7),(31),(33)~$ 知
$\infty>\sum_{k\ge 1}\frac{(g_k^T d_k)^2}{\Vert d_k\Vert^2}\ge c_1^2(1+c_2\tau L)^{-2}\sum_{k\ge 1}\Vert g_k\Vert^2,\tag{34}$
从而 $~(33)~$ 成立。

$(33)$ 表明，由 $~\rm{PRP}~$ 方法产生的点列 $~\left\{x_k\right\}~$ 的任意聚点都是目标函数的稳定点。这一结果比以前获得的收敛性结果都要强。在某种程度上，这一结果的取得归因于当 $~\Vert s_{k-1}\Vert~$ 趋于零时， $~\rm{PRP}~$ 方法给出的方向 $~d_k~$ 靠近于负梯度方向 $~-g_k~$ 。

3、参考文献

$\color{red}{有事，很忙，参考文献以后再写。}$