7、FR 共轭梯度法的一般性理论

前面给出了 FR 共轭梯度法在强 Wolfe 线搜索、推广 Wolfe 线搜素和广义线搜素下的收敛性，本节将给出关于 FR 共轭梯度法的一般性理论，即与其他共轭梯度法的关系，得出一般性的收敛结果。

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~$ 决定不同的共轭梯度法。
1964 年，Fletcher 和 Reeves $^{[1]}$ 首次提出了解决非线性函数的共轭梯度法，我们称为 FR 共轭梯度法，其形式为
$\beta_k=\frac{\Vert g_k\Vert^2}{\Vert g_{k-1}\Vert^2}\tag{4}$
由于不同的 $~\beta_k~$ 决定不同的共轭梯度法，现在我们考虑与 FR 方法相关的一般共轭梯度法，若有
$\vert \beta_k\vert\le\beta_k^{FR}\tag{5}$
1992 年，Gilbert 和 Nocedal $^{[1]}$ 证明了在强 Wolfe 线搜素，即
$f(x_k+\alpha_k d_k)-f(x_k)\le\rho\alpha_k g_k^T d_k$
$\vert g(x_k+\alpha_k d_k)^T d_k\vert\le-\sigma g_k^T d_k$
且 $~0<\rho<\sigma<\frac{1}{2}~$ 时，满足 (5) 关系的 $\beta_k~$ 的共轭梯度法是充分下降并且全局收敛的。戴彧虹 $^{[2]}$ 推广到 $~0<\rho<\sigma\le\frac{1}{2}~$ 时，满足 (5) 关系的 $\beta_k~$ 的共轭梯度法是下降的并且全局收敛的。再后来就是由杜学武和徐成贤 $^{[3]}$ 推广到广义 Wolfe 线搜素，本质是很简单的，我之前也写过，不过后来发现被前人已经写了。在此，我们只是给出文 [2] 中的证明。

2、收敛性证明

定理：设目标函数 $~f(x)~$ 下方有界，导数 Lipschitz 连续。考虑 FR 共轭梯度法 (2)、(3) 和 (4) ，参数 $~\beta_k~$ 满足 (5)。如果 $~\sigma\le\frac{1}{2}~$ ，则方法在下述意义下全局收敛
$\lim\inf\Vert g_k\Vert=0$
证明：将 (3) 式两端与 $~g_k~$ 作内积，并利用 (5) 式得
$\frac{-g_k^T d_k}{\Vert g_k\Vert^2}=1-\frac{\beta_k}{\beta_k^{FR}}\frac{g_k^T d_{k-1}}{\Vert g_{k-1}\Vert^2}$
因为 $~\vert \beta_k\vert\le\beta_k^{FR}~$ ，由强 Wolfe 线搜素知
$1-\sigma\frac{\vert g_{k-1}^T d_{k-1}\vert}{\Vert g_{k-1}\Vert^2}\le\frac{-g_k^T d_k}{\Vert g_k\Vert^2}\le1+\sigma\frac{\vert g_{k-1}^T d_{k-1}\vert}{\Vert g_{k-1}\Vert^2}\tag{6}$
将上式第二个不等式递推，并注意到 $~\frac{-g_1^T d_1}{\Vert g_1\Vert^2}=1~$ ，得知
$\frac{-g_k^T d_k}{\Vert g_k\Vert^2}\le\frac{1-\sigma^k}{1-\sigma}\tag{7}$
对于所有的 $~k\ge 1~$ 成立，利用 (6) 的第一个不等式和 (7) 式以及 $~\sigma\le\frac{1}{2}~$ ，得
$\frac{-g_k^T d_k}{\Vert g_k\Vert^2}\ge\frac{1-2\sigma+\sigma^k}{1-\sigma}>0$
故每一个搜素方向均为下降方向。记
$r_k=\frac{-g_k^T d_k}{\Vert g_k\Vert^2}$
由 (6) 的第一个不等式可知，若 $~r_{k-1}\le\frac{1}{2}~$ ，则 $~r_k\ge 1-\frac{\sigma}{2}\ge \frac{1}{2}~$ ，从而必有
$\max\left\{r_{k-1},r_k\right\}\ge\frac{1}{2}$
由之前的内容可知或者后面会再次谈到这个问题，若 $~\sum_{k\ge 1}r_k^2=\infty~$ ，且 $~g_k^T d_k<0~$ ，则 $~\lim\inf\Vert g_k\Vert=0~$

3、结束语

这节内容很简单，但是却是 FR 共轭梯度法最有用的一节，也经常会用到。而且在此多说一句，如果 定理 1 中的 $~\vert \beta_k\vert\le\beta_k^{FR}~$ 这一界限在常数意义下不可被放宽，否则便会有反列表明算法不收敛。

参考文献
[1] Gilbert J C, Nocedal J. Global convergence properties of conjugate gradient methods for optimization[J]. SIAM, J Optimization, 1992, 2(1) : 21-42.
[2] 戴彧虹. 非线性共轭梯度法[M]. 科学出版社, 2000.
[3] 杜学武, 徐成贤. 由 FR 共轭梯度法控制的两类优化算法的全局收敛性[J]. 高等学校计算数学学报, 2000, 4: 311-318.

7、FR 共轭梯度法的一般性理论

1、简介

2、收敛性证明

3、结束语

推荐阅读更多精彩内容