_共轭梯度法.ppt

问题1: 如何建立有效的算法？ 从二次模型到一般模型. 问题2: 什么样的算法有效呢？ 二次终止性. 共轭方向法和共轭梯度法 最初是由计算数学家Hestenes和几何学家Stiefel于1952年 为求正定系数矩阵线性方程组而独立提出的.他们合作的著名文章Method of conjugate gradients for solving linear systems 被认为是共轭梯度法的奠基性文章。 1964年，Fletcher和Reeves将此方法推广到非线性最优化， 得到了求解一般函数极小值的共轭梯度法. 简介 共轭方向法和共轭梯度法 (3) 共轭梯度法的收敛性分析的早期工作主要由Fletcher、 Powell、Beale等学者给出. (4) Nocedal、Gilbert、Nazareth、Al-Baali、Storey、 Dai、Yuan和Han等学者在收敛性方面得到了不少新成果. 共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一. (1) 建立在二次模型上，具有二次终止性． (2) 一种有效的算法，克服了最速下降法的锯齿现象， 又避免了牛顿法的计算量大和局部收敛性的缺点． (3) 算法简单，易于编程，无需计算二阶导数，存储 空间小等优点，是求解中等规模优化问题的主要 方法． 特点 共轭方向法和共轭梯度法 共轭方向法 定义--共轭方向 注： 若 则 是正交的， 因此, 共轭是正交的推广． 定义--共轭方向法 共轭方向法 性质 特例 n 共轭方向法 算法步骤 Step1: Step2: Step3: Step4: Step5: 共轭方向法 特例 注 共轭方向法具有二次终止性 共轭梯度法 简介 共轭梯度法（conjugate gradient method, CG）是以共轭方向（conjugate direction）作为搜索方向的一类算法。CG法是由Hesteness和Stiefel于1952年为求解线性方程组而提出的。后来用于求解无约束最优化问题，它是一种重要的数学优化方法。这种方法具有二 次终止性。 共轭梯度法 基本思想 确定？ CG的基本思想是把共轭性与最速下降法相结合，利用已知点处的梯度构造一组共轭方向，并沿着此组方向进行搜索，求出目标函数的极小点。 定义--共轭梯度法 一 （Hestenes-Stiefel公式） 共轭梯度法 共轭梯度法的形式 (A) 正定二次函数的无约束最优化问题的共轭梯度法形式 消除Qdk 结合性质: 共轭梯度法 共轭梯度法的形式 一般最优 化问题的共轭梯度法形式 共轭梯度法 共轭梯度法的形式 (B) 一般无约束最优化问题的共轭梯度法形式 （1969） （1964） （1971） 共轭梯度法 注意 说明 根据 的上述三种形式，可分别绪出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法相比，共轭梯度 法具有较弱的收敛条件. 注 全局收敛性 共轭梯度法 优点 收敛速度优于最速下降法，存贮量小，计算简单. 缺点 当 时，收敛速度是线性的. 收敛速度不如Newton法快. 适合于优化变量数目较多的中等规模优化问题.