梯度法和共轭梯度法

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

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

3、1:,. 41 kkdxxkkkk ,)1 ,2(,3)(min:.12221Txxxxf 设设初初始始点点为为用用最最速速下下降降法法求求解解例例。求迭代一次后的迭代点求迭代一次后的迭代点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 .)()(

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

5、最速速下下降降法法是是线线性性收收敛敛几何解释几何解释设设有有二二次次函函数数)()(21)(xxAxxxfT 对对称称正正定定矩矩阵阵，是是其其中中nnA 是是一一个个定定点点。x的的等等值值面面则则函函数数)(xfcxxAxxT )()(21为为中中心心的的椭椭球球面面。是是以以 xx三、共轭方向法三、共轭方向法1. 何谓共轭方向？何谓共轭方向？由于由于,0)()( xxAxf,0)(2 AxfA所所以以正正定定，因因为为的极小点。的极小点。是是因此因此)(xfx,)(2Axf 而而x)()(21)(xxAxxxfT 点点，是是在在某某个个等等值值面面上上的的一一设设)0(x中中的的一一个

6、个方方向向，是是nRd)1(。搜搜索索得得到到点点以以最最优优步步长长沿沿着着)1()1()0(xdxo1xx)1(d)1(x)2(d)0(x)x(fx)(11 处的法向量为处的法向量为该等值面在点该等值面在点所所在在等等值值面面的的切切向向量量。是是点点则则)()(xd11. )()()1()1(xxAxf o1xx)1(d正交，正交，与与则则)()1()1(xfd 。即即0)()1()1( xfdT,)1()2(xxd 令令)1(x所以所以。0)2()1( AddT共共轭轭。小小点点的的向向量量关关于于指指向向极极向向量量与与由由这这一一点点即即等等值值面面上上一一点点处处的的切切A)2(

7、d)x(f1 2. 共轭方向共轭方向定义定义共共轭轭。关关于于和和，则则称称若若有有AddAddT21210 ARdddnk它们两两关于它们两两关于中一组非零向量，如果中一组非零向量，如果是是设设,21。共共轭轭，即即kjijiAddjTi,2,1,0 共共轭轭方方向向。组组共共轭轭的的，也也称称它它们们是是一一则则称称这这组组方方向向是是关关于于AA注注：002121 dddIdTT21dd 共轭是正交的推广。共轭是正交的推广。，和和中中的的两两个个非非零零向向量量的的对对称称正正定定矩矩阵阵，对对于于是是设设21ddRnnAn 是是单单位位矩矩阵阵，则则如如果果 A共共轭轭的的非非零零个个

8、是是阶阶对对称称正正定定矩矩阵阵，是是设设AkdddnAk,21性性无无关关。向向量量，则则这这个个向向量量组组线线. 1定理定理证明证明，使使得得设设存存在在实实数数k ,21,01 kiiid ，则则有有上上式式两两边边同同时时左左乘乘AdTj,01 kiiTjiAdd 可可化化简简为为共共轭轭的的向向量量，所所以以上上式式个个是是因因为为Akdddk,21.0 jTjjAdd ，是是正正定定矩矩阵阵，所所以以而而因因为为0,0 jTjjAddAd所以所以。kjj,2,1,0 线线性性无无关关。因因此此kddd,21. 2定理定理，设有函数设有函数cxbAxxxfTT 21)(共共轭轭向向

9、量量。一一组组是是阶阶对对称称正正定定矩矩阵阵。是是其其中中AdddnAk)()2()1(,进进行行搜搜索索，为为初初始始点点，依依次次沿沿以以任任意意的的)()2()1()1(,kndddRx 上上的的在在是是函函数数则则得得到到点点kkkBxxfxxxx )1()1()1()3()2()(,极极小小点点，其其中中,|1)(RdxxBikiiik 是是时时，当当，生生成成的的子子空空间间。特特别别地地是是由由)1()()2()1(, nkxnkddd上上的的唯唯一一极极小小点点。在在nRxf)(推论推论有有在在上上述述定定理理条条件件下下，必必。kidxfiTk,2,1,0)()()1( 3

10、、共轭方向法对于极小化问题对于极小化问题:法法为为共共轭轭方方向向法法是是正正定定矩矩阵阵，称称下下述述算算其其中中A,21)(mincxbAxxxfTT ；共共轭轭方方向向取取定定一一组组)()2()1(,)1(ndddA,)2()1()()1( kkxxx确确定定点点依依次次按按照照下下式式由由任任取取初初始始点点 )dx(fmin)dx(fdxx)k()k()k(k)k()k(k)k()k(1。满足满足直到某个直到某个0)()()( kkxfx注注至至多多经经过过求求解解上上述述极极小小化化问问题题，可可知知，利利用用共共轭轭方方向向法法由由定定理理2。次次迭迭代代必必可可得得到到最最优

11、优解解n四四. . 共轭梯度法共轭梯度法 ：如何选取一组共轭方向？如何选取一组共轭方向？q 二次函数情形二次函数情形q 非二次函数情形非二次函数情形:共轭梯度法共轭梯度法eevesRFletcher 代代点点向向相相结结合合，利利用用已已知知迭迭将将共共轭轭性性和和最最速速下下降降方方基基本本思思想想：进进行行搜搜索索，求求出出共共轭轭方方向向，并并沿沿此此方方向向处处的的梯梯度度方方向向构构造造一一组组函数的极小点。函数的极小点。以下分析算法的具体步骤。以下分析算法的具体步骤。cxbAxxxfTT 21)(min是常数。是常数。，是对称正定矩阵，是对称正定矩阵，其中其中cRbARxnn ,1

12、 1、 二次函数情形二次函数情形；，第第一一个个搜搜索索方方向向取取为为任任取取初初始始点点)()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()(0kTkkkTkkTkdAdAgdAdd )2()()(1)(kTkkTkkdAdgAd 解得解得:)3(

13、搜搜索索步步长长的的确确定定，步步长长利利用用一一维维搜搜索索确确定定最最优优和和搜搜索索方方向向已已知知迭迭代代点点kkkdx ,)()(。即即求求解解)(min)()(kkdxf , )()()()(kkdxf 记记，令令0)()()()()( kTkkddxf ，即即有有0)()()()( kTkkdbdxA ，则则有有令令bAxxfgkkk )()()(，0)()( kTkkdAdg )3()()()(kTkkTkkAdddg 解解得得3定理定理次次算法在算法在，对于正定二次函数对于正定二次函数nmFRcxbAxxxfTT 21)(），下下列列关关系系成成立立（且且对对所所有有的的一一

14、维维搜搜索索后后即即终终止止，并并mii 1;1,2,1,0)1()()( ijAddjTi;1,2,1,0)2( ijggjTi。iTiiTiggdg )()3(注注共共轭轭的的。是是可可知知搜搜索索方方向向）由由定定理理（Adddm)()2()1(,31则则构构造造的的搜搜索索必必须须取取负负梯梯度度方方向向，否否算算法法中中第第一一个个搜搜索索方方向向)2(方方向向不不能能保保证证共共轭轭性性。）可知，）可知，的（的（由定理由定理33)3(,0|2)( iiTiiTigggdg处处的的下下降降方方向向。是是迭迭代代点点所所以以)()(iixd的的计计算算公公式式可可以以简简化化。算算法法

15、中中，由由定定理理iFR 3)4()()(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 xxxxx

17、f.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(x2

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