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

2、or Yang LipoYanshan UniversityDecember, 2012摘 要最優化理論和方法日益受到重視，已經滲透到生產、管理、商業、軍事、決 策等各個領域，而最優化模型與方法廣泛應用于工業、農業、交通運輸、商業、國防、建筑、同學、政府機關等各個部門及各個領域。伴隨著計算機技術的高速發展，最優化理論與方法的迅速進步為解決實際最優化問題的軟件也在飛速發展。其中，MATLAB軟件已經成為最優化領域應用最廣的軟件之一。有了MATLAB這個強大的計算平臺，既可以利用MATLAB優化工具箱中的函數，又可以通過算法變成實現相應的最優化計算。 在最優化計算中一維最優化方法是優化設計中最簡單

3、、最基本的方法。一維搜索，又稱為線性搜索，一維問題是多維問題的基礎，在數值方法迭代計算過程中，都要進行一維搜索，也可以把多維問題化為一些一維問題來處理。一維問題的算法好壞，直接影響到最優化問題的求解速度。而黃金分割法是一維搜索方法中重要的方法之一，它適用于任何單峰函數求最小值的問題，甚至于對函數可以不要求連續，是一種基于區間收縮的極小點搜索算法。關鍵詞：最優化；黃金分割法；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章 最優化方法基本原理22.1 無約束問題的最優性條件22.2 搜索區間的確定2第3章 黃金分割法的基本原理與思想43.1 黃金分割法的基本思路43.2 黃金分割法的基本原理與步驟43.3 黃金分割0.618算法53.4 算法流程圖6第

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

11、法更是數學科學里面的一個巨大的篇幅，在這個信息化的時代，最優化方法廣泛應用于工業、農業、國防、建筑、通信與政府機關、管理等各個部門、各個領域；它主要解決最優計劃、最優分配、最優決策、最佳設計、最佳管理等最優化問題。而最優解問題是這些所有問題的中心，是最優化方法的重中之重，在求最優解問題中，有多種方法解決，我們在這里著重討論無約束一維極值問題，即非線性規劃的一維搜索方法之黃金分割法。黃金分割法也叫0.618法，屬于區間收縮法，首先找出包含極小點的初始搜索區間，然后按黃金分割點通過對函數值的比較不斷縮小搜索區間。當然要保證極小點始終在搜索區間內，當區間長度小到精度范圍之內時，可以粗略地認為區間端點

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

13、件是：是其目標函數的駐點。 現給出無約束問題局部最優解的充分條件。定理 3 設在點處的海賽矩陣存在，若并且正定，則是無約束問題的嚴格局部最優解。一般而言，無約束問題的目標函數的駐點不一定是無約束問題的最優解。但對于其目標函數是凸函數的無約束凸規劃，下面定理證明了，它的目標函數的駐點就是它的整體最優解。定理 4 設，是上的可微凸函數。若有則是無約束問題的整體最優解。2.2 搜索區間的確定在一維搜索時，我們假設函數具有如單谷性，即在所考慮的區間內部，函數有唯一的極小點*。為了確定極小點*所在的區間a,b，應使函數在a,b區間里形成“高低高”趨勢。為此，從=0開始，以初始步長h0向前試探。如若函數值

14、上升，則步長變號，即改變試探方向。如果函數值下降，則維持原來的試探方向，并將步長加倍。去鑒定的始點、中間點依次沿試探方向移動一步。此過程一直進行到函數值再次上升為止，即可找到搜索區間的終點。最后的得到的三點即為搜索區間的始點、中間點和終點，形成函數值的“高低高”趨勢。第3章 黃金分割法的基本原理與思想3.1 黃金分割法的基本思路黃金分割法適用于區間上的任何單股函數求極小值問題，對函數除要求“單峰”外不做其他要求，甚至可以不連續。因此，這種方法的適應面非常廣。黃金分割法也是建立在區間消去法原理基礎上的試探方法，即在搜索區間內適當插入兩點、，并計算其函數值。、將區間分成三段，應用函數的單峰性質，通

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

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

17、b=u，u=r,轉（3）；3.4 算法流程圖圖3-1 黃金分割算法的流程圖第4章 優化程序的計算結果及其分析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('目標函數為：')f='x4-5*x3+4*x2-6*x+60'disp('最優解為：')best_x=(a+b)/2disp('目標函數極小值為：')best_fx=subs(f,x,best_x)4.2 源程序

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

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

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

22、對以后的學習生活充滿了期待。總的來說，機械優化設計的課程內容是就如何求得機械設計過程中遇到的最優值的選擇問題進行多方法多角度合理闡述。課程敘述了根據不同的約束模型而得到的不同的擇優方法，以及列舉出了許多優化算法在機械方面應用的實例，給我留下了深刻的印象，也使我學到了在本科及工作階段所沒有學到的新的知識。由于課時的關系和學習時間的有限，而且關于本課程編程所需要的Matlab軟件因為以前沒有接觸過而倍感生疏，故本次實驗報告的撰寫以及相關程序的編寫會顯得有些粗略和不足，希望老師您能夠批評指正。我會以后的研究生生活中，繼續對本課程進行研究和學習，爭取達到完全吸收和靈活運用的程度，扎實的打好研一的理論與

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

24、老師有兩句話我深以為然：“中學時你可以逃避責任，因為你的父母可以原諒你；大學時你也可以逃避責任，因為你的老師可以原諒你；工作時你如果再逃避責任，沒人會原諒你，領導只會辭退你”，“要想生存，誰都不能依靠，只能靠自己”我對此深表贊同，生活是現實的，現實是競爭的，競爭是殘酷的，只有學得一身本事，才能在這個充滿競爭的現實社會中擁有立足之地。附 錄一、無約束優化方法程序考核題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