最速下降法原理及其算法實(shí)現(xiàn)

課程名稱:學(xué)院:專業(yè)班級:學(xué)號:姓名:任課教師:課程名稱:學(xué)院:專業(yè)班級:學(xué)號:姓名:任課教師:課程論文論文題目：最速下降法原理與其算法實(shí)現(xiàn)現(xiàn)代信號處理新方法自動化學(xué)院控制科學(xué)與工程1班2111304092嚴(yán)春景勝利2014年6月20日最速下降法原理與其算法實(shí)現(xiàn)容摘要摘要：基于最速下降法在解決無約束非線性規(guī)劃問題中的重要性，對其原理與算法予以討論。論文主要是參閱大量數(shù)學(xué)分析和運(yùn)籌學(xué)書籍以與一些學(xué)術(shù)資料，結(jié)合自己在平時學(xué)習(xí)中掌握的知識，并在指導(dǎo)老師的建議下，針對最速下降法的基本思路和原理進(jìn)行研究。關(guān)鍵詞：運(yùn)籌學(xué)最速下降法無約束梯度法最優(yōu)解Thesteepestdescentmethod,principleanditsalgorithmAbstractBasedonthesteepestdescentmethodinsolvingunconstrainednonlinearprogrammingproblem,theimportanceoftheprincipleandthealgorithmisdiscussed.Papermainlyrefertoamathematicalanalysisandoperationsresearchbooksandsomeacademicmaterial,usuallyinthestudyofknowledgeandmasteryinteacher'ssuggestion,thesteepestdescentmethodaccordingtothebasicideasandprincipleswerestudied.Keywords：operationalresearchsteepestdescentmethodUnconstrainedgradientmethodoptimalsolution序言最速下降法又稱為梯度法，是1847年由著名數(shù)學(xué)家Cauchy給出的，它是解析法中最古老的一種，其他解析方法或是它的變形，或是受它的啟發(fā)而得到的，因此它是最優(yōu)化方法的基礎(chǔ)。作為一種基本的算法，他在最優(yōu)化方法中占有重要地位。其優(yōu)點(diǎn)是工作量少，存儲變量較少，初始點(diǎn)要求不高；缺點(diǎn)是收斂慢，效率不高，有時達(dá)不到最優(yōu)解。非線性規(guī)劃研究的對象是非線性函數(shù)的數(shù)值最優(yōu)化問題。它的理論和方法滲透到許多方面，特別是在軍事、經(jīng)濟(jì)、管理、生產(chǎn)過程自動化、工程設(shè)計(jì)和產(chǎn)品優(yōu)化設(shè)計(jì)等方面都有著重要的應(yīng)用。而最速下降是n元函數(shù)的無約束非線性規(guī)劃問題minf(x)的一種重要解析法，研究最速下降法原理與其算法實(shí)現(xiàn)對我們有著極其重要的意義。一、最速下降法基本原理無約束問題的最優(yōu)性條件無約束問題的最優(yōu)解所要滿足的必要條件和充分條件是我們設(shè)計(jì)算法的依據(jù)，為此我們有以下幾個定理。定理1設(shè)f:RnTR1在點(diǎn)xgRn處可微。若存在peRn，使Vf(x)tp<0則向量p是f在點(diǎn)x處的下降方向。定理2設(shè)f:RnTR1在點(diǎn)x*eRn處可微。若x*是無約束問題的局部最優(yōu)解，則Vf(x*)二0由數(shù)學(xué)分析中我們已經(jīng)知道，使Vf(x)二0的點(diǎn)x為函數(shù)f的駐點(diǎn)或平穩(wěn)點(diǎn)。函數(shù)f的一個駐點(diǎn)可以是極小點(diǎn)；也可以是極大點(diǎn)；甚至也可能既不是極小點(diǎn)也不是極大點(diǎn)，此時稱它為函數(shù)f的鞍點(diǎn)。以上定理告訴我們，x*是無約束問題的的局部最優(yōu)解的必要條件是：x*是其目標(biāo)函數(shù)f的駐點(diǎn)?，F(xiàn)給出無約束問題局部最優(yōu)解的充分條件。定理3設(shè)f:RnTR1在點(diǎn)x*eRn處的Hesse矩陣V2f(x*)存在。若Vf(x*)二0，并且V2f(x*)正定則x*是無約束問題的嚴(yán)格局部最優(yōu)解。一般而言，無約束問題的目標(biāo)函數(shù)的駐點(diǎn)不一定是無約束問題的最優(yōu)解。但對于其目標(biāo)函數(shù)是凸函數(shù)的無約束凸規(guī)劃，下面定理證明了，它的目標(biāo)函數(shù)的駐點(diǎn)就是它的整體最優(yōu)解。定理4設(shè)f:RnTR1,x*GRn,f是Rn上的可微凸函數(shù)。若有Vf(x*)二0則x*是無約束問題的整體最優(yōu)解。最速下降法的基本思想和迭代步驟最速下降法又稱為梯度法，是1847年由著名數(shù)學(xué)家Cauchy給出的。他是解析法中最古老的一種，其他解析方法或是它的變形，或是受它的啟發(fā)而得到的，因此它是最優(yōu)化方法的基礎(chǔ)。設(shè)無約束問題中的目標(biāo)函數(shù)f:RnTRi一階連續(xù)可微。最速下降法的基本思想是：從當(dāng)前點(diǎn)xk出發(fā)，取函數(shù)f(x)在點(diǎn)xk處下降最快的方向作為我們的搜索方向Pk.由f(x)的Taylor展式知f(xk)—f(xk+tpk)=-tVf(xk)Tpk+o(||tpk||)略去t的高階無窮小項(xiàng)不計(jì)，可見取pk=—Vf(xk)時，函數(shù)值下降得最多。于是，我們可以構(gòu)造出最速下降法的迭代步驟。解無約束問題的的最速下降法計(jì)算步驟第1步選取初始點(diǎn)xo，給定終止誤差￡>0，令k:=0；第2步計(jì)算Vf(xk)，若IVf(xk)h<￡，停止迭代?輸出xk.否則進(jìn)行第三步；第3步取pk=—Vf(xk)；第4步進(jìn)行一維搜索，求t，使得kf(xk+1pk)=minf(xk+tpk)k t>0令xk+1=xk+1pk，k:=k+1，轉(zhuǎn)第2步。k由以上計(jì)算步驟可知，最速下降法迭代終止時，求得的是目標(biāo)函數(shù)駐點(diǎn)的一個近似點(diǎn)。確定最優(yōu)步長t的方法如下：k方法一：采用任一種一維尋優(yōu)法此時的f(xk—tVf(xk))已成為步長t的一元函數(shù)，故可用任何一種一維尋優(yōu)法求出t，即kf(xk+1)=f(xk—tVf(xk))=minf(xk—tVf(xk))

kt方法二：微分法因?yàn)?/p>

f(f(Xk—tPf(Xk))二申(t)所以，一些簡單情況下，可令申(t)二0以解出近似最優(yōu)步長t7的值。k最速下降法應(yīng)用舉例例1minf(x)二x—x+2x2+2xx+x2給定初始點(diǎn)X(i)=(0,0)t121122解：目標(biāo)函數(shù)f(x)的梯度Vf(解：目標(biāo)函數(shù)f(x)的梯度Vf(x)=Vf(X(1))二f(x)

Q(x)1Qf(x)Q(x)2令搜索方向d(1)=—Vf(X(1))=步長變量為九，最優(yōu)步長為九，則有X⑴+九〃(1)=11+4x+2x1 2—1+2x+2x12—1100再從X⑴出發(fā)，沿d(1方向作一維尋優(yōu)，令—11-九九0—1—1+=0110—1—1+=011求出X(2)點(diǎn)之后，與上11類似地，進(jìn)行第二次迭代：Vf(X(2))=令d(2)=—Vf(X⑵)=1丁+一151—0.81.2Vf(X⑶)二0.2—0.2此時所達(dá)到的精度||Vf(X⑶)卜0.2828故f(x)二f(X(1)+九d(1))二(一九)一九+2(—九)2+2(—九)九+九2二九2—2九=9(九)1令p'(九)二2九一2二0可得九=1X(2)二X(1)+入d⑴=11令步長變量為入，最優(yōu)步長為為2,則有「-1「+X丁祝一「=11X+1X⑵+九d⑵二f(x)二f(X(2)+九d(2))二(九—1)—(X+1)+2(九—1)2+2(九—1)(九+1)+(九+1)2二5九2—2九—1=p(九)21令p'(九)二10九一2二0可得九=X⑶二X⑵+Xd⑵二2252本題最優(yōu)解X*=二，f(X*)=—1,25例2用最速下降法求解無約束非線性規(guī)劃問題：minf(X)=(x—2)4+(x—2x)2112其中X=(x,x)T，要求選取初始點(diǎn)X0=(0,3)T，終止誤差￡=0.1.12解：因 Vf(X)=[4(x—2)3+2(x—2x),—4(x—2x)]T11212則 Vf(X0)=(—44,24)T

||Vf(Xo)||二50.12>e

po=-Vf(Xo)二(44,—24)t求單變量極小化問題：minf(xo+tpo)=minf(441,3一24t)t>o t>o=min(441-2)4+(92t-6)2t>o的最優(yōu)解10,由o.618法可得tO=o.o6，于是Xi二xo+1opo二(2.7o,1.51)t

Vf(X1)二(o.73,1.28)t

||Vf(X1)|二1.47>￡令 p1=-Vf(X1)再求單變量極小化問題minf(X1+tp1)t>o的最優(yōu)解?略去計(jì)算步驟，由表1-1給出計(jì)算結(jié)果?由表1-1可以知道，||Vf(X7)|=o.o9<8，所以X7=(2.2&1.15)T為近似最優(yōu)解，原問題的近似最優(yōu)值為o.oo7.表1-1迭代次數(shù)kXkf(Xk)Vf(Xk)||Vf(Xk)||tkXk+1o(o.oo,3.oo)t52.00(-44,24)t50.120.06(2.70,1.51)t1(2.7o,1.51)t0.34(0.73,1.28)t1.470.24(2.52,1.20)t2(2.52,1.2o)t0.09(0.80,-0.48)t0.930.11(2.43,1.25)t3(2.43,1.25)t0.04(0.18,0.28)t0.330.31(2.37,1.16)t4(2.37,1.16)t0.02(0.30,-0.20”0.360.12(2.33,1.18)t5(2.33,1.18)t0.01(0.08,0.12)t0.140.36(2.30,1.14)t6(2.3o,1.14)t0.009(0.15,-0.08)t0.170.13(2.28,1.15)t7(2.28,1.15)t0.007(0.05,0.08)t0.09例3用最速下降法求解無約束問題31minf(x)二x2minf(x)二212212取X（1）=（o,o）T,8二io-2。g1，V2f(X)=g23-1卜得到精確一維搜索步長-13-1卜得到精確一維搜索步長-13x—x—2Vf(X)= 1 2x—x21設(shè)d(k)=[d,d卜，Vf(X(k))=[g,g1212gd+gda= -^-1 22k 3d2+d2—2dd1212

取X(1)=(0,0)T，則Vf(X(1))-[-2,0卜，所以d(I)=-Vf(X(1))=【2,0JT,22TOC\o"1-5"\h\za= =—i3x22 3因此2 H2 Ht||Vf(X(9))1=0.025X⑵二X(1)+ad(i)=[0,0]r+【2,0]||Vf(X(9))1=0.025再計(jì)算第二輪循環(huán)，表1-2列出了各次迭代的計(jì)算結(jié)果。共計(jì)算了9個點(diǎn)，10-2,停止計(jì)算，所以X（9）=【0.988,0.988!q乍為問題的最優(yōu)解。表1-2kX(k)f(X(k))Vf(X(k))d(k)ak1(0.000,0.000)0.000(-2.000,0.000)(2.000,0.000)0.3332(0.667,0.000)-0.667(0.000,-0.667)(0.000,0.667)1.0003(0.667,0.667)-0.889(-0.667,0.000)(0.667,0.000)0.3334(0.889,0.667)-0.963(0.000,-0.222)(0.000,0.222)1.0005(0.889,0.889)-0.988(-0.222,0.000)(0.222,0.000)0.3336(0.963,0.889)-0.996(0.000,-0.074)(0.000,0.074)1.0007(0.963,0.963)-0.999(-0.074,0.000)(0.074,0.000)0.3338(0.988,0.963)-1.000(0.000,-0.025)(0.000,0.025)1.0009(0.988,0.988)-1.000(-0.025,0.000)（四）最速下降法的缺點(diǎn)由于沿負(fù)梯度方向目標(biāo)函數(shù)的最速下降性，很容易使人們誤認(rèn)為負(fù)梯度方向是最理想的搜索方向，最速下降法是一種理想的極小化方法。必須指出的是，某點(diǎn)的負(fù)梯度方向，通常只是在該店附近才具有這種最速下降的性質(zhì)。在一般情況下，當(dāng)用最速下降法尋找極小點(diǎn)時，其搜索路徑呈直角鋸齒狀（圖1-3），在開頭幾步，目標(biāo)函數(shù)下降較快；但在接近極小點(diǎn)時，收斂速度長久不理想了。特別適當(dāng)目標(biāo)函數(shù)的等值

圖1-3因此，在實(shí)用中常將最速下降法和其他方法聯(lián)合應(yīng)用，在前期使用最速下降法，而在接近極小點(diǎn)時，可改用收斂較快的其他方法。二、最速下降法算法實(shí)現(xiàn)（一）最速下降法程序流程圖最速下降法的程序流程圖，如圖1-4所示圖1-4(二)最速下降法程序清單用C語言編寫的最速下降法的程序清單如下。其中R是梯度模，P是梯度方向的的單位向量，h是步長，f是目標(biāo)函數(shù)。#include“math.h”#include“stdio.h”floatx[10],y[10],p[10],f,h;intn;vodfun(){inti;for(i=1,i<n;i++)x[i]=y[i]-h*p[i];f=x[1]*x[1]+x[2]*x[2]-x[1]*x[2]-10*x[1]-4*x[2];f=f+60;return;}main(){floatg[10],d[10],q,r,e,h1,h2,h3,h4,t,t0,c1,c2,f1,f2,f3,f4,f5,v;inti,k,u;printf(“inputn,e\n”)；scanf(“%d,%f”,&n,&e);x[1]=0;x[2]=0;p4:g[1]=2*x[1]-x[2]-10;g[2]=2*x[2]-x[1]-4;q=0;for(i=1;i<n;i++)q=g[i]*g[i]+q;r=sqrt(q);for(i=1;i<n;i++){y[i]=x[i];p[i]=g[i]/r;}if(r<e)gotop3;else{t0=1;v=0.1;h1=0;h=h1fun();f1=f;p2:u=0;t=t0;h2=h1+t;h=h2;fun();f2=f;if(f1>f2){t=t+t;u=u+1;else{t=-t;h3=h1;f3=f1;h1=h2;f1=f2;h2=h3;f2=f3;p1:h3=h2+t;h=h3;fun()f3=f;if(f2>f3){t=t+t;u=u+1;h1=h2;f1=f2;h2=h3;f2=f3;gotopl;}else{if(u>0){h4=0.5*(h2+h3);h=h4;fun();f4=f;if(f4>f2){h3=h4;f3=f4;}else{h1=h2;f1=f2;h2=h4;f2=f4;}}c1=(f3-f1)/(h3-h1);c2=((f2-f1)/(h2-h1)-c1)/(h2-h3);if(fabs(c2)<e){h1=h2;f1=f2;t0=v*t0;gotop2;}else{h4=0.5*(h1+h3-(c1/c2));h=h4;fun();f4=f;if(f2<1)f5=1;elsef5=f2;if((fabs(f4-f2)/f5)<e){for(i=1;i<n;i++)x[i]=y[i]-h4*p[i];gotop4;}else{if(f4>f2){h1=h2