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

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

設A是n×n對稱矩陣,若Rn

中的兩個方向d1

和d2滿足(d1)T

Ad2=0（1）則稱這兩個方向關于A共軛,或稱它們關于A正交.則稱這組方向是A共軛,或稱它們?yōu)锳的k個共軛方向定義1設A是n×n對稱矩陣,若Rn中的兩個方向d1和最優(yōu)化理論第4章4無約束優(yōu)化共軛梯度法擬牛頓法課件最優(yōu)化理論第4章4無約束優(yōu)化共軛梯度法擬牛頓法課件最優(yōu)化理論第4章4無約束優(yōu)化共軛梯度法擬牛頓法課件最優(yōu)化理論第4章4無約束優(yōu)化共軛梯度法擬牛頓法課件最優(yōu)化理論第4章4無約束優(yōu)化共軛梯度法擬牛頓法課件共軛梯度法先討論對于二次凸函數(shù)的共軛梯度法,考慮問題求解方法共軛梯度法先討論對于二次凸函數(shù)的共軛梯度法,考慮問題求解方法最優(yōu)化理論第4章4無約束優(yōu)化共軛梯度法擬牛頓法課件最優(yōu)化理論第4章4無約束優(yōu)化共軛梯度法擬牛頓法課件

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

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

定理3

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

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

i

m),下列關系成立:定理3對于正定二次函數(shù),證明:顯然m1,下用歸納法(對i)證之.

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

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

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

i具有下述表達式定理4對于正定二次函數(shù),FR法中因子i具有下述表達式證明:證明:FR共軛梯度法(對二次凸函數(shù))共軛梯度法步驟FR共軛梯度法(對二次凸函數(shù))共軛梯度法步驟3,如果j<n,轉步4,否則,轉53,如果j<n,轉步4,否則,轉5例

用FR法求解下列問題例用FR法求解下列問題令第一次迭代，目標函數(shù)f(x)在點x處的梯度令第一次迭代，目標函數(shù)f(x)在點x處的梯度第2次迭代目標函數(shù)在點x處的梯度(2)第2次迭代目標函數(shù)在點x處的梯度(2)構造搜索方向d.先計算因子

(2)1令構造搜索方向d.先計算因子(2)1令最優(yōu)化理論第4章4無約束優(yōu)化共軛梯度法擬牛頓法課件一般迭代格式用于一般函數(shù)的共軛梯度法－非線性共軛梯度法一般迭代格式用于一般函數(shù)的共軛梯度法－非線性共軛梯度法----PRP(Polak-Ribiere-Polyar-----SW(Sorenson-Wolfe----Daniel-----Dixon----PRP(Polak-Ribiere-Polyar--擬牛頓法牛頓法成功的關鍵在于利用了Hesse矩陣提供的曲率信息，而計算Hesse矩陣工作量大，并且有的目標函數(shù)的Hesse矩陣很難計算，甚至不好求出，這就導致僅利用目標函數(shù)一階導數(shù)的方法。什么是擬牛頓法擬牛頓法牛頓法成功的關鍵在于利用了Hesse矩陣提供的曲率信牛頓法的迭代公式為牛頓法的迭代公式為最優(yōu)化理論第4章4無約束優(yōu)化共軛梯度法擬牛頓法課件記則記則上式稱為擬牛頓條件(方程)，也稱為割線方程.怎樣確定滿足這個條件的Hk+1?上式稱為擬牛頓條件(方程)，也稱為割線方程.

對稱秩1校正

Hk稱為校正矩陣.確定

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

對稱秩2校正DFP校正是第一個擬牛頓校正，是1959年由Davidon提DFP(Davidon-Fletcher-Power)公式DFP(Davidon-Fletcher-Power)公式最優(yōu)化理論第4章4無約束優(yōu)化共軛梯度法擬牛頓法課件DFP算法DFP算法最優(yōu)化理論第4章4無約束優(yōu)化共軛梯度法擬牛頓法課件例

用DFP方法求解下列問