4、非线性共轭梯度法的研究

上节我们研究了线性共轭梯度法，线性共轭梯度法的研究对象是二次函数，且采取的线搜索为精确线搜索。为此可以产生共轭向量组，具有二次终止性。所谓的二次终止性，并不是迭代两次就终止，而是对于二次函数且采取精确线搜索能够有限步终止。基于二次函数的良好性质，我们将推广到一般函数，采用一般线搜索。实际计算中，发现方法是有效的。便有了非线性共轭梯度法，在不引起混淆的情况下，非线性共轭梯度法也被称为线性共轭梯度法。
对共轭梯度法的研究主要集中在参数 $~\beta_k~$ 的选择，混合共轭梯度法，多项共轭梯度法和谱共轭梯度法等方面。

1、前言

共轭梯度法是无约束优化方法，主要解决如下问题
$\min_{x\mathbb{R}^n}~f(x)\tag{1}$
解决问题 (1)，我们采用是线搜索的迭代方法，即
$x_{k+1}=x_k+\alpha_k d_k\tag{2}$
其中 $~d_k~$ 是搜索方向， $~\alpha_k~$ 是搜索步长，无论是混合共轭梯度法，谱共轭梯度法或者是多项共轭梯度法，只是方向 $~d_k~$ 不同。

2、经典共轭参数 $~\beta_k~$ 的选择

一般地，共轭梯度法的搜索方向为
$d_k=\begin{cases}-g_k,&k=1,\\ -g_k+\beta_k d_{k-1},&k\ge2. \end{cases}$
1952 年，Hestenes 和 stiefel $^{[1]}$ 在线性共轭梯度法中提出
$\beta_k^{HS}=\frac{g_k^T(g_k-g_{k-1})}{d_{k-1}^T(g_k-g_{k-1})}$
1964 年，Fletcher 和 Reeves $^{[2]}$ 首次提出了非线性共轭梯度法
$\beta_k^{FR}=\frac{\Vert g_k\Vert^2}{\Vert g_{k-1}\Vert^2}$
1969 年，Polak , Ribiere $^{[3]}$ 和 Polyak $^{[4]}$ 提出
$\beta_k^{PRP}=\frac{g_k^T(g_k-g_{k-1})}{\Vert g_{k-1}\Vert^2}$
1987 年，Fletcher $^{[5]}$ 提出
$\beta_k^{CD}=\frac{\Vert g_k\Vert^2}{-g_{k-1}^Td_{k-1}}$
1991 年，Liu 和 Storey $^{[6]}$ 提出
$\beta_k^{LS}=\frac{g_k^T(g_k-g_{k-1})}{-g_{k-1}^Td_{k-1}}$
1998 年，戴彧虹和袁亚湘 $^{[7]}$ 提出
$\beta_k^{DY}=\frac{\Vert g_k\Vert^2}{d_{k-1}^T(g_k-g_{k-1})}$
2001年，戴彧虹和 Liao $^{[8]}$ 提出
$\beta_k^{DL}=\frac{g_k^T(g_k-g_{k-1}-ts_{k-1})}{d_{k-1}^T(g_k-g_{k-1})}$
其中 $~t> 0~$ ， $s_{k-1}=x_k-x_{k-1}$ .
2005 年，Hager 和 Zhang $^{[9]}$ 提出
$\beta_k^{HZ}=\frac{g_k^T(y_{k-1}-2d_{k-1}\frac{\Vert y_{k-1}\Vert^2}{d_{k-1}^Ty_{k-1}})}{d_{k-1}^Ty_{k-1}}$
其中 $~y_{k-1}=g_k-g_{k-1}~$

以上是八种经典的共轭梯度法，其收敛性会在后面详细介绍。

3、混合共轭梯度法

为了利用各种基本共轭梯度法的不同优点，许多学者采用了不同共轭梯度法的巧妙组合。

Gilbert 和 Nocedal $^{[10]}$ 为保证算法的收敛性和具有较好的数值表现，取
$\beta_k=\begin{cases} &-\beta_k^{FR},&~若~\beta_k^{PRP}<-\beta_k^{FR}\\ &\beta_k^{PRP},&~若~\vert \beta_k^{PRP}\vert\le\beta_k^{FR}\\ &\beta_k^{FR},&~若~\beta_k^{PRP}>\beta_k^{FR} \end{cases}$
戴雨虹和袁亚湘 $^{[11]}$ 提出了混合 DY 和 CD 共轭梯度法
$\beta_k=\frac{\Vert g_k\Vert^2}{\max \left\{d_{k-1}^T(g_k-g_{k-1}),-g_{k-1}^Td_{k-1} \right\}}$
焦宝聪，陈兰平和潘翠英 $^{[12]}$ 提出混合 DY 和 FR 共轭梯度法
$\beta_k=\begin{cases} &\beta_k^{DY},~&若~g_k^T d_{k-1}\ge \Vert g_{k-1}\Vert^2\\ &\beta_k^{FR},~&否则 \end{cases}$
以上只是列出几种混合梯度法而已，具体他们有什么性质，收敛性的证明，后面会有更加全面的介绍。

4、多项项共轭梯度法

基本的共轭梯度法是负梯度方向与前一搜索方向的组合，许多学者在此基础上，研究了负梯度、前一搜索方向或位移、梯度差的各种形式，得到了多项共轭梯度法。多项共轭梯度法中最主要的形式还是三项共轭梯度法。

2006 年，张丽，周伟军，李董辉 $^{[13]}$ 提出了改进的 PRP 共轭梯度法，得到了如下的三项共轭梯度法
$d_k=\begin{cases} &-g_k,&~k=1,\\ &-g_k+\beta_k^{PRP}d_{k-1}-\frac{g_k^T d_{k-1}}{\Vert g_{k-1}\Vert^2}y_{k-1},&~k\ge 2. \end{cases}$
2011 年，Narushima，Yabe 和 Ford $^{[14]}$ 得到了一般的三项共轭梯度法
$d_k=\begin{cases} &-g_k,&k=1,或~g_k^Tp_k=0,\\ &-g_k+\beta_k d_{k-1}-\beta_k\frac{g_k^T d_{k-1}}{g_k^Tp_k}p_k,&其他情形， \end{cases}$
其中 $~p_k~$ 为任意向量
同年，Andrei $^{[15]}$ 将 PRP 公式改进为
$d_k=-\frac{y_{k-1}^Ts_{k-1}}{\Vert g_{k-1}\Vert^2}+\frac{y_{k-1}^Tg_k}{\Vert g_{k-1}\Vert^2}s_{k-1}-\frac{g_k^Ts_{k-1}}{\Vert g_{k-1}\Vert^2}y_{k-1}$
其中 $~s_{k-1}=x_k-x_{k-1},~y_{k-1}=g_k-g_{k-1}~$ .

5、谱共轭梯度法

谱共轭梯度法是由谱梯度法和共轭梯度法发展而来。谱梯度法又称 BB 算法，最早是由 Barzilai 和 Borwein $^{[16]}$ 于 1988 年为求解无约束优化问题 (1) 提出来的。BB 方法的主要思想是在最小二乘意义下，生成能够逼近目标函数 Hesse 矩阵的逆矩阵，其迭代具有以下形式
$x_{k+1}=x_k-\alpha_k d_k$
其中
$\alpha_k=\frac{(x_k-x_{k-1})^T(x_k-x_{k-1})}{(x_k-x_{k-1})^T(g_k-g_{k-1})}$
BB 方法可以看成是最速下降法的改进，优点是它的数值表现远远好于最速下降法。
2001 年，Birgin 和 Martinez $^{[17]}$ 将谱梯度和共轭梯度相结合，提出了谱共轭梯度法，其搜索方向如下
$d_k=\begin{cases} &-g_k,&~k=1,\\ &-\theta_kg_k+\beta_k d_{k-1},&~k\ge 2,\tag{1} \end{cases}$
其中
$\theta_k=\frac{s_{k-1}^Ts_{k-1}}{s_{k-1}^Ty_{k-1}}$
$\beta_k=\frac{g_k^T(\theta_ky_{k-1}-s_{k-1})}{d_{k-1}^Ty_{k-1}}$
$y_{k-1}=g_k-g_{k-1},~~s_{k-1}=x_k-x_{k-1}$
我们把 (1) 的方法称为谱共轭梯度法，但是上式的谱共轭梯度法不能保证是下降算法。
张丽, 周伟军 $^{[18]}$ 提出一种谱共轭梯度法
$d_k=\begin{cases} &-g_k,&k=1,\\ &-(1+\beta_k\frac{g_k^T d_k}{\Vert g_k\Vert^2})g_k+\beta_k d_{k-1},&k\ge 2, \end{cases}$

6、结束语

$\color{red}{以上的内容只是简单的介绍共轭梯度法，后面将会对共轭梯度法作进一步学习}$ ，

7、参考文献

[1] Hestenes M R, Stiefel E. Method of conjugate geadient for linear equations[J]. Research of the National Bureau of Standards, 1952, 49(6): 409-436
[2] Flecher R, Reeves C. Fuction minimization by conjugate gradient gradients[J]. Computer Journal, 1964 7(2): 149-154.
[3] Polak E, Ribiere G. Note surla convergence de directions conjugate[J]. Rev Fr Inform Rech Oper, 1969, 16(3): 35-43.
[4] Polyak B T. The conjugate gradient method in extreme problems. USSR Comput Math Phys, 1969, 9(1): 94-112.
[5] Fletcher R. Practical methods of optimization, vol I: unconstrained optimization[M]. New York: John Wiley and Sons, 1987.
[6] Liu Y, Storey C. Efficient generalized conjugate gradient algorithms, I. Theory[J]. J Optim Theorey Appl, 1991, 69(1): 129-137.
[7] Dai Y H, Yuan Y X. A nonlinear conjugate gradient method with a strong global convergence property. SIAM J Optim, 1999, 10(1): 177-182.
[8] Dai Y H, Liao L Z. New conjugacy conditions and related nonlinear conjugate gradient methods[J]. Applied Mathematics and Optimization, 2001, 43 : 87-101.
[9] Hager W W, Zhang H C. A new conjugate gradient method with guaranteed descent and an efficient line search, SIAM Journal on Optimization, 2005, 1(16) : 170-192.
[10] Gilbert J C, Nocedal J. Global convergence proerties of conjugate gradient methods for optimization[J]. SIAM Journal on Optimization, 1992, 2, 21-42.
[11] Dai Y H, Yuan Y X. Some properties of a new conjugate gradient methods[J]. Advances in Nonlinear Programming. 1998, 12, 251-262.
[12] 焦宝聪，陈兰平，潘翠英. Goldstein 线搜索下混合共轭梯度法的全局收敛性[J]. 计算数学, 2007,2(29): 137-146.
[13] Zhang L, Zhou W J, LI D H. A descent modified Polak_Ribiere-Polak gradient method and its global convergence[J]. IMA Journal of Numerical Analysis, 2006, 26: 629-640.
[14] Yasushi N, Hiroshi Y, John A F. A three-term conjugate gradient method with sufficient descent property for unconstrined optimization[J]. 2011,
[15] Andrei N. Amodified Polak-Ribiere-Polyak conjugate gradient algorithm for unconstrained optimization. Optimization, 60(12), 1457-1471.
[16] Barzilai J, Borwein M J. Two-point step size gradient methods[J]. IMA Journal of Numerical Analysis. 1988, 1(8): 141-148.
[17] Birgin E G, Martinez J M. A spectural conjugate gradeint method for unconstrained optimization[J]. 2001, 2(42): 117-128.
[18] Zhang L, Zhou W J. Two descent hybrid conjugate gradient methods for optimization[J]. Journal of Computation and Applied Mathematics, 2008, 251-264.