共轭梯度法.ppt

《共轭梯度法.ppt》由会员分享，可在线阅读，更多相关《共轭梯度法.ppt（17页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、问题问题1:如何建立有效的算法？如何建立有效的算法？从二次模型到一般模型从二次模型到一般模型.问题问题2:什么样的算法有效呢？什么样的算法有效呢？二次终止性二次终止性.共轭方向法和共轭梯度法共轭方向法和共轭梯度法(1)(1)最初是由计算数学家最初是由计算数学家HestenesHestenes和几何学家和几何学家StiefelStiefel于于19521952年年 (2)(2)为求正定系数矩阵线性方程组而独立提出的为求正定系数矩阵线性方程组而独立提出的.他们合作的著他们合作的著名文章名文章Method of conjugate gradients for solving Method of co

2、njugate gradients for solving linear systemslinear systems 被认为是共轭梯度法的奠基性文章。被认为是共轭梯度法的奠基性文章。(2)(2)19641964年，年，FletcherFletcher和和ReevesReeves将此方法推广到非线性最优化，将此方法推广到非线性最优化，(3)(3)得到了求解一般函数极小值的共轭梯度法得到了求解一般函数极小值的共轭梯度法.简介简介共轭方向法和共轭梯度法共轭方向法和共轭梯度法(3)(3)共轭梯度法的收敛性分析的早期工作主要由共轭梯度法的收敛性分析的早期工作主要由FletcherFletcher、Pow

3、ellPowell、BealeBeale等学者给出等学者给出.(4)(4)Nocedal、Gilbert、Nazareth、Al-Baali、Storey、Dai、Yuan和和Han等学者在收敛性方面得到了不少新成果等学者在收敛性方面得到了不少新成果.共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算和计算HesseHesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组矩阵并求

4、逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一最有用的方法之一，也是解大型非线性最优化最有效的算法之一.(1)建立在二次模型上，具有二次终止性建立在二次模型上，具有二次终止性(2)一种有效的算法，克服了最速下降法的一种有效的算法，克服了最速下降法的锯齿现象锯齿现象，又避免了牛顿法的计算量大和局部收敛性的缺点又避免了牛顿法的计算量大和局部收敛性的缺点(3)算法简单，易于编程，无需计算二阶导数，存储算法简单，易于编程，无需计算二阶导数，存储 空间小等优点，是求解中等规模优化问题的主要空间小等优点，是求解中等规模优化问题的主要 方法方法特点特点共

5、轭方向法和共轭梯度法共轭方向法和共轭梯度法共轭方向法共轭方向法定义定义-共轭方向共轭方向注：注：若若则则 是正交的，是正交的，因此因此,共轭是正交的推广共轭是正交的推广定义定义-共轭方向法共轭方向法共轭方向法共轭方向法性质性质特例特例n共轭方向法共轭方向法算法步骤算法步骤Step1:Step2:Step3:Step4:Step5:共轭方向法共轭方向法特例特例注注共轭方向法具有二次终止性共轭方向法具有二次终止性共轭梯度法共轭梯度法简介简介 共轭梯度法（共轭梯度法（conjugate gradient method,CG）是以）是以共轭方向（共轭方向（conjugate direction）作为搜

6、索方向的一类算）作为搜索方向的一类算法。法。CG法是由法是由Hesteness和和Stiefel于于1952年为求解线性年为求解线性方程组而提出的。后来用于求解无约束最优化问题，方程组而提出的。后来用于求解无约束最优化问题，它是一种重要的数学优化方法。它是一种重要的数学优化方法。这种方法具有二这种方法具有二次终止性。次终止性。共轭梯度法共轭梯度法基本思想基本思想确定？确定？CG的基本思想是把共轭性与最速下降法相结合，利用已的基本思想是把共轭性与最速下降法相结合，利用已知点处的梯度构造一组共轭方向，并沿着此组方向进行搜索，知点处的梯度构造一组共轭方向，并沿着此组方向进行搜索，求出目标函数的极小点

7、。求出目标函数的极小点。定义定义-共轭梯度法共轭梯度法一一（Hestenes-Stiefel公式）公式）共轭梯度法共轭梯度法共轭梯度法的形式共轭梯度法的形式(A)正定二次函数的无约束最优化问题的共轭梯度法形式正定二次函数的无约束最优化问题的共轭梯度法形式消除消除Qdk结合性质结合性质:共轭梯度法共轭梯度法共轭梯度法的形式共轭梯度法的形式一般最优一般最优化问题的化问题的共轭梯度共轭梯度法形式法形式共轭梯度法共轭梯度法共轭梯度法的形式共轭梯度法的形式(B)一般无约束最优化问题的共轭梯度法形式一般无约束最优化问题的共轭梯度法形式（1969）（1964）（1971）共轭梯度法共轭梯度法注意注意说明说明

8、 根据根据 的上述三种形式，可分别绪出的上述三种形式，可分别绪出FR共轭梯度法、共轭梯度法、DM共轭梯度法和共轭梯度法和PRP共轭梯度法对于目标函数是正定二次函数共轭梯度法对于目标函数是正定二次函数的无约束最优化问题的无约束最优化问题(7.3.3)和最优一维投索，这些方法是完全和最优一维投索，这些方法是完全等价的但是，对于目标函数是非二次函数的无约束最优化问等价的但是，对于目标函数是非二次函数的无约束最优化问题题(7.1.1)，它们所产生的按索方向是不同的，它们所产生的按索方向是不同的 由于由于Rn中共扼方向最多有中共扼方向最多有 n 个，因此在用上述二种方法求个，因此在用上述二种方法求解目标

9、函数为非二次函数的无约束最优化问题解目标函数为非二次函数的无约束最优化问题(7.1.1)时，在时，在 n 步之后构造的搜索方向不再是共轭的，从而降低了收敛速度克步之后构造的搜索方向不再是共轭的，从而降低了收敛速度克服的办法是重设初始点，即把经过服的办法是重设初始点，即把经过 n 次迭代得到的次迭代得到的 xn 作为初始作为初始点重新迭代点重新迭代共轭梯度法共轭梯度法算法步骤算法步骤FRFR共轭梯度法共轭梯度法Step1:Step2:Step3:Step5:Step6:Step4:Step7:共轭梯度法共轭梯度法举例举例参见参见 P187 例例7.3.1.共轭梯度法共轭梯度法收敛性分析收敛性分析与与Newton法相比，共轭梯度法相比，共轭梯度 法具有较弱的收敛条件法具有较弱的收敛条件.注注全局收敛性全局收敛性共轭梯度法共轭梯度法优点优点收敛速度优于最速下降法，存贮量小，计算简单收敛速度优于最速下降法，存贮量小，计算简单.缺点缺点当当 时，收敛速度是线性的时，收敛速度是线性的.收敛速收敛速度不如度不如Newton法快法快.适合于优化变量数目较多的中等规模优化问题适合于优化变量数目较多的中等规模优化问题.