數(shù)學(xué)規(guī)劃-(最速下降法-c語(yǔ)言編程)

1、PAGE PAGE 8數(shù) 學(xué) 規(guī) 劃 課 程 設(shè) 計(jì)題目：用最速下降法求解無(wú)約束非線性規(guī)劃問(wèn)題姓名： 學(xué)號(hào)： 成績(jī)： 2011年6月用最速下降法求解無(wú)約束非線性規(guī)劃問(wèn)題摘要：無(wú)約束非線性規(guī)劃問(wèn)題是一類(lèi)重要的數(shù)學(xué)規(guī)劃問(wèn)題。文主要研究了用最速下降法也就是梯度法對(duì)無(wú)約束非線性規(guī)劃問(wèn)題進(jìn)行求解。對(duì)于一個(gè)無(wú)約束非線性規(guī)劃利用最速下降法求解，首先需要確定其優(yōu)化方向，此優(yōu)化方向應(yīng)該選擇為f在當(dāng)前點(diǎn)處的負(fù)梯度方向，利用一維搜索法找出沿此方向上的最小值及其對(duì)應(yīng)點(diǎn)，此后將該點(diǎn)作為新的出發(fā)點(diǎn)重復(fù)上述過(guò)程，直到達(dá)到允許的誤差為止。本文最后利用c+語(yǔ)言編程得到滿足允許誤差內(nèi)的最優(yōu)解。本文主要對(duì)一個(gè)無(wú)約束非線性規(guī)劃問(wèn)題的

2、實(shí)例，首先利用上述迭代的方法，計(jì)算出各迭代點(diǎn)的函數(shù)值，梯度及其模。然后應(yīng)用c+語(yǔ)言編程，得到精確地最優(yōu)解，需迭代六次才使得，得到的最優(yōu)解為，。關(guān)鍵詞：最速下降法 無(wú)約束非線性規(guī)劃 最優(yōu)解一、問(wèn)題重述用最速下降法求解無(wú)約束非線性規(guī)劃問(wèn)題：，設(shè)初始點(diǎn)取為,迭代到滿足允許誤差=0.01為止的精確解。二、問(wèn)題分析2.1 無(wú)約束非線性問(wèn)題的最優(yōu)條件該問(wèn)題是一個(gè)無(wú)約束非線性規(guī)劃問(wèn)題，利用最少下降法求解該問(wèn)題，無(wú)約束非線性規(guī)劃問(wèn)題的最優(yōu)解所要滿足的必要條件和充分條件是我們?cè)O(shè)計(jì)算法的依據(jù)，為此有以下幾個(gè)定理。定理1 設(shè)f：在點(diǎn)處可微，若存在，使，則向量p是f在點(diǎn)處的下降方向。定理2設(shè)f：在點(diǎn)處可微，若是無(wú)約束

3、問(wèn)題的局部最優(yōu)解，則有數(shù)學(xué)分析中我們已經(jīng)知道，使的點(diǎn)x為函數(shù)f的駐點(diǎn)或平穩(wěn)點(diǎn)。函數(shù)f的一個(gè)駐點(diǎn)可以是極小值點(diǎn)；也可以是極大值點(diǎn)；甚至也可能既不是極小值點(diǎn)也不是極大值點(diǎn)，因此稱(chēng)它為函數(shù)f的鞍點(diǎn)，以上定理告訴我們，是無(wú)約束問(wèn)題的局部最優(yōu)解的必要條件是：是其目標(biāo)函數(shù)f的駐點(diǎn)。定理3 設(shè)f：在點(diǎn)處的Hesse矩陣存在，若，并且正定，則是無(wú)約束非線性問(wèn)題的嚴(yán)格局部最優(yōu)解。一般而言，無(wú)約束非線性問(wèn)題的目標(biāo)函數(shù)的駐點(diǎn)不一定是無(wú)約束非線性問(wèn)題的最優(yōu)解，但對(duì)于其目標(biāo)函數(shù)是凸函數(shù)的無(wú)約束凸規(guī)劃，下面定理證明了它的目標(biāo)函數(shù)的駐點(diǎn)就是它的整體最優(yōu)解。定理4設(shè)f：，f是上的可微凸函數(shù)。若有，則是無(wú)約束問(wèn)題的整體最優(yōu)解。

4、2.2最速下降法的基本思想最速下降法又稱(chēng)為梯度法，是1847年由著名數(shù)學(xué)家Cauchy給出的，他是解析法中最古老的一種，其他解析方法或是他的變形，或是他的啟發(fā)得到的，因此它是最優(yōu)化方法的基礎(chǔ)。設(shè)無(wú)約束非線性規(guī)劃問(wèn)題中的目標(biāo)函數(shù)f：在點(diǎn)處可微。最速下降法的基本思想是：從當(dāng)前點(diǎn)出發(fā)，取函數(shù)在點(diǎn)處下降最快的方向作為我們收索方向，由的Taylor展示知 ，略去的高階無(wú)窮小項(xiàng)不計(jì)，可見(jiàn)取時(shí)，函數(shù)值下降的最多 ，于是，我們可以夠造出最速下降法的迭代步驟。2.3無(wú)約束非線性規(guī)劃問(wèn)題的迭代步驟解無(wú)約束非線性規(guī)劃問(wèn)題的最速下降法計(jì)算步驟第1步 選取初始點(diǎn)，給定終止誤差 0，令k=0；第2步 計(jì)算，若，停止迭代，

5、輸出，否則進(jìn)行第3步；第3步 ??；第4步 進(jìn)行一維搜索，求，使得，令，k=k+1。轉(zhuǎn)第2步。由以上計(jì)算步驟可知，最速下降法迭代終止時(shí)，求得的是目標(biāo)函數(shù)駐點(diǎn)的一個(gè)近似點(diǎn)。 三、問(wèn)題求解3.1對(duì)原無(wú)約束非線性規(guī)劃迭代首先進(jìn)行第一次迭代 則 令，即=0，解得：所以，此時(shí)，又因?yàn)?則進(jìn)行第二次迭代則 令，代入即可解得：所以此時(shí)，又因?yàn)?則進(jìn)行第三次迭代則 令，代入即可解得：所以此時(shí)，又因?yàn)?則進(jìn)行第四次迭代則 令，代入即可解得：所以此時(shí)，又因?yàn)?以上仍然沒(méi)有達(dá)到要求，即還需繼續(xù)迭代，直到滿足為止。3.2對(duì)原無(wú)約束非線性規(guī)劃進(jìn)行c+語(yǔ)言編程求解就這樣無(wú)限的迭代下去，直到為止，為此，我們可以用c+語(yǔ)言編程

6、得到，其算法設(shè)計(jì)如下圖（圖3-1）停停取，k:=0計(jì)算是否求令k:=k+1圖（3-1）利用c+語(yǔ)言編程（源代碼如下）：#include#includedouble lambda(double x2,double p2,double a2)double lam1,lam2;lam1=4*(pow(a0,3)*x0*x0+pow(a1,3)*x1*x1);lam2=-4*(pow(a0*x0,2)+pow(a1*x1,2);double s;s=-lam2/(2*lam1);return s;void main()double lamb,x2,a2,p2,g2,e=0.01,y; int i=0;

7、 x0=4.0; x1=4.0;cout輸入函數(shù)的系數(shù)：a0,a1:endl;for(i=0;iai; p0=2*a0*x0; p1=2*a1*x1; g0=-p0; g1=-p1;i=0; /開(kāi)始迭代將次數(shù)賦值為0coute&i=200) lamb=lambda(x,g,a); x0=x0+lamb*g0; x1=x1+lamb*g1; p0=2*a0*x0; p1=2*a1*x1; g0=-p0; g1=-p1; i+; /cout(di %d ci mo=%f x1=%ftx2=%ftbuchang a=%fn,+i,sqrt(g0*g0+g1*g1),x0,x1,a); cout迭代次數(shù)為i p的模sqrt(g0*g0+g1*g1)endlx的值x0 x1endlendl;y=a0*x0*x0+a1*x1*x1; coutendl分別輸出x1,x2：x0 x1endl及極小值y： yendl;3.3結(jié)果分析運(yùn)行即可得到如下結(jié)果：由以上結(jié)果可以得出：要想使得，則需要迭代6次，此時(shí)，。參考文獻(xiàn)1范玉妹，徐爾.數(shù)學(xué)規(guī)劃及其應(yīng)用 M.北京：冶金工業(yè)出版社，2009.9.2倪勤. 最優(yōu)化方法與程序設(shè)計(jì) M.北京：科學(xué)出版社，2009.6.3孫文瑜，徐成賢，朱德通. 最優(yōu)化方法 M.北京：高等教育出版社