第三次梯度法和共軛梯度法72927

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

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

3、 ,2(,3)(min:.12221txxxxf 設(shè)初始點(diǎn)為設(shè)初始點(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 .)()(ktkkddxf )(min)(kkkkk

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

5、斂斂3共軛梯度法共軛梯度法1. 共軛方向和共軛方向法共軛方向和共軛方向法定義定義共軛。共軛。關(guān)于關(guān)于和和，則稱(chēng)，則稱(chēng)若有若有addaddt21210 ardddnk它們兩兩關(guān)于它們兩兩關(guān)于中一組非零向量，如果中一組非零向量，如果是是設(shè)設(shè),21。共軛，即共軛，即kjijiaddjti,2,1,0 共軛方向。共軛方向。組組共軛的，也稱(chēng)它們是一共軛的，也稱(chēng)它們是一則稱(chēng)這組方向是關(guān)于則稱(chēng)這組方向是關(guān)于aa注注：002121 dddidtt21dd 共軛是正交的推廣。共軛是正交的推廣。，和和中的兩個(gè)非零向量中的兩個(gè)非零向量的對(duì)稱(chēng)正定矩陣，對(duì)于的對(duì)稱(chēng)正定矩陣，對(duì)于是是設(shè)設(shè)21ddrnnan 是是單單位位矩

6、矩陣陣，則則如如果果 a共軛的非零共軛的非零個(gè)個(gè)是是階對(duì)稱(chēng)正定矩陣，階對(duì)稱(chēng)正定矩陣，是是設(shè)設(shè)akdddnak,21性無(wú)關(guān)。性無(wú)關(guān)。向量，則這個(gè)向量組線向量，則這個(gè)向量組線. 1定理定理證明證明，使得，使得設(shè)存在實(shí)數(shù)設(shè)存在實(shí)數(shù)k ,21,01 kiiid ，則有，則有上式兩邊同時(shí)左乘上式兩邊同時(shí)左乘adtj,01 kiitjiadd 可化簡(jiǎn)為可化簡(jiǎn)為共軛的向量，所以上式共軛的向量，所以上式個(gè)個(gè)是是因?yàn)橐驗(yàn)閍kdddk,21.0 jtjjadd ，是正定矩陣，所以是正定矩陣，所以而而因?yàn)橐驗(yàn)?,0 jtjjaddad所以所以。kjj,2,1,0 線性無(wú)關(guān)。線性無(wú)關(guān)。因此因此kddd,21幾何意義幾

7、何意義設(shè)有二次函數(shù)設(shè)有二次函數(shù))()(21)(xxaxxxft 對(duì)稱(chēng)正定矩陣，對(duì)稱(chēng)正定矩陣，是是其中其中nna 是一個(gè)定點(diǎn)。是一個(gè)定點(diǎn)。x的等值面的等值面則函數(shù)則函數(shù))(xfcxxaxxt )()(21為中心的橢球面。為中心的橢球面。是以是以 x由于由于,0)()( xxaxf,0)(2 axfa所以所以正定，正定，因?yàn)橐驗(yàn)榈臉O小點(diǎn)。的極小點(diǎn)。是是因此因此)(xfxx,)(2axf 而而點(diǎn)，點(diǎn)，是在某個(gè)等值面上的一是在某個(gè)等值面上的一設(shè)設(shè))0(x處的法向量為處的法向量為該等值面在點(diǎn)該等值面在點(diǎn))1(x. )()()1()1(xxaxf o1x2xx)1(d)0(x中的一個(gè)方向，中的一個(gè)方向，是

8、是nrd)1(。以最優(yōu)步長(zhǎng)搜索得到點(diǎn)以最優(yōu)步長(zhǎng)搜索得到點(diǎn)沿著沿著)1()1()0(xdx所所在在等等值值面面的的切切向向量量。是是點(diǎn)點(diǎn)則則)1()1(xd正交，正交，與與則則)()1()1(xfd , 0)()1()1( xfdt即即,)1()2(xxd 令令)1(x所以所以, 0)2()1( addt共軛。共軛。小點(diǎn)的向量關(guān)于小點(diǎn)的向量關(guān)于向量與由這一點(diǎn)指向極向量與由這一點(diǎn)指向極即等值面上一點(diǎn)處的切即等值面上一點(diǎn)處的切a)2(d. 2定理定理，設(shè)有函數(shù)設(shè)有函數(shù)cxbaxxxftt 21)(共軛向量。共軛向量。一組一組是是階對(duì)稱(chēng)正定矩陣。階對(duì)稱(chēng)正定矩陣。是是其中其中adddnak)()2()1

9、(,進(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 是是時(shí)，時(shí)，當(dāng)當(dāng)，生成的子空間。特別地生成的子空間。特別地是由是由)1()()2()1(, nkxnkddd上上的的唯唯一一極極小小點(diǎn)點(diǎn)。在在nrxf)(推論推論有有在上述定理?xiàng)l件下，必在上述定理?xiàng)l件下，必。kidxfitk,2,1,0)()()1( 共軛方向法對(duì)于極小化問(wèn)題對(duì)于極小化問(wèn)題:法法為為共共軛軛方方向向法法是是正正定

10、定矩矩陣陣，稱(chēng)稱(chēng)下下述述算算其其中中 a,21)(mincxbaxxxftt ；共軛方向共軛方向取定一組取定一組)()2()1(,)1(nddda,)2()1()()1( kkxxx確定點(diǎn)確定點(diǎn)依次按照下式由依次按照下式由任取初始點(diǎn)任取初始點(diǎn) )(min)()()()()()()()1(kkkkkkkkkdxfdxfdxx 。滿(mǎn)足滿(mǎn)足直到某個(gè)直到某個(gè)0)()()( kkxfx注注至多經(jīng)過(guò)至多經(jīng)過(guò)求解上述極小化問(wèn)題，求解上述極小化問(wèn)題，可知，利用共軛方向法可知，利用共軛方向法由定理由定理2。次次迭迭代代必必可可得得到到最最優(yōu)優(yōu)解解n2. 共軛梯度法 如何選取一組共軛方向？如何選取一組共軛方向？:

11、共軛梯度法共軛梯度法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ù)。，是對(duì)稱(chēng)正定矩陣，是對(duì)稱(chēng)正定矩陣，其中其中crbarxnn ,；，第一個(gè)搜索方向取為，第一個(gè)搜索方向取為任取初始點(diǎn)任取初始點(diǎn))()1()1()1()1(xfdx ，令令，若若，設(shè)已求得點(diǎn)設(shè)已求得點(diǎn))(0)(

12、)2()1(1)1()1( kkkkxfgxfx:)1(按如下方式確定按如下方式確定則下一個(gè)搜索方向則下一個(gè)搜索方向 kd)1()(1)1(kkkkdgd 令令共軛。共軛。關(guān)于關(guān)于和和要求要求addkk)()1( ？如何確定如何確定k ，得，得）式兩邊同時(shí)左乘）式兩邊同時(shí)左乘則在（則在（adtk)(1)()(1)()1()(0ktkkktkktkdadagdadd )2()()(1)(ktkktkkdadgad 解得解得:)3(搜搜索索步步長(zhǎng)長(zhǎng)的的確確定定，步長(zhǎng)步長(zhǎng)利用一維搜索確定最優(yōu)利用一維搜索確定最優(yōu)和搜索方向和搜索方向已知迭代點(diǎn)已知迭代點(diǎn)kkkdx ,)()(。即求解即求解)(min)(

13、)(kkdxf , )()()()(kkdxf 記記，令令0)()()()()( ktkkddxf ，即有即有0)()()()( ktkkdbdxa ，則有，則有令令baxxfgkkk )()()(，0)()( ktkkdadg )3()()()(ktkktkkadddg 解得解得3定理定理次次算法在算法在，對(duì)于正定二次函數(shù)對(duì)于正定二次函數(shù)nmfrcxbaxxxftt 21)(），下下列列關(guān)關(guān)系系成成立立（且且對(duì)對(duì)所所有有的的一一維維搜搜索索后后即即終終止止，并并mii 1;1,2,1,0)1()()( ijaddjti;1,2,1,0)2( ijggjti。itiitiggdg )()3(注

14、注共共軛軛的的。是是可可知知搜搜索索方方向向）由由定定理理（adddm)()2()1(,31則則構(gòu)構(gòu)造造的的搜搜索索必必須須取取負(fù)負(fù)梯梯度度方方向向，否否算算法法中中第第一一個(gè)個(gè)搜搜索索方方向向)2(方方向向不不能能保保證證共共軛軛性性。）可知，）可知，的（的（由定理由定理33)3(,0|2)( iitiitigggdg處的下降方向。處的下降方向。是迭代點(diǎn)是迭代點(diǎn)所以所以)()(iixd的的計(jì)計(jì)算算公公式式可可以以簡(jiǎn)簡(jiǎn)化化。算算法法中中，由由定定理理ifr 3)4()()(1)(itiitiiaddgad )()()(1itiitiadddag / )( / )( )()1()()()1(1i

15、iitiiiitixxadxxag .)()()(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(3,dxxgd 為所求極小點(diǎn)；為所求極小點(diǎn)；停止，停止，若若令令)1(1)1(1,|, )(. 3 kkkkxgxfg ）計(jì)算。）計(jì)算。用公式（用公式（其中其

16、中否則，令否則，令4,)(1)1(kkkkkdgd 。轉(zhuǎn)轉(zhuǎn)，令，令）計(jì)算）計(jì)算利用公式（利用公式（3,3. 4)()()1(kkkkkdxx 。令令1: kk算算法法求求解解下下述述問(wèn)問(wèn)題題：用用例例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 xxxxxf.2004 a而而 482004)4,8(48)4,8(185 )1(1)1()2(dxx 所以所以tt)4,8(185)2,2( t)98,9

17、2( 次迭代：次迭代：第第 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(x3. 用于一般函數(shù)的共軛梯度法nrxtsxf .)(min共軛梯度法進(jìn)行修改：共軛梯度法進(jìn)行修改：對(duì)用于正定二次函數(shù)的對(duì)用于正定二次函數(shù)的確確定定。）計(jì)計(jì)算算，需需由由一一維維搜搜索索不不能能利利用用公公式式（搜搜索索步步長(zhǎng)長(zhǎng)3)2(i 。速下降方向，即速下降方向，即第一個(gè)搜索方向仍取最第一個(gè)搜索方向仍取最)()1()1()1(xfd 算算：其其它它搜搜索索方方向向按按下下式式計(jì)計(jì),)()()1()1(iiiidxfd 。其中其中2)(2)1(|)(|)(|iiixfxf 此此時(shí)時(shí)可可采采取取一一定定