BFGS算法分析與實現(xiàn)

1、最 優(yōu) 化 方 法課 程 設 計題 目：BFGS算法分析與實現(xiàn)院 系： 數(shù)學與計算科學學院 專 業(yè)： 統(tǒng)計學 姓名學號： 左想 1200720133 指導教師： 李豐兵 日 期： 2014 年 01 月 22 日摘 要在求解無約束最優(yōu)化問題的眾多算法中,擬牛頓法是頗受歡迎的一類算法。尤其是用于求解中小規(guī)模問題時該類算法具有較好的數(shù)值效果。 BFGS 算法被認為是數(shù)值效果最好的擬牛頓法，其收斂理論的研究也取得了很好的成果. 在一定的條件下，BFGS 算法具有全局收斂性和超線性收斂速度。 然而，對于大規(guī)模最優(yōu)化問題來求解，包括 BFGS 算法在內(nèi)擬牛頓法具有明顯的缺陷。有許多的例子表明，一旦處理問

2、題很大時，一些對小規(guī)模問題非常成功的算法變得毫無吸引力。究其原因，主要是由于在中小型問題一些不太重要的因素在求解大規(guī)模問題時，變得代價很高。隨著速度更快及更復雜的計算機的出現(xiàn)，增強了我們的計算處理能力。 同時也為我們設計算法帶來了新的課題。并行計算機的發(fā)展為求解大規(guī)模最優(yōu)化問題提供了一條新途徑。關鍵詞：BFGS 擬牛頓法；無約束最優(yōu)化問題；大規(guī)模問題AbstractQuasi-Newton methods are welcome numerical methods for solving optimization problems. They are particularly effectiv

3、e when applied to solve small or middle size problems. BFGS method is regarded as the most effective quasi-Newton method due toits good numerical perfor mance. It also possesses very good global and superlinear con vergen ceproperties. On the other hand, however, when applied to solve larg escalepro

4、blems, quasi-Newton methods including BFGS method don ot perform well. Themajor drawback for a quasi-Newton method, when used to solve large scaleoptimization problem, is that the matrix gener ated by the method does not retain thesparsity of the Hessian matrix of the objective function. There are e

5、xamples showing that many success methods for solving small-sized optimization become unattractive once the problem to be tackled is large. An important reason for thisfeature is that some process that is important for small problems may become veryexpensive for large scale problems.The fast develop

6、ment of computer has enhanced our ability to solve large scaleproblems. In particular, the parallel computer provides us a new way to solve largescale problems efficiently. In recent years, there has been growing interest in the studyin parallel methods. It has been found that many good methods that

7、 are efficient forsolving small and middle size problems can be parallized. Key Words: BFGS quasi-Newton method; unconstrained optimization problem, large scale problem目 錄1、引言12、BFGS算法及其修正形式32.1 擬牛頓法32.2 BFGS算法42.3 修正形式的BFGS算法53、BFGS算法對大規(guī)模問題研究54、數(shù)值分析74.1代碼實現(xiàn)74.3 算法測試84.4結果分析85、總結95.1 總結概括95.2 個人感言96

8、、參考文獻：10最優(yōu)化課程設計1 .引言最優(yōu)化問題在經(jīng)濟計劃，生產(chǎn)管理，交通，運輸，物理和通信等居多領域有廣泛而又深入的應用。本文主要考察無約束最優(yōu)化問題。無約束最優(yōu)化問題(UC)的數(shù)學模型如下: (1.1)其中是一個連續(xù)可微函數(shù).我們用 x和 2 (x)分別表示f在x 處的梯度和 Hessian 陣。在求解上述無約束最優(yōu)化問題時，通常采用算法是迭代算法，其迭代格式如下: ， (1.2)其中dk為搜索方向，一般滿足 (xk)Tdk<0，因而dk是 (x)在xk處的一個下降方向。k>0稱為步長，由線性搜索得到，為簡便起見，在整篇文章中，我們分別把(xk)記為gk， (xk)記為k ，

9、 (x*)記為* 。上面的迭代法稱為下降算法，自上世紀 70 年代以來，下降算法的研究得到了飛速發(fā)展。迄今為止，已提出了許多的下降算法，這些算法具有各自的優(yōu)缺點。 常用的算法有： 最速下降法. 即取dk=-gk。該算法的優(yōu)點是計算簡便且存儲量小，可用于大規(guī)模最優(yōu)化問題求解。但該算法僅有線性收斂速度，收斂速度太慢。 牛頓法.即取dk=-2(xk)-1gk。其中2 (xk)表示在xk處的Hessian陣。該算法的優(yōu)點是收斂速度快，可達到二階收斂速度，但每次迭代需計算目標函數(shù)Hessian矩陣，計算量大。 擬牛頓法. 即取dk=-Hkgk。其中Hk 是2(xk)-1的近似。擬牛頓法的優(yōu)點是超線性收斂

10、速度，而且，大多數(shù)擬牛頓法可產(chǎn)生下降方向，但擬牛頓法需貯存一個矩陣。共軛梯度法.即取dk=-gk ，k=1-gk+k*dk-1，k2 (1.3)1其中參數(shù)k的選取依賴于不同的共軛梯度法。優(yōu)點在于克服了最速下降法收斂慢的缺點，又避免了存貯和計算牛頓法所需的二階導數(shù)信息。所以對大規(guī)模問題來說，也是一種很不錯的算法。超記憶梯度法. 即取dk=-gk ，k=1-i=1mk-i+1*gk-i+1，k2 (1.4)其中當km時，k-i+1=m-1gk2gk2+gkTgk-i+1,i=1,2,3m;k=1-i=2mk-i+1Miele 和 Cantrell 研究了這種記憶梯度法(memory gradien

11、t method)。同時 Cantrell發(fā)現(xiàn)，當用于二次函數(shù)極小值問題求解時,記憶梯度法與 Fletcher- -Reeves 算法是一致的.Cragg 和 Levy 進一步地研究了一種超記憶梯度法(super-memory gradient method),實際上是記憶梯度法的一般化.其他有關超記憶梯度法可參考文獻3,4等。無論是記憶梯度法還是超記憶梯度法,都比共軛梯度法更為有效,因為它使用了更多的先前迭代信息,并且增加了參數(shù)的自由度,但在形式上與共軛梯度法很相似,并且避免了計算與Hessian陣有關的矩陣,盡管收斂速度不如擬牛頓法,但也適合于大規(guī)模稀疏問題的求解。在選取步長k時，通常有如

12、下幾種方式：精確搜索: 即k滿足 k=argmin>0(xk+dk) (1.5)此種搜索由于計算量大，所以在實際中很少采用。非精確搜索:(i) Armijo 搜索:給定 (0,1),步長k滿足下列不等式 xk+dkxk+ xkTdk , (1.6)確定步長k的一種方式是令其為集合1,2,3, 滿足條件(1.6)的最大者。2(ii) Wolfe-Powell 搜索: 即步長同時滿足下面的兩個不等式: xk+kdkxk+1 xkTdk；xk+kdkTdk2 xkTdk， (1.7)其中1,2為常數(shù),滿足0112,1212. BFGS 算法及其修正形式自上世紀七十年代以來，關于擬 Newton

13、 法的收斂性研究取得了重大進展。 假設目標函數(shù) f(x)是凸的，采用精確線性搜索時，Powell 等證明了 Broyden 族算法具有全局收斂性和超線性收斂速率。 當采用非精確線性搜索時，即Wolfe-Powell準則確定步長，Byrd等在1987年證明了Broyden 族算法(除DFP 算法外)具有全局收斂性。 若假設目標函數(shù)是一致凸的，其二階導數(shù)矩陣在極小點附近滿足 Lipschitz 條件，且在正定的條件下，還證明了其收斂速度是 Q-超線性的. Bryd 和 Nocedal 證明了采用 Armijo 線性搜索時，BFGS 方法的全局收斂性等在文獻得出：當目標函數(shù)是偽凸函數(shù)時，Broyde

14、n 算法依然具有全局收斂性.Li 證明了：當目標函數(shù)是凸二次函數(shù)，DFP 算法仍然具有全局收斂性。在 2001 年，Li 和 Fukushima 在文獻提出了一種求解非凸函數(shù)極小值問題的修正擬牛頓法，并證明了修正的擬牛頓法的全局收斂性，并在適當?shù)募僭O條件下，證明了超線性收斂速率。本文將側重于對擬牛頓法中 BFGS 算法的研究. 在眾多求解無約束最優(yōu)化的擬牛頓法中, BFGS(Broyden,Fletcher, Goldfarb,Shanno)法被認為是數(shù)值效果最好的方法.該方法中Bk 的修正公式為 Bk+1=Bk+ykykTykTsk-BkskskTBkskTBksk， (2.1)其中sk=x

15、k+1-xk,yk= f xk+1- xk.修正公式(2.1)具有如下重要性質:定理 2.1 設Bk+1是由 BFGS 修正公式產(chǎn)生,若矩陣Bk是對稱正定的且ykTsk>0，則矩陣Bk+1也是正定的。3求解(1.1)的 BFGS 算法步驟如下：算法 2.1步 1 :取初始點, x0 Rn，初始對稱正定矩陣B0Rn*n。精度 >0。令 k = 0。步 2 :若| f xk|，則算法終止。得問題的解xk，否則，轉步 3。步 3 :解線性方程組 Bkd+ f xk=0 (2.2)得解dk .轉步 4.步 4 :由線性搜索方法確定步長k.步 5 :令xk+1=xk+kdk.若| f xk|

16、，則得解xk+1.否則，由擬牛頓修正公式(2.1)確定Bk+1.步 6 :令 k=k+1，轉步 2.若將算法(2.1)中的Bk的修正公式換成其它公式，則得相應的擬牛頓法的計算步驟。對于非凸函數(shù)的最優(yōu)化問題，即使采用精確搜索，標準的 BFGS 方法也不具有全局收斂性.為了克服 BFGS 算法的這種缺陷，下面簡單扼要地介紹 BFGS 的修正形式MBFGS(Modified BFGS)算法及保守 BFGS 修正CBFGS(caution BFGS)算法.詳細內(nèi)容可看參考文獻.MBFGS 法的修正公式與標準的 BFGS 修正公式形式上是完全相同的，所不同的是其中yk的定義，LiFukushima的修正

17、 BFGS 公式中的yk定義如下: yk=k+vk(xk+1-xk)，其中: k= f xk+1- f xk。為了保證Bk+1的對稱正定性.可以通過對參數(shù)vk的調(diào)整，使得 ykTsk>0， k 0, (2.3)滿足上式的vk的取法有許多.例如vk可由下式確定4vk=ctk| xk|n，其中，tk=1+max-kTsk|sk|2,0c-1| xk|-n，其中 u > 0, c> 0是常數(shù)。MBFGS 算法的一個重要優(yōu)點是:該算法用于求解非凸函數(shù)極小值問題時，也具有全局收斂性.而且Bk的對稱正定性與算法的線性搜索以及目標函數(shù)的凸性無關.文獻17提出了一種保守 BFGS 修正CBF

18、GS 修正方式.具體如下: Bk+1=Bk-BkskskTBkBkskTBk+ykykTykTsk ，ykTsk|sk|2>| f xk|uBk ，ykTsk|sk|2| f xk|u， (2,4)其中，>0, u>0是常數(shù)。容易看出，若Bk對稱正定，則有 CBFGS 公式產(chǎn)生的矩陣序列Bk 滿足ykTsk>0。因此，對所有的 k 0，矩陣Bk對稱正定.該性質與算法的線性搜索以及函數(shù)f(x)的凸性無關.此外，若不等式 ykTsk|sk|2>| xk|u， (2,5)成立，則算法還原為標準的 BFGS 算法.因而，算法的仿射不變性成立。3.BFGS算法對大規(guī)模問題研

19、究所謂的大規(guī)模問題，就是所涉及的變量的維數(shù)很高，通常上千維，有的甚至達到了萬維，百萬維的. 一般來說，大規(guī)模問題 f(x)的二階導Hessian陣f(x)2常常是對稱的、正定的，尤其具有某種稀疏的結構.在求解大規(guī)模問題時，我們總是希望得到收斂速度快、計算量少和存貯量小的算法. 而用于求解中小型最優(yōu)化問題的傳統(tǒng)算法，來求解大規(guī)模問題時，許多的優(yōu)點已經(jīng)變得不太重要，(比如數(shù)值效果較好的 BFGS 算法，雖然校正矩陣Bk+1能夠繼承正定性和對稱性，卻不能繼承其稀疏性)，且在經(jīng)過一定數(shù)量的迭代后，先前的信息有可能被舍棄，算法必須計算新的信息重新開始,例如共軛梯度法.下面簡要地介紹幾種大規(guī)模算法：5No

20、cedal 研究了一種有限記憶擬牛頓法.動機是當存儲成為關鍵因素,怎樣利用BFGS擬牛頓法來求解大規(guī)模最優(yōu)化問題.其基本思想是利用最新m步迭代信息去產(chǎn)生新的近似 Hessian 矩陣.在每次迭代時用最新的信息去取代舊的信息.同時數(shù)值結果也表明逐漸增加迭代信息時，數(shù)值效果也會逐漸改善. 在下一節(jié)將作詳細的介紹。求解具有線性方程組 Hd = g的大規(guī)模問題最常用的方法是預處理共軛梯度法(PCG)，可見文獻19。考慮求解線性方程組Ax =b其中 A是稀疏、對稱和正定矩陣.共軛梯度法是有效的方法之一，但由于其收斂性受到依賴于系數(shù)矩陣 A的譜條件數(shù)，即最大特征值和最小特征值之比. 為了改善收斂速度，就要

21、設法改善矩陣 A的條件數(shù). 通常是用預處理技術來改進共軛梯度法，其做法是使用左或右預條件矩陣M 使得方程組變成易于求解的形式：AM-1y=b ，x=M-1y或者M-1Ax=M-1b然后使用共軛梯度法求之。構造預條件矩陣的方法很多，如不完全分解法，結合實際問題的區(qū)域分解做預條件矩陣，基于迭代法的多項式預條件技術，基于系數(shù)矩陣的近似逆的預條件技術等。4數(shù)值實驗無約束優(yōu)化問題在matlab中可由三個功能函數(shù)實現(xiàn)，即函數(shù)fminbnd(單變量的最小函數(shù)值)、fminsearch (多變量的最小函數(shù)值)、fminune(多變量函數(shù)最小值時的變量值)其中fminbnd和fminsearch的優(yōu)化算法簡單，

22、處理簡單問題方便，但對復雜問題卻力不從心；fminunc的算法復雜，可解決較為復雜的問題，且提供了幾種可供選擇的不同算法Fminunc算法為無約束優(yōu)化提供了大型優(yōu)化和中型優(yōu)化算法引，由option -s中的參數(shù)控制；Fminunc算法同時也為中型優(yōu)化算法的搜索方向提供了4種算法，由options中的參數(shù)hessupdate控制，當hessupdate=bfgs(默認值)，擬Newton的BFGS公式；當hessupdate=dfp，擬Newton的DFP公式。實例分析：分別用BFGS方法和DFP方法求解如下的Powell奇異函數(shù)的最小值點6f=(x1+x2)2+5(x3-x4)2+(x2-2x

23、3)4+10(x1-x4)4解：可以看出，最小值點即為(0 0 0 0)點此例只是為比較各方法的應用，并無大的實際意義。在matlab里編制的程序并運行結果如下：function x,val,k=bfgs(fun,gfun,x0)maxk=500; %給出最大迭代次數(shù)rho=0.55;sigma=0.4;epsilon=1e-5;k=0;n=length(x0);Bk=eye(n);%Bk=feval('Hess',x0);while(k<maxk)    gk=feval(gfun,x0); %計算梯

24、度    if (norm(gk)<epsilon),break;end %檢驗終止準則    dk=-Bkgk; %解方程組，計算搜索方向    m=0;mk=0;    while(m<20) %用Armijo搜索求步長        newf=feval(fun,x0+rhom*dk); &

25、#160;      oldf=feval(fun,x0);        if (newf<oldf+sigma*rhom*gk'*dk)            mk=m;break;        end  &#

26、160;     m=m+1;    end    %BFGS校正    x=x0+rhomk*dk;    sk=x-x0;yk=feval(gfun,x)-gk;    if (yk'*sk>0)        Bk=Bk-(Bk*sk*sk

27、'*Bk)/(sk'*Bk*sk)+(yk*yk')/(yk'*sk);    end    k=k+1;x0=x;7endval=feval(fun,x0);function f=pfun(x)f=(x(1)+x(2)2+5*(x(3)-x(4)2+(x(2)-2*x(3)4+10*(x(1)-x(4)4x0=3,-1,0,1%BFGS算法實現(xiàn)%采用混合插值法options(6)=0;Options(7)=0;fminunc('pfun',x0,Options)ans=0.0027 -0.0003 -0.0057 -0.0057%采用立方差值法options(6)=0;Options(7)=1;fminunc('pfun',x0,Options)ans=-0.0156 0.0015 -0.0146 -0.0146%DFP算法實現(xiàn)%采用混合插值法options(6)=1;Options(7)=0;fminunc('pfun',x0,Options)ans=0.0214 -0.0021 0.0119 0.0120%采用立方差值法options(6)=1;Options(7)=1;fminunc(