最速下降法與牛頓法及其區(qū)別

最速下降法與牛頓法及其區(qū)別■=J最摘要：無(wú)約束優(yōu)化方法是優(yōu)化技術(shù)中極為重要和基本內(nèi)容之一。它不僅可以直接用來(lái)求解無(wú)約束優(yōu)化問(wèn)題，而且很多約束優(yōu)化問(wèn)題也常將其轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題，然后用無(wú)約束優(yōu)化方法來(lái)求解。最速下降法和牛頓法是比較常見(jiàn)的求解無(wú)約束問(wèn)題的最優(yōu)化方法，這兩種算法作為基本算法，在最優(yōu)化方法中占有重要的地位。其中最速下降法又稱(chēng)梯度法，其優(yōu)點(diǎn)是工作量少，存儲(chǔ)變量較少，初始點(diǎn)要求不高；缺點(diǎn)是收斂慢，效率低。牛頓法的優(yōu)點(diǎn)是收斂速度快；缺點(diǎn)是對(duì)初始點(diǎn)要求嚴(yán)格，方向構(gòu)造困難，計(jì)算復(fù)雜且占用內(nèi)存較大。同時(shí)，這兩種算法的理論和方法滲透到許多方面，特別是在軍事、經(jīng)濟(jì)、管理、生產(chǎn)過(guò)程自動(dòng)化、工程設(shè)計(jì)和產(chǎn)品優(yōu)化設(shè)計(jì)等方面都有著重要的應(yīng)用。因此，研究最速下降法和牛頓法的原理及其算法對(duì)我們有著及其重要的意義。關(guān)鍵字：無(wú)約束優(yōu)化最速下降法 牛頓法Abstract:unconstrainedoptimizationmethodistooptimizethetechnologyisextremelyimportantandbasiccontentof.Itnotonlycanbedirectlyusedtosolveunconstrainedoptimizationproblems,andalotofconstrainedoptimizationproblemsareoftentransformedintounconstrainedoptimizationproblem,andthenusetheunconstrainedoptimizationmethodstosolve.ThesteepestdescentmethodandNewton-Raphsonmethodisrelativelycommonintheunconstrainedproblemoptimizationmethod,thesetwokindsofalgorithmasthebasicalgorithm,theoptimizationmethodplaysanimportantrolein.Oneofthesteepestdescentmethodalsoknownasgradientmethod,itsadvantagesarelessworkload,storagevariableisless,theinitialrequirementsisnothigh;drawbackistheslowconvergence,lowefficiency.Newtonianmethodhastheadvantagesoffastconvergencespeed;drawbackistheinitialpointofstrictconstructiondifficulties,directions,complicatedcalculationandlargermemory.Atthesametime,thesetwokindsofalgorithmtheoryandmethodsintomanyaspects,especiallyinthemilitary,economic,management,productionprocessautomation,engineeringdesignandproductoptimizationdesignhasimportantapplications.Therefore,tostudythesteepestdescentmethodandNewton-Raphsonmethodprincipleandalgorithmforuswithitsimportantsignificance.Keywords:unconstrainedoptimizationsteepestdescentmethod一、算法的基本原理1.1最速下降法的基本原理在基本迭代公式Xk+1=xk+tP^中，每次迭代搜索方向P取為目標(biāo)函數(shù)f(X)的負(fù)梯度方向，即Pk=-Nf(Xk)，而每次迭代的步長(zhǎng)tk取為最優(yōu)步長(zhǎng)，由此確定的算法稱(chēng)為最速下降法。為了求解問(wèn)題minf(X)，假定我們已經(jīng)迭代了k次，獲得了第k個(gè)迭代點(diǎn)X.?，F(xiàn)在從X出發(fā)，可選擇的下降方法很多，一個(gè)非常自然的想法是沿最速下降方向(即負(fù)梯度方k向)進(jìn)行搜索應(yīng)該是有利的，至少在Xk鄰近的范圍內(nèi)是這樣。因此，去搜索方向?yàn)镻k=Kf(XJ.為了使目標(biāo)函數(shù)在搜索方向上獲得最多的下降，沿P進(jìn)行一維搜索，由此得到第k+1k個(gè)跌帶點(diǎn)，即Xk+i=XLkW(Xk)，其中步長(zhǎng)因子t按下式確定kf(X-1Nf(X))=minf(X-1Nf(X))，kk k kk k(1)Xk+1=Is(Xk，-Nf(Xk)).(1)顯然，令k=0,1,2,…就可以得到一個(gè)點(diǎn)列X0,X「X2,...，其中X0是初始點(diǎn)，由計(jì)算者任意選定。當(dāng)f(X)滿(mǎn)足一定的條件時(shí)，由式(1)所產(chǎn)生的點(diǎn)列｛X｝必收斂于f(X)的k極小點(diǎn)。下面為書(shū)寫(xiě)方便，記g(X)=Nf(X)。因此gk=g(X)=Nf(Xk).1.2牛頓法的基本原理設(shè)最優(yōu)化問(wèn)題為minf(X)，其中f:Rn—R1二階可導(dǎo)，Hesse矩陣N2f(X)正定。不妨設(shè)經(jīng)過(guò)k次迭代已獲點(diǎn)Xk，現(xiàn)將f(X)在X=Xk處展成二階泰勒公式，于是有f(X)rQ(X)=f(X)+Nf(X)t(X-X)+；(X-X)tN2f(X)(X-X)k k k2 k k k顯然Q(X)是二次函數(shù)，特別由假設(shè)知Q(X)還是正定二次函數(shù)，所以Q(X)是凸函數(shù)且存在唯一全局極小點(diǎn)。為求此極小點(diǎn)，令Q(X)=Nf(Xk)+V2f(Xk)(X-Xk)=0即可解得X=X廣[V2f(Xk)]-1Vf(XJ,亦即Xk+1=Xk-[V2f(Xk)]-1Vf(XJ。 (2)對(duì)照基本迭代公式Xni=Xk+代易知，式(2)中的搜索方向P=—[V2f(Xk)]-1Vf(Xk)， (3)步長(zhǎng)因子七二1。換句話說(shuō)從點(diǎn)Xk出發(fā)沿搜索方向P=_[V2f(Xk)]-1Vf(Xk)并取步長(zhǎng)七二1即可得Q(X)的極小點(diǎn)Xk+1。因此，P=-[V2f(Xk)]-1Vf(Xk)是直指點(diǎn)X處近似二次函數(shù)Q(X)的極小點(diǎn)的方向。此時(shí)稱(chēng)kP=_[V2f(Xk)]-1Vf(Xk)為從點(diǎn)Xk出發(fā)的Nowton方向。從初始點(diǎn)開(kāi)始，每一輪從當(dāng)前迭代點(diǎn)出發(fā)，沿Nowton方向并取步長(zhǎng)七二1的算法稱(chēng)為牛頓法。二、算法的迭代步驟及流程圖2.1最速下降法迭代步驟已知目標(biāo)函數(shù)f(X)及其梯度g(X)，終止限七,82和￡3.選定初始點(diǎn)X0，計(jì)算f0=f(X0),g0=g(X0)；置k=0.作直線搜索：Xk+1=ls(Xk，—g「；計(jì)算f++1=f(乂小),幺虹廣g(Xk+「.

k+1 k+1用終止準(zhǔn)則檢驗(yàn)是否滿(mǎn)足:若滿(mǎn)足，則打印最優(yōu)解(X,f(X))，結(jié)束；否則，置kk+1 k+1轉(zhuǎn)(2)(3)最速下降法算法流程圖如圖所示.2.2牛頓法迭代步驟已知目標(biāo)函數(shù)f(X)及其梯度g(X),Hesse矩陣G(X)，終止限￡.⑴選定初始點(diǎn)X0；計(jì)算f0=f(X),g(2)計(jì)算G=V2f(X「.

由方程GPk=-gk解出pk.計(jì)算X=X+P,f=f(X),g=g(X).k+1 kkk+1 k+1k+1 k+1判別終止準(zhǔn)則是否滿(mǎn)足：若滿(mǎn)足，則打印最優(yōu)解(Xk"fk+「結(jié)束；否則，置k=k+1，轉(zhuǎn)(2)。牛頓法的流程如圖所示。

三、實(shí)例分析分別用牛頓法和最速下降法求解minf(X)=x2+25x2，選取X=3.1最速下降法求解由題意可知Vf(X)=Vf(X)=2xi50x2」Vf(X0)=4100P0=-Vf(X0)=-4-100X=XX=X+人P=「2「+人「-4-=2-4人0一1 0 0020-1002-100人L 0」f(X1)=f(X0+孔P)=(2-4人)2+25(2-100人)2.人0為最佳步長(zhǎng)，應(yīng)滿(mǎn)足f；*0.則有500032人-500032人-10016=0,或人010016^0.0200307,0=500032故有1.919877-0.003070繼續(xù)迭代，要經(jīng)過(guò)10次迭代才可滿(mǎn)足精度8=10故有1.919877-0.003070繼續(xù)迭代，要經(jīng)過(guò)10次迭代才可滿(mǎn)足精度8=10-6的要求，以下計(jì)算從略。3.2牛頓法求解由題意可知Vf(X)=2x150x2」20050故有是正定矩陣。又由(3)式計(jì)算「4_「20一,V2f(X)=1000050[V2f(X0)]-1=是正定矩陣。又由(3)式計(jì)算「4_「20一,V2f(X)=1000050[V2f(X0)]-1=0150「10一1-. -14221=—1002L050」—1由x.+1=Xk+P計(jì)算2+-2=02-20計(jì)算Vf(X1)為Vf(X1)=故有IlVf(X])||e.「0]停止迭代，并輸出X1=0作為極小點(diǎn)。四、算法的優(yōu)缺點(diǎn)分析4.1最速下降法的優(yōu)缺點(diǎn)分析最速下降法的優(yōu)點(diǎn)是算法簡(jiǎn)單，每次迭代計(jì)算量小，占用內(nèi)存量小，且對(duì)初始點(diǎn)要求不高，即使從一個(gè)不好的初始點(diǎn)出發(fā)，往往也能收斂到局部極小點(diǎn)，但它有一個(gè)嚴(yán)重缺點(diǎn)就是收斂速度慢，特別是當(dāng)橢圓比較扁平時(shí)，最速下降法的收斂速度越慢。4.2牛頓法的優(yōu)缺點(diǎn)分析牛頓法收斂速度非?？?，具有二次收斂的優(yōu)點(diǎn)，但它存在下面四個(gè)嚴(yán)重的缺點(diǎn)：每次迭代不能保證f(X)下降，當(dāng)Hesse矩陣非正定時(shí)，牛頓法的搜索將會(huì)失敗;（2） 對(duì)初始點(diǎn)要求嚴(yán)格，一般要求比較接近或有利于接近極小點(diǎn)，但這在實(shí)際生活中很難辦到；（3） 在進(jìn)行迭代時(shí)可能求不出搜索方向；（4） 構(gòu)造困難，計(jì)算復(fù)雜，占用機(jī)器內(nèi)存較大。五、 設(shè)計(jì)總結(jié)通過(guò)上面的實(shí)例中兩種算法的對(duì)比，可以看出牛頓法對(duì)于二