第9讲梯度法和共轭梯度法课件.ppt

1、4.1 梯度法和共轭梯度法梯度法和共轭梯度法1.无约束最优化问题无约束最优化问题2.梯度法梯度法3.共轭梯度法共轭梯度法一一.无约束最优化问题无约束最优化问题无无约约束束最最优优化化问问题题nRxtsxf.)(min有有一一阶阶连连续续偏偏导导数数。其其中中)(xf解析方法：利用函数的解析性质构造迭代公式使之收敛到最优解。二二.梯度法（最速下降法）梯度法（最速下降法）迭代公式：迭代公式：kkkkdxx 1如何选择下降最快的方向？如何选择下降最快的方向？)(kxf)(kxf 函函数数值值下下降降最最快快的的方方向向函函数数值值增增加加最最快快的的方方向向函函数数值值下下降降的的方方向向kx梯度法

2、（最速下降法）：梯度法（最速下降法）：也称为最速下降方向；也称为最速下降方向；搜索方向：搜索方向：,)(.1kkxfd。即即满满足足取取最最优优步步长长搜搜索索步步长长)(min)(,:.2kkkkkkdxfdxf 梯度法算法步骤：梯度法算法步骤：。令令允许误差允许误差给定初始点给定初始点1,0,.11 kRxn;)(.2kkxfd 计算搜索方向计算搜索方向kkkxd 否则，求最优步长否则，求最优步长为所求极值点；为所求极值点；则停止计算，则停止计算，若若,|.3。使得使得)(min)(kkkkkdxfdxf 。转转令令令令2,1:,.41 kkdxxkkkk,)1,2(,3)(min:.12

3、221Txxxxf 设初始点为设初始点为用最速下降法求解用最速下降法求解例例。求迭代一次后的迭代点求迭代一次后的迭代点2x解：解：,)6,2()(21Txxxf .)6,4()(11Txfd .)61,42(11Tdx ，令令2211)61(3)42()()(dxf)(min 求解求解0)61(36)42(8)(令令62131 Tdxx)318,3136(1112 收敛性收敛性)(min)(kkkkkdxfdxf 。则有则有0)(kTkkkddxf 性质性质.证明：证明：所以所以，令令)()(kkdxf .)()(kTkkddxf )(min)(kkkkkdxfdxf .0)()(kTkkkk

4、ddxf 满足满足步长步长有一阶连续偏导数，若有一阶连续偏导数，若设设kxf)(注：注：。kkkTkdddd 110)(所以所以，因为梯度法的搜索方向因为梯度法的搜索方向)(1kkkkdxfd 锯齿现象锯齿现象在极小点附近，目标函数可以用二次函数近似，其等值面近似椭球面。椭球面。1x*x2x3x它只是它只是。标函数的一种局部性质标函数的一种局部性质最速下降方向反映了目最速下降方向反映了目局部目标函数值下降最快的方向。锯齿形状,越接近极小点,步长越小,前进越慢!注注 最速下降法反映的目标函数的一种局部性质最速下降法反映的目标函数的一种局部性质,从局部看从局部看,最速下降方向确是目标函数值下降最快

5、的方向最速下降方向确是目标函数值下降最快的方向,选择这样的选择这样的方向进行搜索是有利的方向进行搜索是有利的.但从全局来看但从全局来看,由于由于锯齿现象锯齿现象的影响的影响,即使向着极小点即使向着极小点移近不太大的距离移近不太大的距离,也要经历不小的也要经历不小的”弯路弯路”,因此收敛速度因此收敛速度大为减慢大为减慢.最速下降法一般适用于计算过程的前期迭代最速下降法一般适用于计算过程的前期迭代,或者作为或者作为间插步骤间插步骤.3共轭梯度法共轭梯度法1.共轭方向和共轭方向法共轭方向和共轭方向法定义定义共轭。共轭。关于关于和和，则称，则称若有若有AddAddT21210 ARdddnk它们两两关

6、于它们两两关于中一组非零向量，如果中一组非零向量，如果是是设设,21。共轭，即共轭，即kjijiAddjTi,2,1,0 共共轭轭方方向向。组组共共轭轭的的，也也称称它它们们是是一一则则称称这这组组方方向向是是关关于于AA注注：002121 dddIdTT21dd 共轭是正交的推广。共轭是正交的推广。，和和中的两个非零向量中的两个非零向量的对称正定矩阵，对于的对称正定矩阵，对于是是设设21ddRnnAn 是是单单位位矩矩阵阵，则则如如果果 A共轭的非零共轭的非零个个是是阶对称正定矩阵，阶对称正定矩阵，是是设设AkdddnAk,21性无关。性无关。向量，则这个向量组线向量，则这个向量组线2.定理

7、证明证明，使得，使得设存在实数设存在实数k ,21,01 kiiid jTdA上式两边同时左乘，则有,01 kiiTjiAdd 可化简为可化简为共轭的向量，所以上式共轭的向量，所以上式个个是是因为因为Akdddk,21.0 jTjjAdd 0,0jjTjdAdAd因为而 是正定矩阵，所以，所以所以。kjj,2,1,0 线性无关。线性无关。因此因此kddd,21几何意义几何意义设设有有二二次次函函数数)()(21)(xxAxxxfT 对称正定矩阵，对称正定矩阵，是是其中其中nnA 是一个定点。是一个定点。x的等值面的等值面则函数则函数)(xfcxxAxxT )()(21为中心的椭球面。为中心的椭

8、球面。是以是以 x由于由于,0)()(xxAxf,0)(2 AxfA所以所以正定，正定，因为因为的极小点。的极小点。是是因此因此)(xfxx,)(2Axf 而而点，点，是在某个等值面上的一是在某个等值面上的一设设)0(x处的法向量为处的法向量为该等值面在点该等值面在点)1(x.)()()1()1(xxAxf o1x2xx)1(d)0(x中的一个方向，中的一个方向，是是nRd)1(。以最优步长搜索得到点以最优步长搜索得到点沿着沿着)1()1()0(xdx所所在在等等值值面面的的切切向向量量。是是点点则则)1()1(xd正交，正交，与与则则)()1()1(xfd,0)()1()1(xfdT即即,)

9、1()2(xxd 令令)1(x所以所以,0)2()1(AddT共轭。共轭。小点的向量关于小点的向量关于向量与由这一点指向极向量与由这一点指向极即等值面上一点处的切即等值面上一点处的切A)2(d3.定理，设有函数设有函数cxbAxxxfTT 21)(共轭向量。共轭向量。一组一组是是阶对称正定矩阵。阶对称正定矩阵。是是其中其中AdddnAk)()2()1(,进行搜索，进行搜索，为初始点，依次沿为初始点，依次沿以任意的以任意的)()2()1()1(,kndddRx 上的上的在在是函数是函数则则得到点得到点kkkBxxfxxxx )1()1()1()3()2()(,极小点，其中极小点，其中,|1)(R

10、dxxBikiiik 是是时，时，当当，生成的子空间。特别地生成的子空间。特别地是由是由)1()()2()1(,nkxnkddd上上的的唯唯一一极极小小点点。在在nRxf)(推论推论有有在上述定理条件下，必在上述定理条件下，必。kidxfiTk,2,1,0)()()1(共轭方向法对于极小化问题对于极小化问题:法法为为共共轭轭方方向向法法是是正正定定矩矩阵阵，称称下下述述算算其其中中 A,21)(mincxbAxxxfTT ；共轭方向共轭方向取定一组取定一组)()2()1(,)1(ndddA,)2()1()()1(kkxxx确定点确定点依次按照下式由依次按照下式由任取初始点任取初始点 )(min

11、)()()()()()()()1(kkkkkkkkkdxfdxfdxx 。满足满足直到某个直到某个0)()()(kkxfx注注3由定理 可知，利用共轭方向法求解上述极小化问题，至多经过。次次迭迭代代必必可可得得到到最最优优解解n2.共轭梯度法 如何选取一组共轭方向？如何选取一组共轭方向？:共轭梯度法共轭梯度法eevesRFletcher 代代点点向向相相结结合合，利利用用已已知知迭迭将将共共轭轭性性和和最最速速下下降降方方基基本本思思想想：进进行行搜搜索索，求求出出共共轭轭方方向向，并并沿沿此此方方向向处处的的梯梯度度方方向向构构造造一一组组函数的极小点。函数的极小点。以下分析算法的具体步骤。

12、以下分析算法的具体步骤。cxbAxxxfTT 21)(min是常数。是常数。，是对称正定矩阵，是对称正定矩阵，其中其中cRbARxnn ,；，第一个搜索方向取为，第一个搜索方向取为任取初始点任取初始点)()1()1()1()1(xfdx，令令，若若，设已求得点设已求得点)(0)()2()1(1)1()1(kkkkxfgxfx:)1(按如下方式确定按如下方式确定则下一个搜索方向则下一个搜索方向 kd)1()(1)1(kkkkdgd 令令共轭。共轭。关于关于和和要求要求Addkk)()1(？如何确定如何确定k，得，得）式两边同时左乘）式两边同时左乘则在（则在（AdTk)(1)()(1)()1()(

13、0kTkkkTkkTkdAdAgdAdd )2()()(1)(kTkkTkkdAdgAd 解得解得:)3(搜搜索索步步长长的的确确定定，步长步长利用一维搜索确定最优利用一维搜索确定最优和搜索方向和搜索方向已知迭代点已知迭代点kkkdx,)()(。即求解即求解)(min)()(kkdxf ,)()()()(kkdxf 记记，令令0)()()()()(kTkkddxf ，即有即有0)()()()(kTkkdbdxA，则有，则有令令bAxxfgkkk )()()(，0)()(kTkkdAdg)3()()()(kTkkTkkAdddg 解得解得4定理次次算法在算法在，对于正定二次函数对于正定二次函数n

14、mFRcxbAxxxfTT 21)(），下下列列关关系系成成立立（且且对对所所有有的的一一维维搜搜索索后后即即终终止止，并并mii 1;1,2,1,0)1()()(ijAddjTi;1,2,1,0)2(ijggjTi。iTiiTiggdg )()3(注注(1)(2)()14,mdddA（）由定理 可知搜索方向是共轭的。则则构构造造的的搜搜索索必必须须取取负负梯梯度度方方向向，否否算算法法中中第第一一个个搜搜索索方方向向)2(方方向向不不能能保保证证共共轭轭性性。(3)43由定理 的（）可知，,0|2)(iiTiiTigggdg处的下降方向。处的下降方向。是迭代点是迭代点所以所以)()(iixd

15、(4)4iFR由定理，算法中的计算公式可以简化。)()(1)(iTiiTiiAddgAd )()()(1iTiiTiAdddAg /)(/)()()1()()()1(1iiiTiiiiTixxAdxxAg .)()()(bxAxfgiii )()(1)(11iiTiiiTiiggdggg iTiigdg)(21|)4(|221iigg 算算法法步步骤骤：FR。，令，令精度要求精度要求，任取初始点任取初始点1.1)1(kx 为所求极小点；为所求极小点；停止，停止，若若令令)1(1)1(1,|,)(.2xgxfg 。令令，）计算）计算利用公式（利用公式（否则，令否则，令)1(1)1()2(11)1

16、(3,dxxgd 为所求极小点；为所求极小点；停止，停止，若若令令)1(1)1(1,|,)(.3 kkkkxgxfg）计算。）计算。用公式（用公式（其中其中否则，令否则，令4,)(1)1(kkkkkdgd 。转转，令，令）计算）计算利用公式（利用公式（3,3.4)()()1(kkkkkdxx 。令令1:kk算算法法求求解解下下述述问问题题：用用例例FR22212)(minxxxf 。初始点取为初始点取为Tx)2,2()1(解：解：.)2,4()(21Txxxf 次迭代：次迭代：第第1,)4,8(1)1(Tgd 令令)1()1()1(11AdddgTT ,2004),(21)(2121 xxxx

17、xf.2004 A而而 482004)4,8(48)4,8(185)1(1)1()2(dxx 所以所以TT)4,8(185)2,2(T)98,92(次迭代：次迭代：第第 2.)916,98(2Tg 21221|gg .81448)916()98(2222 )1(12)2(dgd TT)4,8(814)916,98(T)4,1(8140 )2()2()2(22AdddgTT 412004)4,1()8140(41)916,98(81402209)2(2)2()3(dxx TT)4,1(8140209)98,92(T)0,0(Tg)0,0(3 即为所求极小点。即为所求极小点。)3(x3.用于一般函

18、数的共轭梯度法nRxtsxf.)(min共轭梯度法进行修改：共轭梯度法进行修改：对用于正定二次函数的对用于正定二次函数的确确定定。）计计算算，需需由由一一维维搜搜索索不不能能利利用用公公式式（搜搜索索步步长长3)2(i。速下降方向，即速下降方向，即第一个搜索方向仍取最第一个搜索方向仍取最)()1()1()1(xfd 算算：其其它它搜搜索索方方向向按按下下式式计计,)()()1()1(iiiidxfd 。其中其中2)(2)1(|)(|)(|iiixfxf 此此时时可可采采取取一一定定能能满满足足停停止止条条件件，算算法法在在有有限限步步迭迭代代后后不不)3(如如下下措措施施：没没有有求求成成一一轮轮搜搜索索后后，如如果果还还次次迭迭代代为为一一轮轮，每每次次完完以以n新的初始点，新的初始点，的最后一个迭代点作为的最后一个迭代点作为得极小点，则以上一轮得极小点，则以上一轮一轮搜索。一轮搜索。一个搜索方向，开始下一个搜索方向，开始下取最速下降方向作为第取最速下降方向作为第注注，如如算算采采用用其其它它形形式式的的公公式式计计在在共共轭轭梯梯度度法法中中，也也可可i。）共轭梯度法共轭梯度法PRPgggggiTiiiTii()(11 其他详见其他详见P121.