文档介绍：共轭梯度法是介于最速下降法与牛顿法之间的一个方法。它仅需要利用一阶导数信息,但克服了最速下降法收敛慢的缺点,又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点。共轭梯度法不仅是解决大型线性方程组最有用的发发之一,也是解大型非线性最优化问题最有效的算法之一。
共轭梯度法最早是由计算数学家Hestenes 和几何学家Stiefel 在20世纪50年代初为求解线性方程组而各自独立提出的。他们合作的文章被公认为共轭梯度法的奠基之作。该文详细讨论了求解线性方程组的共轭梯度法的性质以及它和其他方法的关系。在A为对称正定阵时,上述线性方程组等价于最优化问题。由此,Hestenes和Stiefel的方法也可视为求二次函数。
提到最优化问题,这里首先介绍最速下降法。考虑线性方程组的求解问题,其中A是给定的n阶对称正定矩阵,b是给定的n维向量。为此我们定义二次泛函
对最速下降法做一简单分析就会发现,负梯度方向虽从局部来看是最佳的下山方向,但从整体来看并非最佳。这就促使人们去寻求更好的下山方向,当然,我们自然希望每步确定新的下山方向付出的代价不要太大。共轭梯度法就是根据这一意思设计的,其具体计算过程如下:
给定初始向量,第一步仍选负梯度方向为下山方向,即= ,于是有,,对以后各步,例如,第k+1步(),下山方向就不再取,而是在过点由向量和所张成的二维平面内找出使函数下降最快的方向作为新的下山方向。考虑在上的限制:
直接计算可得:
其中最后一式用到了,这可由的定义直接验证。
令==0,即知在内有唯一的极小点,其中和满足方程组(1)
0 (2)
上式蕴含着必有0,因此我们可取作为新的下山方向。显然,这是在平面内可得到的最佳下山方向,令,则由(2)式得到。
这样确定的满足=0,即所谓的与是相互共轭的。
确定以后的确定仍用公式=,然后计算。总结上述讨论,可得如下计算公式:=
在实际计算中,常将上述公式进一步简化,从而得到一个形式上更为简单而且对称的计算公式。首先来简化的计算公式:
==(3)
因为在计算时已经求出,所以,计算时可以不必将代入方程去计算,而是由(3)得到。
再来简化和的计算公式。我们需要用到下面的关系式:
,k=1,2,…(4)
这些关系式的证明包含在方程组(1)(2)的证明中。由(3)(4)导出,。
由此可得:,
最优化方法的收敛性是算法研究领域的基本问题。一种算法是否具备应用价值,取决于是否具备局部或全局收敛性,以及收敛速度的快慢。共轭梯度法不同的方向修正公式,以及采用何种线搜索策略来确定步长,都取决于它的收敛性质。下面重点简述两个共轭梯度法收敛性的成果。
:
早期对FR方法的收敛性研究是建立在精确线搜索基础上的。Powell在精确线搜索下,得到FR方法的一个很不利的性质,即:如果FR方法在某一步产生一个很小的步长,则相继的许多步长也可能非常小。同时,Powell还给出了FR方法最简单的全局有效性分析。这些分析解释了为什么FR方法在数值表现上并不十分满意。尽管FR方法可能收敛速度很慢,Zoutendijk证明了采取精确线搜索的FR方法对一般非凸函数总是收敛的。
在实际计算中,人们通常采用非精确线搜索,而不是使用精确线搜索。