1、備：戰林電孑科被火屋7jGUILINUNIVERSITYOFELECTRONICTECHhOLOGY最優化方法課程設計題目：BFGST法分析與實現院系：數學與計算科學學院專業：統計學姓名學號：左想1200720133指導教師：李豐兵日期：2014年01月22日在求解無約束最優化問題的眾多算法中，擬牛頓法是頗受歡迎的一類算法。尤其是用于求解中小規模問題時該類算法具有較好的數值效果。BFGS算法被認為是數值效果最好的擬牛頓法，其收斂理論的研究也取得了很好的成果.在一定的條件下，BFGS算法具有全局收斂性和超線性收斂速度。然而，對于大規模最優化問題來求解，包括BFGS算法在內擬牛頓法具有明顯的缺陷。

2、有許多的例子表明，一旦處理問題很大時，一些對小規模問題非常成功的算法變得毫無吸引力。究其原因，主要是由于在中小型問題一些不太重要的因素在求解大規模問題時，變得代價很高。隨著速度更快及更復雜的計算機的出現，增強了我們的計算處理能力。同時也為我們設計算法帶來了新的課題。并行計算機的發展為求解大規模最優化問題提供了一條新途徑。關鍵詞：BFGS擬牛頓法；無約束最優化問題；大規模問題AbstractQuasi-Newtonmethodsarewelcomenumericalmethodsforsolvingoptimizationproblems.Theyareparticularlyeffective

3、whenappliedtosolvesmallormiddlesizeproblems.BFGSmethodisregardedasthemosteffectivequasi-Newtonmethodduetoitsgoodnumericalperformance.Italsopossessesverygoodglobalandsuperlinearconvergenceproperties.Ontheotherhand,however,whenappliedtosolvelargescaleproblems,quasi-NewtonmethodsincludingBFGSmethoddono

4、tperformwell.Themajordrawbackforaquasi-Newtonmethod,whenusedtosolvelargescaleoptimizationproblem,isthatthematrixgeneratedbythemethoddoesnotretainthesparsityoftheHessianmatrixoftheobjectivefunction.Thereareexamplesshowingthatmanysuccessmethodsforsolvingsmall-sizedoptimizationbecomeunattractiveoncethe

5、problemtobetackledislarge.Animportantreasonforthisfeatureisthatsomeprocessthatisimportantforsmallproblemsmaybecomeveryexpensiveforlargescaleproblems.Thefastdevelopmentofcomputerhasenhancedourabilitytosolvelargescaleproblems.Inparticular,theparallelcomputerprovidesusanewwaytosolvelargescaleproblemsef

6、ficiently.Inrecentyears,therehasbeengrowinginterestinthestudyinparallelmethods.Ithasbeenfoundthatmanygoodmethodsthatareefficientforsolvingsmallandmiddlesizeproblemscanbeparallized.KeyWords:BFGSquasi-Newtonmethod;unconstrainedoptimizationproblem,largescaleproblem1、引言錯誤！未定義書簽。2、BFGS 算法及其修正形式32.1擬牛頓法3.

7、2.2 BFGS算法4.2.3修正形式的BFGS算法5.3、BFGSI 法對大規模問題研究54、數值分析7.4.1代碼實現7.4.3算法測試8.4.4結果分析8.5、總結9.5.1總結概括9.5.2個人感言9.6、參考文獻：10最優化問題在經濟計劃，生產管理，交通，運輸，物理和通信等居多領域有廣泛而又深入的應用。本文主要考察無約束最優化問題。無約束最優化問題的數學模型如下：minf(x),xRn(1.1)其中f：RnTR是一個連續可微函數.我們用f和f分別表示在處的梯度和Hessian陣。在求解上述無約束最優化問題時，通常采用算法是迭代算法，其迭代格式如下：乂小=Xk+%dk,(1.2)其中為

8、搜索方向，一般滿足f，因而是f在處的一個下降方向。稱為步長，由線性搜索得到，為簡便起見，在整篇文章中，我們分別把f記為，f記為f,f記為f。上面的迭代法稱為下降算法，自上世紀70年代以來，下降算法的研究得到了飛速發展。迄今為止，已提出了許多的下降算法，這些算法具有各自的優缺點。常用的算法有：最速下降法.即取。該算法的優點是計算簡便且存儲量小，可用于大規模最優化問題求解。但該算法僅有線性收斂速度，收斂速度太慢。該算法的優點是收斂速度快，可達到二階收斂速度，但每次迭代需計算目標函數Hessian矩陣，計算量大。線性收斂速度，而且，大多數擬牛頓法可產生下降方向，但擬牛頓法需貯存一個矩陣。牛頓法.即取

9、=f其中f表示f在處的Hessian陣擬牛頓法.即取0 其中是的近似。擬牛頓法的優點是超(1.3)共腕梯度法.即取(i)Armijo搜索：給定6f,步長滿足下列不等式ff(1.6)確定步長的一種方式是令其為集合滿足條件(1.6)的最大者其中參數的選取依賴于不同的共腕梯度法。 優點在于克服了最速下降法收斂慢的缺點， 又避免了存貯和計算牛頓法所需的二階導數信息。所以對大規模問題來說，也是一種很不錯的算法。超記憶梯度法.即取(1.4)其中當時,Miele和Cantrell研究了這種記憶梯度法(memorygradientmethod)。同時Cantrell發現，當用于二次函數極小值問題求解時，記憶梯

10、度法與Fletcher-Reeves算法是一致的.Cragg和Levy進一步地研究了一種超記憶梯度法(supermemorygradientmethod),實際上是記憶梯度法的一般化.其他有關超記憶梯度法可參考文獻3,4等。無論是記憶梯度法還是超記憶梯度法， 都比共腕梯度法更為有效， 因為它使用了更多的先前迭代信息， 并且增加了參數的自由度，但在形式上與共腕梯度法很相似，并且避免了計算與Hessian陣有關的矩陣，盡管收斂速度不如擬牛頓法，但也適合于大規模稀疏問題的求解。在選取步長時，通常有如下幾種方式：精確搜索：即滿足(1.5)此種搜索由于計算量大，所以在實際中很少采用。非精確搜索:(ii)

11、Wolfe-Powell搜索：即步長同時滿足下面的兩個不等式：fff;ff,(1.7)其中為常數，滿足-2.BFGS 算法及其修正形式自上世紀七十年代以來，關于擬Newton法的收斂性研究取得了重大進展。假設目標函數f(x)是凸的，采用精確線性搜索時，Powell等證明了Broyden族算法具有全局收斂性和超線性收斂速率。當采用非精確線性搜索時，即Wolfe-Powell準則確定步長，Byrd等在1987年證明了Broyden族算法(除DFP算法外)具有全局收斂性。若假設目標函數是一致凸的，其二階導數矩陣在極小點附近滿足Lipschitz條件，且在正定的條件下，還證明了其收斂速度是Q-超線性的

12、.Bryd和Nocedal證明了采用Armijo線性搜索時，BFGS方法的全局收斂性等在文獻得出： 當目標函數是偽凸函數時，Broyden算法依然具有全局收斂性.Li證明了：當目標函數是凸二次函數，DFP算法仍然具有全局收斂性。在2001年，Li和Fukushima在文獻提出了一種求解非凸函數極小值問題的修正擬牛頓法，并證明了修正的擬牛頓法的全局收斂性，并在適當的假設條件下，證明了超線性收斂速率。本文將側重于對擬牛頓法中BFGS算法的研究.在眾多求解無約束最優化的擬牛頓法中，BFGS(Broyden,Fletcher,Goldfarb,Shanno)法被認為是數值效果最好的方法該方法中的修正公

13、式為一，(2.1)其中，f修正公式(2.1)具有如下重要性質：定理2.1設是由BFGS修正公式產生，若矩陣是對稱正定的且，則矩陣也是正定的。求解(1.1)的BFGS算法步驟如下：算法2.1步1:取初始點，初始對稱正定矩陣。精度e。令步2:若，則算法終止。得問題的解，否則，轉步3。步3:解線性方程組(2.2)得解.轉步4.步4:由線性搜索方法確定步長.步5:令.若，則得解.否則，由擬牛頓修正公式(2.1)確定步6:令,轉步2.若將算法(2.1)中的的修正公式換成其它公式，則得相應的擬牛頓法的計算步驟。對于非凸函數的最優化問題，即使采用精確搜索，標準的BFGS方法也不具有全局收斂性.為 了 克 服

14、BFGS算 法 的 這 種 缺 陷 ， 下 面 簡 單 扼 要 地 介 紹BFGS的 修 正 形式MBFGS(ModifiedBFGS算法及保守BFGS修正一CBFGS(cautionBFGS瘴法.詳細內容可看參考文獻.MBFG鼠的修正公式與標準的BFGS修正公式形式上是完全相同的， 所不同的是其中的定義，LiFukushima的修正BFGS公式中的定義如下：,其中：。為了保證的對稱正定性.可以通過對參數的調整，使得,(2.3)滿足上式的的取法有許多.例如可由下式確定是常數。MBFGSJ法的一個重要優點是：該算法用于求解非凸函數極小值問題時，也具有全局收斂性.而且的對稱正定性與算法的線性搜索以

15、及目標函數的凸性無關文獻17提出了一種保守BFGS修正一CBFG夠正方式.具體如下:，(2,4)其中，是常數。容易看出，若對稱正定，則有CBFGS公式產生的矩陣序列滿足因此，對所有的，矩陣對稱正定.該性質與算法的線性搜索以及函數的凸性無關.此外，若不等式f,(2,5)成立，則算法還原為標準的BFGS算法.因而，算法的仿射不變性成立。3.BFGS 算法對大規模問題研究所謂的大規模問題，就是所涉及的變量的維數很高，通常上千維，有的甚至達到了萬維，百萬維的.一般來說，大規模問題的二階導Hessian陣常常是對稱的、正定的，尤其具有某種稀疏的結構.在求解大規模問題時，我們總是希望得到收斂速度快、計算量

16、少和存貯量小的算法.而用于求解中小型最優化問題的傳統算法，來求解大規模問題時，許多的優點已經變得不太重要，(比如數值效果較好的BFGS算法，雖然校正矩陣能夠繼承正定性和對稱性，卻不能繼承其稀疏性)，且在經過一定數量的迭代后，先前的信息有可能被舍棄，算法必須計算新的信息重新開始，例如共腕梯度法.下面簡要地介紹幾種大規模算法：其中,其中Nocedal研究了一種有限記憶擬牛頓法.動機是當存儲成為關鍵因素，怎樣利用BFGS以牛頓法來求解大規模最優化問題.其基本思想是利用最新m步迭代信息去產生新的近似Hessian矩陣.在每次迭代時用最新的信息去取代舊的信息.同時數值結果也表明逐漸增加迭代信息時， 數值

17、效果也會逐漸改善.在下一節將作詳細的介紹。求解具有線性方程組Hd=-g的大規模問題最常用的方法是預處理共腕梯度法（PCG） ,可見文獻19。考慮求解線性方程組其中A是稀疏、對稱和正定矩陣.共腕梯度法是有效的方法之一，但由于其收斂性受到依賴于系數矩陣A的譜條件數，即最大特征值和最小特征值之比.為了改善收斂速度，就要設法改善矩陣A的條件數.通常是用預處理技術來改進共腕梯度法，其做法是使用左或右預條件矩陣M使得方程組變成易于求解的形式：,或者然后使用共腕梯度法求之。構造預條件矩陣的方法很多，如不完全分解法，結合實際問題的區域分解做預條件矩陣，基于迭代法的多項式預條件技術，基于系數矩陣的近似逆的預條件

18、技術等。4 .數值實驗無約束優化問題在matlab中可由三個功能函數實現， 即函數fminbnd（單變量的最小函數值） 、fminsearch（多變量的最小函數值）、fminune（多變量函數最小值時的變量值）,其中fminbnd和fminsearch的優化算法簡單，處理簡單問題方便，但對復雜問題卻力不從心；fminunc的算法復雜，可解決較為復雜的問題，且提供了幾種可供選擇的不同算法.Fminunc算法為無約束優化提供了大型優化和中型優化算法引，由option-s中的參數控制；Fminunc算法同時也為中型優化算法的搜索方向提供了4種算法，由options中的參數hessupdate控制，當

19、hessupdate=bfgs（默認值），擬Newton的BFG宓式；當hessupdate=dfp,擬Newton的DF吆式。實例分析：分別用BFGW法和DFPTJ法求解如下的Powell奇異函數的最小值點6解：可以看出，最小值點即為(0000)點.此例只是為比較各方法的應用，并無大的實際意義。在matlab里編制的程序并運行結果如下：functionx,val,k=bfgs(fun,gfun,x0)maxk=500;%給出最大迭代次數rho=0.55;sigma=0.4;epsilon=1e-5;k=0;n=length(x0);Bk=eye(n);%Bk=feval(Hess,x0);w

20、hile(kmaxk)gk=feval(gfun,x0);%計算梯度if(norm(gk)epsilon),break;end%檢驗終止準則dk=-Bkgk;%解方程組，計算搜索方向m=0;mk=0;while(m20)%用 Armijo 搜索求步長newf=feval(fun,x0+rhoAm*dk);oldf=feval(fun,x0);if(newf0)Bk=Bk-(Bk*sk*sk*Bk)/(sk*Bk*sk)+(yk*yk)/(yk*sk);endk=k+1;x0=x;endval=feval(fun,x0);functionf=pfun(x)f=(x(1)+x(2)A2+5*(x(

21、3)-x(4)A2+(x(2)-2*x(3)A4+10*(x(1)-x(4)A4x0=3,-1,0,1%BFGS 算法實現%采用混合插值法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.01560.0015-0.0146-0.0146%DFP 算法實現%采用混合插值法options(6)=1;Options(7)=0;fminunc(pfun,x0,Options)ans=0.0214-0.00210.01190.0120%采用立方差值法options(6)=1;Options(7)=1;fminunc(pfun,x0,Options)ans=-0.01390.0014-0.0064-0.0064其中對函數fminunc來說。Options(6)為控制搜索方向算法，取默認值O時，是BFGS方法；取1時為DFP方法。0ptionsw(7)為控制插值法，其中取默認值0時是混合插值；取1時為立方插值。5 .總結5.1總結概括在當今社會，優化問題已成為科學研究、工程設計和