3 共轭梯度法.ppt

《3 共轭梯度法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、问题1:如何建立有效的算法？从二次模型到一般模型.问题2:什么样的算法有效呢？二次终止性.共轭方向法和共轭梯度法最初是由计算数学家Hestenes和几何学家Stiefel于1952年为求正定系数矩阵线性方程组而独立提出的.他们合作的著名文章Methodofconjugategradientsforsolvinglinearsystems被认为是共轭梯度法的奠基性文章。1964年，Fletcher和Reeves将此方法推广到非线性最优化，得到了求解一般函数极小值的共轭梯度法.简介共轭方向法和共轭梯度法(3)共轭梯度法的收敛性分析的早期工作主要由Fle

2、tcher、Powell、Beale等学者给出.(4)Nocedal、Gilbert、Nazareth、Al-Baali、Storey、Dai、Yuan和Han等学者在收敛性方面得到了不少新成果.共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一.(1)建立在二次模型上，具有二次终止性．(2)一种有效的算法，克服了最速下降法的锯齿现象，又避免了牛顿法

3、的计算量大和局部收敛性的缺点．(3)算法简单，易于编程，无需计算二阶导数，存储空间小等优点，是求解中等规模优化问题的主要方法．特点共轭方向法和共轭梯度法共轭方向法定义--共轭方向注：若则是正交的，因此,共轭是正交的推广．定义--共轭方向法共轭方向法性质特例n共轭方向法算法步骤Step1:Step2:Step3:Step4:Step5:共轭方向法特例注共轭方向法具有二次终止性共轭梯度法简介共轭梯度法（conjugategradientmethod,CG）是以共轭方向（conjugatedirection）作为搜索方向的一类算法。CG法是由Hesten

4、ess和Stiefel于1952年为求解线性方程组而提出的。后来用于求解无约束最优化问题，它是一种重要的数学优化方法。这种方法具有二次终止性。共轭梯度法基本思想确定？CG的基本思想是把共轭性与最速下降法相结合，利用已知点处的梯度构造一组共轭方向，并沿着此组方向进行搜索，求出目标函数的极小点。定义--共轭梯度法一（Hestenes-Stiefel公式）共轭梯度法共轭梯度法的形式(A)正定二次函数的无约束最优化问题的共轭梯度法形式消除Qdk结合性质:共轭梯度法共轭梯度法的形式一般最优化问题的共轭梯度法形式共轭梯度法共轭梯度法的形式(B)一般无约束最优化

5、问题的共轭梯度法形式（1969）（1964）（1971）共轭梯度法注意说明根据的上述三种形式，可分别绪出FR共轭梯度法、DM共轭梯度法和PRP共轭梯度法．对于目标函数是正定二次函数的无约束最优化问题(7.3.3)和最优一维投索，这些方法是完全等价的．但是，对于目标函数是非二次函数的无约束最优化问题(7.1.1)，它们所产生的按索方向是不同的．由于Rn中共扼方向最多有n个，因此在用上述二种方法求解目标函数为非二次函数的无约束最优化问题(7.1.1)时，在n步之后构造的搜索方向不再是共轭的，从而降低了收敛速度克服的办法是重设初始点，即把经过n次迭代得到

6、的xn作为初始点重新迭代．共轭梯度法算法步骤—FR共轭梯度法Step1:Step2:Step3:Step5:Step6:Step4:Step7:共轭梯度法举例参见P187例7.3.1.共轭梯度法收敛性分析与Newton法相比，共轭梯度法具有较弱的收敛条件.注全局收敛性共轭梯度法优点收敛速度优于最速下降法，存贮量小，计算简单.缺点当时，收敛速度是线性的.收敛速度不如Newton法快.适合于优化变量数目较多的中等规模优化问题.