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 梯度法算法步驟：梯度法算法步驟：。令令允允許許誤誤差差給給定定初初始始點點1,0,. 11 kRxn ;)(. 2kkxfd 計計算算搜搜索索方方向向kkkxd 否則，求最優(yōu)步長否則，求最優(yōu)步長為所求極值點；為所求極值點；則停止計算，則停止計算，若若,|. 3 。使使得得)(min)(kkkkkdxfdxf 。轉(zhuǎn)轉(zhuǎn)令令令令2,

3、1:,. 41 kkdxxkkkk ,)1 ,2(,3)(min:.12221Txxxxf 設(shè)設(shè)初初始始點點為為用用最最速速下下降降法法求求解解例例。求迭代一次后的迭代點求迭代一次后的迭代點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ù)偏導(dǎo)數(shù)，若有一階連續(xù)偏導(dǎo)數(shù)，若設(shè)設(shè)kxf )(注：注：。kkkTkdddd 110)(所所以以，因因為為梯梯度度法法的的搜搜索索方方向向)(1kkkkdxfd 鋸鋸齒齒現(xiàn)現(xiàn)象象，其其等等值值面面近近似似數(shù)數(shù)可可以以用用二二次次函函數(shù)數(shù)近近似似在在極極小小點點附附近近，目目標(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 是是一一個個定定點點。x的的等等值值面面則則函函數(shù)數(shù))(xfcxxAxxT )()(21為為中中心心的的橢橢球球面面。是是以以 xx三、共軛方向法三、共軛方向法1. 何謂共軛方向？何謂共軛方向？由于由于,0)()( xxAxf,0)(2 AxfA所所以以正正定定，因因為為的極小點。的極小點。是是因此因此)(xfx,)(2Axf 而而x)()(21)(xxAxxxfT 點點，是是在在某某個個等等值值面面上上的的一一設(shè)設(shè))0(x中中的的一一

6、個個方方向向，是是nRd)1(。搜搜索索得得到到點點以以最最優(yōu)優(yōu)步步長長沿沿著著)1()1()0(xdxo1xx)1(d)1(x)2(d)0(x)x(fx)(11 處的法向量為處的法向量為該等值面在點該等值面在點所所在在等等值值面面的的切切向向量量。是是點點則則)()(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(

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ù)k ,21,01 kiiid ，則則有有上上式式兩兩邊邊同同時時左左乘乘AdTj,01 kiiTjiAdd 可可化化簡簡為為共共軛軛的的向向量量，所所以以上上式式個個是是因因為為Akdddk,21.0 jTjjAdd ，是是正正定定矩矩陣陣，所所以以而而因因為為0,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)行行搜搜索索，為為初初始始點點，依依次次沿沿以以任任意意的的)()2()1()1(,kndddRx 上上的的在在是是函函數(shù)數(shù)則則得得到到點點kkkBxxfxxxx )1()1()1()3()2()(,極極小小點點，其其中中,|1)(RdxxBikiiik 是是時，時，當(dāng)當(dāng)，生成的子空間。特別地生成的子空間。特別地是由是由)1()()2()1(, nkxnkddd上上的的唯唯一一極極小小點點。在在nRxf)(推論推論有有在在上上述述定定理理條條件件下下，必必。kidxfiTk,2,1,0)()()1

10、( 3、共軛方向法對于極小化問題對于極小化問題:法法為為共共軛軛方方向向法法是是正正定定矩矩陣陣，稱稱下下述述算算其其中中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。次次迭迭代代必必可可得得

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

12、 ,1 1、 二次函數(shù)情形二次函數(shù)情形；，第第一一個個搜搜索索方方向向取取為為任任取取初初始始點點)()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 解得解得:

13、)3(搜搜索索步步長長的的確確定定，步步長長利利用用一一維維搜搜索索確確定定最最優(yōu)優(yōu)和和搜搜索索方方向向已已知知迭迭代代點點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處的下降方向。處的下降方向。是迭代點是迭代點所以所以)()(iixd的的計計算算公公式式可可以以簡簡化化。算算法

15、法中中，由由定定理理iFR 3)4()()(1)(iTiiTiiAddgAd )()()(1iTiiTiAdddAg / )( / )( )()1()()()1(1iiiTiiiiTixxAdxxAg .)()()(bxAxfgiii )()(1)(11iiTiiiTiiggdggg iTiigdg)(21| )4(|221iigg 算算法法步步驟驟：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算算法法求求解解下下述述問問題題：用用例例FR22212)(minxxxf 。初初始始點點取取為為Tx)2,2()1( 解：解：.)2,4()(21Txxxf 次迭代：次迭代：第第1,)4,8(1)1(Tgd 令令)1()1()1(11AdddgTT ,2004),(21)(2121 xxxx

17、xf.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 即即為為所所求求極極小小點點。)3(x2

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