最優(yōu)化課程設(shè)計(jì)

最優(yōu)化方法課程設(shè)計(jì)最優(yōu)化理論和方法日益受到重視，已經(jīng)滲透到生產(chǎn)、管理、商業(yè)、軍事、決最優(yōu)化理論和方法日益受到重視，已經(jīng)滲透到生產(chǎn)、管理、商業(yè)、軍事、決題目：黃金分割法及其算法實(shí)現(xiàn)院（系）：數(shù)學(xué)與計(jì)算科學(xué)專業(yè)：信息與計(jì)算科學(xué)課題類型：■驗(yàn)證性口設(shè)計(jì)性 工綜合性 □軟件開發(fā)2011年12月25日策等各個(gè)領(lǐng)域，而最優(yōu)化模型與方法廣泛應(yīng)用于工業(yè)、農(nóng)業(yè)、交通運(yùn)輸、商業(yè)、國防、建筑、同學(xué)、政府機(jī)關(guān)等各個(gè)部門及各個(gè)領(lǐng)域。伴隨著計(jì)算機(jī)技術(shù)的高速發(fā)展，最優(yōu)化理論與方法的迅速進(jìn)步為解決實(shí)際最優(yōu)化問題的軟件也在飛速發(fā)展。其中，MATLAB軟件已經(jīng)成為最優(yōu)化領(lǐng)域應(yīng)用最廣的軟件之一。有了MATLAB這個(gè)強(qiáng)大的計(jì)算平臺(tái)，既可以利用MATLAB優(yōu)化工具箱(OptimizationToolbox)中的函數(shù)，又可以通過算法變成實(shí)現(xiàn)相應(yīng)的最優(yōu)化計(jì)算。在最優(yōu)化計(jì)算中一維最優(yōu)化方法是優(yōu)化設(shè)計(jì)中最簡單、最基本的方法。一維搜索，又稱為線性搜索，一維問題是多維問題的基礎(chǔ)，在數(shù)值方法迭代計(jì)算過程中，都要進(jìn)行一維搜索，也可以把多維問題化為一些一維問題來處理。一維問題的算法好壞，直接影響到最優(yōu)化問題的求解速度。而黃金分割法是一維搜索方法中重要的方法之一，它適用于任何單峰函數(shù)求最小值的問題，甚至于對(duì)函數(shù)可以不要求連續(xù)，是一種基于區(qū)間收縮的極小點(diǎn)搜索算法。關(guān)鍵詞：最優(yōu)化、黃金分割法、MATLAB、算法、一維搜索AbstractOptimizationtheoryandmethodsandmoreattention,havepenetratedintotheproduction,management,business,military,decision-makingandotherfields,andoptimizationmodelsandmethodswidelyusedinindustry,agriculture,transportation,commerce,defense,construction,students,governmentvariousdepartmentsandagenciesandotherfields.Withtherapiddevelopmentofcomputertechnology,optimizationtheoryandmethodsfortherapidprogressoftheoptimizationproblemtosolvepracticalsoftwareisalsodevelopingrapidly.Which,MATLABsoftwarehasbecomethemostoptimizationsoftwareisoneofthemostwidelyused.WiththispowerfulcomputingplatformMATLAB,eitherusingMATLABoptimizationtoolbox(OptimizationToolbox)inthefunction,butalsocanachievetheappropriatealgorithmtooptimizeintothecalculation.Inthecalculationofone-dimensionaloptimizationoptimizationmethodistooptimizethedesignofthesimplest,mostbasicmethod.One-dimensionalsearch,alsoknownaslinearsearch,one-dimensionalproblemismulti-dimensionalproblembasedoniterativemethodsinnumericalcalculation,shouldbeone-dimensionalsearch,canalsomulti-dimensionalproblemintoanumberofone-dimensionalproblemtodealwith.One-dimensionalalgorithmsaredirectlyaffectedbythespeedofsolvingoptimizationproblems.Thegoldensectionmethodisaone-dimensionalsearchmethodisoneimportantmethod,whichappliestoanysinglepeakfunctionfortheminimumoftheproblem,evenonthefunctiondoesnotrequireacontinuous,interval-basedcontractionisaverysmallpointsearchalgorithm.Keywords:Optimization、Goldensectionmethod、MATLAB>Algorithm、One-dimensionalsearch目錄摘要 2TOC\o"1-5"\h\z第一章引言 5\o"CurrentDocument"第二章最優(yōu)化方法原理 62.1無約束問題的最優(yōu)性條件 6\o"CurrentDocument"第三章黃金分割法的基本思想與原理 7\o"CurrentDocument"3.1黃金分割法基本思路： 7\o"CurrentDocument"3.2黃金分割法的基本原理與步驟 73.30.618法算法 83.4算法流程圖 83.5用matlab編寫源程序 9\o"CurrentDocument"第四章黃金分割法應(yīng)用舉例 10\o"CurrentDocument"例1 10\o"CurrentDocument"例2 11\o"CurrentDocument"第五章總結(jié) 12\o"CurrentDocument"5.1概括總結(jié) 12\o"CurrentDocument"5.2具體分工 12\o"CurrentDocument"5.3個(gè)人感言 12\o"CurrentDocument"參考文獻(xiàn) 15第一章引言數(shù)學(xué)科學(xué)不僅是自然科學(xué)的基礎(chǔ)，也是一切重要技術(shù)發(fā)展的基礎(chǔ)。最優(yōu)化方法更是數(shù)學(xué)科學(xué)里面的一個(gè)巨大的篇幅，在這個(gè)信息化的時(shí)代，最優(yōu)化方法廣泛應(yīng)用于工業(yè)、農(nóng)業(yè)、國防、建筑、通信與政府機(jī)關(guān)、管理等各個(gè)部門、各個(gè)領(lǐng)域;它主要解決最優(yōu)計(jì)劃、最優(yōu)分配、最優(yōu)決策、最佳設(shè)計(jì)、最佳管理等最優(yōu)化問題。而最優(yōu)解問題是這些所有問題的中心，是最優(yōu)化方法的重中之重，在求最優(yōu)解問題中，有多種方法解決，我們?cè)谶@里著重討論無約束一維極值問題，即非線性規(guī)劃的一維搜索方法之黃金分割法。黃金分割法也叫0.618法，屬于區(qū)間收縮法，首先找出包含極小點(diǎn)的初始搜索區(qū)間，然后按黃金分割點(diǎn)通過對(duì)函數(shù)值的比較不斷縮小搜索區(qū)間。當(dāng)然要保證極小點(diǎn)始終在搜索區(qū)間內(nèi)，當(dāng)區(qū)間長度小到精度范圍之內(nèi)時(shí)，可以粗略地認(rèn)為區(qū)間端點(diǎn)的平均值即為極小值的近似值。所以用0.618法得出的是比較精確的最優(yōu)解了。本實(shí)驗(yàn)的運(yùn)行環(huán)境是matlabR2009a版本的運(yùn)行環(huán)境。第二章最優(yōu)化方法原理2.1無約束問題的最優(yōu)性條件無約束問題的最優(yōu)解所要滿足的必要條件和充分條件是我們?cè)O(shè)計(jì)算法的依據(jù)，為此我們有以下幾個(gè)定理。定理1設(shè)f：RnTR1在點(diǎn)X處可微。若存在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的一個(gè)駐點(diǎn)可以是極小點(diǎn)；也可以是極大點(diǎn)；甚至也可能既不是極小點(diǎn)也不是極大點(diǎn)，此時(shí)稱它為函數(shù)f的鞍點(diǎn)。以上定理告訴我們，x*是無約束問題的的局部最優(yōu)解的必要條件是：x*是其目標(biāo)函數(shù)f的駐點(diǎn)。現(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)解。但對(duì)于其目標(biāo)函數(shù)是凸函數(shù)的無約束凸規(guī)劃，下面定理證明了，它的目標(biāo)函數(shù)的駐點(diǎn)就是它的整體最優(yōu)解。定理4設(shè)f：RnTR1，X*eRn，f是Rn上的可微凸函數(shù)。若有Vf(X*)=0則x*是無約束問題的整體最優(yōu)解。第三章黃金分割法的基本思想與原理3.1黃金分割法基本思路：黃金分割法適用于［a,b］區(qū)間上的任何單股函數(shù)求極小值問題，對(duì)函數(shù)除要求“單峰”外不做其他要求，甚至可以不連續(xù)。因此，這種方法的適應(yīng)面非常廣。

黃金分割法也是建立在區(qū)間消去法原理基礎(chǔ)上的試探方法，即在搜索區(qū)間［Q,b］內(nèi)適當(dāng)插入兩點(diǎn)al，a2，并計(jì)算其函數(shù)值。al，a2將區(qū)間分成三段，應(yīng)用函數(shù)的單峰性質(zhì)，通過函數(shù)值大小的比較，刪去其中一段，是搜索區(qū)間得以縮小。然后再在保留下來的區(qū)間上作同樣的處理，如此迭代下去，是搜索區(qū)間無限縮小，從而得到極小點(diǎn)的數(shù)值近似解。3.2黃金分割法的基本原理與步驟一維搜索是解函數(shù)極小值的方法之一，其解法思想為沿某一已知方向求目標(biāo)函數(shù)的極小值點(diǎn)。一維搜索的解法很多，這里主要采用黃金分割法(0.618法)。如圖所示rl=a+0.382(b-a)r2=a+0.618(b-a)如圖所以新區(qū)間為何,r2］以為新區(qū)間，繼續(xù)求新的試點(diǎn)黃金分割法是用于一元函數(shù)f(x)在給定初始區(qū)間［a,b］內(nèi)搜索極小點(diǎn)a*的一種方法。它是優(yōu)化計(jì)算中的經(jīng)典算法，以算法簡單、收斂速度均勻、效果較好而著稱，是許多優(yōu)化算法的基礎(chǔ)，但它只適用于一維區(qū)間上的凸函數(shù)，即只在單峰區(qū)間內(nèi)才能進(jìn)行一維尋優(yōu)，其收斂效率較低。其基本原理是：依照“去劣存優(yōu)”原則、對(duì)稱原則、以及等比收縮原則來逐步縮小搜索區(qū)間。具體步驟是：在區(qū)間［a,b］內(nèi)取點(diǎn)：al,a2把［a,b］分為三段。如果f(al)>f(a2),令a=a1,a1=a2,a2=a+r*(b一a)；如果f(al)<f(a2)，令b=a2,a2=al，al=a+r*(b一a)，如果|(b-a)/b|和|(yl-y2)/y2〔都大于收斂精度￡重新開始。因?yàn)椋踑,b］為單峰區(qū)間，這樣每次可將搜索區(qū)間縮小0.618倍或0.382倍，處理后的區(qū)間都將包含極小點(diǎn)的區(qū)間縮小，然后在保留下來的區(qū)間上作同樣的處理，如此迭代下去，將使搜索區(qū)［a,b］逐步縮小，滿足預(yù)先給定的精度時(shí)，即獲得一維優(yōu)化問題的近似最優(yōu)解。3.30.618法算法給定區(qū)間［a,b］，及eps>0;計(jì)算r=a+0.382(b-a),u=a+0.618(b-a);;若f(r)>f(u)，轉(zhuǎn)(4)，否則轉(zhuǎn)(5)⑷若u-r<eps，則停，輸出X*=u,f*=f(u)否則令a=r，r=u，u=a+0.618(b一a)，轉(zhuǎn)(3)(5)若u-r<eps，則停，輸出x*=r,f*=f(r)否則令b=u，u=r，r=a+0.382(b-a)，轉(zhuǎn)(3)3.4算法流程圖3.5用matlab編寫源程序編寫程序，并且輸出每次的搜索區(qū)間。則源程序如下:f618程序function[x,fval,iter]=f618(a,b)iter=0;whileabs(b-a)>1e-5iter=iter+1;lambda=a+0.382*(b-a);miu=a+0.618*(b-a);[dy,f1]=fun1(lambda);[dy,f2]=fun1(miu);iff1>f2a=lambda;disp(['the'num2str(iter)'iterationsearchareais:['num2str(a)','num2str(b)']'])elseb=miu;disp(['the'num2str(iter)'iterationsearchareais:['num2str(a)','num2str(b)']'])endendx=(a+b)/2;[dy,fval]=fun1(x);funl程序function[dy,val]=fun1(x)%val=exp(-x)+exp(x);%dy=-exp(-x)+exp(x);%val=-((sin(x))八6*tan(1-x)*exp(30*x));%dy=-(6*(sin(x))八5*cos(x)*tan(1-x)*exp(30*x)+(sin(x))八6*(1/cos(1-x))八2*(-1)*exp(30*x)+(sin(x))八6*tan(1-x)*exp(30*x)*30);第四章黃金分割法應(yīng)用舉例4.1例1根據(jù)0.618算法編寫程序，求函數(shù)f(x)=(sinx)6tan(1一x)e30x在區(qū)間lo,1]上的極大值。解：令g(X)=一f(x)=一(sinx)6tan(1一x)e30*，求ming(x)婦0,1]funl程序?yàn)椋篺unction[dy,val]=fun1(x)val=-((sin(x))"*tan(1-x)*exp(30*x));dy=-(6*(sin(x))八5*cos(x)*tan(1-x)*exp(30*x)+(sin(x))八6*(1/cos(1-x))八2*(-1)*exp(30*x)+(sin(x))"*tan(1-x)*exp(30*x)*30);取eps=1e-5運(yùn)行結(jié)果：[x,fval,iter]=f618(0,1)theliteration search area is :[0.382,1]the2iteration search area is :[0.61808,1]the3iteration search area is :[0.76397,1]the4iteration search area is :[0.85413,1]the5iteration search area is :[0.90985,1]the6iteration search area is :[0.94429,1]the7iteration search area is :[0.94429,0.97872]the8iteration search area is :[0.95744,0.97872]the9iteration search area is :[0.96557,0.97872]the10iteration search area is :[0.96557,0.9737]the11iteration search area is :[0.96867,0.9737]the12iteration search area is :[0.96867,0.97178]the13iteration search area is :[0.96986,0.97178]the14iteration search area is :[0.96986,0.97104]the15iteration search area is :[0.97031,0.97104]the16iteration search area is :[0.97031,0.97077]the17iteration search area is :[0.97049,0.97077]the18iteration search area is :[0.97059,0.97077]the19iteration search area is :[0.97059,0.9707]the20iteration search area is :[0.97063,0.9707]the21iteration search area is :[0.97063,0.97067]the22iteration search area is :[0.97065,0.97067]the23iteration search area is :[0.97066,0.97067]the24iteration search area is :[0.97066,0.97067]x=0.9707fval=-4.1086e+010iter=24則ming(x)為4.1086e+010xe[0,1]例2求函數(shù)W(t)=e-1+et在[-1,1]內(nèi)的極小值解：funl程序?yàn)椋篺unction[dy,val]=fun1(x)val=exp(-x)+exp(x);dy=-exp(-x)+exp(x);令eps=1e-5運(yùn)行結(jié)果；[x,fval,iter]=f618(-1,1)theliterationsearch area is :[-1,0.236]the2iterationsearch area is :[-0.52785,0.236]the3iterationsearch area is :[-0.23606,0.236]the4iterationsearch area is :[-0.055732,0.236]the5iterationsearch area is :[-0.055732,0.12456]the6iterationsearch area is :[-0.055732,0.055688]the7iterationsearch area is :[-0.01317,0.055688]the8iterationsearch area is :[-0.01317,0.029384]the9iterationsearch area is :[-0.01317,0.013129]the10iterationsearch area is :[-0.0031238,0.013129]the11iterationsearch area is :[-0.0031238,0.0069202]the12iterationsearch area is :[-0.0031238,0.0030834]the13iterationsearch area is :[-0.00075262,0.0030834]the14iterationsearch area is :[-0.00075262,0.001618]the15iterationsearch area is :[-0.00075262,0.00071244]the16iterationsearch area is :[-0.00019297,0.00071244]the17iterationsearch area is :[-0.00019297,0.00036658]the18iterationsearch area is :[-0.00019297,0.00015283]the19iterationsearch area is :[-6.0873e-005,0.00015283]the20iterationsearch area is :[-6.0873e-005,7.1195e-005]the21iterationsearch area is :[-6.0873e-005,2.0745e-005]the22iterationsearch area is :[-2.9695e-005,2.0745e-005]the23iterationsearch area is :[-1.0427e-005,2.0745e-005]the24iterationsearch area is :[-1.0427e-005,8.8374e-006]the25iterationsearch area is :[-3.068e-006,8.8374e-006]the26iterationsearch area is :[-3.068e-006,4.2895e-006]x=6.1078e-007fval=2.0000iter=26則原式極小值為：6.1078e-007第五章總結(jié)5.1概括總結(jié)最開始接觸黃金分割法大概要算初中時(shí)候?qū)W過的黃金分割點(diǎn)，是把一條線段分割為兩部分，使其中一部分與全長之比等于另一部分與這部分之比。其比值是一個(gè)無理數(shù)，取其前三位數(shù)字的近似值是0.618，所以也稱為0.618法。然后在大學(xué)的最優(yōu)化方法這門課上，我們又重新認(rèn)識(shí)了黃金分割法，知道它不僅是最優(yōu)化中解決無約束問題的方法中重要的一環(huán)，而且是不可或缺的方法。通過這次課程設(shè)計(jì)，我們重新學(xué)習(xí)了以前遺忘的知識(shí)，加深了記憶和理解。真正做到了理論和實(shí)踐相結(jié)合，鍛煉了自己分析，處理實(shí)際問題的能力，也認(rèn)識(shí)到了自己的不足。為以后畢業(yè)設(shè)計(jì)總結(jié)了經(jīng)驗(yàn)和教訓(xùn)將指導(dǎo)我未來的工作和學(xué)習(xí)，我會(huì)更加努力，取得更大的成績。5.2具體分工本次課程設(shè)計(jì)中，我們小組的主要分工形式為：（1） 顏海峰同學(xué)主要負(fù)責(zé)將課本的理論與實(shí)際題目結(jié)合，并進(jìn)行論文的撰寫與修改；（2） 黃雷同學(xué)主要負(fù)責(zé)題目的求解，特別是利用matlab軟件編寫程序方便地將復(fù)雜的題目求解出來；（3） 藍(lán)田同學(xué)主要負(fù)責(zé)資料的搜索與文獻(xiàn)的查閱。以上為大致的分工，然而在實(shí)際問題的求解與操作過程中，分工并不是絕對(duì)的，大家都常常相互討論研究，工作常常相互交叉進(jìn)行，互相配合完成。5.3個(gè)人感言本次最優(yōu)化課程設(shè)計(jì)中我的主要任務(wù)是負(fù)責(zé)資料的收集和論文的撰寫。經(jīng)過兩個(gè)隊(duì)友和我堅(jiān)持不懈奮斗，最終完成了本次的課程設(shè)計(jì)。從開始選題到組隊(duì)，再到組員分工，以及最后的實(shí)際操作，我們組的成員都體現(xiàn)出了相當(dāng)強(qiáng)的凝聚力。在完成各自分工的同時(shí)，也與隊(duì)友協(xié)作完成其他部分。但在協(xié)作過程中也存在著一些分歧，比如大家都在幫我找資料的時(shí)候，大家找到不同的了，會(huì)像吵架一樣爭著要用上自己收集的資料。但在最后，真理戰(zhàn)勝了大家小小的虛榮。在收集的資料中，取其精華，去其糟粕。在撰寫論文過程中我也得到了隊(duì)友們的協(xié)助，但是各有各的排版風(fēng)格，在各自的論文排版設(shè)計(jì)風(fēng)格面前，我們遵照了老師的要求，完成了本次課程設(shè)計(jì)至關(guān)重要的最后一步。通過完成這次最優(yōu)化課程設(shè)計(jì)，在解決問題的過程中，充分體會(huì)到了最優(yōu)化方法對(duì)于解決一些實(shí)際問題的重要性。一個(gè)多星期的課程設(shè)計(jì)，雖然有些疲勞和困倦，但是帶給了我很多我在課本上學(xué)不到的知識(shí)。實(shí)踐是檢驗(yàn)真理的唯一標(biāo)準(zhǔn)，沒有實(shí)踐，就不會(huì)發(fā)現(xiàn)和深刻體會(huì)知識(shí)的真實(shí)所在，只有通過了實(shí)踐檢驗(yàn)的真理，在自己的心里，才會(huì)得到認(rèn)可。最優(yōu)化課程設(shè)計(jì)的完成，讓我懂得了真理重要性，只有理論和實(shí)踐相結(jié)合，才能真正的掌握所學(xué)的的知識(shí)?！伜７逶谶@次課程設(shè)計(jì)過程中，我不斷地成長，不斷地累積我的知識(shí)。不僅是知識(shí)的成長，并且學(xué)會(huì)了與隊(duì)友溝通、合作，團(tuán)隊(duì)意識(shí)也得到了提高。同時(shí)我認(rèn)為我們的工作是一個(gè)團(tuán)隊(duì)的工作，團(tuán)隊(duì)需要個(gè)人，個(gè)人也離不開團(tuán)隊(duì)，必須發(fā)揚(yáng)團(tuán)結(jié)協(xié)作的精神。某個(gè)人的離群都可能導(dǎo)致整項(xiàng)工作的失敗。通過課程設(shè)計(jì)我才發(fā)現(xiàn)，一個(gè)人單單知道知識(shí)理論是遠(yuǎn)遠(yuǎn)不夠的，還有結(jié)合實(shí)踐，這樣我們才能更好的掌握所學(xué)的知識(shí)。在這次設(shè)計(jì)過程中，體現(xiàn)出自己建模能力以及綜合運(yùn)用知識(shí)的能力，體會(huì)了學(xué)以致用、突出自己勞動(dòng)成果的喜悅心情，從中發(fā)現(xiàn)自己平時(shí)學(xué)習(xí)的不足和薄弱環(huán)節(jié)，從而加以彌補(bǔ)。通過這次編程也告訴了我一個(gè)問題不僅只有一種方