最優(yōu)化理論4無約束優(yōu)化共軛梯度法擬牛頓法

第4章無約束非線性規(guī)劃哈爾濱工程大學(xué)理學(xué)院戴運(yùn)桃Email:peach0040@126.com共軛方向法是介于最速下降法與牛頓法之間的一類方法。它僅需利用一階導(dǎo)數(shù)信息，但克服了最速下降法收斂慢的缺點(diǎn)，又避免了存儲和計(jì)算牛頓法所需要的二階導(dǎo)數(shù)信息。因而簡便、易實(shí)現(xiàn)、且十分適合大規(guī)模（稀疏）優(yōu)化問題的計(jì)算，通常只經(jīng)過較少的迭代次數(shù)就能獲得滿足所要求精度的近似解。共軛方向法共軛梯度法定義1

設(shè)A是n×n對稱矩陣,若Rn

中的兩個方向d1

和d2滿足(d1)T

Ad2=0（1）則稱這兩個方向關(guān)于A共軛,或稱它們關(guān)于A正交.則稱這組方向是A共軛,或稱它們?yōu)锳的k個共軛方向共軛梯度法先討論對于二次凸函數(shù)的共軛梯度法,考慮問題求解方法

綜上分析,在第一個搜索方向取負(fù)梯度的前提下,重復(fù)使用公式3,5-7就能伴隨計(jì)算點(diǎn)的增加,構(gòu)造出一組搜索方向.注意,初始搜索方向選擇最速下降方向十分重要,

如果選擇別的方向作為初始方向,其余方向均按FR方法構(gòu)造,則極小化正定二次函數(shù)時,這樣構(gòu)造出來的一組方向并不能保證共軛性.注意,在FR法中,初始搜索方向必須取最速下降方向

定理3

對于正定二次函數(shù),具有精確一維搜索的Fletcher-Reeves法在m

n次一維搜索后即終止,并且對所有i(1

i

m),下列關(guān)系成立:證明:顯然m1,下用歸納法(對i)證之.

設(shè)對某個i<m,這些關(guān)系均成立,我們證明對于i+1也成立.先證2),由迭代公式兩端左乘A,再加上b,得其中由于故（3）當(dāng)j<i時,根據(jù)歸納假設(shè),式(3)等號右端各項(xiàng)均為0再證1),運(yùn)用當(dāng)j=i時,把

βk代入上式第一個等號的右端,立得當(dāng)j<i時,由前面已經(jīng)證明的結(jié)論和歸納假設(shè),式中第2個等號右端顯然為0,因此最后證3),易知綜上,對i+1,上述三種關(guān)系成立定理4

對于正定二次函數(shù),FR法中因子

i具有下述表達(dá)式證明:FR共軛梯度法(對二次凸函數(shù))共軛梯度法步驟3,如果j<n,轉(zhuǎn)步4,否則,轉(zhuǎn)5例

用FR法求解下列問題令第一次迭代，目標(biāo)函數(shù)f(x)在點(diǎn)x處的梯度第2次迭代目標(biāo)函數(shù)在點(diǎn)x處的梯度(2)構(gòu)造搜索方向d.先計(jì)算因子

(2)1令一般迭代格式用于一般函數(shù)的共軛梯度法－非線性共軛梯度法----PRP(Polak-Ribiere-Polyar-----SW(Sorenson-Wolfe----Daniel-----Dixon擬牛頓法牛頓法成功的關(guān)鍵在于利用了Hesse矩陣提供的曲率信息，而計(jì)算Hesse矩陣工作量大，并且有的目標(biāo)函數(shù)的Hesse矩陣很難計(jì)算，甚至不好求出，這就導(dǎo)致僅利用目標(biāo)函數(shù)一階導(dǎo)數(shù)的方法。什么是擬牛頓法牛頓法的迭代公式為記則上式稱為擬牛頓條件(方程)，也稱為割線方程.怎樣確定滿足這個條件的Hk+1?

對稱秩1校正

Hk稱為校正矩陣.確定

Hk的一個方法是令(2)(3)從而(4)利用(2),(4-5),(1)可寫成(5)(6)---秩1校正公式利用秩1校正極小化函數(shù)f(x),在第k次迭代中,令搜索方向(7)確定后繼點(diǎn)DFP校正是第一個擬牛頓校正，是1959年由Davidon提出的，后來由Fletcher和Powell(1963)解釋和發(fā)展的.BFGS校正是目前最流行的也是最有效的擬牛頓校正，它是由Broyden,Fletcher,Goldfarb和Schanno在1970年各自獨(dú)立提出的擬牛頓法。

對稱秩2校正DFP(Davidon-Fletche