优化设计-梯度法和共轭梯度法

梯度法和共轭梯度法 1. 无约束最优化问题 2. 梯度法 3. 共轭梯度法 一. 无约束最优化问题 无约束最优化问题 n Rxts xf .. )(min 有一阶连续偏导数。其中 )(xf 解析方法：利用函数的解析性质构造迭代公式使之收敛到最优解。 二. 梯度法（最速下降法） 迭代公式： k k kk dxx 1 如何选择下降最快的方向？ )( k xf )( k xf 函数值下降最快的方向 函数值增加最快的方向 函数值下降的方向 k x 梯度法（最速下降法）： 也称为最速下降方向；搜索方向： ,)(.1 kk xfd  。即满足取最优步长搜索步长 )(min)(,:.2 kkkk k k dxfdxf    梯度法算法步骤： 。令允许误差给定初始点 1,0,.1 1  kRx n  ;)(.2 kk xfd 计算搜索方向 k kk xd  否则，求最优步长为所求极值点；则停止计算，若 ,||||.3  。使得 )(min)( kkkk k dxfdxf    。转令令 2,1:,.4 1  kkdxx kk kk  ,)1,2(,3)(min:. 12 2 2 1 T xxxxf  设初始点为用最速下降法求解例 。求迭代一次后的迭代点 2x 解： ,)6,2()( 21 T xxxf  .)6,4()( 11 T xfd  .)61,42( 11 T dx   ，令 2211 )61(3)42()()(   dxf )(min   求解 0)61(36)42(8)(  令 62 13 1   T dxx ) 31 8 , 31 36 ( 1 1 12   最速下降法的程序流程图 锯齿现象 ，其等值面近似数可以用二次函数近似在极小点附近，目标函 椭球面。 1 x * x 2 x 3 x 它只是。标函数的一种局部性质最速下降方向反映了目 快的方向。局部目标函数值下降最 注  的算法。最速下降法是线性收敛 共轭梯度法 :共轭梯度法eevesRFletcher  代点向相结合，利用已知迭将共轭性和最速下降方基本思想： 进行搜索，求出共轭方向，并沿此方向处的梯度方向构造一组 函数的极小点。 以下分析算法的具体步骤。 cxbAxxxf TT  2 1 )(min 是常数。，是对称正定矩阵，其中 cRbARx nn  , 三.共轭梯度法 ；，第一个搜索方向取为任取初始点 )()1( )1()1()1( xfdx  ，令，若，设已求得点 )(0)()2( )1(1 )1()1(     kk kk xfgxfx : )1( 按如下方式确定则下一个搜索方向 kd )1( )( 1 )1( k kk k dgd   令 共轭。关于和 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 Add kk )()1(  ？如何确定 k ，得）式两边同时左乘则在（ Ad Tk )( 1 )()( 1 )()1()( 0 kTk kk TkkTk dAdAgdAdd    )2( )()( 1 )( kTk k Tk k dAd gAd 解得 :)3( 搜索步长的确定 ，步长利用一维搜索确定最优和搜索方向已知迭代点 k kk dx ,)()( 。即求解 )(min )()( kk dxf    ,)()( )()( kk dxf  记 ，令 0)()( )()()(  kTkk ddxf  ，即有 0])([ )()()(  kTkk dbdxA  ，则有令 bAxxfg kkk  )()( )( ，0][ )()(  kTkk dAdg  )3( )()( )( kTk kT k k Add dg 解得 3定理 次算法在，对于正定二次函数 nmFRcxbAxxxf TT  2 1 )( ），下列关系成立（且对所有的一维搜索后即终止，并 mii 1 ;1,,2,1,0)1( )()(  ijAdd j Ti  ;1,,2,1,0)2(  ijgg j T i  。i T i iT i ggdg  )( )3( 注 共轭的。是可知搜索方向）由定理（ Addd m)()2()1( ,,,31  则构造的搜索必须取负梯度方向，否算法中第一个搜索方向)2( 方向不能保证共轭性。 ）可知，的（由定理 33)3( ,0|||| 2)(  ii T i iT i gggdg 处的下降方向。是迭代点所以 )()( ii xd 的计算公式可以简化。算法中，由定理 iFR 3)4( )()( 1 )( iTi i Ti i Add gAd  )()( )( 1 iTi iT i Add dAg  ]/)([ ]/)([ )()1()( )()1( 1 i iiTi i iiT i xxAd xxAg         .)( )()( bxAxfg ii i  )( )( 1 )( 11 ii Ti ii T i i ggd ggg      i Ti i gd g )( 2 1 ||||    )4( |||| |||| 2 2 1 i i g g  算法步骤：FR 。，令精度要求，任取初始点 1.1 )1( kx  为所求极小点；停止，若令 )1(1 )1( 1 ,||||,)(.2 xgxfg  。令，）计算利用公式（否则，令 )1(1 )1()2( 11 )1( 3, dxxgd   为所求极小点；停止，若令 )1(1 )1( 1 ,||||,)(.3      k k k k xgxfg  ）计算。用公式（其中否则，令 4,)(1 )1( k k kk k dgd    。转，令）计算利用公式（ 3,3.4 )()()1( kk kk k dxx    。令 1:  kk 算法求解下述问题：用例 FR 2 2 2 12)(min xxxf  。初始点取为 Tx )2,2()1(  解： .)2,4()( 21 T xxxf  次迭代：第 1 ,)4,8(1 )1( T gd 令 )1()1( )1( 1 1 Add dg T T  , 20 04 ),( 2 1 )( 2 1 21              x x xxxf . 20 04        A 而                         4 8 20 04 )4,8( 4 8 )4,8( 18 5  )1( 1 )1()2( dxx 所以 TT )4,8( 18 5 )2,2(  T) 9 8 , 9 2 (   次迭代：第 2 .) 9 16 , 9 8 (2 T g   2 1 2 2 1 |||| |||| g g   . 81 4 48 ) 9 16 () 9 8 ( 22 22      )1( 12 )2( dgd  TT )4,8( 81 4 ) 9 16 , 9 8 (    T )4,1( 81 40  )2()2( )2( 2 2 Add dg T T                       4 1 20 04 )4,1() 81 40 ( 4 1 ) 9 16 , 9 8 ( 81 40 2 20 9  )2( 2 )2()3( dxx  TT )4,1( 81 40 20 9 ) 9 8 , 9 2 (    T )0,0( T g )0,0(3  即为所求极小点。)3(x