变度量法.ppt

* * 本质上是是将最速下降法与Newton法的优点结合起来，也称修正Newton法或拟Newton法或变尺度法. 变度量法 简介 (1) 变尺度法是1959年由Davidon、Fletcher和Powell提出的. (2) Broyden、Goldstein、Shanno 等人于1970年进一步改进 . 牛顿法每次都计算 1959年,Davidon提出设想仅用每次迭代中得到的梯 度信息来近似 Gk，基于此导致了一类非常成功的 方法----变度量法. 本节介绍Broyden族拟牛顿法： DFP算法和BFGS算法． 变度量法 基本思想 计算量大； 当Gk非正定时, 不能保证所求方向为下降方向. 当Gk奇异时，步长可能变成无界 . 最速下降法和阻尼牛顿法的迭代公式可统一为： 变度量法 基本原理 思考 能否构造近似于 的Gk 使之不需要计算Hesse矩阵及其拟矩阵，并能使相应的算法保持 Newton法的收敛速度快的优点，同时计算较简单? 构造矩阵列 满足： 变度量法 基本思路 C1： 是对称正定阵． 由 产生: C2： 其中 C3： 满足拟牛顿方程： 其中 拟Newton条件 变度量法 算法步骤 Step4: Step1: Step3: Step5: 一族算法 Step2: 变度量法 注释 由于对称矩阵G在迭代过程中是不断修正改变的， 它对于一般尺度的梯度起到改变尺度的作用， 因此G又称变尺度矩阵。称相应的算法为变尺度法. （DFP校正公式） DFP 法 校正公式 其中 ,满足 拟Newton条件 考虑 满足拟Newton条件 满足对称性 ？？确定 算法步骤 Step2: Step4: Step1: DFP 法 Step3: Step5: Step6: Step7: 用DFP算法求解： 取 解： Step1 DFP 法 举例 Step2 DFP 法 举例 DFP 法 正定继承性 性质 二次终止性 一种共轭方向法 全局收敛性 可证明DFP法具有超线性收敛性 Gk BFGS 法 基本思想 ,则产生 另一种求解无约束优化问题的方法---BFGS法. 校正公式 (BFGS公式) (BFGS方向) 算法步骤 参见DFP法的算法步骤. 其中 x