共轭梯度法

共轭梯度法（Conjugate Gradient Method）^[1]是选择一组相互共轭的下降方向作为迭代方向进行迭代的方法^[6]，是解决大规模无约束优化问题的有效方法之一^[7]，它不用求矩阵的逆，存储量很小，对初始点的要求也不高，收敛速度较快，介于最速下降法与Newton法之间，特别适合求解高维优化问题^[8]。

1952年，数学家马格努斯·赫斯滕斯（Magnus Hestenes）和爱德华·斯蒂费尔（Eduard Stiefel）^[1]为了求解正定系数矩阵的线性方程组，首次提出了共轭梯度法，并将其应用于求解线性系统^[9]。随后，在1964年，费雷歇（Fletcher）和里夫斯（Reeves）首次将共轭梯度法应用于求解非线性最优化问题，提出FR共轭梯度法，这一扩展使得共轭梯度法成为解决大型非线性最优化问题的有效算法之一^[10]。随着计算机技术的快速发展，共轭梯度法的研究内容及其方式日益丰富，PRP共轭梯度法^[11][12]、CD共轭梯度法^[13]、DY共轭梯度法^[14]、混合共轭梯度法、记忆梯度法、谱共轭梯度法、参数共轭梯度法^[15]接连被学者提出，不断优化了数值实验效果。

共轭梯度法具有下降性^[16]、二次终止性^[5]和收敛性^[17][18][19]的性质，基于共轭梯度法的特殊性质，可广泛应用于线性方程组和非线性方程组最优化问题当中^[10][9]，除此之外，共轭梯度法还广泛应用于物理学、电信技术、矿业工程^{[3][4][20][21]}等各种领域。

共扼方向法是介于最速下降法与牛顿法之间的一个方法。它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了存贮和计算牛顿法所需要的二阶导数信息。共轭方向法是从研究二次函数的极小化产生的，但是它可以推广到处理非二次函数的极小化问题，最典型的共轭方向法是共扼梯度法^[22]。

为更好地讨论共轭梯度法这一算法，这里我们先来引入共轭方向的概念，设是对称正定矩阵，若中的两个方向和满足，则称这两个方向关于A共轭，或称它们关于A正交；若是中个方向，它们两两关于共轭，即满足则称这组方向是共轭的，或称它们为的个共轭方向^[2]。

讨论对于两个方向关于矩阵共轭的几何意义，以正定二次函数为例，设有二次函数，其中是对称正定矩阵，是一个定点，函数的等值面是以为中心的椭球面，由于，正定，因此是的极小点^[2]。

又设是在某个等值面上的一点，该等值面在点处的法向量，设是这个等值面在处的一个切向量，记作。自然，与正交，即，因此有，即等值面上一点处的切向量与由这一点指向极小点的向量关于共轭（如摘要图所示）。由此可知，极小化所定义的二次函数，若依次沿着和进行一维搜索，则经两次迭次必达到极小点^[2]。

共轭梯度法是最著名的共轭方向法^[23]，它的基本思想就是把共轭性与最速下降法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向进行搜索，求出目标函数的极小点^[2]。

讨论对于二次凸函数的共轭梯度法，考虑问题，其中，是对称正定矩阵，是常数。首先任意给定一个初始点，计算出目标函数在这点的梯度，在这里，我们用表示函数在处的梯度，即。若，则停止计算，否则，令，沿方向搜索，得到点，计算在处的梯度，若，则利用和构造第2个搜索方向，再沿搜索^[2]。

若已知点和搜索方向，则从出发，沿进行搜索，得到，其中步长满足，此时可求出的显示表达，令，求的极小点，令（1），根据二次函数的梯度的表达式，得（1）式为

，

，

，

得到，计算在处的梯度。若，则停止计算；否则，用和构造下一个搜索方向，并使和关于共轭，按此设想，令式两端左乘，并令，由此得到。^[2]

再从出发，沿方向搜索，重复上述操作^[2]。

最优化方法也称作运筹学方法，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化起源于二战期间，主要用于各国对导弹、雷达等武器的精确控制问题。在最优化方法的研究中，很多的问题都能描述成无约束优化问题，而在求解无优化问题过程中有一种方法叫做共轭梯度法^[24]。

20世纪中叶电子计算机的出现刺激了开发数值算法的一系列活动，这些算法可以应用于比过去更难解决的计算问题，特别是用于解决线性系统和矩阵特征值问题的算法。几乎所有应用领域都会出现此类问题，例如流体流动建模、油藏工程、机械工程、半导体器件分析、核反应模型和电路仿真。这些矩阵可能很大，有数百万个未知量需要确定^[9]。为了求解正定系数矩阵的高维线性方程组问题，NBS数值分析研究所的马格努斯·赫斯滕斯和来自苏黎世联邦理工学院的访客爱德华·斯蒂费尔成功地开发了一种新的迭代算法，即共轭梯度法，也称HS共轭梯度法，其参数形式为^[25]，其中^[1][9]。

20世纪60年代，费雷歇等人首次将共轭梯度法应用于求解非线性最优化问题，提出了FR共轭梯度法，被称为非线性共轭梯度方法的开端^[10]，其参数形式为^[25]。

为使算法具有良好的收敛性质又能够达到良好的数值实验效果，1969年，波拉克（Polak），里比埃（Ribiere）^[11]和波莉娅（Polyak）^[12]提出了新参数βk的共轭梯度法，被称为PRP共轭梯度法；1987年，费雷歇提出CD共轭梯度法，并证明此方法具有在强Wolfe线搜索^[26]条件下不需要任何限制参数，即可产生下降搜索方向并且方法是全局收敛等优点^[13]；戴玉红和袁亚湘在1999年给出了一个新选择的βk的共轭梯度法，称为DY共轭梯度法，并证明了算法的收敛性^[14]，同年，IEEE计算机学会和美国物理研究所的出版物《科学与工程中的计算》将克雷洛夫子空间迭代评为本世纪十大算法之一^[27]，特别引用了马格努斯·赫斯滕斯和爱德华·斯蒂费尔以及另一位NBS/INA研究员科尔内留斯·兰措什（Cornelius Lanczos）的开创性工作^[9]。

近年来无数专家学者推广了前人对共轭梯度法的研究，不断对参数βk进行修正，又或者直接提出了新的βk，不断优化数值实验效果，出现了混合共轭梯度法、记忆梯度法、谱共轭梯度法、参数共轭梯度法^[15]等新的研究方向的成就。现在共轭梯度法已经广泛地应用于实际问题中^{[3][4][20][21]}。

设具有连续的一阶偏导数，并假设一维搜索是精确^[26]的，考虑用共轭梯度法求解无约束问题，若，则搜索方向是处的下降方向^[16]。

共轭梯度法的基本思想是把共轭性与最速下降方法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向进行搜索，求出目标函数的极小值。根据共轭方向的基本性质，这种方法具有二次终止性^[5]。

例：用FR法求解下列问题：。取初始点^[28]。

解：在点处，目标函数的梯度是，第1次迭代，令，从出发，沿方向作一维搜索，得，^[28]。

第2次迭代，在点处，目标函数的梯度，构造搜索方向，先计算因子：，令，从出发，沿方向作一维搜索，得，^[28]。

显然点处目标函数的梯度，已达到极小点，验证了共轭梯度法的二次终止性^[28]。

假如设是上连续可微实函数，PRP算法产生的序列，又设在点处，目标函数的梯度，则有（相关证明过程请查阅相关文献资料）^[17]。又假如是上的二次连续可微凸函数，对任意点，存在正数和，使得当，和时，有，取初始点和因子均由PRP方法确定，则，其中，在此条件上，当任取初始点时，有水平集为紧集，则PRP方法是严格下降算法，即当处的梯度时，必有并且算法产生的序列或终止于或收敛于函数在上的惟一极小点^[17]。

假定在有界水平集上连续可微，那么采用公式和精确线性搜索^[26]FR共轭梯度法产生的序列至少有一个聚点是驻点，即：

（1）当是有穷点列时，其最后一个点是的驻点。

（2）当是无穷点列时，它必有极限点，且其任一极限点是的驻点^[18]。

假定水平集是有界集，是Lipschitz连续，则采用精确线搜索准则^[26]的Crowder Wolfe再开始共轭梯度法产生的点列至少有一个聚点存在，且是驻点^[19]。

最早的线性共轭梯度法是由数学家马格努斯·赫斯滕斯和爱德华·斯蒂费尔在考虑求解线性方程组时分别独立提出，其中^[1][29]。

当对称正定时，求解，等于求解下面的二次优化问题。因此，线性共轭梯度法也可以看成是求二次函数极小值的共轭梯度法，下面为线性共轭梯度法的一般迭代格式^[29]。

步1：选取初始点，令。

步2：如果，则终止，否则，转步3。

步3：利用精确线搜索【满足】^[26]，计算步长因子，即

步4：更新迭代点，计算参数。

步5：令，转步2^[29]。

1964年，费雷歇等人首次将共轭梯度法应用于求解非线性最优化问题，提出了FR共轭梯度法，被称为非线性共轭梯度方法的开端^[10]，下面是六种常用的非线性共轭梯度法。

FR方法最早是由费雷歇和里夫斯在1964年率先提出来的^[10]，具有良好的收敛性和数值表现不佳等特点^[13]。使用FR方法时，公式计算因子为^[25]。

（1）对于二次凸函数，FR法的计算步骤如下：^[30]

步1：给定初始点，置;步2：计算，若，则停止计算，得点；否则，进行下一步;步3：构造搜索方向，令，其中，当时，，当时，按，计算因子;步4：令，其中按式计算步长;步5：若，则停止计算，得点；否则，置，返回步2^[30]。

（2）对于一般函数，FR法的计算步骤如下：^[31]

步1：给定初始点，允许误差，置;步2：若，则停止计算，否则，作一维搜索，求，满足，;

步3：如果，则进行步4；否则，进行步5;步4：令，其中，置，转步2;步5：令，置，转步2^[31]。

PRP方法是由波拉克，里比埃和波莉娅在1969年提出来的^[11][12]。该方法的优点是数值表现很好，主要原因是在实际操作中PRP方法一旦产生小步长，可以有效地避免连续产生小步长，这是因为其搜索方向可以主动地靠近负梯度方向，只是缺点在于理论收敛性质非常的一般^[13]。

使用PRP方法时，公式计算因子为^[25]。

HS方法最早是由数学家马格努斯·赫斯滕斯和爱德华·斯蒂费尔在1952年率先提出来的^[1]，在收敛性和数值表现上类似于上面提到的PRP方法。若选取的搜索方向是精确的线搜索^[26]时，当时，有^[13]。

使用HS方法时，公式计算因子为^[25]。

CD方法是由费雷歇于1987年提出。在精确线搜索^[26]的基础上，此方法也同样类似于上面提到的FR方法。那么，此方法具有在强Wolfe线搜索^[26]条件下不需要任何限制参数，即可产生下降搜索方向并且方法是全局收敛等优点。所以，CD方法在标准的Wolfe线搜索下也能得到很好的收敛结果，不必使用强Wolfe非精确线搜索^[13]。

使用CD方法时，公式计算因子为^[25]。

1999年，戴玉红和袁亚湘提出了一个新选择的βk的共轭梯度法，并证明了算法的收敛性，这个方法被称为DY共轭梯度法^[14]，此方法类似于方法，在不使用任何线搜索下，戴玉红证明了当DY方法中的点列远离最优点时，对大部分的迭代点列都满足充分下降条件，由此在一般线搜索下，可证明DY方法的全局收敛性，而在2000年戴玉红和袁亚湘证明了在Wolfe线性搜索下，每一步搜索方向均产生一个下降方向，DY方法具有全局收敛性^[13]。

使用DY方法时，公式计算因子为^[25]。

混合共轭梯度法，也被称为杂交共轭梯度法，是利用每种方法优点，以其得到一个具有全局收敛性并且好的数值表现的算法。在上述介绍的六种共轭梯度法中，FR和CD方法具有收敛速度快但数值表现不佳的特点，PRP和HS方法具有数值表现快但是收敛速度不佳的特点，基于上述的考虑，研究者设计了一种混合共轭梯度法，其方法具有两者的优点，同时又摒弃了它们的缺点^[15]。

最早的混合共轭梯度法由图阿蒂·艾哈迈德（Touati-Ahmed）和斯托里（Storey）在1990年提出来的，主要时将FR方法和PRP方法混合，公式如下，上式能够有效的防止PRP方法产生连续小步长的问题^[15]。

1969年米勒（Miele）和坎特雷尔（Cantrell）首次提出记忆梯度法^[32]，该方法是在共轭梯度法的基础上，这种算法能有效解决大规模病态优化问题，主要原因是在操作中，无需计算二阶导数，计算公式简单，并且算法本身具有较好的全局收敛性等优点，使其有效地避免存贮和计算矩阵，但其缺点是除利用当前的迭代信息外，所设计的算法在每一次进行迭代时，依旧要用到前面若干点的迭代信息，这就导致记忆步数越多。在实际解决问题时，一般的迭代公式只要在很复杂的情况下，记忆二步到三步是比较恰当的，根据搜索方向的不同，记忆梯度法大致分为两类：一类是由上一个迭代点的搜索方向和目前迭代点的负梯度方向线性组合而成的搜索方向。具体公式，如下，^[15]。

另一类是由上一迭代点的负梯度方向和目前迭代点的负梯度方向线性组合而成搜索方向，具体公式如下，，基于记忆梯度方法的优势，自从记忆梯度法产生以来，许多学者们也对其进行研究，也产生了一些好的结果^[15]。

最早谱梯度法称为两点步长梯度法，而这个梯度法是由巴尔齐莱（Barzilai）和博温（Borwein）提出的，其基本思想是：用当前迭代点的信息来提取步长因子，随后，伯金（Bergin）和马丁内斯（Martinez）在2001年结合谱梯度方法和共轭梯度法，给出了一类谱共轭梯度法，其优点主要表现在算法简单和存储需求小，至此，谱共轭梯度算法大量应用于求解无约束最优化问题中。其迭代格式为：，，其中为搜索方向，为搜索步长因子，为谱系数，为共轭系数，它们分别表示为，，其中，^[15]。

若且有某种共轭梯度法决定的共轭参数，则得到了共轭梯度法，谱共轭梯度法基本思想是选取不同的和，构成不同的谱共轭梯度算法。近十年来，也被越来越多的学者研究，大量的数值实验表明，谱共轭梯度法比传统的共轭梯度法要更有效，除此之外，此方法也可以用到训练神经网络。但是，谱共轭梯度法不能保证对于所有的，其搜索方向总是下降的，因此在设计谱共轭梯度方法时，研究者应该优先保证迭代方向的下降性^[15]。

在共轭梯度法中适当选择参数，在参数中加入适当的变量，使其具有最佳的收敛性和数值表现，这种参数共轭梯度法主要的公式如下^[15]。

戴玉红和袁亚湘的单参数共轭梯度法簇：，其中^[15]。

拿撒勒（Nazarethm）也提出了双参数共轭梯度法簇：，其中^[15]。

戴玉红和袁亚湘也提出来了三参数共轭梯度法簇：，其中参数，^[15]。

对于正定二次函数，共轭方向法至多经步精确线搜索^[26]终止；且每一都是在和方向所长成的线性流形中的极小点^[33]。

设有函数，其中是阶对称正定矩阵，是共轭的非零向量，以任意的为初始点，依次沿进行一维搜索，得到点，则是函数在线性流形上的惟一极小点。特别地，当时，是函数在上的惟一极小点。其中是生成的子空间。在此基础上，必有^[34]。

共轭梯度法的优点是不用求矩阵的逆，存储量很小，对初始点的要求也不高，收敛速度较快，介于最速下降法与Newton法之间，特别适合求解高维优化问题；缺点是其收敛性强烈依赖于精确的一维搜索，为此需要付出很大代价^[8]。

利用光学层析技术重建温度场是测量复杂流场领域的难点问题，温国庆在研究现有重建方法及其适用性的基础上探讨了光学层析重建温度场时投影数据的转化以及由共轭梯度法求解投影方程组实现温度场的重建，用数值模拟考察该方法对单峰对称温度分布的重建效果，重建结果表明这是一种有效的方法，可以用于重建整个温度场分布，相比传统的测温方法有很大的改善^[3]。

压缩感知的重建过程就是求解最优解的过程，针对目前压缩感知重建常用的共轭梯度法重建的缺陷——只能搜索到局部最优解，在此基础上，高明生提出了新的结合全局最优化算法与局部最优化算法。经过研究，结果表明，新算法的重建效果优于共轭梯度算法重建^[4]。

王静等学者为讨论信号恢复问题，用三项共轭梯度法对模型进行求解，证明了水平集的有界性，函数梯度的Lipschitz连续性，得到了算法的全局收敛性。进行了数值实验，数值实验结果表明本文方法的有效性^[20]。

陆上地震资料由于低频信息缺失、波场复杂等问题，加剧了反演的非线性。王立德^[21]等学者基于改进共轭梯度法的时间域多尺度分层反演方法有效重建了纵、横波速度场，有效降低陆上实际资料带来的非线性影响^[21]。

在4个频带共80次的迭代过程中，改进CG反演的速度误差曲线均位于传统方法误差曲线下方，误差曲线下降更快，说明优化后反演的速度场精度更高，收敛更快，通过更少的迭代次数即可达到传统CG反演的精度^[21]。