Lecture9_使用導(dǎo)數(shù)的最優(yōu)化方法

1、最優(yōu)化方法最優(yōu)化方法 Optimization第九章第九章 使用導(dǎo)數(shù)的最優(yōu)化方法使用導(dǎo)數(shù)的最優(yōu)化方法無約束優(yōu)化問題算法無約束優(yōu)化問題算法 最速下降法最速下降法 牛頓法牛頓法 共軛梯度法共軛梯度法 擬牛頓法擬牛頓法 信賴域法信賴域法 最小二乘法最小二乘法最速下降法最速下降法最速下降方向最速下降方向min( ). .( )nf xstxEf x具有一階連續(xù)偏導(dǎo)數(shù)取搜索方向取搜索方向:)()()(kkxfd步驟步驟:. 1, 0,. 1)1(kExn置允許誤差給定初點).(. 2)()(kkxfd計算搜索方向).(min)(. 3)()(0)()()()()(kkkkkkkkkdxfdxfdxd，使

2、進行一維搜索，求沿出發(fā)，從，則停止計算；否則，若. 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(進行一維搜索，求步長出發(fā)，沿方向從dx)(min)(min)1()1(00dxf.) 12() 12()(,)2,2(22)1()1(Tdx210) 12(4) 12(4)(1，得令第二次迭代第二次迭代為最優(yōu)解。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 設(shè)是連續(xù)可微實函數(shù)，解集合，最速下降算法產(chǎn)生的序列含于某個緊集，則序列的每個聚點。二次函數(shù)情形二次函數(shù)情形1( )2TTf xx Qxb x10n nnQaA其中是正定矩陣，其特征值為( )*,*0.1( )* ,21( )( )*.2TTf xxQxbE xxxQ xxE xf xxQx 設(shè)的唯一極小點為則定義函數(shù)則( )( )( )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設(shè)是一個正定對稱矩陣，則對任意的有其中 和 分別是的最小和最大特征值定理（最速下降法定理（最速下降法二次情形）二次情形）(0)2(1)(

5、 )( )*,1( )* .2nkkTxEf xxkAaE xE xAaE xxxQ xx對任意，最速下降法產(chǎn)生的序列收斂于的唯一極小點而且，對任意的有其中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例：考慮二次函數(shù)其中其最小特征值最大特征值每次迭代將使目標(biāo)函數(shù)的誤差減至十分之一以上.等價于每次迭代將增加大約一位數(shù)字的精確度.( )0012.156363522.174406232.17464

6、4042.174658552.174659562.1746595kkfx2()()2( )()0()kkfxxHessefxaAxxfxAaAafx設(shè)存在連續(xù)二階偏導(dǎo)數(shù)， 是局部極小點，矩陣的最小特征值，最大特征值為 ，算法產(chǎn)生的序列收斂于點 ，則目標(biāo)函數(shù)值的序列以不大于的收斂比線性的收斂于。定理：定理：22=,11.1AraAarAar令則條件數(shù)條件數(shù)非二次情形非二次情形結(jié)論：在相繼兩次迭代中結(jié)論：在相繼兩次迭代中,梯度方向互相正交梯度方向互相正交.正交。與即方向得的極小點，令出發(fā)沿方向為求出從證明：令)()(0)()(0)()()()()()()()1()1()()1()()()()()(

7、)()()()(kkkkkTkkTkkkkkkkkkkxfdxfdxfxfddxfdxxfddxfEx 陳寶林書陳寶林書 P3281. (1)x并從出發(fā)用最速下降法求極小點，迭代次。基本思想基本思想用一個二次函數(shù)去近似目標(biāo)函數(shù)用一個二次函數(shù)去近似目標(biāo)函數(shù)f f( (x x),),然后精確地求出這個二次函數(shù)的極小點然后精確地求出這個二次函數(shù)的極小點. .牛頓法牛頓法()()()()()()2()()()2()()2()(1)()2()1( )*( )( )( )()() ()1()()()2( )( )()()()0()()(kkkkTkkTkkkkkkkkkxfxxkfxxTaylorfxxf

8、xfxxxxxfxxxxxfxfxxxfxxxfxfx 設(shè)是的極小點的第 次近似，將在點作二階展開，得為求的極小點，令設(shè)可逆，則得)()2()1()()()kkkkdfxfx 。令牛頓牛頓方向方向定理：定理：21(1)1212(1)22112( )( )0( ),01( )( )( )()( )nf xxExf xf xxxk kk kxXx xxxxf xf xf xxxf xkkxxx 設(shè)為二次可微函數(shù)， 滿足，且存在。又設(shè)充分接近，使得存在，滿足，且對每一個和成立，則牛頓法產(chǎn)生的序列收斂于 。21212121221212( )( )( ).( )0( )( )()( ) ( )( )(

9、) ( )( )( )()( )( )( )( )()kxXxxyxf xf xf xyxxf xf xxxxf xf xf xf xf xf xf x xxyxf xf xf xf x xxk kxxxxxXX 令，且，又令因為因迭代產(chǎn)生的序列。易知為緊集，因此迭代產(chǎn)生的( )kxx序列含于緊集中。所以迭代產(chǎn)生的序列必收斂于 。牛頓法計算步驟牛頓法計算步驟:。置允許誤差給定初點0, 0,. 1)0(kExn。轉(zhuǎn)，則停止計算；否則，若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法求解無約束問題會出現(xiàn)以下情形：法求解無

13、約束問題會出現(xiàn)以下情形：（1）收斂到極小點）收斂到極小點（2）收斂到鞍點）收斂到鞍點（3）Hesse矩陣不可逆，無法迭代下去矩陣不可逆，無法迭代下去優(yōu)點優(yōu)點:（1）Newton法產(chǎn)生的點列法產(chǎn)生的點列x(k)若收若收斂，則收斂速度快斂，則收斂速度快-具有至少二階收斂速率。具有至少二階收斂速率。.*)()()(,.*, 0)(21)(,:1)0(1)0()0(1)0(2)0()1()0(1xbAbAxAxxfxfxxxNewtonbAxbAxxfcxbAxxxfATT得出發(fā)從任一點迭代公式若用得令且正定矩陣為對稱設(shè)證明(2) Newton法具有二次終止性法具有二次終止性缺點缺點:（1）可能會出現(xiàn)

14、在某步迭代時，目標(biāo)）可能會出現(xiàn)在某步迭代時，目標(biāo)函數(shù)值上升函數(shù)值上升.（2）當(dāng)初始點遠離極小點時，牛頓法）當(dāng)初始點遠離極小點時，牛頓法產(chǎn)生的點列可能不收斂，或者收斂到鞍產(chǎn)生的點列可能不收斂，或者收斂到鞍點，或者點，或者Hesse矩陣不可逆，無法計算矩陣不可逆，無法計算.（3）需要計算）需要計算Hesse矩陣，計算量大矩陣，計算量大.步驟步驟:。置允許誤差給定初點1, 0,. 1)1(kExn。，計算1)(2)()()(. 2kkxfxf).()(,)(. 3)(1)(2)()(kkkkxfxfdxf則停止迭代；否則，令若阻尼牛頓法阻尼牛頓法)()()1()()()()()()(),()(min

15、. 4kkkkkkkkkkkdxxdxfdxfdx令作一維搜索：出發(fā)，沿方向從。，轉(zhuǎn)置21:. 5 kk。置允許誤差給定初點1,0,.1)1(kExn()2()()()2.()()()3kkkkkfxGfxfxx 計算，。若，則停止計算，得點；否則轉(zhuǎn) 。()1()3.,().kkkkkkkkkBGIBdBf x 置其中是一個非負數(shù)，選取，使得是對稱正定矩陣，計算修正牛頓方向)()()1()()()()()()(),()(min.4kkkkkkkkkkkdxxdxfdxfdx令作一維搜索：出發(fā)，沿方向從。，轉(zhuǎn)置21:. 5 kk修正牛頓法修正牛頓法Ex 陳寶林書陳寶林書 P328 2 并用牛頓法

16、從給定點處出發(fā)求解極小點并用牛頓法從給定點處出發(fā)求解極小點共軛方向法共軛方向法共軛方向共軛方向定義：定義：正交。共軛，或稱它們關(guān)于則稱這兩個方向關(guān)于滿足和向中的兩個方對稱正定矩陣，若是設(shè)AAAddddEnnATn0)()2()1()2()1(個共軛方向。的共軛的，或稱它們?yōu)閯t稱這組方向是共軛，即滿足關(guān)于個方向，它們倆倆中是若kAAkjijiAddAkEdddjTink, 1, 0)(,)()()()2()1(例：例：(1)(1)(2)(2)(3)(3)(1)(1)11103020131121111212131001223TxyxyxyAxAy 則定理定理112( )( )( ),kAndddk

17、Ak設(shè)設(shè) 是是 階階對對稱稱正正定定矩矩陣陣，是是 個個 共共軛軛的的非非零零向向量量，則則這這 個個向向量量線線性性無無關(guān)關(guān)。證明：證明：線性無關(guān)。正定，所以又因為，所以有共軛的非零向量，個是因為，左乘，使得設(shè)存在數(shù))()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設(shè)設(shè)有有二二次次函函數(shù)數(shù)，其其中中是是對對稱稱正正定定矩矩陣陣，是是共共軛軛的的非非零零向向量量，從從任任意意一一點點出出發(fā)發(fā)，依依次次沿沿這這組組向向量量進進行行一一維維搜搜索索，則則。證明：證明：., 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設(shè)設(shè)有有二二次次函函數(shù)數(shù)，其其中中是是對對稱稱正正定定矩矩陣陣，是是 共共軛軛的的非非零零向向量量，從從任任意意一一點點出出發(fā)發(fā)，依依次次沿沿這這組組向向量量進進行行一一維維搜

20、搜索索，則則至至多多經(jīng)經(jīng)過過步步收收斂斂，即即是是在在上上的的極極小小點點(0)(1)(1)(0)(0)(0)(1)(1)011( )( )(0)( )(0)( )(1)01*( )( *)*0,*:( *)TTTTnnnnnnjjjjnnjxEf xEf xAxbdddAExxxxa da daddAdA xxa dAdadAda證明：設(shè)是在上的極小點，則為一組 共軛的非零向量，線性無關(guān)，即構(gòu)成的一組基可由這組向量線性表出，令兩邊左乘( )(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與已經(jīng)得到的共軛向量與已經(jīng)得到的共軛向量d(k-1)的線性組合來確定。的線性組合來確定。1in2m()TTfxxA xbxc11111112111111111111121122000( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( )( ),(),*,*TTTTTxdgxdggf xdxxddAddAdxxgxxgdgd 選選取取初初始始點點，取取從從出出發(fā)發(fā)，沿沿做

23、做一一維維搜搜索索，當(dāng)當(dāng)時時。若若（否否則則迭迭代代終終止止），則則與與線線性性無無關(guān)關(guān)。2121111212212111112211( )( )( )( )(2)( )( )( )( )( )( )( )( )( )( )(2)( )(2)(2)22222(2)(2)(2)(2)(2)(2)0()()TTTTTTTTTTTTTdgddAdAddAgdAgdgddAddAdxdggf xdggf xddAddAddAd 令令用用左左乘乘上上式式，并并令令，得得從從出出發(fā)發(fā)，沿沿做做一一維維搜搜索索，得得以此類推，得以此類推，得)()()()()1()1()1()1(1)1(1)(kkkTkkk

24、kkkkkkkkkkkkAddggdxxAddAgddgdTTT( )()()()(1),(1)(2)0,1, 2,1;(3).(00,1, 2,1;)FRTTijTiTiiiiijdAdjmniimggjigdggdi 定定 理理 ： 對對 正正 定定 二二 次次 函函 數(shù)數(shù) ，法法 在在次次 一一 維維 搜搜 索索 后后 終終 止止 ，且且 對對下下 列列 關(guān)關(guān) 系系 式式 成成 立立 ：蘊蘊 含含( )(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 證明：（用歸納法）時，成立。時，由構(gòu)造法，即成立。由一維搜索性質(zhì)，而成立。成立。(1)( )( )(1)(1)( )( )( )( )( )1( )( )( )( )( )( )1( )( )(1)1(2)()()0iiiiiiiiiiiiiiiiTTiiiiii Tii TiTTi TTijiijTi TjjijijTijixxdf xAxbAxAdbf xAdggAdgggddAddAdgggdAgggdAddggd 歸納假設(shè)即其中( )( )( )(1)1( )(1)100i Tji Tjij

26、TTi TjijijijAddAdijggggdAdij )2(1)3(),2(),1 ( ,3先證也成立。均成立，下證對假設(shè)對某個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 若由，以下假設(shè)。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共軛梯度法共軛梯度法( (二次凸函數(shù)二次凸函數(shù)) )111111221111112031014 ( )()()()( - )-()()()()()()()()-.().-.5.kkkkkkkkTkkkkkTkTkkk