3_共轭梯度法.ppt

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

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

3、(3) 算法简单，易于编程，无需计算二阶导数，存储 空间小等优点，是求解中等规模优化问题的主要 方法,特点,共轭方向法和共轭梯度法,共轭方向法,定义-共轭方向,定义-共轭方向法,共轭方向法,性质,特例,n,共轭方向法,算法步骤,Step1:,Step2:,Step3:,Step4:,Step5:,共轭方向法,特例,注,共轭方向法具有二次终止性,共轭梯度法,简介,共轭梯度法（conjugate gradient method, CG）是以共轭方向（conjugate direction）作为搜索方向的一类算法。CG法是由Hesteness和Stiefel于1952年为求解线性方程组而提出的。后来

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

5、法,注意,说明,根据 的上述三种形式，可分别绪出FR共轭梯度法、DM 共轭梯度法和PRP共轭梯度法对于目标函数是正定二次函数 的无约束最优化问题(7. 3. 3)和最优一维投索，这些方法是完全 等价的但是，对于目标函数是非二次函数的无约束最优化问 题 (7. 1. 1)，它们所产生的按索方向是不同的,由于Rn中共扼方向最多有 n 个，因此在用上述二种方法求 解目标函数为非二次函数的无约束最优化问题(7.1.1)时，在 n 步之后构造的搜索方向不再是共轭的，从而降低了收敛速度克服的办法是重设初始点，即把经过 n 次迭代得到的 xn 作为初始 点重新迭代,共轭梯度法,算法步骤FR共轭梯度法,Step1:,Step2:,Step3:,Step5:,Step6:,Step4:,Step7:,共轭梯度法,举例,参见 P187 例7.3.1.,共轭梯度法,收敛性分析,与Newton法相比，共轭梯度 法具有较弱的收敛条件.,注,全局收敛性,共轭