基于MATLAB的無約束優化問題對稱秩－1法與BFGS法之探討

楊伍梅，劉 權

(1.益陽職業技術學院， 湖南 益陽 413049; 2.湖南益陽電廠， 湖南 益陽 413000)

0 前言

隨著計算機的廣泛應用，在科學研究、經濟管理和工程設計等許多領域中，常常會遇到怎樣使成本最低、利潤最大等最優化問題.在數學上往往將這類問題在合理假設下建立相應模型，將之轉化為無約束優化問題:minf(x)，x ∈Rn的求解.而擬牛頓法是目前求解無約束優化問題的最成熟，應用最廣泛的方法之一，它具有收斂速度快與數值效果好等優點.最常見的擬牛頓法有Broyden 族秩1 校正(R1)法［1］，對稱秩1 法(SR1)［1］，BFGS 法［2］，DFP 法［3］，PSB 法［4］.本文就無約束優化問題采用對稱秩1 法和BFGS 法進行探討.

1 兩種方法的比較

1.1 對稱秩1 法

設目標函數f ∶Rn→R 連續可微，無約束優化問題的基本形式為［3］:對稱秩1 法的主要思想是用一個秩 1 矩陣:去校正擬牛頓矩陣，使得所產生的矩陣:

滿足擬牛頓方程Bk+1sk= yk.其中sk= xk+1－xk，yk= gk+1－ gk.顯然因為其修正矩陣的秩為1，所以矩陣Bk更新很簡單;對所有的k，只要初始矩陣B0對稱正定，必有Bk對稱正定;且Bk≈2f(xk)，因而可使算法產生的方向近似于牛頓方向，算法具有較快的收斂速度［3］.

對稱秩1 算法的一般計算步驟如下:

步1 給定點x0∈Rn，終止誤差0 ＜ε＜1，初始對稱矩陣B0= I，令k ∶= 0.

步2 若‖gk‖ε，則算法終止，輸出xk作為近似極小點.

步3 由方程Bkdk+ g(xk)= 0 計算搜索方向dk.

步4 用線性搜索技術求步長因子αk.

步5 令xk+1= xk+αkdk，由對稱秩1 公式(2)確定Bk+1.

步6 令k ∶= k +1，轉步2.

下面給出Armijor 線性搜索［3］下的對稱秩1 算法的程序.

程序1 (對稱秩1 算法程序)

1.2 BFGS 算法

BFGS 算法是擬Newton 算法中最有效的方法之一［6］，它是由Broyden、Fletcher、Goldfarb 和Shanno 四人在1970年各自獨立提出的.其思想、步驟與對稱秩1 算法的步驟類似，只需將矩陣迭代公式(2)換成:

而且由理論可知，在Armijor 搜索準則下一般不能保證的矩陣序列{Bk}的對稱正定性.但Armijor 搜索準則因其簡單且易于程序實現深得人們的喜愛，因此，為了保證采用Armijor 搜索準則時矩陣序列{Bk}的對稱正定性，可采用如下的校正方式:

不難發現，只要B0對稱正定，上述校正公式可以保證矩陣序列{Bk}的對稱正定性，利用公式(4)產生的Hessian 矩陣的近似，避免了直接計算Hessian 矩陣的麻煩，從而具有快速的收斂性和較好的數值效果［6］，它已成為人們解決最優化問題的一類最受歡迎的方法

.

下面給出Armijor 線性搜索下BFGS 算法的步驟［7］:

步1 給定參數δ ∈(0，1)，σ ∈(0，0．5)，初始點x0∈Rn，終止誤差0 ε ＜＜1.初始對稱矩陣B0= I，令k ∶= 0.

步2 若‖gk‖ε，則算法終止，輸出xk作為近似極小點.

步3 由方程組Bkdk+g(xk)= 0 計算搜索方向dk.

步4 設mk為滿足的最小非負整數m，令αk= δmk，

步5 令xk+1= xk+ αkdk，由(4)式確定矩陣Bk+1;

步6 令k ∶= k +1，轉步2.

Armijor 線性搜索下的BFGS 算法［8］的MATLAB 程序如下:

程序2 (BFGS 算法程序)

2 無約束優化問題在matlab 中的實現

利用程序1 和程序2 求解無約束優化問題［9］:

該問題有精確解x*= (1，1)T，f(x*)= 0．

對于實例1，采用MATLAB 編寫程序，在帶有1.80GHZ 的CPU 處理器，1.00GB 內存的個人電腦上實現.表1 列出對了稱秩－1 法與BFGS 法計算實例1的數值結果，其中初始點為x1= (0，0)T，x2= (0．5，0．5)T，x3= (2，2)T，x4= (－1，－1)T，x5= (1，10)T，x6=(10，10)T.表中“init”為初始點，“k”為總的迭代次數，“f(xk)”為目標函數值，“total”為總數，“average”為平均數.

表1 對稱秩1 法與BFGS 法的數值比較

從表1 的數據中不難發現，在相同的初始條件和線性搜索下BFGS 法的平均迭代次數為60.666 次，而對稱秩1 法的平均迭代次數為32 次，可以發現BFGS法的平均迭代次數比對稱秩1 法減少約28.666 次;且當初始點離精確解較近時，兩種方法的秩代次數相差不大，當初始點離精確解較遠時，對稱秩1 法所用的秩代次數將是BFGS 法的兩倍還多，這在很大程度上影響了求解速度.從精確度而言兩種方法所求得的值都在10－11以上，都達到很高的精度，沒有太大的差別.由此可知，對于無約束優化問題的求解BFGS 法優勢更明顯.

3 結論

本文主要針對無約束優化問題，對對稱秩1 法與BFGS 法進行了探討，并編寫了兩種方法的matlab 程序，通過對實例進行求解，由其數值結果分析出BFGS算法比對稱秩－1 法更為有效;且用MATLAB 編程來計算無約束優化問題，結果可靠，計算精度高，是一個值得推廣的方法.對于兩種方法求解實例時只給出了秩代次數和精確度的數據比較，以后還可從計算時間上進行數據比較.

［1］Broyden C G．A class of methods for solving nonlinear simultaneous equations［J］．Math．Compu．，1965，19:577－593．

［2］Dennis J E，Moré J J．A characterization of superlinear convergence and its application to quasi－ Newton methods［J］．Math．Compu．，1974，28:549－560．

［3］Dennis J E．Toward a unified convergence theory for Newton－like methods，in:L．B．Rall， (Eds．)，Nonlinear functional analysis and applications［J］．Academic press，NewYork，London，1971:425－472．

［4］陳蘭平，焦寶聰．非凸無約束優化問題的廣義擬牛頓法的全局收斂性［J］．應用數學，2005 (18):573－579．

［5］李董輝，童小嬌，萬中．數值最優化算法與理論［M］．北京:科學出版社，2010．

［6］劉陶文．BFGS 方法及其在求解約束優化問題中的應用［D］．長沙:湖南大學，2006:7－12．

［7］馬昌鳳．最優化方法及其MATLAB 程序設計［M］．北京:科學出版社，2010．

［8］李明．詳解MATLAB 在最優化計算中的應用［M］．北京:電子工業出版社，2011．

［9］沈歡．用Newton 法、DFP 方法和BFGS 方法求解函數極值［D］．北京:北京大學工學學院，2011．

［10］劉敬華．無約束向量集值優化中的二次最優性條件［J］．懷化學院學報，2007 (11):30－33．