共轭梯法PPT学习教案

1、会计学1共轭梯法共轭梯法(1)(1)最初是由计算数学家最初是由计算数学家HestenesHestenes和几何学家和几何学家StiefelStiefel于于19521952年年 为求正定系数矩阵线性方程组而独立提出的为求正定系数矩阵线性方程组而独立提出的. .他们合作的著他们合作的著名文章名文章Method of conjugate gradients for solving Method of conjugate gradients for solving linear systemslinear systems 被认为是共轭梯度法的奠基性文章。被认为是共轭梯度法的奠基性文章。 (2)(2)

2、19641964年，年，FletcherFletcher和和ReevesReeves将此方法推广到非线性最优化，将此方法推广到非线性最优化， 得到了求解一般函数极小值的共轭梯度法得到了求解一般函数极小值的共轭梯度法. .简介简介共轭方向法和共轭梯度法共轭方向法和共轭梯度法(3) (3) 共轭梯度法的收敛性分析的早期工作主要由共轭梯度法的收敛性分析的早期工作主要由FletcherFletcher、 PowellPowell、BealeBeale等学者给出等学者给出. . (4) (4) Nocedal、Gilbert、Nazareth、Al-Baali、Storey、 Dai、Yuan和和Han

3、等学者在收敛性方面得到了不少新成果等学者在收敛性方面得到了不少新成果.共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算储和计算HesseHesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一. .第1页/共17页(1

4、) 建立在二次模型上，具有二次终止性建立在二次模型上，具有二次终止性(2) 一种有效的算法，克服了最速下降法的一种有效的算法，克服了最速下降法的锯齿现象锯齿现象， 又避免了牛顿法的计算量大和局部收敛性的缺点又避免了牛顿法的计算量大和局部收敛性的缺点(3) 算法简单，易于编程，无需计算二阶导数，存储算法简单，易于编程，无需计算二阶导数，存储 空间小等优点，是求解中等规模优化问题的主要空间小等优点，是求解中等规模优化问题的主要 方法方法特点特点共轭方向法和共轭梯度法共轭方向法和共轭梯度法第2页/共17页共轭方向法共轭方向法定义定义-共轭方向共轭方向注：注：若若,IG 则则 是正交的，是正交的，因此

5、因此, 共轭是正交的推广共轭是正交的推广定义定义-共轭方向法共轭方向法第3页/共17页共轭方向法共轭方向法性质性质特例特例n第4页/共17页共轭方向法共轭方向法算法步骤算法步骤Step1:Step2:Step3:Step4:Step5:第5页/共17页共轭方向法共轭方向法特例特例注注共轭方向法具有二次终止性共轭方向法具有二次终止性第6页/共17页共轭梯度法共轭梯度法简介简介 共轭梯度法（共轭梯度法（conjugate gradient method, CG）是）是以共轭方向（以共轭方向（conjugate direction）作为搜索方向的一）作为搜索方向的一类算法。类算法。CG法是由法是由H

6、esteness和和Stiefel于于1952年为求解年为求解线性方程组而提出的。后来用于求解无约束最优化问线性方程组而提出的。后来用于求解无约束最优化问题，它是一种重要的数学优化方法。题，它是一种重要的数学优化方法。这种方法具有二这种方法具有二次终止性。次终止性。第7页/共17页共轭梯度法共轭梯度法基本思想基本思想. 1,.,2 , 1,)(11 nkdxfdkkkk 确定确定？ CG的基本思想是把共轭性与最速下降法相结合，利用已的基本思想是把共轭性与最速下降法相结合，利用已知点处的梯度构造一组共轭方向，并沿着此组方向进行搜索知点处的梯度构造一组共轭方向，并沿着此组方向进行搜索，求出目标函数

7、的极小点。，求出目标函数的极小点。定义定义-共轭梯度法共轭梯度法一一第8页/共17页（Hestenes-Stiefel公式）公式）共轭梯度法共轭梯度法共轭梯度法的形式共轭梯度法的形式(A) 正定二次函数的无约束最优化问题的共轭梯度法形式正定二次函数的无约束最优化问题的共轭梯度法形式消除消除Qdk结合性质结合性质:第9页/共17页共轭梯度法共轭梯度法共轭梯度法的形式共轭梯度法的形式一般最优一般最优化问题的化问题的共轭梯度共轭梯度法形式法形式第10页/共17页共轭梯度法共轭梯度法共轭梯度法的形式共轭梯度法的形式(B) 一般无约束最优化问题的共轭梯度法形式一般无约束最优化问题的共轭梯度法形式（196

8、9）（1964）（1971）第11页/共17页共轭梯度法共轭梯度法注意注意说明说明 根据根据 的上述三种形式，可分别绪出的上述三种形式，可分别绪出FR共轭梯度法、共轭梯度法、DM共轭梯度法和共轭梯度法和PRP共轭梯度法对于目标函数是正定二次函数共轭梯度法对于目标函数是正定二次函数的无约束最优化问题的无约束最优化问题(7. 3. 3)和最优一维投索，这些方法是完全和最优一维投索，这些方法是完全等价的但是，对于目标函数是非二次函数的无约束最优化问等价的但是，对于目标函数是非二次函数的无约束最优化问题题 (7. 1. 1)，它们所产生的按索方向是不同的，它们所产生的按索方向是不同的k 由于由于Rn中

9、共扼方向最多有中共扼方向最多有 n 个，因此在用上述二种方法求个，因此在用上述二种方法求解目标函数为非二次函数的无约束最优化问题解目标函数为非二次函数的无约束最优化问题(7.1.1)时，在时，在 n 步之后构造的搜索方向不再是共轭的，从而降低了收敛速度克步之后构造的搜索方向不再是共轭的，从而降低了收敛速度克服的办法是重设初始点，即把经过服的办法是重设初始点，即把经过 n 次迭代得到的次迭代得到的 xn 作为初始作为初始点重新迭代点重新迭代第12页/共17页共轭梯度法共轭梯度法算法步骤算法步骤FRFR共轭梯度法共轭梯度法Step1: Step2:Step3:Step5:Step6:Step4:Step7:第13页/共17页共轭梯度法共轭梯度法举例举例参见参见 P187 例例7.3.1.第14页/共17页共轭梯度法共轭梯度法收敛性分析收敛性分析与与Newton法相比，共轭梯度法相比，共轭梯度 法具有较弱的收敛条件法具有较弱的收敛条件.注注全局收敛性全局收敛性第15页/共17页共轭梯度法共轭梯度法优点优点收敛速度优于最速