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

1、梯度法和共軛梯度法梯度法和共軛梯度法1. 無約束最優(yōu)化問題無約束最優(yōu)化問題2. 梯度法梯度法3. 共軛梯度法共軛梯度法一一. 無約束最優(yōu)化問題無約束最優(yōu)化問題無約束最優(yōu)化問題無約束最優(yōu)化問題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、梯度法（最速下降法）：梯度法（最速下降法）：也稱為最速下降方向；也稱為最速下降方向；搜索方向：搜索方向：, )(. 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,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 滿足滿足步長步長有一階連續(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)于和和，則稱，則稱若有若有addaddt21210 ardddnk它們兩兩關(guān)于它們兩兩關(guān)于中一組非零向量，如果中一組非零向量，如果是是設(shè)設(shè),21。共軛，即共軛，即kjijiaddjti,2,1,0 共軛方向。共軛方向。組組共軛的，也稱它們是一共軛的，也稱它們是一則稱這組方向是關(guān)于則稱這組方向是關(guān)于aa注注：002121 dddidtt21dd 共軛是正交的推廣。共軛是正交的推廣。，和和中的兩個非零向量中的兩個非零向量的對稱正定矩陣，對于的對稱正定矩陣，對于是是設(shè)設(shè)21ddrnnan 是是單單位位矩

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

7、何意義設(shè)有二次函數(shù)設(shè)有二次函數(shù))()(21)(xxaxxxft 對稱正定矩陣，對稱正定矩陣，是是其中其中nna 是一個定點(diǎn)。是一個定點(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)，是在某個等值面上的一是在某個等值面上的一設(shè)設(shè))0(x處的法向量為處的法向量為該等值面在點(diǎn)該等值面在點(diǎn))1(x. )()()1()1(xxaxf o1x2xx)1(d)0(x中的一個方向，中的一個方向，是

8、是nrd)1(。以最優(yōu)步長搜索得到點(diǎn)以最優(yōu)步長搜索得到點(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)(共軛向量。共軛向量。一組一組是是階對稱正定矩陣。階對稱正定矩陣。是是其中其中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 是是時，時，當(dāng)當(dāng)，生成的子空間。特別地生成的子空間。特別地是由是由)1()()2()1(, nkxnkddd上上的的唯唯一一極極小小點(diǎn)點(diǎn)。在在nrxf)(推論推論有有在上述定理?xiàng)l件下，必在上述定理?xiàng)l件下，必。kidxfitk,2,1,0)()()1( 共軛方向法對于極小化問題對于極小化問題:法法為為共共軛軛方方向向法法是是正正定

10、定矩矩陣陣，稱稱下下述述算算其其中中 a,21)(mincxbaxxxftt ；共軛方向共軛方向取定一組取定一組)()2()1(,)1(nddda,)2()1()()1( kkxxx確定點(diǎn)確定點(diǎn)依次按照下式由依次按照下式由任取初始點(diǎn)任取初始點(diǎn) )(min)()()()()()()()1(kkkkkkkkkdxfdxfdxx 。滿足滿足直到某個直到某個0)()()( kkxfx注注至多經(jīng)過至多經(jīng)過求解上述極小化問題，求解上述極小化問題，可知，利用共軛方向法可知，利用共軛方向法由定理由定理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ù)。，是對稱正定矩陣，是對稱正定矩陣，其中其中crbarxnn ,；，第一個搜索方向取為，第一個搜索方向取為任取初始點(diǎn)任取初始點(diǎn))()1()1()1()1(xfdx ，令令，若若，設(shè)已求得點(diǎn)設(shè)已求得點(diǎn))(0)(

12、)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(搜搜索索步步長長的的確確定定，步長步長利用一維搜索確定最優(yōu)利用一維搜索確定最優(yōu)和搜索方向和搜索方向已知迭代點(diǎn)已知迭代點(diǎn)kkkdx ,)()(。即求解即求解)(min)(

13、)(kkdxf , )()()()(kkdxf 記記，令令0)()()()()( ktkkddxf ，即有即有0)()()()( ktkkdbdxa ，則有，則有令令baxxfgkkk )()()(，0)()( ktkkdadg )3()()()(ktkktkkadddg 解得解得3定理定理次次算法在算法在，對于正定二次函數(shù)對于正定二次函數(shù)nmfrcxbaxxxftt 21)(），下下列列關(guān)關(guān)系系成成立立（且且對對所所有有的的一一維維搜搜索索后后即即終終止止，并并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ù)梯梯度度方方向向，否否算算法法中中第第一一個個搜搜索索方方向向)2(方方向向不不能能保保證證共共軛軛性性。）可知，）可知，的（的（由定理由定理33)3(,0|2)( iitiitigggdg處的下降方向。處的下降方向。是迭代點(diǎn)是迭代點(diǎn)所以所以)()(iixd的的計(jì)計(jì)算算公公式式可可以以簡簡化化。算算法法中中，由由定定理理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算算法法求求解解下下述述問問題題：用用例例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)行修改：對用于正定二次函數(shù)的對用于正定二次函數(shù)的確確定定。）計(jì)計(jì)算算，需需由由一一維維搜搜索索不不能能利利用用公公式式（搜搜索索步步長長3)2(i 。速下降方向，即速下降方向，即第一個搜索方向仍取最第一個搜索方向仍取最)()1()1()1(xfd 算算：其其它它搜搜索索方方向向按按下下式式計(jì)計(jì),)()()1()1(iiiidxfd 。其中其中2)(2)1(|)(|)(|iiixfxf 此此時時可可采采取取一一定定