使用导数的最优化方法-课件.pptx

1、使用导数的最优化方法一、无约束最优化问题无约束最优化问题无约束最优化问题nRxtsxf.)(min有有一一阶阶连连续续偏偏导导数数。其其中中)(xf 无约束非线性规划问题的求解方法分为解析法和直截了当法两类。解析法 需要计算函数的梯度,利用函数的解析性质构造迭代公式使之收敛到最优解。本节介绍最速下降法、共轭梯度法、牛顿法、变尺度法等解析方法 直截了当法 仅通过比较目标函数值的大小来移动迭代点。下一章主要介绍模式搜索法等直截了当方法。无约束非线性规划问题的求解方法分为解析法和直截了当法两类。一般来说,无约束非线性规划问题的求解是通过一系列一维搜索来实现。因此,如何选择搜索方向是解无约束非线性规划

2、问题的核心问题,搜索方向的不同选择,形成不同的求解方法。本章主要介绍解析法;另一类只用到目标函数值,不必计算导数,通常称为直截了当方法,放在第11章讨论、nExxf)(min本章考虑如下的下降算法:;1,)1()1()1(kdx令选定搜索方向给定初始点)()(min)()()2()()(0)()(kkkkdxfdxf，求一维搜索问题令：.k得到解为步；转第令处的搜索方向否则，选取在是最优解，停；若令：2,1,)3()1()1()1()()()1(kkdxxdxxkkkkkkk算法。选取不同，得到不同的搜索方向)(kd主要介绍最速下降法、牛顿法,共轭梯度法,拟牛顿法等10.1 最速下降法 10.

3、1.1 最速下降方向 考虑无约束问题nExxf)(min(6.1.2)其中函数 具有一阶连续偏导数、人们在处理这类问题时,总希望从某一点出发,选择一个目标函数值下降最快的方向,以利于尽快达到极小点、正是基于如此一种愿望,早在1847年法国著名数学家Cauchy提出了最速下降法、后来,Curry等人作了进一步的研究、现在最速下降法差不多成为众所周知的一种最基本的算法,它对其他算法的研究也特别有启发作用,因此在最优化方法中占有重要地位、下面我们先来讨论如何选择最速下降方向、)(xf 人们在处理这类问题时,总希望从某一点出发,选择一个目标函数值下降最快的方向,以利于尽快达到极小点.正是基于这样一种愿

4、望,早在1847年法国著名数学家Cauchy提出了最速下降法.后来,Curry等人作了进一步的研究.现在最速下降法已经成为众所周知的一种最基本的算法,它对其他算法的研究也很有启发作用,因此在最优化方法中占有重要地位.下面我们先来讨论怎样选择最速下降方向.我们知道,函数 在点 处沿方向 的变化率可用方向导数来表达,对于可微函数,方向导数等于梯度与方向的内积,即)(xfxddxfdxDfT)();(6.1.2)因此,求函数 在点 处的下降最快的方向,可归结为求解下列非线性规划:)(xfx1.)(mindtsdxfT(6.1.3)根据Schwartz不等式,有)()()(xfdxfdxfT去掉绝对值

5、符号,可以得到)()(xfdxfT(6.1.4)由上式可知,当)()(xfxfd(6.1.5)时等号成立.因此,在点 处沿(6.1.5)所定义的方向变化率最小,即负梯度方向为最速下降方向.这里要特别指出,在不同尺度下最速下降方向是不同的.前面定义的最速下降方向,是在向量 的殴氏范数 不大于1的限制得到的,属于殴氏度量意义下的最速下降方向.如果改用其他度量,比xd2d如,设 为对称正定矩阵,在向量 的 范数 不大于1的限制下,极小化 ,则得到的最速下降方向与前者不同.AdA21)(AdddTAdxfT)(10.1.2 最速下降算法 最速下降法的迭代公式是)()()1(kkkkdxx(10.1.6

6、)其中 是从 出发的搜索方向,这里取在点 处的最速下降方向,即)()()(kkxfd)(kd)(kx 是从 出发沿方向 进行一维搜索的步长,即 满足k)(kx)(kdk)(min)()()(0)()(kkkkkdxfdxf(10.1.11)(kx 计算步骤如下:1.给定初点 ,允许误差 ,置 .nEx)1(01k 2.计算搜索方向)()()(kkxfd 3.若 ,则停止计算;否则,从 出发,沿 进行一维搜索,求 ,使)(kd)(kx)(kdk)(min)()()(0)()(kkkkkdxfdxf 4.令 ,置 ,转步2.)()()1(kkkkdxx1:kk 例10.1.1 用最速下降法解下列问

7、题:22212)(minxxxf.101,)1,1()1(Tx初点解:,)2,4()(21Txxxf.)2,4()()1(1Txfd.)21,41()1()1(Tdx，令22)1()1()21()41(2)()(dxf)(min求解0)21(4)41(16)(令1851Tdxx)94,91()1(1)1()2(22212)(minxxxf)1,1()1(x第二次迭代:.)9/8,9/4()()2()2(Txfd1.0789.15/54)9/8()9/4(22)2(dTdx984941)2()2(，令81)21(1681)41(2)()(22)2()2(dxfTdx984941)2()2(，令8

8、1)21(1681)41(2)()(22)2()2(dxf)(min求解，令081)21(6481)41(16)(1252Tdxx11272)2(2)2()3(第三次迭代:.)27/4,27/8()()3()3(Txfd1.03313.027/54)27/4()27/8(22)3(d进行一维搜索：沿从)3()3(dx)()(min)3()3(dxf求解21412721227411272)3()3(dx)()(min)()(kkdxf求解在最速下降法的一位搜素中0)()()(T)()(kkkddxf由k解得步长满足：故步长k0)()(T)()(kkkkddxf)()()1(kkkkdxx0)()

9、(T)1(kkdxf)()()(kkxfd其中0)(T)1(kkdd即在最速下降法中相邻两次搜索方向是正交的。)()(min)()(kkdxf对于一维搜索cxbAxxxfTT21)(关于二次严格凸函数其中A为n维对称正定矩阵能够求出步长因子k)()()(kkxfd其中满足：由步长k0)()(T)()(kkkkddxfbAx)(xf由0)()()()(kTkkkdbdxA解得：)()()()()()()()()()()(kTkkTkkTkkTkkAdddxfAdddbAx)()()1(kkxfxf）（)()(2)()()()()(21kTkkTkAddxfxf(本章习题7)锯齿现象 最速下降法的

10、迭代点在向极小点靠近的过程中,走的是曲折的路线:后一次搜索方向d(k+1)与前一次搜索方向 d(k)总是相互垂直的,称它为锯齿现象。这一点在前面的例题中已得到验证。除极特别的目标函数(如等值面为球面的函数)和极特别的初始点外,这种现象一般都要发生。最速下降法的收敛性 从直观上能够看到,在远离极小点的地方,每次迭代都有估计使目标函数值有较多的下降,但在接近极小点的地方,由于锯齿现象,每次迭代行进的距离开始逐渐变小。因而收敛速度不快。已有结论表明,最速下降法关于正定二次函数关于任意初始点都是收敛的(定理10、1、2),而且恰好是线性收敛的。10.2 牛顿法 6.2.1 牛顿法 设 是二次可微实函数

11、,.又设 是 的极小点的一个估计,我们把 在 展成Taylor级数,并取二阶近似:)(xfnEx)(kx)(xf)(xf)(kx)()(21)()()()()()()(2)()()()(kkTkkTkkxxxfxxxxxfxfxxf其中 是 在 处的Hessian矩阵.为求 的平稳点,令)()(2kxf)(xf)(kx)(x0)(x0)()()()(2)(kkkxxxfxf即(10.2.1)设 可逆,有(10.2.1)得到牛顿法的迭代公式)()(2kxf)()()(1)(2)()1(kkkkxfxfxx(10.2.2)其中 是Hessian矩阵 的逆矩阵.这样,知道 后,算出在这一点处目标函数

12、的梯度和Hessian矩阵的逆,代人(10.2.2),便得到后继点 ,用 代替 ,再用(10.2.2)计算,又得到 的后继点.依此类推,产生序列 .在适当的条件下,这个序列收敛.1)(2)(kxf)()(2kxf)(kx)1(kx1kk)1(kx)(kx 22112)()()(.2)(.1kxxxxxfxfxfkxf则牛顿法产生的序列收敛于 、x 实际上,当牛顿法收敛时,有下列关系:2)()1(xxcxxkk其中 C 是某个常数、因此,牛顿法至少2级收敛,参看文献19、可见牛顿法的收敛速率是特别快的、例10、2、1 用牛顿法解下列问题:2241)1(minxx.)1,0()1(Tx 我们取初点

13、解:)()()(1)(2)()1(kkkkxfxfxx2312)1(4)(xxxf24)()1(xf200)1(12)(212xxf20012)(2xf)()()1(1)1(2)1()2(xfxfxx242/10012/11003/113/110第2次迭代:027/32)()2(xf2009/48)()2(2xf第2次迭代:027/32)()2(xf2009/48)()2(2xf)()()2(1)2(2)2()3(xfxfxx027/322/10048/903/103/1)2(x09/5接着迭代,得到,.081/65,027/19)5()4(xx最终收敛到最优解x*=(1,0)T我们先用极值条

14、件求解、令0)(bAxxf下面用牛顿法求解、任取初始点x(1),依照牛顿法的迭代公式:特别地,关于二次凸函数,用牛顿法求解,经1次迭代即达极小点、设有二次凸函数cxbAxxxfTT21)(其中A是对称正定矩阵。)()()(1)(2)()1(kkkkxfxfxx求迭代点x(2)bAx1得到是最小值点吗？bAx1为什么？xbAbAxAxxfAxx1)1(1)1()1(1)1()2()()(即1次迭代达到极小点、)()(12xfxfd不一定是下降方向,经迭代,目标函数值可能上升.此外,即使目标函数值下降,得到的点 也不一定是沿牛顿方向的最好点或极小点.因此,人们对牛顿法进行修正,提出了阻尼牛顿法.值

15、得注意,当初始点远离极小点时,牛顿法可能不收敛.原因之一,牛顿方向 以后还会遇到一些算法,把它们用于二次凸函数时,类似于牛顿法,经有限次迭代必达到极小点.这种性质称为二次终止性.)1(kx关于二次凸函数,用牛顿法求解,经1次迭代即达极小点 10.2.2 阻尼牛顿法 阻尼牛顿法与原始牛顿法的区别在于增加了沿牛顿方向的一维搜索,其迭代公式是)()()1(kkkkdxx(6.2.6)其中 为牛顿方向,是由一维搜索得到的步长,即满足)(min)()()()()(kkkkkdxfdxfk)()()(1)(2)(kkkxfxfd 阻尼牛顿法的计算步骤如下:1.给定初始点 ,允许误差 ,置 .2.计算 )1

16、(x01k1)(2)()(),(kkxfxf 3.若 ,则停止迭代;否则,令)()(kxf)()()(1)(2)(kkkxfxfd 4.从 出发,沿方向 作一维搜索:)(kx)(kd)()(min)()()()(kkkkkdxfdxf令 .)()()1(kkkkdxx 5.置 ,转步2.1:kk 由于阻尼牛顿法含有一维搜索,因此每次迭代目标函数值一般有所下降(决不会上升).可以证明,阻尼牛顿法在适当的条件下具有全局收敛性,且为2级收敛.1010、3 3、共轭梯度法10、3、1 共轭方向法1、共轭方向和共轭方向法定义定义共轭。共轭。关于关于和和，则称，则称若有若有AddAddT21210 ARd

17、ddnk它们两两关于它们两两关于中一组非零向量，如果中一组非零向量，如果是是设设,21。共轭，即共轭，即kjijiAddjTi,2,1,0 共轭方向。共轭方向。组组共轭的，也称它们是一共轭的，也称它们是一则称这组方向是关于则称这组方向是关于AA注：注：002121 dddIdTT21dd 共轭是正交的推广。，和和中的两个非零向量中的两个非零向量的对称正定矩阵，对于的对称正定矩阵，对于是是设设21ddRnnAn 是是单单位位矩矩阵阵，则则如如果果 A几何意义设有二次函数设有二次函数)()(21)(xxAxxxfT 对称正定矩阵，对称正定矩阵，是是其中其中nnA 是一个定点。是一个定点。x的等值面

18、的等值面则函数则函数)(xfcxxAxxT )()(21为中心的椭球面。为中心的椭球面。是以是以 x由于由于,0)()(xxAxf,0)(2 AxfA所以所以正定，正定，因为因为的极小点。的极小点。是是因此因此)(xfxx,)(2Axf 而而几何意义设有二次函数设有二次函数)()(21)(xxAxxxfT 对称正定矩阵，对称正定矩阵，是是其中其中nnA 是一个定点。是一个定点。x的等值面的等值面则函数则函数)(xfcxxAxxT )()(21为中心的椭球面。为中心的椭球面。是以是以 x由于由于,0)()(xxAxf,0)(2 AxfA所以所以正定，正定，因为因为的极小点。的极小点。是是因此因此

19、)(xfxx,)(2Axf 而而，设有函数设有函数cxbAxxxfTT 21)(共轭向量。共轭向量。一组一组是是阶对称正定矩阵。阶对称正定矩阵。是是其中其中AdddnAk)()2()1(,推论:进行搜索，进行搜索，为初始点，依次沿为初始点，依次沿以任意的以任意的)()2()1()1(,kndddRx 上的上的在在是函数是函数则则得到点得到点kkkBxxfxxxx )1()1()1()3()2()(,|1)(RdxxBikiiik 上上的的唯唯一一极极小小点点。在在nRxf)(nkkidxfiTk，且有),1,0(0)()()1(0)()1(nxf时，当，特别地nk 极小点，其中极小点，其中点。

20、经有限次迭代必得极小沿一组共轭方向搜索，即对于二次凸函数，若共轭方向法对于极小化问题对于极小化问题:法法为为共共轭轭方方向向法法是是正正定定矩矩阵阵，称称下下述述算算其其中中 A,21)(mincxbAxxxfTT ；共轭方向共轭方向取定一组取定一组)()2()1(,)1(ndddA,)2()1()()1(kkxxx确定点确定点依次按照下式由依次按照下式由任取初始点任取初始点 )(min)()()()()()()()1(kkkkkkkkkdxfdxfdxx 。满足满足直到某个直到某个0)()()(kkxfx注注至多经过至多经过求解上述极小化问题，求解上述极小化问题，可知，利用共轭方向法可知，利

21、用共轭方向法由定理由定理2。次次迭迭代代必必可可得得到到最最优优解解n )(min)()()()()()()()1(kkkkkkkkkdxfdxfdxx ；共轭方向取定一组)()2()1(,ndddA关于上述正交方向法,它是下降算法不？不难得到:,0)()(T)1(kkdxf由)()()()()()(kTkkTkkAdddxfcxbAxxxfTT21)()()(21)()()()(yxAyxyxyfyfxfTT由)()(21)()()()()()1()()1()()1()()1(kkTkkkkTkkkxxAxxxxxfxfxf）（)()(2)()()()(21kTkkTkAdddxf,0)()

22、()1(kkxfxf）（，若0)()()(kTkdxf).()()1(kkxfxf）（则故正交方向法,它是下降算法。？共轭方向如何构造一组)()2()1(,ndddA可由一组线性无关向量组,类似于schmidt正交化过程,。共轭方向构造一组)()2()1(,ndddA.13具体步骤见本章习题共轭方向的方法。下一节介绍另一种构造cxbAxxxfTT21)(min化问题对于二次凸函数的极小10.3 共轭梯度法 10.3.2 共轭梯度法 共轭梯度法最初由Hesteness和Stiefel于1952年为求解线性方程组而提出.后来,人们把这种方法用于求解无约束最优化问题,使之成为一种重要的最优化方法.下

23、面,重点介绍Fletcher-Reeves共轭梯度法,简称FR法.共轭梯度法的基本思想是把共轭性与最速下降方法相结合,利用已知点处的梯度构造一组共轭方向,并沿这组方向进行搜索,求出目标函数的极小点.根据共轭方向的基本性质,这种方法具有二次终止性.我们先讨论对于二次凸函数的共轭梯度法,然后再把这种方法推广到极小化一般函数的情形.10、3、2、共轭梯度法 如何选取一组共轭方向？:共轭梯度法共轭梯度法eevesRFletcher 代点代点向相结合，利用已知迭向相结合，利用已知迭将共轭性和最速下降方将共轭性和最速下降方基本思想：基本思想：进行搜索，求出进行搜索，求出共轭方向，并沿此方向共轭方向，并沿此

24、方向处的梯度方向构造一组处的梯度方向构造一组函数的极小点。函数的极小点。以下分析算法的具体步骤。cxbAxxxfTT 21)(min是常数。是常数。，是对称正定矩阵，是对称正定矩阵，其中其中cRbARxnn ,我们先讨论关于二次凸函数的共轭梯度法,然后再把这种方法推广到极小化一般函数的情形；，第一个搜索方向取为，第一个搜索方向取为任取初始点任取初始点)()1()1()1()1(xfdx，令令，若若，设已求得点设已求得点)(0)()2()1(1)1()1(kkkkxfgxfx:)1(按如下方式确定按如下方式确定则下一个搜索方向则下一个搜索方向 kd)1()(1)1(kkkkdgd 令令共轭。共轭

25、。关于关于和和要求要求Addkk)()1(？如何确定如何确定k，得，得）式两边同时左乘）式两边同时左乘则在（则在（AdTk)(1)()(1)()1()(0kTkkkTkkTkdAdAgdAdd )2()()(1)(kTkkTkkdAdgAd 解得解得cxbAxxxfTT 21)(min初始搜索方向为最速下降方向)1964,Re(|221evesFletcherggiii式：外，还有下列等价表达除表达式有多个等价式，定理中，对于二次凸规划，上述221|iiiigg)1972,()()(1)(11wolfeseensenggdgggiiTiiiTii)1967,()()()(1DanielAddA

26、dgiTiiTii)()(11dixongdggiTiiTii)1969,()()(11PPRgggggiTiiiTii常用两个公式:著名的FR和PPR公式算算法法步步骤骤：FR。，令，令精度要求精度要求，任取初始点任取初始点1.1)1(kx 为所求极小点；为所求极小点；停止，停止，若若令令)1(1)1(1,|,)(.2xgxfg 。令令，）计算）计算利用公式（利用公式（否则，令否则，令)1(1)1()2(11)1(3,dxxgd 为所求极小点；为所求极小点；停止，停止，若若令令)1(1)1(1,|,)(.3 kkkkxgxfg）计算。）计算。用公式（用公式（其中其中否则，令否则，令4,)(1

27、)1(kkkkkdgd 。转转，令，令）计算）计算利用公式（利用公式（3,3.4)()()1(kkkkkdxx 。令令1:kk)3()()()(kTkkTkkAdddg)4(|221iiiggcxbAxxxfTT21)(min求解二次凸规划的FR 共轭梯度法求解二次凸规划的FR 共轭梯度法迭代多少次才能够达到最优解？10、3、3、用于一般函数的共轭梯度法nRxtsxf.)(min共轭梯度法进行修改：共轭梯度法进行修改：对用于正定二次函数的对用于正定二次函数的确确定定。）计计算算，需需由由一一维维搜搜索索不不能能利利用用公公式式（搜搜索索步步长长3)2(i。速下降方向，即第一个搜索方向仍取最)(

28、)1()1()1(xfd算算：其其它它搜搜索索方方向向按按下下式式计计,)()()1()1(iiiidxfd 。其中其中2)(2)1(|)(|)(|iiixfxf )3()()()(kTkkTkkAdddg）计算。用公式（其中令4,1)(1)1(kkkkkdgdk10、3、3、用于一般函数的共轭梯度法nRxtsxf.)(min。速下降方向，即第一个搜索方向仍取最)()1()1()1(xfd)4(|221iiigg)(min)2()()(kkdxf但求解一维搜索问题确定。）计算，需由一维搜索不能利用公式（搜索步长3i)3()()()(kTkkTkkAdddg10.3 共轭梯度法 10.3.2 共

29、轭梯度法 共轭梯度法最初由Hesteness和Stiefel于1952年为求解线性方程组而提出.后来,人们把这种方法用于求解无约束最优化问题,使之成为一种重要的最优化方法.下面,重点介绍Fletcher-Reeves共轭梯度法,简称FR法.共轭梯度法的基本思想是把共轭性与最速下降方法相结合,利用已知点处的梯度构造一组共轭方向,并沿这组方向进行搜索,求出目标函数的极小点.根据共轭方向的基本性质,这种方法具有二次终止性.我们先讨论对于二次凸函数的共轭梯度法,然后再把这种方法推广到极小化一般函数的情形.考虑问题cxbAxxxfTT21)(min其中 ,是对称正定矩阵,是常数.nExAc 具体求解方法

30、如下:首先,任意给定一个初始点 ,计算出目标函数 在这点的梯度,若 ,则停止计算;否则,令)1(x)(xf01g1)1()1()(gxfd(10.3.12)沿方向 搜索,得到点 .计算在 处的梯度,若 ,则利用 和 构造第2个搜索方向 ,再沿 搜索.)1(d)2(x)2(x02g2g)1(d)2(d)2(d 一般地,若已知点 和搜索方向 ,则从 出发,沿 进行搜索,得到)(kx)(kd)(kx)(kd)()()1(kkkkdxx(10.3.14)其中步长 满足k)(min)()()()()(kkkkkdxfdxf我们可以求出 的显式表达.令k)()()()(kkdxf求 的极小点,令)(0)(

31、)()()1(kTkdxf(10.3.15)根据二次函数的梯度的表达式,(6.3.15)即00(0)()()()()()()()1(kTkkkkTkkkkTkdAdgdbdxAdbAx(10.3.16)由(6.3.16)得到)()()(kTkkTkkAdddg(10.3.17)计算 在 处的梯度.若 ,则停止计算;否则,用共轭.按此设想,令)(xf)1(kx01kgAddddgkkkkk关于和，并使构造下一个搜索方向和)()1()1()(1)(1)1(kkkkdgd(10.3.18)上式两端左乘 ,并令0)()(1)()1()(kTkkkTkkTkAddAgdAdd由此得到AdTk)()()(

32、1)(kTkkTkkAddAgd(10.3.19)再从 出发,沿方向 搜索.)1(kx)1(kd综上分析，在第个搜索方向取负梯度的前提下,重复使用公式(10.3.14),(10.3.17),(10.3.18)和(10.3.19),就能伴随计算点的增加,构造出一组搜索方向.下面将要证明,这组方向是关于 共轭的.因此,上述方法具有二次终止性.A 定理10.3.3 对于正定二次函数(10.3.12),具有精确一维搜索的Fletcher-Reeves法在 次一维搜索后即终止，并且对所有 ,下列关系成立:nm)1(mii)0(.31,2,10.21,2,10.1)()()(iiTiiTijTijTidg

33、gdgijggijAdd蕴涵 例6.3.1 考虑下列问题：2322212121minxxx 取初始点和初始搜索方向分别为021111)1()1(dx和 在FR法中，初始搜索方向必须取最速下降方向，这一点绝不可忽视。对于二次凸函数，FR法的计算步骤如下：1.给定初始点 ,置 .)1(x1k 2.计算 ,若 ,则停止计算,得点 ;否则,进行下一步.)()(kkxfg0kg)(kxx 3.构造搜索方向,令)1(1)(kkkkdgd其中,当 时,当 时,按公式 1k01k1k)0,1(221iiiigigg计算因子 .1k 4.令)()()1(kkkkdxx其中按公式(6.3.17)计算步长k 5.若

34、 ,则停止计算,得点 ;否则,置 ,返回步2.nk)1(kxx1:kk 由10、4 拟牛顿法 6、4、1 拟牛顿条件前面介绍了牛顿法,它的突出优点是收敛特别快、然而,运用牛顿法需要计算二阶便导数,而且目标函数的Hessian矩阵估计非正定、为了克服牛顿法的缺点,人们提出了拟牛顿法、它的基本思想是用不包含二阶导数的矩阵近似牛顿法中的Hessian矩阵的逆矩阵、Newton法的优缺点都特别突出。优点:高收敛速度(二阶收敛);缺点:对初始点、目标函数要求高,计算量、存储量大(需要计算、存储Hesse矩阵及其逆)。拟Newton法是模拟Newton法给出的一个保优去劣的算法 拟Newton法是效果特别

35、好的一大类方法。它当中的DFP算法和BFGS算法是直到目前为止在不用Hesse矩阵的方法中的最好方法。由于构造近似矩阵的方法不同,因而出现不同的拟牛顿法、经理论证明和实践检验,拟牛顿法差不多成为一类公认的比较有效的算法下面分析如何构造近似矩阵并用它取代牛顿法中的Hessian矩阵的逆、前面差不多给出牛顿法的迭代公式,即)()()1(kkkkdxx)()()(1)(2)(kkkxfxfd其中 k是从 xk 出发沿牛顿方向搜索的最优步长、设在第 次迭代后,得到点 ,我们将目标函数 在点 展成Taylor级数,并取二阶近似,得到k)1(kx)(xf)1(kx)()(21)()()()()1()1(2

36、)1()1()1()1(kkTkkTkkxxxfxxxxxfxfxf由此可知,在 附近有)1(kx)()()()1()1(2)1(kkkxxxfxfxf令 ,则)(kxx)()()()1()()1(2)1()(kkkkkxxxfxfxf记作)()1()(kkkxxp)()()()1()(kkkxfxfq(10.4.3)(10.4.4)则有)(1)1(2)()(kkkpxfq(10.4.5)又设Hessian矩阵 可逆,则)()1(2kxf)(1)1(2)()(kkkqxfp(10.4.6)这样,计算出 后,可以根据(10.4.6)估计在 处的Hessian矩阵的逆.因此,为了用不包含二阶导数的

37、矩阵 取代牛顿法中的Hessian矩阵 的逆矩阵,有理由令 满足)()(kkqp和)1(kx1kH)()1(2kxf1kH)(1)(kkkqHp(10.4.7)()()()1()()1(2)1()(kkkkkxxxfxfxf式(10.4.7)有时称为拟牛顿条件.下面旧来研究怎样确定满足这个条件的矩阵 .1kH 10.4.3 DFP算法 著名的 DFP 方法是 Davidon 首先提出,后来又被 Fletcher 和 Powell 改进的算法,又称为变尺度法.在这种方法中,定义校正矩阵为)()()()()()()()(kkTkkTkkkkTkTkkkqHqHqqHqpppH(6.4.16)容易验证,这样定义校正矩阵 ,得到的矩阵kH)()()()()()()()(1kkTkkTkkkkTkTkkkkqHqHqqHqpppHH(6.4.17)(1)(kkkqHp(10、4、7)满足拟牛顿条件(6.4.7).(6.4.17)称为DFP公式.DFP方法计算步骤如下:1.给定初始点 ,允许误差 .2.置 (单位矩阵),计算出在 处的梯度nEx)1(0nIH 1)1(x)()1(1xfg.1k置 3.令 kkkgHd)(4.从 出发,沿方向 搜索,求步长 ,使它满足)(kx)(kdk)(min)()()(0)()(kkkkkdxfdxf感谢您的聆听！