最優(yōu)化理論與算法(第四章)

1、1第四章第四章共軛梯度法共軛梯度法4.14.1共軛方向法共軛方向法共軛方向法是無(wú)約束最優(yōu)化問(wèn)題的一類(lèi)重要算法。它一方面克服了最速下降法中，迭代點(diǎn)列呈鋸齒形前進(jìn)，收斂慢的缺點(diǎn)，同時(shí)又不像牛頓法中計(jì)算牛頓方向耗費(fèi)大量的工作量，尤其是共軛方向法具有所謂二次收斂性質(zhì)，即當(dāng)將其用于二次函數(shù)時(shí)，具有有限終止性質(zhì)。一、共軛方向一、共軛方向定義定義4.14.1設(shè)是對(duì)稱正定矩陣，，是維非零向量，若Gnn?1d2dn（4.1）120TdGd?則稱，是－共軛

2、的。類(lèi)似地，設(shè)是中一組非零向量。若1d2dG1mdd?nR（4.2）0TijdGd?()ij?則稱向量組是－共軛的。1mdd?G注：注：(1)當(dāng)時(shí)，共軛性就變?yōu)檎恍?，故共軛是正交概念的推廣。GI?(2)若－共軛，則它們必線性無(wú)關(guān)。1mdd?G二、共軛方向法二、共軛方向法共軛方向法就是按照一組彼此共軛方向依次搜索。模式算法：1）給出初始點(diǎn)，計(jì)算，計(jì)算，使，（初始共軛方向）；0x00()ggx?0d000Tdg?:0k?2）計(jì)算和，使得，

3、令；k?1kx?0()min()kkkkkfxdfxd???????1kkkkxxd????3）計(jì)算，使，，令，轉(zhuǎn)2）。1kd?10TkjdGd??01jk??:1kk??三、共軛方向法的基本定理三、共軛方向法的基本定理共軛方向法最重要的性質(zhì)就是：當(dāng)算法用于正定二次函數(shù)時(shí)，可以在有限多次迭代后終止，得到最優(yōu)解（當(dāng)然要執(zhí)行精確一維搜索）。3000000000()()1()()()2iijjjiiiTTjjjjjjjjjttfxtdxtdG

4、xtdbxtdc??????????????????200000011()[]()22iiTTTTTjjjjjjjjtdGdxGdbdtxGxbxc??????????由知為的凸函數(shù)。因而0TjjdGd?(0)ji??0()itt??0itt?100()min()0iiittRjttt??????????(0)ji??00()0iTjjjjfxtdd??????(0)ji??注意到：當(dāng)，時(shí)，jjt??(0)ji??。00100iijjj

5、jijjxtdxdx??????????而由定理前部分證明，在處有1ix?，11()0TTijijfxdgd?????(0)ji??故在處，取得極小，即00()()iitt?????0()itt??100iiijjxxd??????是在線性流形上的極小點(diǎn)。()fx4.24.2共軛梯度法共軛梯度法上節(jié)一般地討論了共軛方向法，在那里個(gè)共軛方向是預(yù)先給定的，而如何獲得這些共軛方向n并為提及。本節(jié)討論一種重要的共軛方向法——共軛梯度法。這種方法