碩士研究生機(jī)械優(yōu)化設(shè)計(jì)作業(yè)

1、機(jī) 械 優(yōu) 化 設(shè) 計(jì) 報(bào) 告REPORT FOR OPTIMAL DESIGN OF MACHINE 作業(yè)題目 黃金分割一維搜索方法作者姓名 黎 原作者學(xué)號(hào) 學(xué)科專業(yè) 機(jī)械設(shè)計(jì)及理論指導(dǎo)教師 楊立坡教授 2012年12月研究生機(jī)械優(yōu)化設(shè)計(jì)報(bào)告黃金分割一維搜索方法碩士研究生：黎 原碩士生學(xué)號(hào)導(dǎo)師：楊利坡教授學(xué)科專業(yè)：機(jī)械設(shè)計(jì)及理論所 在 單 位：機(jī)械工程學(xué)院Report in Mechanical Design and TheoryTHE GOLDEN SPLITING ONE-DIMENSIONAL SEARCHING METHODby Li Yuan Supervisor: Profess

2、or Yang LipoYanshan UniversityDecember, 2012摘 要最優(yōu)化理論和方法日益受到重視，已經(jīng)滲透到生產(chǎn)、管理、商業(yè)、軍事、決 策等各個(gè)領(lǐng)域，而最優(yōu)化模型與方法廣泛應(yīng)用于工業(yè)、農(nóng)業(yè)、交通運(yùn)輸、商業(yè)、國(guó)防、建筑、同學(xué)、政府機(jī)關(guān)等各個(gè)部門及各個(gè)領(lǐng)域。伴隨著計(jì)算機(jī)技術(shù)的高速發(fā)展，最優(yōu)化理論與方法的迅速進(jìn)步為解決實(shí)際最優(yōu)化問(wèn)題的軟件也在飛速發(fā)展。其中，MATLAB軟件已經(jīng)成為最優(yōu)化領(lǐng)域應(yīng)用最廣的軟件之一。有了MATLAB這個(gè)強(qiáng)大的計(jì)算平臺(tái)，既可以利用MATLAB優(yōu)化工具箱中的函數(shù)，又可以通過(guò)算法變成實(shí)現(xiàn)相應(yīng)的最優(yōu)化計(jì)算。 在最優(yōu)化計(jì)算中一維最優(yōu)化方法是優(yōu)化設(shè)計(jì)中最簡(jiǎn)單

3、、最基本的方法。一維搜索，又稱為線性搜索，一維問(wèn)題是多維問(wèn)題的基礎(chǔ)，在數(shù)值方法迭代計(jì)算過(guò)程中，都要進(jìn)行一維搜索，也可以把多維問(wèn)題化為一些一維問(wèn)題來(lái)處理。一維問(wèn)題的算法好壞，直接影響到最優(yōu)化問(wèn)題的求解速度。而黃金分割法是一維搜索方法中重要的方法之一，它適用于任何單峰函數(shù)求最小值的問(wèn)題，甚至于對(duì)函數(shù)可以不要求連續(xù)，是一種基于區(qū)間收縮的極小點(diǎn)搜索算法。關(guān)鍵詞：最優(yōu)化；黃金分割法；MATLAB；算法；一維搜索；AbstractOptimization theory and methods which have been paid more attention, have penetrated into

4、 the production, management, business, military, decision-making and other fields, and optimization models and methods widely used in industry, agriculture, transportation, commerce, defense, construction, students, government various departments and agencies and other fields. With the rapid develop

5、ment of computer technology, optimization theory and methods for the rapid progress of the optimization problem to solve practical software is also developing rapidly. MATLAB software has become the most optimization software is one of the most widely used. With this powerful computing platform MATL

6、AB, we can use not only MATLAB optimization toolbox in the function, but also can achieve the appropriate algorithm to optimize into the calculation. In the calculation of one-dimensional optimization method is to optimize the design of the simplest, most basic method. One-dimensional search, also k

7、nown as linear search, one-dimensional problem is multi-dimensional problem based on iterative methods in numerical calculation, should be one-dimensional search, can also multi-dimensional problem into a number of one-dimensional problem to deal with. One-dimensional algorithms are directly affecte

8、d by the speed of solving optimization problems. The golden section method as a one-dimensional search method is one important method, which applies to any single peak function for the minimum of the problem, even on the function that does not require a continuous. The golden section method is a ver

9、y small point search algorithm based on a interval-based contraction.Keywords: Optimization;Golden section method;MATLAB;Algorithm; One-dimensional search;目 錄摘 要IABSTRACTII第1章 緒 論1第2章 最優(yōu)化方法基本原理22.1 無(wú)約束問(wèn)題的最優(yōu)性條件22.2 搜索區(qū)間的確定2第3章 黃金分割法的基本原理與思想43.1 黃金分割法的基本思路43.2 黃金分割法的基本原理與步驟43.3 黃金分割0.618算法53.4 算法流程圖6第

10、4章 優(yōu)化程序的計(jì)算結(jié)果及其分析74.1 用matlab編寫源程序74.2 源程序計(jì)算過(guò)程及結(jié)果7第5章 一維搜索優(yōu)化的比較和分析95.1 進(jìn)退法的原理及特點(diǎn)95.1.1 算法思想95.1.2 計(jì)算步驟95.2 插值法的原理及特點(diǎn)95.2.1 算法原理簡(jiǎn)介95.2.1 插值算法計(jì)算過(guò)程9總 結(jié)11附 錄12一、無(wú)約束優(yōu)化方法程序考核題121. 牛頓法的 Matlab編程源程序122. 牛頓法編程的計(jì)算結(jié)果14二、約束優(yōu)化方法程序考核題141. Matlab自帶函數(shù)編程的源程序142. 程序運(yùn)行的結(jié)果16參考文獻(xiàn)17第1章 緒 論數(shù)學(xué)科學(xué)不僅是自然科學(xué)的基礎(chǔ)，也是一切重要技術(shù)發(fā)展的基礎(chǔ)。最優(yōu)化方

11、法更是數(shù)學(xué)科學(xué)里面的一個(gè)巨大的篇幅，在這個(gè)信息化的時(shí)代，最優(yōu)化方法廣泛應(yīng)用于工業(yè)、農(nóng)業(yè)、國(guó)防、建筑、通信與政府機(jī)關(guān)、管理等各個(gè)部門、各個(gè)領(lǐng)域；它主要解決最優(yōu)計(jì)劃、最優(yōu)分配、最優(yōu)決策、最佳設(shè)計(jì)、最佳管理等最優(yōu)化問(wèn)題。而最優(yōu)解問(wèn)題是這些所有問(wèn)題的中心，是最優(yōu)化方法的重中之重，在求最優(yōu)解問(wèn)題中，有多種方法解決，我們?cè)谶@里著重討論無(wú)約束一維極值問(wèn)題，即非線性規(guī)劃的一維搜索方法之黃金分割法。黃金分割法也叫0.618法，屬于區(qū)間收縮法，首先找出包含極小點(diǎn)的初始搜索區(qū)間，然后按黃金分割點(diǎn)通過(guò)對(duì)函數(shù)值的比較不斷縮小搜索區(qū)間。當(dāng)然要保證極小點(diǎn)始終在搜索區(qū)間內(nèi)，當(dāng)區(qū)間長(zhǎng)度小到精度范圍之內(nèi)時(shí)，可以粗略地認(rèn)為區(qū)間端點(diǎn)

12、的平均值即為極小值的近似值。所以用0.618法得出的是比較精確的最優(yōu)解了。本次作業(yè)程序的運(yùn)行環(huán)境是matlab7.0版本的運(yùn)行環(huán)境。第2章 最優(yōu)化方法基本原理2.1 無(wú)約束問(wèn)題的最優(yōu)性條件無(wú)約束問(wèn)題的最優(yōu)解所要滿足的必要條件和充分條件是我們?cè)O(shè)計(jì)算法的依據(jù)，為此我們有以下幾個(gè)定理。定理1 設(shè)在點(diǎn)處可微。若存在，使 則向量是在處的下降方向。定理2 設(shè)在點(diǎn)處可微。若是無(wú)約束問(wèn)題的局部最優(yōu)解，則由數(shù)學(xué)分析中我們已經(jīng)知道，使的點(diǎn)x為函數(shù)f的駐點(diǎn)或平穩(wěn)點(diǎn)。函數(shù)的一個(gè)駐點(diǎn)可以是極小點(diǎn)；也可以是極大點(diǎn)；甚至也可能既不是極小點(diǎn)也不是極大點(diǎn)，此時(shí)稱它為函數(shù)的鞍點(diǎn)。以上定理告訴我們，是無(wú)約束問(wèn)題的局部最優(yōu)解的必要條

13、件是：是其目標(biāo)函數(shù)的駐點(diǎn)。 現(xiàn)給出無(wú)約束問(wèn)題局部最優(yōu)解的充分條件。定理 3 設(shè)在點(diǎn)處的海賽矩陣存在，若并且正定，則是無(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è)，是上的可微凸函數(shù)。若有則是無(wú)約束問(wèn)題的整體最優(yōu)解。2.2 搜索區(qū)間的確定在一維搜索時(shí)，我們假設(shè)函數(shù)具有如單谷性，即在所考慮的區(qū)間內(nèi)部，函數(shù)有唯一的極小點(diǎn)*。為了確定極小點(diǎn)*所在的區(qū)間a,b，應(yīng)使函數(shù)在a,b區(qū)間里形成“高低高”趨勢(shì)。為此，從=0開(kāi)始，以初始步長(zhǎng)h0向前試探。如若函數(shù)值

14、上升，則步長(zhǎng)變號(hào)，即改變?cè)囂椒较?。如果函?shù)值下降，則維持原來(lái)的試探方向，并將步長(zhǎng)加倍。去鑒定的始點(diǎn)、中間點(diǎn)依次沿試探方向移動(dòng)一步。此過(guò)程一直進(jìn)行到函數(shù)值再次上升為止，即可找到搜索區(qū)間的終點(diǎn)。最后的得到的三點(diǎn)即為搜索區(qū)間的始點(diǎn)、中間點(diǎn)和終點(diǎn)，形成函數(shù)值的“高低高”趨勢(shì)。第3章 黃金分割法的基本原理與思想3.1 黃金分割法的基本思路黃金分割法適用于區(qū)間上的任何單股函數(shù)求極小值問(wèn)題，對(duì)函數(shù)除要求“單峰”外不做其他要求，甚至可以不連續(xù)。因此，這種方法的適應(yīng)面非常廣。黃金分割法也是建立在區(qū)間消去法原理基礎(chǔ)上的試探方法，即在搜索區(qū)間內(nèi)適當(dāng)插入兩點(diǎn)、，并計(jì)算其函數(shù)值。、將區(qū)間分成三段，應(yīng)用函數(shù)的單峰性質(zhì)，通

15、過(guò)函數(shù)值大小的比較，刪去其中一段，是搜索區(qū)間得以縮小。然后再在保留下來(lái)的區(qū)間上作同樣的處理，如此迭代下去，是搜索區(qū)間無(wú)限縮小，從而得到極小點(diǎn)的數(shù)值近似解。3.2 黃金分割法的基本原理與步驟一維搜索是解函數(shù)極小值的方法之一，其解法思想為沿某一已知方向求目標(biāo)函數(shù)的極小值點(diǎn)。一維搜索的解法很多，這里主要采用黃金分割法（0.618法）。黃金分割法是用于一元函數(shù)在給定初始區(qū)間內(nèi)搜索極小點(diǎn)的一種方法。它是優(yōu)化計(jì)算中的經(jīng)典算法，以算法簡(jiǎn)單、收斂速度均勻、效果較好而著稱，是許多優(yōu)化算法的基礎(chǔ)，但它只適用于一維區(qū)間上的凸函數(shù)，即只在單峰區(qū)間內(nèi)才能進(jìn)行一維尋優(yōu)，其收斂效率較低。其基本原理是：依照“去劣存優(yōu)”原則、

16、對(duì)稱原則、以及等比收縮原則來(lái)逐步縮小搜索區(qū)間。具體步驟如下：在區(qū)間內(nèi)取點(diǎn)把分為三段。如果>,令=,=,=；如果<，令=,=,=,如果和都大于收斂精度，則重新開(kāi)始。因?yàn)闉閱畏鍏^(qū)間，這樣每次可將搜索區(qū)間縮小0.618倍或0.382倍，處理后的區(qū)間都將包含極小點(diǎn)的區(qū)間縮小，然后在保留下來(lái)的區(qū)間上作同樣的處理，如此迭代下去，將使搜索區(qū)逐步縮小，滿足預(yù)先給定的精度時(shí)，即獲得一維優(yōu)化問(wèn)題的近似最優(yōu)解。3.3 黃金分割0.618算法（1）給定區(qū)間及>0； （2）計(jì)算，并計(jì)算；（3）若，轉(zhuǎn)（4），否則轉(zhuǎn)（5）；（4）若，則停止，輸出，否則a=r，r=u,轉(zhuǎn)（3）；（5）若，則停止，輸出，否則

17、b=u，u=r,轉(zhuǎn)（3）；3.4 算法流程圖圖3-1 黃金分割算法的流程圖第4章 優(yōu)化程序的計(jì)算結(jié)果及其分析4.1 用matlab編寫源程序syms x;f=inline('x4-5*x3+4*x2-6*x+60','x');a=0;b=10;epsilon=0.00001; x1=b-0.618*(b-a);f1=f(x1); x2=a+0.618*(b-a);f2=f(x2);while(abs(b-a)>epsilon) if f1<f2 b=x2;x2=x1;f2=f1; x1=a+0.382*(b-a); f1=subs(f,x,x1);

18、elseif f1=f2 a=x1;b=x2; x2=a+0.618*(b-a);f2=subs(f,x,x2); x1=a+0.382*(b-a);f1=subs(f,x,x1); else a=x1;x1=x2;f1=f2; x2=a+0.618*(b-a); f2=subs(f,x,x2); endenddisp('目標(biāo)函數(shù)為：')f='x4-5*x3+4*x2-6*x+60'disp('最優(yōu)解為：')best_x=(a+b)/2disp('目標(biāo)函數(shù)極小值為：')best_fx=subs(f,x,best_x)4.2 源程序

19、計(jì)算過(guò)程及結(jié)果1. 給定搜索區(qū)間0,10以及收斂精度epsilon=0.000012. 按坐標(biāo)點(diǎn)計(jì)算公式，計(jì)算和，并計(jì)算其對(duì)應(yīng)的函數(shù)值，。3. 根據(jù)區(qū)間消去法原理縮短搜索區(qū)間。為了能用原來(lái)的坐標(biāo)點(diǎn)計(jì)算公式，需進(jìn)行區(qū)間名稱的代換，并在保留區(qū)間中計(jì)算一個(gè)新的試驗(yàn)點(diǎn)及其函數(shù)值。4. 檢查區(qū)間是否縮短到足夠小和函數(shù)值收斂到足夠近，如果條件不滿足則返回到步驟2。5. 如果條件滿足，則取最后的兩試驗(yàn)點(diǎn)的平均值作為極小點(diǎn)的數(shù)值近似解。6. 該程序運(yùn)行的結(jié)果如下截屏所示。圖4-1 黃金分割法程序運(yùn)行結(jié)果第5章 一維搜索優(yōu)化的比較和分析5.1 進(jìn)退法的原理及特點(diǎn) 算法思想從某一點(diǎn)出發(fā)，任選一個(gè)方向和步長(zhǎng)，向前試

20、探性的走一步，求出該點(diǎn)的函數(shù)值。如果有利（指該點(diǎn)函數(shù)值較?。?，就向前走一步，并加大步長(zhǎng)再向前試探一步；否則，就縮小步長(zhǎng)反方向（后退方向）試探一步。如此反復(fù)搜索，當(dāng)步長(zhǎng)縮小到一定程度時(shí)停止。最后搜索到的點(diǎn)即為極值點(diǎn)。其特點(diǎn)為：結(jié)構(gòu)和程序簡(jiǎn)單，但效率偏低。 計(jì)算步驟1. 給定初始點(diǎn)t0，初始點(diǎn)長(zhǎng)h>0，允許誤差e>0，步長(zhǎng)因子blpha屬于（0，1），alpha>1，計(jì)算f0=f(t0)。2. 令試算點(diǎn)t=xk+h，計(jì)算ft=f(t)。3. 若fk>f，則k=k+1，xk=t，h=alpha*h，轉(zhuǎn)第二步：否則，置h=-blpha*h，轉(zhuǎn)第 （4）步。4. 若|h|<

21、e，則停止計(jì)算，xk 為近似極小點(diǎn)：否則轉(zhuǎn)第二步。5.2 插值法的原理及特點(diǎn) 算法原理簡(jiǎn)介在求解一元函數(shù)的極小點(diǎn)時(shí)，常常利用一個(gè)低次插值多項(xiàng)式來(lái)逼近原目標(biāo)函數(shù)，然后求該多項(xiàng)式的極小點(diǎn)(低次多項(xiàng)式的極小點(diǎn)比較容易計(jì)算)，并以此作為目標(biāo)函數(shù)的近似極小點(diǎn)。如果其近似的程度尚未達(dá)到所要求的精度時(shí)，可以反復(fù)使用此法，逐次擬合，直到滿足給定的精度時(shí)為止。其特點(diǎn)為搜索效率較高，收斂速度快。 插值算法計(jì)算過(guò)程圖5-1 插值算法的流程圖總 結(jié)一、 課程心得本人覺(jué)得優(yōu)化設(shè)計(jì)這門學(xué)科很有意義，很有價(jià)值，對(duì)整個(gè)機(jī)械行業(yè)以及其他的行業(yè)的幫助非常大，是難得的一門課程，當(dāng)然自身的收獲也讓自己覺(jué)得研究生的生活是非常充實(shí)的，并

22、對(duì)以后的學(xué)習(xí)生活充滿了期待?？偟膩?lái)說(shuō)，機(jī)械優(yōu)化設(shè)計(jì)的課程內(nèi)容是就如何求得機(jī)械設(shè)計(jì)過(guò)程中遇到的最優(yōu)值的選擇問(wèn)題進(jìn)行多方法多角度合理闡述。課程敘述了根據(jù)不同的約束模型而得到的不同的擇優(yōu)方法，以及列舉出了許多優(yōu)化算法在機(jī)械方面應(yīng)用的實(shí)例，給我留下了深刻的印象，也使我學(xué)到了在本科及工作階段所沒(méi)有學(xué)到的新的知識(shí)。由于課時(shí)的關(guān)系和學(xué)習(xí)時(shí)間的有限，而且關(guān)于本課程編程所需要的Matlab軟件因?yàn)橐郧皼](méi)有接觸過(guò)而倍感生疏，故本次實(shí)驗(yàn)報(bào)告的撰寫以及相關(guān)程序的編寫會(huì)顯得有些粗略和不足，希望老師您能夠批評(píng)指正。我會(huì)以后的研究生生活中，繼續(xù)對(duì)本課程進(jìn)行研究和學(xué)習(xí)，爭(zhēng)取達(dá)到完全吸收和靈活運(yùn)用的程度，扎實(shí)的打好研一的理論與

23、方法基礎(chǔ)，為今后的科研生活做好準(zhǔn)備。二、內(nèi)容體會(huì)本人比較喜歡楊老師講課時(shí)嚴(yán)謹(jǐn)又不乏幽默的風(fēng)格。本來(lái)這門課程講的都是一些優(yōu)化算法以及數(shù)學(xué)理論方面的東西，盡管意義重大，但不免會(huì)有些枯燥和乏味，但楊老師能夠在講理論、述方法的同時(shí)給我們講了許多歷史、地理、物理、政治、生活、工作、理想以及國(guó)內(nèi)外的相關(guān)事件，并對(duì)其進(jìn)行解析和描述，讓我們?cè)趯W(xué)習(xí)疲憊之時(shí)能夠及時(shí)得到放松，更重要的是，我們可以從中學(xué)到一些數(shù)學(xué)優(yōu)化方法之外的東西，我稱之為人生優(yōu)化方法。本人是工作了一年之后才選擇辭職回來(lái)讀研的，接觸過(guò)社會(huì)上的生活，也領(lǐng)教過(guò)一些社會(huì)上的生存之道，所以對(duì)楊老師就企業(yè)工作以及責(zé)任義務(wù)方面的觀點(diǎn)深表贊同，自然也深有體會(huì)。楊

24、老師有兩句話我深以為然：“中學(xué)時(shí)你可以逃避責(zé)任，因?yàn)槟愕母改缚梢栽從悖淮髮W(xué)時(shí)你也可以逃避責(zé)任，因?yàn)槟愕睦蠋熆梢栽從悖还ぷ鲿r(shí)你如果再逃避責(zé)任，沒(méi)人會(huì)原諒你，領(lǐng)導(dǎo)只會(huì)辭退你”，“要想生存，誰(shuí)都不能依靠，只能靠自己”我對(duì)此深表贊同，生活是現(xiàn)實(shí)的，現(xiàn)實(shí)是競(jìng)爭(zhēng)的，競(jìng)爭(zhēng)是殘酷的，只有學(xué)得一身本事，才能在這個(gè)充滿競(jìng)爭(zhēng)的現(xiàn)實(shí)社會(huì)中擁有立足之地。附 錄一、無(wú)約束優(yōu)化方法程序考核題1. 牛頓法的 Matlab編程源程序fx=sym('4*(x1-5)2+(x2-6)2');f1=diff(fx,'x1');diff(fx,'x2');ot1=diff(fx,&#

25、39;x1',2); ot2=diff(fx,'x2',1);ot2=diff(ot2,'x1',1);ot3=diff(fx,'x2',1);ot3=diff(ot3,'x1',1);ot4=diff(fx,'x2',2);f2=ot1,ot2;ot3,ot4; X=8;9; zz=8;9; while norm(double(zz)>0.001 yy=X; f3=subs(f1,'x1',X(1); f3=subs(f3,'x2',X(2); f4=subs(f2,

26、'x1',X(1); f4=subs(f4,'x2',X(2); g1=-inv(f4)*f3; b1=sym('b1'); X=yy+b1*g1; f5=subs(fx,'x1',X(1); f5=subs(f5,'x2',X(2); sw2=sym2poly(f5);sw1=polyder(sw2); if sw1=0 dwj=eval(f5);elsewe=roots(sw1);for t=1 : length(we) cc(t)=polyval(sw2,we(t);endhi=find(cc=min(min(cc); digits(8); qq=vpa(we(hi); end X=yy+qq*g1; zz=X