新建变尺度法1

1、变尺度法变尺度法PPT制作：冯希光 李明勇演讲人：陈若愚资料收集者：刘昊问题收集人：刘庆同回答问题：李彩军v变尺度法是近几十年来无约束优化方法发展中最重要的研究成果；v是基于牛顿法和最速下降法的思想而又作了重要改进的一类方法；v DFP变尺度法首先有戴维顿（Davidon）与1959年提出，又于1963年由弗莱彻（Fletcher）和鲍维尔加以发展和完善，故称DFP变尺度法，简称DFP法。至今仍被公认为是求解无约束优化问题的最有效的算法之一。变尺度的发展变尺度法的基本思想变尺度法的基本思想 变尺度法的基本思想与梯度法和牛顿法有着密切的联系。观察梯度法和牛顿法迭代公式： 分析比较这两种方法可知：

2、前者只需计算函数的一阶偏导数，计算工作量小，但是当迭代点接近最优点时收敛速度很慢。后者不仅需要计算一阶偏导数而且要计算二阶偏导数矩阵及其逆矩阵，计算量很大，但牛顿法具有二次收敛性，当迭代点接近最优点时收敛速度很快。对这两种方法取其优，去其劣，迭代过程先用梯度法，后用牛顿法并避开牛顿法的海森矩阵的逆矩阵的繁琐计算，这就是萌生建立“变尺度法”的基本构想。式中 是人为构造的一个n阶对称矩阵，它在迭代过程中随迭代点的位置变化而变化。若在初始点取 为单位矩阵E，则公式变为梯度法的迭代公式，搜索方向为负梯度方向。随着迭代过程不断地修正构造矩阵，使它在整个迭代过程中逐步地逼近目标函数在极小点处的海森矩阵的逆

3、矩阵,当 时，公式变为牛顿法的迭代公式，当迭代点逼近最优点时，搜索方向就趋于牛顿方向。如能实现这种构想，那就综合了梯度法和牛顿法的优点。实现上述变尺度法的基本思想，关键在于如何产生合乎要求的变尺度矩阵 。变尺度法的迭代公式为：构造变尺度矩阵的基本要求构造变尺度矩阵的基本要求 根据变尺度法的基本思想，需要构造一个矩阵 ，使其得到的搜索方向 具有下降性、收敛性和计算的简便性为了保证所构造的近似矩阵具有这些特点，必须：1.为了使拟牛顿搜索方向 朝着目标函数值下降的方向， 必须为对称正定矩阵。若有目标函数由 点沿 方向具有下降的性质，可知搜索方向 与负梯度方向 之间的夹角应成锐角，即两者的点积应大于零

4、： 将 代入上式，则有2.为使逐次构造的变尺度矩阵 逐渐逼近海森矩阵的逆矩阵 ， 须满足拟牛顿条件： 变尺度矩阵 必须是对称正定矩阵才能保证变尺度算法拟牛顿搜索方向是函数值下降方向。用矩阵表示为：将目标函数展开为Taylor的二次近似式取其梯度，得称为拟牛顿条件或DFP条件，在这个关系式中，只含有两个迭代点的向量差以及梯度向量差的信息，也就是说，应通过这两者信息来构造矩阵。取 为极值点附近第k+1次迭代点，则有：3.为适应迭代计算的需要，希望变尺度矩阵有如下递推形式：式中， 称为第k次校正矩阵，它只依赖于当前的已知量。从而的DFP公式：DFP变尺度法算法步骤变尺度法算法步骤00,. 1Step

5、00kEAx，误差正定矩阵给定初始点; )(.2k0kxfAsStep - - 计算搜索方向kkkkkkkkkkksxxsxfsxfep1k)(min)(:3St于是得进行一维搜索1:*kxx则停止，其最小点为。令kkkkkkkkkkkkxxxggxfxfgxfgxfg-11111,)()(, )(, )(. 5Step. 21NewtonNewton,1111stepkkxgHHHHHHkkkkkkkk转，令。方程：或拟条件拟满足使得计算按照校正公式Step 4. 判断判断 是否满足终止准则是否满足终止准则 计算计算(x(xk+1k+1) )，若，若 yes: No : 转转 step 5

6、。?)()1( - - kkxx221212112( ,)242f x xxxxx x-l解：解： 1）取初始点）取初始点 ，为了按，为了按DFP法构造第法构造第一次搜寻方向一次搜寻方向d0，需计算初始点处的梯度，需计算初始点处的梯度01 1Tx00120212244()422xxfxx-xgx取初始变尺度矩阵为单位矩阵取初始变尺度矩阵为单位矩阵H0=I，则第一次，则第一次搜寻方向为搜寻方向为 00010440122H- - -dg010000014141 212 - xxd为一维搜索最佳步长，应满足为一维搜索最佳步长，应满足01002()min()min(40203)ff-xxd得得:00.25120.5x,2）再按）再按DFP法构造点法构造点x1处的搜寻方向处的搜寻方向d1，需计算，需计算010143224y-gg0102110.510.5s - - xx代入校正公式代入校正公式01310.5340.543310.53444E-梯度为零向量梯度为零向量,海赛矩阵正定。可见点满足极值充要海赛矩阵正定。可见点满足极值充要条件，因此为极小点。条件，因此为极小点。 *242Txx*()8f -x变尺度法的主要特点只需用到函数的一