梯度法和共軛梯度法

1、梯度法和共軛梯度法梯度法和共軛梯度法無約束最優(yōu)化問題無約束最優(yōu)化問題2. 梯度法梯度法3. 共軛方向法共軛方向法4. 共軛梯度法共軛梯度法一一. 無約束最優(yōu)化問題無約束最優(yōu)化問題無無約約束束最最優(yōu)優(yōu)化化問問題題nRxtsxf .)(min有有一一階階連連續(xù)續(xù)偏偏導(dǎo)導(dǎo)數(shù)數(shù)。其其中中)(xf解析法解析法：利用函數(shù)的解析性質(zhì)構(gòu)造迭代公式。：利用函數(shù)的解析性質(zhì)構(gòu)造迭代公式。二二. 梯度法（最速下降法）梯度法（最速下降法）迭代公式：迭代公式：kkkkdxx 1如何選擇下降最快的方向？如何選擇下降最快的方向？)(kxf )(kxf 函函數(shù)數(shù)值值下下降降最最快快的的方方向向函函數(shù)數(shù)值值增增加加最最快快的的方

2、方向向函數(shù)值下降的方向函數(shù)值下降的方向kx梯度法（最速下降法）：梯度法（最速下降法）：也稱為最速下降方向；也稱為最速下降方向；搜索方向：搜索方向：, )(. 1kkxfd 。即即滿滿足足取取最最優(yōu)優(yōu)步步長長搜搜索索步步長長)(min)(,:. 2kkkkkkdxfdxf 梯度法算法步驟：梯度法算法步驟：。令令允許誤差允許誤差給定初始點(diǎn)給定初始點(diǎn)1,0,. 11 kRxn ;)(. 2kkxfd 計(jì)算搜索方向計(jì)算搜索方向kkkxd 否則，求最優(yōu)步長否則，求最優(yōu)步長為所求極值點(diǎn)；為所求極值點(diǎn)；則停止計(jì)算，則停止計(jì)算，若若,|. 3 。使使得得)(min)(kkkkkdxfdxf 。轉(zhuǎn)轉(zhuǎn)令令令令2,

3、1:,. 41 kkdxxkkkk ,)1 ,2(,3)(min:.12221Txxxxf 設(shè)設(shè)初初始始點(diǎn)點(diǎn)為為用用最最速速下下降降法法求求解解例例。求迭代一次后的迭代點(diǎn)求迭代一次后的迭代點(diǎn)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 性質(zhì)性質(zhì). 證明：證明：所所以以，令令)()(kkdxf .)()(

4、kTkkddxf )(min)(kkkkkdxfdxf .0)()( kTkkkkddxf 滿滿足足步步長長有有一一階階連連續(xù)續(xù)偏偏導(dǎo)導(dǎo)數(shù)數(shù)，若若設(shè)設(shè)kxf )(注：注：。kkkTkdddd 110)(所所以以，因因?yàn)闉樘萏荻榷确ǚǖ牡乃阉阉魉鞣椒较蛳?(1kkkkdxfd 鋸鋸齒齒現(xiàn)現(xiàn)象象，其其等等值值面面近近似似數(shù)數(shù)可可以以用用二二次次函函數(shù)數(shù)近近似似在在極極小小點(diǎn)點(diǎn)附附近近，目目標(biāo)標(biāo)函函橢球面。橢球面。1x*x2x3x它它只只是是。標(biāo)標(biāo)函函數(shù)數(shù)的的一一種種局局部部性性質(zhì)質(zhì)最最速速下下降降方方向向反反映映了了目目快快的的方方向向。局局部部目目標(biāo)標(biāo)函函數(shù)數(shù)值值下下降降最最注注的的算算法法。最

5、最速速下下降降法法是是線線性性收收斂斂幾何解釋幾何解釋設(shè)設(shè)有有二二次次函函數(shù)數(shù))()(21)(xxAxxxfT 對對稱稱正正定定矩矩陣陣，是是其其中中nnA 是是一一個個定定點(diǎn)點(diǎn)。x的的等等值值面面則則函函數(shù)數(shù))(xfcxxAxxT )()(21為為中中心心的的橢橢球球面面。是是以以 xx三、共軛方向法三、共軛方向法1. 何謂共軛方向？何謂共軛方向？由于由于,0)()( xxAxf,0)(2 AxfA所所以以正正定定，因因?yàn)闉榈臉O小點(diǎn)。的極小點(diǎn)。是是因此因此)(xfx,)(2Axf 而而x)()(21)(xxAxxxfT 點(diǎn)點(diǎn)，是是在在某某個個等等值值面面上上的的一一設(shè)設(shè))0(x中中的的一一個

6、個方方向向，是是nRd)1(。搜搜索索得得到到點(diǎn)點(diǎn)以以最最優(yōu)優(yōu)步步長長沿沿著著)1()1()0(xdxo1xx)1(d)1(x)2(d)0(x)x(fx)(11 處的法向量為處的法向量為該等值面在點(diǎn)該等值面在點(diǎn)所所在在等等值值面面的的切切向向量量。是是點(diǎn)點(diǎn)則則)()(xd11. )()()1()1(xxAxf o1xx)1(d正交，正交，與與則則)()1()1(xfd 。即即0)()1()1( xfdT,)1()2(xxd 令令)1(x所以所以。0)2()1( AddT共共軛軛。小小點(diǎn)點(diǎn)的的向向量量關(guān)關(guān)于于指指向向極極向向量量與與由由這這一一點(diǎn)點(diǎn)即即等等值值面面上上一一點(diǎn)點(diǎn)處處的的切切A)2(

7、d)x(f1 2. 共軛方向共軛方向定義定義共共軛軛。關(guān)關(guān)于于和和，則則稱稱若若有有AddAddT21210 ARdddnk它們兩兩關(guān)于它們兩兩關(guān)于中一組非零向量，如果中一組非零向量，如果是是設(shè)設(shè),21。共共軛軛，即即kjijiAddjTi,2,1,0 共共軛軛方方向向。組組共共軛軛的的，也也稱稱它它們們是是一一則則稱稱這這組組方方向向是是關(guān)關(guān)于于AA注注：002121 dddIdTT21dd 共軛是正交的推廣。共軛是正交的推廣。，和和中中的的兩兩個個非非零零向向量量的的對對稱稱正正定定矩矩陣陣，對對于于是是設(shè)設(shè)21ddRnnAn 是是單單位位矩矩陣陣，則則如如果果 A共共軛軛的的非非零零個個

8、是是階階對對稱稱正正定定矩矩陣陣，是是設(shè)設(shè)AkdddnAk,21性性無無關(guān)關(guān)。向向量量，則則這這個個向向量量組組線線. 1定理定理證明證明，使使得得設(shè)設(shè)存存在在實(shí)實(shí)數(shù)數(shù)k ,21,01 kiiid ，則則有有上上式式兩兩邊邊同同時時左左乘乘AdTj,01 kiiTjiAdd 可可化化簡簡為為共共軛軛的的向向量量，所所以以上上式式個個是是因因?yàn)闉锳kdddk,21.0 jTjjAdd ，是是正正定定矩矩陣陣，所所以以而而因因?yàn)闉?,0 jTjjAddAd所以所以。kjj,2,1,0 線線性性無無關(guān)關(guān)。因因此此kddd,21. 2定理定理，設(shè)有函數(shù)設(shè)有函數(shù)cxbAxxxfTT 21)(共共軛軛向向

9、量量。一一組組是是階階對對稱稱正正定定矩矩陣陣。是是其其中中AdddnAk)()2()1(,進(jìn)進(jìn)行行搜搜索索，為為初初始始點(diǎn)點(diǎn)，依依次次沿沿以以任任意意的的)()2()1()1(,kndddRx 上上的的在在是是函函數(shù)數(shù)則則得得到到點(diǎn)點(diǎn)kkkBxxfxxxx )1()1()1()3()2()(,極極小小點(diǎn)點(diǎn)，其其中中,|1)(RdxxBikiiik 是是時時，當(dāng)當(dāng)，生生成成的的子子空空間間。特特別別地地是是由由)1()()2()1(, nkxnkddd上上的的唯唯一一極極小小點(diǎn)點(diǎn)。在在nRxf)(推論推論有有在在上上述述定定理理?xiàng)l條件件下下，必必。kidxfiTk,2,1,0)()()1( 3

10、、共軛方向法對于極小化問題對于極小化問題:法法為為共共軛軛方方向向法法是是正正定定矩矩陣陣，稱稱下下述述算算其其中中A,21)(mincxbAxxxfTT ；共共軛軛方方向向取取定定一一組組)()2()1(,)1(ndddA,)2()1()()1( kkxxx確確定定點(diǎn)點(diǎn)依依次次按按照照下下式式由由任任取取初初始始點(diǎn)點(diǎn) )dx(fmin)dx(fdxx)k()k()k(k)k()k(k)k()k(1。滿足滿足直到某個直到某個0)()()( kkxfx注注至至多多經(jīng)經(jīng)過過求求解解上上述述極極小小化化問問題題，可可知知，利利用用共共軛軛方方向向法法由由定定理理2。次次迭迭代代必必可可得得到到最最優(yōu)

11、優(yōu)解解n四四. . 共軛梯度法共軛梯度法 ：如何選取一組共軛方向？如何選取一組共軛方向？q 二次函數(shù)情形二次函數(shù)情形q 非二次函數(shù)情形非二次函數(shù)情形:共軛梯度法共軛梯度法eevesRFletcher 代代點(diǎn)點(diǎn)向向相相結(jié)結(jié)合合，利利用用已已知知迭迭將將共共軛軛性性和和最最速速下下降降方方基基本本思思想想：進(jìn)進(jìn)行行搜搜索索，求求出出共共軛軛方方向向，并并沿沿此此方方向向處處的的梯梯度度方方向向構(gòu)構(gòu)造造一一組組函數(shù)的極小點(diǎn)。函數(shù)的極小點(diǎn)。以下分析算法的具體步驟。以下分析算法的具體步驟。cxbAxxxfTT 21)(min是常數(shù)。是常數(shù)。，是對稱正定矩陣，是對稱正定矩陣，其中其中cRbARxnn ,1

12、 1、 二次函數(shù)情形二次函數(shù)情形；，第第一一個個搜搜索索方方向向取取為為任任取取初初始始點(diǎn)點(diǎn))()1()1()1()1(xfdx ，令令，若若，設(shè)設(shè)已已求求得得點(diǎn)點(diǎn))(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 解得解得:)3(

13、搜搜索索步步長長的的確確定定，步步長長利利用用一一維維搜搜索索確確定定最最優(yōu)優(yōu)和和搜搜索索方方向向已已知知迭迭代代點(diǎn)點(diǎn)kkkdx ,)()(。即即求求解解)(min)()(kkdxf , )()()()(kkdxf 記記，令令0)()()()()( kTkkddxf ，即即有有0)()()()( kTkkdbdxA ，則則有有令令bAxxfgkkk )()()(，0)()( kTkkdAdg )3()()()(kTkkTkkAdddg 解解得得3定理定理次次算法在算法在，對于正定二次函數(shù)對于正定二次函數(shù)nmFRcxbAxxxfTT 21)(），下下列列關(guān)關(guān)系系成成立立（且且對對所所有有的的一一

14、維維搜搜索索后后即即終終止止，并并mii 1;1,2,1,0)1()()( ijAddjTi;1,2,1,0)2( ijggjTi。iTiiTiggdg )()3(注注共共軛軛的的。是是可可知知搜搜索索方方向向）由由定定理理（Adddm)()2()1(,31則則構(gòu)構(gòu)造造的的搜搜索索必必須須取取負(fù)負(fù)梯梯度度方方向向，否否算算法法中中第第一一個個搜搜索索方方向向)2(方方向向不不能能保保證證共共軛軛性性。）可知，）可知，的（的（由定理由定理33)3(,0|2)( iiTiiTigggdg處處的的下下降降方方向向。是是迭迭代代點(diǎn)點(diǎn)所所以以)()(iixd的的計(jì)計(jì)算算公公式式可可以以簡簡化化。算算法法

15、中中，由由定定理理iFR 3)4()()(1)(iTiiTiiAddgAd )()()(1iTiiTiAdddAg / )( / )( )()1()()()1(1iiiTiiiiTixxAdxxAg .)()()(bxAxfgiii )()(1)(11iiTiiiTiiggdggg iTiigdg)(21| )4(|221iigg 算算法法步步驟驟：FR。，令令精精度度要要求求，任任取取初初始始點(diǎn)點(diǎn)1. 1)1( kx 為為所所求求極極小小點(diǎn)點(diǎn)；停停止止，若若令令)1(1)1(1,|, )(. 2xgxfg 。令令，）計(jì)算）計(jì)算利用公式（利用公式（否則，令否則，令)1(1)1()2(11)1(

16、3,dxxgd 為為所所求求極極小小點(diǎn)點(diǎn)；停停止止，若若令令)1(1)1(1,|, )(. 3 kkkkxgxfg ）計(jì)計(jì)算算。用用公公式式（其其中中否否則則，令令4,)(1)1(kkkkkdgd 。轉(zhuǎn)轉(zhuǎn)，令，令）計(jì)算）計(jì)算利用公式（利用公式（3,3. 4)()()1(kkkkkdxx 。令令1: kk算算法法求求解解下下述述問問題題：用用例例FR22212)(minxxxf 。初初始始點(diǎn)點(diǎn)取取為為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 即為所求極小點(diǎn)。即為所求極小點(diǎn)。)3(x2

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