Lecture9_使用导数的最优化方法

1、最优化方法最优化方法 Optimization第九章第九章 使用导数的最优化方法使用导数的最优化方法无约束优化问题算法无约束优化问题算法 最速下降法最速下降法 牛顿法牛顿法 共轭梯度法共轭梯度法 拟牛顿法拟牛顿法 信赖域法信赖域法 最小二乘法最小二乘法最速下降法最速下降法最速下降方向最速下降方向min( ). .( )nf xstxEf x具有一阶连续偏导数取搜索方向取搜索方向:)()()(kkxfd步骤步骤:. 1, 0,. 1)1(kExn置允许误差给定初点).(. 2)()(kkxfd计算搜索方向).(min)(. 3)()(0)()()()()(kkkkkkkkkdxfdxfdxd，使

2、进行一维搜索，求沿出发，从，则停止计算；否则，若. 21:. 4)()()1(，返回，置令kkdxxkkkk带精确线搜索的最速下降法带精确线搜索的最速下降法例例:22(1)12min( )(1)(1)(0,0) ,15.Tf xxxxe求，取第一次迭代第一次迭代Txxxf) 1(2),1(2)(21解解:22,)2, 2()2, 2()1()1(ddTT.1)1()1(进行一维搜索，求步长出发，沿方向从dx)(min)(min)1()1(00dxf.) 12() 12()(,)2,2(22)1()1(Tdx210) 12(4) 12(4)(1，得令第二次迭代第二次迭代为最优解。TTdd) 1,

3、 1 (,0)0, 0()2()2(.) 1, 1 ()1(1)1()2(Tdxx令Txxxf) 1(2),1(2)(21最速下降法的收敛性最速下降法的收敛性( )( )( ) |( )0kkf xxf xxxx 设是连续可微实函数，解集合，最速下降算法产生的序列含于某个紧集，则序列的每个聚点。二次函数情形二次函数情形1( )2TTf xx Qxb x10n nnQaA其中是正定矩阵，其特征值为( )*,*0.1( )* ,21( )( )*.2TTf xxQxbE xxxQ xxE xf xxQx 设的唯一极小点为则定义函数则( )( )( )deff xE xQxbg x (1)( )(

4、)( )( )( ).kkkkkkkkkkxxdxggfxQxb 其中最速下降法表示为最速下降法表示为( )( )( )( )( )12TkkkTkkkkkTkkkkkTkkfxgxgQ xgbxgggfxgg Qg在处达到极小。(1)( )TkkkkkTkkggxxgg Qg2(1)()111.TkkkkTTkkkkggE xE xgQggQg引理最速下降法满足Kantorovich不等式不等式221,4.n nTTTQxx xaAx Qxx QxaAaAQ设是一个正定对称矩阵，则对任意的有其中 和 分别是的最小和最大特征值定理（最速下降法定理（最速下降法二次情形）二次情形）(0)2(1)(

5、 )( )*,1( )* .2nkkTxEf xxkAaE xE xAaE xxxQ xx对任意，最速下降法产生的序列收敛于的唯一极小点而且，对任意的有其中21( ),20.780.020.120.140.020.860.040.060.120.040.720.080.140.060.080.740.76,0.08,1.12,0.680.52,0.940.081TTTf xx Qxb xQbaAAaAa例：考虑二次函数其中其最小特征值最大特征值每次迭代将使目标函数的误差减至十分之一以上.等价于每次迭代将增加大约一位数字的精确度.( )0012.156363522.174406232.17464

6、4042.174658552.174659562.1746595kkfx2()()2( )()0()kkfxxHessefxaAxxfxAaAafx设存在连续二阶偏导数， 是局部极小点，矩阵的最小特征值，最大特征值为 ，算法产生的序列收敛于点 ，则目标函数值的序列以不大于的收敛比线性的收敛于。定理：定理：22=,11.1AraAarAar令则条件数条件数非二次情形非二次情形结论：在相继两次迭代中结论：在相继两次迭代中,梯度方向互相正交梯度方向互相正交.正交。与即方向得的极小点，令出发沿方向为求出从证明：令)()(0)()(0)()()()()()()()1()1()()1()()()()()(

7、)()()()(kkkkkTkkTkkkkkkkkkkxfdxfdxfxfddxfdxxfddxfEx 陈宝林书陈宝林书 P3281. (1)x并从出发用最速下降法求极小点，迭代次。基本思想基本思想用一个二次函数去近似目标函数用一个二次函数去近似目标函数f f( (x x),),然后精确地求出这个二次函数的极小点然后精确地求出这个二次函数的极小点. .牛顿法牛顿法()()()()()()2()()()2()()2()(1)()2()1( )*( )( )( )()() ()1()()()2( )( )()()()0()()(kkkkTkkTkkkkkkkkkxfxxkfxxTaylorfxxf

8、xfxxxxxfxxxxxfxfxxxfxxxfxfx 设是的极小点的第 次近似，将在点作二阶展开，得为求的极小点，令设可逆，则得)()2()1()()()kkkkdfxfx 。令牛顿牛顿方向方向定理：定理：21(1)1212(1)22112( )( )0( ),01( )( )( )()( )nf xxExf xf xxxk kk kxXx xxxxf xf xf xxxf xkkxxx 设为二次可微函数， 满足，且存在。又设充分接近，使得存在，满足，且对每一个和成立，则牛顿法产生的序列收敛于 。21212121221212( )( )( ).( )0( )( )()( ) ( )( )(

9、) ( )( )( )()( )( )( )( )()kxXxxyxf xf xf xyxxf xf xxxxf xf xf xf xf xf xf x xxyxf xf xf xf x xxk kxxxxxXX 令，且，又令因为因迭代产生的序列。易知为紧集，因此迭代产生的( )kxx序列含于紧集中。所以迭代产生的序列必收敛于 。牛顿法计算步骤牛顿法计算步骤:。置允许误差给定初点0, 0,. 1)0(kExn。转，则停止计算；否则，若3)(. 2)(kxf。，返回置，计算21:)()(. 3)(1)(2)()1(kkxfxfxxkkkk222125)(min:xxxf求例00100450100

10、2122)()(5010021)(50002)(1004502)(,)2, 2(:)0(1)0(2)0()1(1)0(2)0(221)0()0()0(xfxfxxxfxfxxxfxxT则取解22212123:min( )4(1,1) ,(3,4) ,(2,0) ,10.TTABTCfxxxx xxxx例 求分 别 取 初 始 点 为精 度 要 求22212122112212121( )4( )82, 2822( ).22Tfxxxx xfxxx xxxxxfxx解 ： (1)1(1,1) ,TAxx取则( )( )( )( )2( )11.00004.0006.00006.08286.0000

11、2.00001.00001.00002.0002.000020.75004.51567.87508.449510.5001.50001.25003.06251.50002.000030.15500.12731.29111.33888.33000.31000.165kkkkkkxfxfxfxfx00.35400.31002.000040.00570.00030.04590.05118.02220.01150.01110.02230.01152.000050.00000.00000.00010.00018.00000.00000.00000.00000.00002.0000 (1)2(3,4) ,

12、TBxx取则( )( )( )( )2( )13.000016.0000.00001.00000.00006.00004.00001.00006.0002.000022.833316.00000.00000.02780.00005.66674.00000.20785.66672.000032.828416.00000.00000.00000.00005.65694.00kkkkkkxfxfxfxfx000.00005.65692.0000 (1)2(1)3(2,0) ,84=42TCxxfxHesse取得到由于矩阵不可逆，无法进行下一步。用用Newton法求解无约束问题会出现以下情形：法求解无

13、约束问题会出现以下情形：（1）收敛到极小点）收敛到极小点（2）收敛到鞍点）收敛到鞍点（3）Hesse矩阵不可逆，无法迭代下去矩阵不可逆，无法迭代下去优点优点:（1）Newton法产生的点列法产生的点列x(k)若收若收敛，则收敛速度快敛，则收敛速度快-具有至少二阶收敛速率。具有至少二阶收敛速率。.*)()()(,.*, 0)(21)(,:1)0(1)0()0(1)0(2)0()1()0(1xbAbAxAxxfxfxxxNewtonbAxbAxxfcxbAxxxfATT得出发从任一点迭代公式若用得令且正定矩阵为对称设证明(2) Newton法具有二次终止性法具有二次终止性缺点缺点:（1）可能会出现

14、在某步迭代时，目标）可能会出现在某步迭代时，目标函数值上升函数值上升.（2）当初始点远离极小点时，牛顿法）当初始点远离极小点时，牛顿法产生的点列可能不收敛，或者收敛到鞍产生的点列可能不收敛，或者收敛到鞍点，或者点，或者Hesse矩阵不可逆，无法计算矩阵不可逆，无法计算.（3）需要计算）需要计算Hesse矩阵，计算量大矩阵，计算量大.步骤步骤:。置允许误差给定初点1, 0,. 1)1(kExn。，计算1)(2)()()(. 2kkxfxf).()(,)(. 3)(1)(2)()(kkkkxfxfdxf则停止迭代；否则，令若阻尼牛顿法阻尼牛顿法)()()1()()()()()()(),()(min

15、. 4kkkkkkkkkkkdxxdxfdxfdx令作一维搜索：出发，沿方向从。，转置21:. 5 kk。置允许误差给定初点1,0,.1)1(kExn()2()()()2.()()()3kkkkkfxGfxfxx 计算，。若，则停止计算，得点；否则转 。()1()3.,().kkkkkkkkkBGIBdBf x 置其中是一个非负数，选取，使得是对称正定矩阵，计算修正牛顿方向)()()1()()()()()()(),()(min.4kkkkkkkkkkkdxxdxfdxfdx令作一维搜索：出发，沿方向从。，转置21:. 5 kk修正牛顿法修正牛顿法Ex 陈宝林书陈宝林书 P328 2 并用牛顿法

16、从给定点处出发求解极小点并用牛顿法从给定点处出发求解极小点共轭方向法共轭方向法共轭方向共轭方向定义：定义：正交。共轭，或称它们关于则称这两个方向关于满足和向中的两个方对称正定矩阵，若是设AAAddddEnnATn0)()2()1()2()1(个共轭方向。的共轭的，或称它们为则称这组方向是共轭，即满足关于个方向，它们俩俩中是若kAAkjijiAddAkEdddjTink, 1, 0)(,)()()()2()1(例：例：(1)(1)(2)(2)(3)(3)(1)(1)11103020131121111212131001223TxyxyxyAxAy 则定理定理112( )( )( ),kAndddk

17、Ak设设 是是 阶阶对对称称正正定定矩矩阵阵，是是 个个 共共轭轭的的非非零零向向量量，则则这这 个个向向量量线线性性无无关关。证明：证明：线性无关。正定，所以又因为，所以有共轭的非零向量，个是因为，左乘，使得设存在数)()2()1()()()()()()2()1()()()2(2)1(121,000,0,kiiiiiikikkkdddAddAAddAkdddAddddTTT定理定理2：011001100 1120 11( )( )()( )( )( )( )( )()( )( )()( )( ),min()(), ,(), ,TTnn nnkkkkkkkkkkTjf xx Axb xcAdd

18、dAxEf xdf xdxxdknf xdjk设设有有二二次次函函数数，其其中中是是对对称称正正定定矩矩阵阵，是是共共轭轭的的非非零零向向量量，从从任任意意一一点点出出发发，依依次次沿沿这这组组向向量量进进行行一一维维搜搜索索，则则。证明：证明：., 1 , 0, 0)(, 0)()()(:)()()()()()()()()1()1()1()0()()1(1)()()()1()()1()(1)()1()1(1)()1(1)()1()()1(1)1()()1(1)1()()()()()1()1(kjdxfAddddxfdAddxfdxfdAdxfxfAdxfbAdAxbAdAdAxbAddxAb

19、AdAxbdxAbAxxfbAxxfjTknjTjkjijTiijTjjTkjkjiTiiTjTkkjiiijkjiiijkkkkkkkkkkkkkkkkkkTT共轭的是右乘定理定理3：011001120 11( )( )()( )( )( )( )( )()( )( )( )( ),min()(), ,( ).TTnn nnkkkkkkkkknnf xx Axb xcAdddAxEf xdf xdxxdknxf xEn设设有有二二次次函函数数，其其中中是是对对称称正正定定矩矩阵阵，是是 共共轭轭的的非非零零向向量量，从从任任意意一一点点出出发发，依依次次沿沿这这组组向向量量进进行行一一维维搜

20、搜索索，则则至至多多经经过过步步收收敛敛，即即是是在在上上的的极极小小点点(0)(1)(1)(0)(0)(0)(1)(1)011( )( )(0)( )(0)( )(1)01*( )( *)*0,*:( *)TTTTnnnnnnjjjjnnjxEf xEf xAxbdddAExxxxa da daddAdA xxa dAdadAda证明：设是在上的极小点，则为一组 共轭的非零向量，线性无关，即构成的一组基可由这组向量线性表出，令两边左乘( )(0)( )(0)( )( )( )( )( )(0)( )( )( *)(*)()(1)TTTTTTjjjjjjjjjdA xxdAxAxdAddAdd

21、bAxdAd (1)( )( )( )(0)(0)(1)(1)011( )( )( )(0)( )( )(0)( )( )( )( )(0)( )(0)( )( )( )( )( )(,:()()()1)(TTTTTTTTTkkkknnnjjnjnjjjjjjjjjjjnxxdxxddddAdA xxdAxAxdAddAdbAxdAxbdAdddAdf x另一方面，由依次递推得两边左乘与（ ）(0)( )(0)( ),0,1,1.*.jjnnajnxxxxxx比较，得：共轭梯度法共轭梯度法(FR法法)记号：记号：kkgxf)()( 在共轭梯度法中，初始点处的搜索方向取在共轭梯度法中，初始点处的

22、搜索方向取为该点的负梯度方向，即取为该点的负梯度方向，即取 1)1()1()(gxfd而以下各共轭方向而以下各共轭方向d(k)由第由第k次迭代点次迭代点x(k)处的负梯处的负梯度度-gk与已经得到的共轭向量与已经得到的共轭向量d(k-1)的线性组合来确定。的线性组合来确定。1in2m()TTfxxA xbxc11111112111111111111121122000( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( ),(),*,*TTTTTxdgxdggf xdxxddAddAdxxgxxgdgd 选选取取初初始始点点，取取从从出出发发，沿沿做

23、做一一维维搜搜索索，当当时时。若若（否否则则迭迭代代终终止止），则则与与线线性性无无关关。2121111212212111112211( )( )( )( )(2)( )( )( )( )( )( )( )( )( )( )(2)( )(2)(2)22222(2)(2)(2)(2)(2)(2)0()()TTTTTTTTTTTTTdgddAdAddAgdAgdgddAddAdxdggf xdggf xddAddAddAd 令令用用左左乘乘上上式式，并并令令，得得从从出出发发，沿沿做做一一维维搜搜索索，得得以此类推，得以此类推，得)()()()()1()1()1()1(1)1(1)(kkkTkkk

24、kkkkkkkkkkkkAddggdxxAddAgddgdTTT( )()()()(1),(1)(2)0,1, 2,1;(3).(00,1, 2,1;)FRTTijTiTiiiiijdAdjmniimggjigdggdi 定定 理理 ： 对对 正正 定定 二二 次次 函函 数数 ，法法 在在次次 一一 维维 搜搜 索索 后后 终终 止止 ，且且 对对下下 列列 关关 系系 式式 成成 立立 ：蕴蕴 含含( )(1)1(1)1(1)(1)TTkkkkkkkkkdgddAgdAd (1)(1)11(2)(1)(2)(1)(1)121(2)(1)21(2)(1)2221221(),(3)20,(1)

25、()00(2)()(3)TTTTTTigf xdgidAdf xddgggdgdgdggdgg 证明：（用归纳法）时，成立。时，由构造法，即成立。由一维搜索性质，而成立。成立。(1)( )( )(1)(1)( )( )( )( )( )1( )( )( )( )( )( )1( )( )(1)1(2)()()0iiiiiiiiiiiiiiiiTTiiiiii Tii TiTTi TTijiijTi TjjijijTijixxdf xAxbAxAdbf xAdggAdgggddAddAdgggdAgggdAddggd 归纳假设即其中( )( )( )(1)1( )(1)100i Tji Tjij

26、TTi TjijijijAddAdijggggdAdij )2(1)3(),2(),1 ( ,3先证也成立。均成立，下证对假设对某个imi( )( )( )(1)0(2)0(3).TijTijTiTiiidAdg gg dg g (1)( )1(1)( )( )( )( )( )( )11( )(1)( )1( )( )(1)( )1(1)( )( )( )( )()(1),)(0)()iiiiiiiiiiTiTjijTji Tjiiiii TiTiiiiiiiTiiidgddAdgdAdgAddAddAgijdAdggAxbAxbA xijdAxxAdxAd 若由，以下假设。1(1)( )(

27、 )( )()1( )( )1111)110jjiTjTi TjiijTTi TijijiiiijiijjggdAdgdAddggggdAggddA ( )( )( )(1)0(2)0(3).TijTijTiTiiidAdg gg dg g .0)()3(11)1(11111)1(111)1(11)1(11)(1)(111)(11)1(1iTiiTiTiiTiiiTiiiiiTiiTiiTiiiTiiiiTiiTiggdgggdgdgdggdgdgggdggdg( )( )( )(1)0(2)0(3).TijTijTiTiiidAdg gg dg g 2( )112( )( )(1,0).i Tiiiii TiigdAgigdAdg定理定理:22111)(1)(1111)(111)(111iiiTiiTiiTiiTiiTiiTiiiiTiiTiiiijjjjgggggggdgdggggggdgggggAd得证明：由( )( )( )(1)0(2)0(3).TijTijTiTiiidAdg gg dg g FRFR共轭梯度法共轭梯度法( (二次凸函数二次凸函数) )111111221111112031014 ( )()()()( - )-()()()()()()()()-.().-.5.kkkkkkkkTkkkkkTkTkkk