用最速下降法求解無約束非線性規(guī)劃問題

1、運籌學實習報告姓 名： xxxxxxxxxx 學 號： xxxxxxxxxxx 專業(yè)班級： xxxxxxxxxxxx 2 0 1 3年 7 月 0 4 日題目：用最速下降法求解無約束非線性規(guī)劃問題摘要：無約束最優(yōu)化問題的求解方法分為解析法和直接法兩大類。解析法需要計算函數(shù)的梯度，其中最速下降法就屬于解析法中的一種。對于一個無約束非線性規(guī)劃利用最速下降法求解，首先需要確定其優(yōu)化方向，此優(yōu)化方向應(yīng)該選擇為f在當前點處的負梯度方向，利用一維搜索法找出沿此方向上的最小值及其對應(yīng)點，此后將該點作為新的出發(fā)點重復(fù)上述過程，直到達到允許的誤差為止。本文通過理論的計算方法，進一步分析，最后用c+編程實現(xiàn)求出允

2、許誤差內(nèi)的最優(yōu)解。此編程可用于計算符合下列形式的函數(shù)求最優(yōu)解過程：f(x)=a0x1*x1+a1x2*x2+a2x1*x2+a3x1+a4x2+a5其中：ai (i=0,1,2,3,4,5) 為函數(shù)的系數(shù)。本文以“ 李占利 主編，中國礦業(yè)大學出版社出版”的最優(yōu)化理論與方法 第五章 “無約束最優(yōu)化方法，5.1 最速下降法 ”例51為實例，首先利用上述迭代的方法，計算出各迭代點的函數(shù)值，梯度及其模。然后應(yīng)用c+語言編程，得到在精度范圍內(nèi)的精確最優(yōu)解。*(3)Tx=x=-0.00823045,0.0329218 C+編程計算的最優(yōu)解為 : 。即轉(zhuǎn)化為分數(shù)結(jié)果為：x=x*(3)2-1= 。 2434滿

3、足精度要求的模為：|p(3)|=0.0736154<=110。關(guān)鍵詞：無約束非線性規(guī)劃 解析法 最速下降法 梯度 模 最優(yōu)解1一、算法思想無約束最優(yōu)化方法中的最速下降法首先需要確定其優(yōu)化方向，此優(yōu)化方向應(yīng)該選擇為f在當前點處的負梯度方向，利用一維搜索法找出沿此方向上的最小值及其對應(yīng)點，此后將該點作為新的出發(fā)點重復(fù)上述過程，直到達到允許的誤差為止。主要依據(jù)解無約束非線性規(guī)劃問題的最速下降法計算步驟進行設(shè)計算法。 具體步驟如下：第1步 選取初始點x，給定終止誤差 >0，令k=0；kkf(xk)f(x) 第2步 計算，若，停止迭代，輸出x，否則進行第30步；kkp=-f(x)； 第3步

4、取f(xk+kpk)=minf(xk+pk)k0 第4步 進行一維搜索，求k，使得，令xk+1=xk+kpk，k=k+1。轉(zhuǎn)第2步。由以上計算步驟可知，最速下降法迭代終止時，求得的是目標函數(shù)駐點的一個近似點。 依據(jù)以上步驟就可以用C+編程實現(xiàn)最速下降法求解最優(yōu)解的算法。二、算法流程圖2三、程序代碼#include<iostream.h>#include<math.h>double lamda(double x2,double p2,double a2)double lam1,lam2;lam1=(pow(a0,3)*x0*x0+pow(a1,3)*x1*x1); lam

5、2=-(pow(a0*x0,2)+pow(a1*x1,2); double s;3s=-lam2/(2*lam1);return s;void main()cout<<""<<endl; cout<<" 最速下降法求解最優(yōu)解程序運行結(jié)果 "<<endl; cout<<""<<endl;cout<<endl;double lamd,x3,a6;double p2,g2,e,y,m,n;int i=0;cout<<"請輸入精度e&qu

6、ot;<<endl;cin>>e;cout<<"請輸入初始點x0,x1的值：n"<<endl;cin>>m;cin>>n;x0=m;x1=n;cout<<"函數(shù)通式為f(x)=a0x1*x1+a1x2*x2+a2x1*x2+a3x1+a4x2+a5"<<endl; cout<<"請依次輸入函數(shù)的系數(shù)：a0、a1、a2、a3、a4、a5:"<<endl;for(i=0;i<6;i+)cin>>ai;p

7、0=(2*a0*x0+a2*x1+a3);p1=(2*a1*x1+a2*x0+a4);g0=-p0;g1=-p1;i=0;cout<<endl;while(sqrt(g0*g0+g1*g1)>e&&i<=200)lamd=lamda(x,g,a);x0=x0+lamd*g0;x1=x1+lamd*g1;4p0=2*a0*x0;p1=2*a1*x1;g0=-p0;g1=-p1;i+;cout<<"*"<<endl;cout<<"第"<<i<<"次迭

8、代結(jié)果："<<endl;cout<<"p的模為："<<sqrt(g0*g0+g1*g1)<<endl;cout<<"x的值"<<x0<<" "<<x1<<endl;cout<<"*"<<endl;cout<<endl;y=(a0*x0*x0+a1*x0*x1+a2*x0*x1+a3*x0+a4*x1+a5);cout<<"此時滿足精度要求的p

9、的模為:"<<sqrt(g0*g0+g1*g1)<<endl;cout<<endl;cout<<"滿足精度的最優(yōu)近似結(jié)果x1,x2分別為："<<endl;cout<<"x1="<<x0<<endl;cout<<"x2="<<x1<<endl;cout<<endl;cout<<"滿足進度要求所得的最優(yōu)值為："<<endl;cout<&l

10、t;"minf(x)="<<y<<endl;四、例子與結(jié)果例子為“ 李占利 主編，中國礦業(yè)大學出版社出版”的最優(yōu)化理論與方法第五章 “無約束最優(yōu)化方法，5.1 最速下降法 ”例51。用最速下降法求解中很明顯有：a0=2,a1=1,a2=a3=a4=a5=0;e=0.1；x0=x1=1; 12=0.1。則體現(xiàn)在程序minf(x)=2x12+x2，初始迭代點x(0)=1，精度為則程序運行結(jié)果為：512即在允許的精度范圍內(nèi)minf(x)=2x12+x2，初始迭代點x(0)=1，精度為=0.1。得到在精度范圍內(nèi)的精確最優(yōu)解為：*(3)T2-1*(3)x=x=

11、-0.008230,40.50329218 ，即x=x= 。 2434滿足精度要求的模為：|p(3)|=0.0736154<=110。6五、結(jié)論與總結(jié)最速下降法為最優(yōu)化萬千方法中的一種，要想更好地利用最優(yōu)化方法解決我們身邊的問題，光靠這一種方法遠遠不夠。因此我必須要好好掌握其他的各種方法。還有通過這次實習讓我深深認識到，并不是所有的問題都能夠手工完成的，我們平常接觸的例題，都非?；A(chǔ)，那完全可以手工計算得到答案，但如果問題比較復(fù)雜時，我們是沒有辦法用手工完成的。所以我們必須借助計算機來解決那些復(fù)雜的問題。因此這就要求我們必須要熟練掌握編程技巧，要能夠把實際的復(fù)雜問題通過編寫程序來解決它。還有此次用最速下降法求解最優(yōu)解的程序，我編的還不夠完美，還有很多不足之處，只能用于研究二元函數(shù)的最優(yōu)解問題，不能進行其他的更深入的研究，所以還有很多改進的地方，以后我還要繼續(xù)努力。 對于編程一定要多練、多動手操作，通過這次實習讓我深深地認識到，光靠理論知識是不行的，理論知道再多，如果不動手實踐的話照樣編不出程序，只有在實踐中，在編寫程序的過程中我們才能發(fā)現(xiàn)自己的不足，才能知道問題出在哪兒。所以無論學習什么編程語言，我今后一定要多動手，今后無論學習什么我都