梯法和共軛梯法PPT課件

1、一一. 無約束最優(yōu)化問題無約束最優(yōu)化問題無無約約束束最最優(yōu)優(yōu)化化問問題題nRxtsxf .)(min有有一一階階連連續(xù)續(xù)偏偏導(dǎo)導(dǎo)數(shù)數(shù)。其其中中)(xf解析法：利用函數(shù)的解析性質(zhì)構(gòu)造迭代公式。第1頁/共27頁二二. 梯度法（最速下降法）梯度法（最速下降法）迭代公式：kkkkdxx 1如何選擇下降最快的方向？)(kxf )(kxf 函函數(shù)數(shù)值值下下降降最最快快的的方方向向函函數(shù)數(shù)值值增增加加最最快快的的方方向向函數(shù)值下降的方向函數(shù)值下降的方向kx第2頁/共27頁梯度法（最速下降法）：也稱為最速下降方向；也稱為最速下降方向；搜索方向：搜索方向：, )(. 1kkxfd 。即即滿滿足足取取最最優(yōu)優(yōu)步步

2、長長搜搜索索步步長長)(min)(,:. 2kkkkkkdxfdxf 梯度法算法步驟：。令令允許誤差允許誤差給定初始點給定初始點1,0,. 11 kRxn ;)(. 2kkxfd 計算搜索方向計算搜索方向kkkxd 否則，求最優(yōu)步長否則，求最優(yōu)步長為所求極值點；為所求極值點；則停止計算，則停止計算，若若,|. 3 。使得使得)(min)(kkkkkdxfdxf 。轉(zhuǎn)轉(zhuǎn)令令令令2,1:,. 41 kkdxxkkkk 第3頁/共27頁,)1 ,2(,3)(min:.12221Txxxxf 設(shè)初始點為設(shè)初始點為用最速下降法求解用最速下降法求解例例。求迭代一次后的迭代點求迭代一次后的迭代點2x解：,)

3、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 第4頁/共27頁收斂性)(min)(kkkkkdxfdxf 。則有則有0)( kTkkkddxf 性質(zhì). 證證明明：所以所以，令令)()(kkdxf .)()(kTkkddxf )(min)(kkkkkdxfdxf .0)()( kTkkkkddxf 滿足滿足步長步長有一階連續(xù)偏導(dǎo)數(shù)，若有一階連續(xù)偏導(dǎo)數(shù)，若設(shè)設(shè)kxf )(注注：。kkkTkdddd 110)(

4、所所以以，因因為為梯梯度度法法的的搜搜索索方方向向)(1kkkkdxfd 第5頁/共27頁鋸齒現(xiàn)象鋸齒現(xiàn)象，其其等等值值面面近近似似數(shù)數(shù)可可以以用用二二次次函函數(shù)數(shù)近近似似在在極極小小點點附附近近，目目標標函函橢球面。橢球面。1x*x2x3x它它只只是是。標標函函數(shù)數(shù)的的一一種種局局部部性性質(zhì)質(zhì)最最速速下下降降方方向向反反映映了了目目快快的的方方向向。局局部部目目標標函函數(shù)數(shù)值值下下降降最最注注的的算算法法。最最速速下下降降法法是是線線性性收收斂斂第6頁/共27頁幾何解釋設(shè)設(shè)有有二二次次函函數(shù)數(shù))()(21)(xxAxxxfT 對對稱稱正正定定矩矩陣陣，是是其其中中nnA 是是一一個個定定點點

5、。x的的等等值值面面則則函函數(shù)數(shù))(xfcxxAxxT )()(21為為中中心心的的橢橢球球面面。是是以以 xx三、共軛方向法三、共軛方向法1. 何謂共軛方向？第7頁/共27頁由于由于,0)()( xxAxf,0)(2 AxfA所所以以正正定定，因因為為的極小點。的極小點。是是因此因此)(xfx,)(2Axf 而而x)()(21)(xxAxxxfT 點點，是是在在某某個個等等值值面面上上的的一一設(shè)設(shè))0(x中中的的一一個個方方向向，是是nRd)1(。搜搜索索得得到到點點以以最最優(yōu)優(yōu)步步長長沿沿著著)1()1()0(xdxo1xx)1(d)1(x)2(d)0(x第8頁/共27頁)x(fx)(11

6、 處的法向量為處的法向量為該等值面在點該等值面在點所所在在等等值值面面的的切切向向量量。是是點點則則)()(xd11. )()()1()1(xxAxf o1xx)1(d正交，正交，與與則則)()1()1(xfd 。即即0)()1()1( xfdT,)1()2(xxd 令令)1(x所以所以。0)2()1( AddT共共軛軛。小小點點的的向向量量關(guān)關(guān)于于指指向向極極向向量量與與由由這這一一點點即即等等值值面面上上一一點點處處的的切切A)2(d)x(f1 第9頁/共27頁2. 共軛方向定義定義共軛。共軛。關(guān)于關(guān)于和和，則稱，則稱若有若有AddAddT21210 ARdddnk它們兩兩關(guān)于它們兩兩關(guān)于

7、中一組非零向量，如果中一組非零向量，如果是是設(shè)設(shè),21。共軛，即共軛，即kjijiAddjTi,2,1,0 共共軛軛方方向向。組組共共軛軛的的，也也稱稱它它們們是是一一則則稱稱這這組組方方向向是是關(guān)關(guān)于于AA注注：002121 dddIdTT21dd 共軛是正交的推廣。，和和中的兩個非零向量中的兩個非零向量的對稱正定矩陣，對于的對稱正定矩陣，對于是是設(shè)設(shè)21ddRnnAn 是是單單位位矩矩陣陣，則則如如果果 A第10頁/共27頁共共軛軛的的非非零零個個是是階階對對稱稱正正定定矩矩陣陣，是是設(shè)設(shè)AkdddnAk,21性性無無關(guān)關(guān)。向向量量，則則這這個個向向量量組組線線. 1定理定理證明證明，使使

8、得得設(shè)設(shè)存存在在實實數(shù)數(shù)k ,21,01 kiiid ，則則有有上上式式兩兩邊邊同同時時左左乘乘AdTj,01 kiiTjiAdd 可可化化簡簡為為共共軛軛的的向向量量，所所以以上上式式個個是是因因為為Akdddk,21.0 jTjjAdd ，是是正正定定矩矩陣陣，所所以以而而因因為為0,0 jTjjAddAd所以所以。kjj,2,1,0 線性無關(guān)。線性無關(guān)。因此因此kddd,21第11頁/共27頁. 2定理定理，設(shè)有函數(shù)設(shè)有函數(shù)cxbAxxxfTT 21)(共共軛軛向向量量。一一組組是是階階對對稱稱正正定定矩矩陣陣。是是其其中中AdddnAk)()2()1(,進進行行搜搜索索，為為初初始始點

9、點，依依次次沿沿以以任任意意的的)()2()1()1(,kndddRx 上的上的在在是函數(shù)是函數(shù)則則得到點得到點kkkBxxfxxxx )1()1()1()3()2()(,極極小小點點，其其中中,|1)(RdxxBikiiik 是是時，時，當當，生成的子空間。特別地生成的子空間。特別地是由是由)1()()2()1(, nkxnkddd上上的的唯唯一一極極小小點點。在在nRxf)(推論推論有有在在上上述述定定理理條條件件下下，必必。kidxfiTk,2,1,0)()()1( 第12頁/共27頁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注注至多經(jīng)過至多經(jīng)過求解上述極小化問題，求解上述極小化問題，可知，利用共軛方向法可知，利用共軛方向法由定理由定理2。次次迭迭代代必必可可得得到到最最優(yōu)優(yōu)解解n第13頁/共27頁四四. . 共軛梯度法共軛梯度法 ：如何選取一組共軛方向？q 二次函數(shù)

11、情形二次函數(shù)情形q 非二次函數(shù)情形非二次函數(shù)情形第14頁/共27頁:共軛梯度法共軛梯度法eevesRFletcher 代代點點向向相相結(jié)結(jié)合合，利利用用已已知知迭迭將將共共軛軛性性和和最最速速下下降降方方基基本本思思想想：進進行行搜搜索索，求求出出共共軛軛方方向向，并并沿沿此此方方向向處處的的梯梯度度方方向向構(gòu)構(gòu)造造一一組組函數(shù)的極小點。函數(shù)的極小點。以下分析算法的具體步驟。cxbAxxxfTT 21)(min是常數(shù)。是常數(shù)。，是對稱正定矩陣，是對稱正定矩陣，其中其中cRbARxnn ,1 1、 二次函數(shù)情形二次函數(shù)情形第15頁/共27頁；，第第一一個個搜搜索索方方向向取取為為任任取取初初始始

12、點點)()1()1()1()1(xfdx ，令令，若若，設(shè)設(shè)已已求求得得點點)(0)()2()1(1)1()1( kkkkxfgxfx:)1(按按如如下下方方式式確確定定則則下下一一個個搜搜索索方方向向 kd)1()(1)1(kkkkdgd 令令共軛。共軛。關(guān)于關(guān)于和和要求要求Addkk)()1( ？如何確定如何確定k ，得得）式式兩兩邊邊同同時時左左乘乘則則在在（AdTk )(1)()(1)()1()(0kTkkkTkkTkdAdAgdAdd )2()()(1)(kTkkTkkdAdgAd 解得解得第16頁/共27頁:)3(搜搜索索步步長長的的確確定定，步步長長利利用用一一維維搜搜索索確確定

13、定最最優(yōu)優(yōu)和和搜搜索索方方向向已已知知迭迭代代點點kkkdx ,)()(。即求解即求解)(min)()(kkdxf , )()()()(kkdxf 記記，令令0)()()()()( kTkkddxf ，即有即有0)()()()( kTkkdbdxA ，則有，則有令令bAxxfgkkk )()()(，0)()( kTkkdAdg )3()()()(kTkkTkkAdddg 解得解得第17頁/共27頁3定理定理次次算法在算法在，對于正定二次函數(shù)對于正定二次函數(shù)nmFRcxbAxxxfTT 21)(），下下列列關(guān)關(guān)系系成成立立（且且對對所所有有的的一一維維搜搜索索后后即即終終止止，并并mii 1;1

14、,2,1,0)1()()( ijAddjTi;1,2,1,0)2( ijggjTi。iTiiTiggdg )()3(注注共共軛軛的的。是是可可知知搜搜索索方方向向）由由定定理理（Adddm)()2()1(,31則則構(gòu)構(gòu)造造的的搜搜索索必必須須取取負負梯梯度度方方向向，否否算算法法中中第第一一個個搜搜索索方方向向)2(方方向向不不能能保保證證共共軛軛性性。）可知，）可知，的（的（由定理由定理33)3(,0|2)( iiTiiTigggdg處的下降方向。處的下降方向。是迭代點是迭代點所以所以)()(iixd第18頁/共27頁的的計計算算公公式式可可以以簡簡化化。算算法法中中，由由定定理理iFR 3

15、)4()()(1)(iTiiTiiAddgAd )()()(1iTiiTiAdddAg / )( / )( )()1()()()1(1iiiTiiiiTixxAdxxAg .)()()(bxAxfgiii )()(1)(11iiTiiiTiiggdggg iTiigdg)(21| )4(|221iigg 第19頁/共27頁算算法法步步驟驟：FR。，令，令精度要求精度要求，任取初始點任取初始點1. 1)1( kx 為所求極小點；為所求極小點；停止，停止，若若令令)1(1)1(1,|, )(. 2xgxfg 。令令，）計算）計算利用公式（利用公式（否則，令否則，令)1(1)1()2(11)1(3,

16、dxxgd 為所求極小點；為所求極小點；停止，停止，若若令令)1(1)1(1,|, )(. 3 kkkkxgxfg ）計算。）計算。用公式（用公式（其中其中否則，令否則，令4,)(1)1(kkkkkdgd 。轉(zhuǎn)轉(zhuǎn)，令，令）計算）計算利用公式（利用公式（3,3. 4)()()1(kkkkkdxx 。令令1: kk第20頁/共27頁算算法法求求解解下下述述問問題題：用用例例FR22212)(minxxxf 。初始點取為初始點取為Tx)2,2()1( 解：解：.)2,4()(21Txxxf 次迭代：次迭代：第第1,)4,8(1)1(Tgd 令令)1()1()1(11AdddgTT ,2004),(2

17、1)(2121 xxxxxf.2004 A而而 482004)4,8(48)4,8(185 第21頁/共27頁)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 第22頁/共27頁)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(

18、 Tg)0,0(3 即為所求極小點。即為所求極小點。)3(x第23頁/共27頁2. 用于一般函數(shù)的共軛梯度法nRxtsxf .)(min共共軛軛梯梯度度法法進進行行修修改改：對對用用于于正正定定二二次次函函數(shù)數(shù)的的確確定定。）計計算算，需需由由一一維維搜搜索索不不能能利利用用公公式式（搜搜索索步步長長3)2(i 。速速下下降降方方向向，即即第第一一個個搜搜索索方方向向仍仍取取最最)()1()1()1(xfd 算算：其其它它搜搜索索方方向向按按下下式式計計,)()()1()1(iiiidxfd 。其中其中2)(2)1(|)(|)(|iiixfxf 第24頁/共27頁此此時時可可采采取取一一定定能能滿滿足足停停止止條條件件，算算法法在在有有限限步步迭迭代代后后不不)3(如如下下措措施施：沒沒有有求求成成一一輪輪搜搜索索后后，如如果果還還次次迭迭代代為為一一輪輪，每每次次完完以以n新新的的初初始始點點，的的最最后后一一個個迭迭代代點點作作為為得得極極小小點點，則則以以上上一一輪輪一輪搜索。一輪搜索。一個搜索方向，開始下一個搜索方向，開始下取最速下降方向作為第取最速下降方向作為第注注，如如可可采采用用不不同同形形式式的的公公式式在在共共軛軛梯梯度度法法中中，計計算算i 年年共共軛軛梯梯度度