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

楊伍梅，劉 權(quán)

(1.益陽職業(yè)技術(shù)學(xué)院， 湖南 益陽 413049; 2.湖南益陽電廠， 湖南 益陽 413000)

0 前言

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

1 兩種方法的比較

1.1 對稱秩1 法

設(shè)目標(biāo)函數(shù)f ∶Rn→R 連續(xù)可微，無約束優(yōu)化問題的基本形式為［3］:對稱秩1 法的主要思想是用一個(gè)秩 1 矩陣:去校正擬牛頓矩陣，使得所產(chǎn)生的矩陣:

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

對稱秩1 算法的一般計(jì)算步驟如下:

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

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

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

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

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

步6 令k ∶= k +1，轉(zhuǎn)步2.

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

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

1.2 BFGS 算法

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

而且由理論可知，在Armijor 搜索準(zhǔn)則下一般不能保證的矩陣序列{Bk}的對稱正定性.但Armijor 搜索準(zhǔn)則因其簡單且易于程序?qū)崿F(xiàn)深得人們的喜愛，因此，為了保證采用Armijor 搜索準(zhǔn)則時(shí)矩陣序列{Bk}的對稱正定性，可采用如下的校正方式:

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

.

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

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

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

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

步4 設(shè)mk為滿足的最小非負(fù)整數(shù)m，令αk= δmk，

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

步6 令k ∶= k +1，轉(zhuǎn)步2.

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

程序2 (BFGS 算法程序)

2 無約束優(yōu)化問題在matlab 中的實(shí)現(xiàn)

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

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

對于實(shí)例1，采用MATLAB 編寫程序，在帶有1.80GHZ 的CPU 處理器，1.00GB 內(nèi)存的個(gè)人電腦上實(shí)現(xiàn).表1 列出對了稱秩－1 法與BFGS 法計(jì)算實(shí)例1的數(shù)值結(jié)果，其中初始點(diǎn)為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”為初始點(diǎn)，“k”為總的迭代次數(shù)，“f(xk)”為目標(biāo)函數(shù)值，“total”為總數(shù)，“average”為平均數(shù).

表1 對稱秩1 法與BFGS 法的數(shù)值比較

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

3 結(jié)論

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

［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］陳蘭平，焦寶聰．非凸無約束優(yōu)化問題的廣義擬牛頓法的全局收斂性［J］．應(yīng)用數(shù)學(xué)，2005 (18):573－579．

［5］李董輝，童小嬌，萬中．?dāng)?shù)值最優(yōu)化算法與理論［M］．北京:科學(xué)出版社，2010．

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

［7］馬昌鳳．最優(yōu)化方法及其MATLAB 程序設(shè)計(jì)［M］．北京:科學(xué)出版社，2010．

［8］李明．詳解MATLAB 在最優(yōu)化計(jì)算中的應(yīng)用［M］．北京:電子工業(yè)出版社，2011．

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

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