1、 最優化方法題目： 斐波那契法分析與實現 院 系： 信息與計算科學學院 專 業： 統計學 姓名學號： 小熊熊 11071050137 指導教師： 大胖胖 日期： 2014 年 01 月 10 日摘 要科學的數學化是當代科學發展的一個主要趨勢，最優化理論與算法是一個重 要的數學分支，它所研究的問題是討論在眾多的方案中什么樣的方案最優以及怎 樣找出最優方案.一維搜索是指尋求一元函數在某個區間上的最優點的方法.這類方法不僅有 實用價值，而且大量多維最優化方法都依賴于一系列的一維最優化.本文就斐波 那契法的一維搜索進行了詳細的分析，并且成功的用 MATLAB 實現了斐波那契法 求解單峰函數的極小值問題

2、.斐波那契法的一維搜索過程是建立在一個被稱為斐波那契數列的基礎上進 行的，斐波那契法成功地實現了單峰函數極值范圍的縮減.從理論上來說，斐波 那契法的精度比黃金分割法要高.但由于斐波那契法要事先知道計算函數值的次 數，故相比之下，黃金分割法更為簡單一點，它不需要事先知道計算次數，并且 當 n 7 時，黃金分割法的收斂速率與斐波那契法越來越接近.因此，在實際應用 中，常常采用黃金分割法. 斐波那契法也是一種區間收縮算法，和黃金分割法不 同的是：黃金分割法每次收縮只改變搜索區間的一個端點，即它是單向收縮法. 而斐波那契法同時改變搜索區間的兩個端點，是一種雙向收縮法.關鍵字：一維搜索斐波那契法單峰函數

3、黃金分割法MATLABAbstractMathematical sciences is a major trend in contemporary scientific development, optimization theory and algorithms is an important branch of mathematics, the problems it was discussed in numerous research programs in the best of what programs and how to find the optimal solution .O

4、ne-dimensional search is the best method of seeking functions of one variable on the merits of a certain interval. Such methods not only have practical value, but also a large number of multi-dimensional optimization methods rely on a series of one-dimensional optimization article on Fibonacci the o

5、ne-dimensional search method carried out a detailed analysis, and successful in MATLAB Fibonacci method for solving unimodal function minimization problem.Fibonacci method of one-dimensional search process is based on the Fibonacci sequence is called a Fibonacci conducted on, Fibonacci method succes

6、sfully achieved a unimodal function extreme range reduction. Theory , Fibonacci method accuracy is higher than the golden section method, but the number of times due to the Fibonacci method to calculate function values to know in advance, so the contrast, the golden section method is more simply, it

7、 does not need to know in advance the number of calculations and at that time, the rate of convergence of golden section and the Fibonacci method getting closer, so in practical applications, often using the golden section method. Fibonacci method is also a range contraction algorithm, and the golde

8、n section method the difference is: golden section each contraction only one endpoint to change the search range that it is unidirectional shrinkage law Fibonacci search method while changing the two endpoints of the range, is a two-way contraction method.Key words: one-dimensional searchFibonacci m

9、ethodunimodal functionGolden Section functionMATLAB目 錄1.前言11.1 一維搜索11.2 單峰函數11.3 單峰函數的性質12.斐波那契法分析22.1 區間縮短率22.2 斐波那契數列32.3 斐波那契法原理32.4 斐波那契法與黃金分割法的關系63.斐波那契法實現73.1 斐波那契算法步驟73.2 斐波那契法的 MATLAB 程序83.3 斐波那契算法舉例 104.課程設計總結 124.1 概述 124.2 個人心得體會 125.參考文獻 131. 前言一維搜索是指尋求一元函數在某區間上的最優值點的方法.這類方法不僅有 實用價值，而且大量

10、多維最優化方法都依賴于一系列的一維最優化.斐波那契法的一維搜索過程是建立在一個被稱為斐波那契數列的基礎上進 行的.從理論上來說，斐波那契法的精度比黃金分割法要高.但由于斐波那契法要 事先知道計算函數值的次數，故相比之下，黃金分割法更為簡單一點，它不需要 事先知道計算次數，并且當 n 7 時，黃金分割法的收斂速率與斐波那契法越來 越接近.因此，在實際應用中，常常采用黃金分割法.1.1 一維搜索很多迭代下降算法具有一個共同點，即得到點 x k 后，需要按某種規則確定 一個方向 d k ，再從 x k 出發，沿著方向 d k 在直線或射線上尋求目標函數的極小點， 進而得到 x k 的后繼點 x k

11、+1 .重復上面的做法，直至求得問題的解.這里所謂求目標函數在直線上的極小點，稱為一維搜索或線性搜索.1.2 單峰函數定義 1.2.1 設 f 是定義在閉區間a, b上的一元實函數，x* 是 f 在a, b上的極小*點，對 x1 , x2 a, b 且 x1 f (x2) ，當 x* x 時，1f (x2 ) f (x1 ) ，則稱 f 是閉區間a, b上的單峰函數.1.3 單峰函數的性質單峰函數具有很重要的性質：通過計算閉區間a, b內兩個不同點處的函數 值，就能確定一個包含極小點的子區間.這也是斐波那契法的理論基礎.為了后面分析的方便，先證明下面的定理，這個定理是斐波那契方法的理論 基礎.

12、定理 1.3.1 設 f 是閉區間 a, b 上的單峰函數， x1 , x2 a, b ，且 x1 f (x2 ) ， 則 對 x a, x1 ， 有f (x) f (x2 ) ； 如 果f (x1 ) f (x2 ) ， 則 對x x2 , b，有 f (x) f (x1 ) .證明：（反證法）先證第一種情形.假設當 f (x1 ) f (x2 ) 時， ，使得f () f (x2) .(1.3.1.1)顯然 x1 不是極小點.這時有兩種可能性，要么極小點 x a, x1 )，要么 x (x1 , b .當 a, x1 )時，根據單峰函數的定義，有f (x2 ) f (x1 ) .(1.3.

13、1.2)這與假設矛盾.當 (x1 , b時，根據單峰函數的定義，有f () f (x ) .1(1.3.1.3)由于假設 f (x1 ) f (x2 ) ，因此(1.3.1.3)式與(1.3.1.1)式相矛盾.綜上可知，當f (x1 ) f (x2 ) 時，對x a, x1 ，必有f (x) f (x2 ) .(1.3.1.4)同理可以證明第二種情形.*證畢. 根據上面的定理知：只需選擇兩個試探點，就可以將包含極小點的區間縮短.事實上，如果 f (x1 ) f (x2 ) ，則 x x1 , b ；如果 f (x1 ) f (x2) ，則 x* a, x .2這就是斐波那契法的理論基礎. 2.

14、 斐波那契法分析斐波那契法的一維搜索過程是建立在一個被稱為斐波那契數列的基礎上進 行的.在此之前，有必要知道區間縮短率以及斐波那契數列的概念.2.1 區間縮短率定義 2.1.1 在逐次縮短區間時，設 稱tk (k = 1,2, ) 為區間縮短率.對于上面的tk 不外乎兩種情況，要么tk = c ，要么tk c ( c 為常數).第一種情況就可以引入前面提到的黃金分割法，第二種情況就是下面要分析的斐波那契 法.2.2 斐波那契數列斐波那契數列是 13 世紀,由意大利的數學家列昂納多斐波那契(Leonardo Fibonacci)提出的，當時和兔子的繁殖問題有關，它是一個很重要的數學模型. 斐波那

15、契數列，又被稱為“黃金分割數列”，它指的是這樣的一個數列：數列的 第一個和第二個數都為 1，接下來每個數都等于前面兩個數的和.在數學上，斐波那契數列有如下的遞歸定義：故，斐波那契數列如表 2.2.1 所示.表 2.2.1 斐波那契數列表n0123456789Fn11235813213455斐波那契數列的通項公式(又稱為“比內公式”)如下：此時2.3 斐波那契法原理在定義2.1.1中，若，可取.其中滿足斐波那契數列的遞推關系。斐波那契法成功地實現了單峰函數極值范圍的縮減.現設某一單峰函數在閉區間a,b上有一極小點，則在此區間內任意取兩點,使得分別計算其函數值可能出現的以下兩種情況：（1）（2）可

16、以看出，只要在閉區間a, b內任意取兩點 a1 和b1 (a1 0 ，利用下式 求出計算函數值的次數 n .并設d 0 .接著由下式 計算試探點 p1和q1 .令 k = 1 .如果 f ( pk ) 令f (qk )，轉；否則轉. 若 k = n - 2 ，則轉；否則轉.令 若 k = n - 2 ，則轉；否則轉.令 k = k + 1，轉.令 pn = pn-1 , qn = pn-1 + d，計算 f ( pn )和f (qn ) .若則令 否則令 停止計算，極小點3.2 斐波那契法的 MATLAB 程序用 MATLAB 編寫斐波那契法程序如下所示： function x,minf =

17、minFBNQ(f,a,b,delta,eps) format long;if nargin=4 %輸入參數的個數eps=1.0e-6;endF=ones(2,1); %產生一個2行1列值全為1的矩陣N=(b-a)/eps; c=F(2)-N; n=2;while cfqa=p; %第一種情況，改變區間的左端點p=q;q=a+F(n-k-1)*(b-a)/F(n-k); %縮短搜索區間if(k=n-3)break;else k=k+1;end elseb=q; %第二種情況，改變區間的右端點q=p;p=a+F(n-k-2)*(b-a)/F(n-k); %縮短搜索區間if(k=n-3)break

18、;else k=k+1;endendendif k=100000 disp(未找到最小值！);x=NaN;minf=NaN; %not a number!return;endq=p+delta; fp=subs(f,findsym(f),p); fq=subs(f,findsym(f),q); if fpfqa=p;else b=p;end x=(a+b)/2; minf=subs(f,findsym(f),x); format short;end調用格式：x, min f = min FBNQ( f , a, b, delta, eps) . 符號說明：x 目標函數取最小值時的自變量;min

19、 f 目標函數的最小值;f 目標函數;a 極值區間左端點; b 極值區間右端點; delta 算法結束參數;eps 精度;3.3 斐波那契算法舉例現在，用上面的 MATLAB 程序求解兩個一維搜索問題，并進行驗證. 問題一：試用斐波那契法求函數 f (x) = 3x 2 - 12x + 10 的極小點，要求縮短后的區 間不大于初始給定的區間1,4的 0.05 倍.解：在 MATLAB 窗口輸入如下命令 syms x; f=3*x2-12*x+10; x,minf=minFBNQ(f,1,4,0.05)運行結果為x =2.0000minf =-2.0000下面用數學分析的方法來驗證所求結果的正確

20、性：因為 f (x) = 3x 2 - 12x + 10 是二次函數，將其配方后可得 f (x) = 3(x - 2)2 - 2 .對稱軸為直線 x = 2 .由于 x = 2 1,4，拋物線的開口向上，故在頂點處取得極小值(也是最小值).頂點的縱坐標 y = -2 即為函數 f (x) = 3x 2 - 12x + 10 在區間1,4上的極小點.證畢.因此，這個結果和用 MATLAB 求解的結果是一致的.說明了斐波那契法的正確性.問題二：用斐波那契法求解下列問題min f (x) = 2x 2 - x - 1 . 初始區間為- 1,1，精度要求e 0.16 .解：在 MATLAB 窗口輸入如

21、下命令 syms x; f=2*x2-x-1; x,minf=minFBNQ(f,-1,1,0.16)運行結果為x =0.2500minf =-1.1250下面用數學分析的方法驗證所求結果的正確性：二次函數的對稱軸拋物線的開口向上故在頂點處取得最小值.頂點縱坐標為即為函數在區間-1,1上的極小點（也是最小點）.證畢所以，跟上一個問題的結論一樣，這個結果證明了斐波那契法的正確性.4. 課程設計總結4.1 概述 最優化理論與算法是一個重要的數學分支，它所研究的問題是討論在眾多的方案中什么樣的方案最優以及怎樣找出最優方案.求解最優問題是一個艱難而具 有挑戰性的過程，最優化方法涵蓋了無約束最優化問題、凸集與凸函數、等式約 束最優化問題和不等式約束最優化問題等知識點.本次課程設計的題目是：斐波那契分析與實現. 斐波那契法的一維搜索過程