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

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

2、題很大時(shí)，一些對(duì)小規(guī)模問(wèn)題非常成功的算法變得毫無(wú)吸引力。究其原因，主要是由于在中小型問(wèn)題一些不太重要的因素在求解大規(guī)模問(wèn)題時(shí)，變得代價(jià)很高。隨著速度更快及更復(fù)雜的計(jì)算機(jī)的出現(xiàn)，增強(qiáng)了我們的計(jì)算處理能力。 同時(shí)也為我們?cè)O(shè)計(jì)算法帶來(lái)了新的課題。并行計(jì)算機(jī)的發(fā)展為求解大規(guī)模最優(yōu)化問(wèn)題提供了一條新途徑。關(guān)鍵詞：BFGS 擬牛頓法；無(wú)約束最優(yōu)化問(wèn)題；大規(guī)模問(wèn)題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算法對(duì)大規(guī)模問(wèn)題研究54、數(shù)值分析74.1代碼實(shí)現(xiàn)74.3 算法測(cè)試84.4結(jié)果分析85、總結(jié)95.1 總結(jié)概括95.2 個(gè)人感言96

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

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

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

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

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

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

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

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

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

17、 BFGS 公式中的yk定義如下: yk=k+vk(xk+1-xk)，其中: k= f xk+1- f xk。為了保證Bk+1的對(duì)稱正定性.可以通過(guò)對(duì)參數(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 算法的一個(gè)重要優(yōu)點(diǎn)是:該算法用于求解非凸函數(shù)極小值問(wèn)題時(shí)，也具有全局收斂性.而且Bk的對(duì)稱正定性與算法的線性搜索以及目標(biāo)函數(shù)的凸性無(wú)關(guān).文獻(xiàn)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對(duì)稱正定，則有 CBFGS 公式產(chǎn)生的矩陣序列Bk 滿足ykTsk>0。因此，對(duì)所有的 k 0，矩陣Bk對(duì)稱正定.該性質(zhì)與算法的線性搜索以及函數(shù)f(x)的凸性無(wú)關(guān).此外，若不等式 ykTsk|sk|2>| xk|u， (2,5)成立，則算法還原為標(biāo)準(zhǔn)的 BFGS 算法.因而，算法的仿射不變性成立。3.BFGS算法對(duì)大規(guī)模問(wèn)題研

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

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

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

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

23、3)4+10(x1-x4)4解：可以看出，最小值點(diǎn)即為(0 0 0 0)點(diǎn)此例只是為比較各方法的應(yīng)用，并無(wú)大的實(shí)際意義。在matlab里編制的程序并運(yùn)行結(jié)果如下：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); %計(jì)算梯

24、度    if (norm(gk)<epsilon),break;end %檢驗(yàn)終止準(zhǔn)則    dk=-Bkgk; %解方程組，計(jì)算搜索方向    m=0;mk=0;    while(m<20) %用Armijo搜索求步長(zhǎng)        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算法實(shí)現(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算法實(shí)現(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(