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

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

3、bstractMathematical 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 .One-dimension

4、al 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 one-dimension

5、al 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 successfully achie

6、ved 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 does not ne

7、ed 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 golden section me

8、thod 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 methodunimoda

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

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

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

12、 是閉區(qū)間 a, b 上的單峰函數(shù)， 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 ) .證明：（反證法）先證第一種情形.假設(shè)當(dāng) f (x1 ) f (x2 ) 時， ，使得f () f (x2) .(1.3.1.1)顯然 x1 不是極小點.這時有兩種可能性，要么極小點 x a, x1 )，要么 x (x1 , b .當(dāng) a, x1 )時，根據(jù)單峰函數(shù)的定義，有f (x2 ) f (x1 ) .(1.3.1.2)這與假設(shè)矛盾.當(dāng)

13、 (x1 , b時，根據(jù)單峰函數(shù)的定義，有f () f (x ) .1(1.3.1.3)由于假設(shè) f (x1 ) f (x2 ) ，因此)式與)式相矛盾.綜上可知，當(dāng)f (x1 ) f (x2 ) 時，對x a, x1 ，必有f (x) f (x2 ) .(1.3.1.4)同理可以證明第二種情形.*證畢. 根據(jù)上面的定理知：只需選擇兩個試探點，就可以將包含極小點的區(qū)間縮短.事實上，如果 f (x1 ) f (x2 ) ，則 x x1 , b ；如果 f (x1 ) f (x2) ，則 x* a, x .2這就是斐波那契法的理論基礎(chǔ). 2. 斐波那契法分析斐波那契法的一維搜索過程是建立在一個被稱

14、為斐波那契數(shù)列的基礎(chǔ)上進 行的.在此之前，有必要知道區(qū)間縮短率以及斐波那契數(shù)列的概念.2.1 區(qū)間縮短率定義 2.1.1 在逐次縮短區(qū)間時，設(shè) 稱tk (k = 1,2, ) 為區(qū)間縮短率.對于上面的tk 不外乎兩種情況，要么tk = c ，要么tk c ( c 為常數(shù)).第一種情況就可以引入前面提到的黃金分割法，第二種情況就是下面要分析的斐波那契 法.2.2 斐波那契數(shù)列斐波那契數(shù)列是 13 世紀(jì),由意大利的數(shù)學(xué)家列昂納多斐波那契(Leonardo Fibonacci)提出的，當(dāng)時和兔子的繁殖問題有關(guān)，它是一個很重要的數(shù)學(xué)模型. 斐波那契數(shù)列，又被稱為“黃金分割數(shù)列”，它指的是這樣的一個數(shù)列

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

16、，利用下式 求出計算函數(shù)值的次數(shù) n .并設(shè)d 0 .接著由下式 計算試探點 p1和q1 .令 k = 1 .如果 f ( pk ) 令f (qk )，轉(zhuǎn)；否則轉(zhuǎn). 若 k = n - 2 ，則轉(zhuǎn)；否則轉(zhuǎn).令 若 k = n - 2 ，則轉(zhuǎn)；否則轉(zhuǎn).令 k = k + 1，轉(zhuǎn).令 pn = pn-1 , qn = pn-1 + d，計算 f ( pn )和f (qn ) .若則令 否則令 停止計算，極小點3.2 斐波那契法的 MATLAB 程序用 MATLAB 編寫斐波那契法程序如下所示： function x,minf = minFBNQ(f,a,b,delta,eps) format lo

17、ng;if nargin=4 %輸入?yún)?shù)的個數(shù)eps=1.0e-6;endF=ones(2,1); %產(chǎn)生一個2行1列值全為1的矩陣N=(b-a)/eps; c=F(2)-N; n=2;while cfqa=p; %第一種情況，改變區(qū)間的左端點p=q;q=a+F(n-k-1)*(b-a)/F(n-k); %縮短搜索區(qū)間if(k=n-3)break;else k=k+1;end elseb=q; %第二種情況，改變區(qū)間的右端點q=p;p=a+F(n-k-2)*(b-a)/F(n-k); %縮短搜索區(qū)間if(k=n-3)break;else k=k+1;endendendif k=100000 d

18、isp(未找到最小值！);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調(diào)用格式：x, min f = min FBNQ( f , a, b, delta, eps) . 符號說明：x 目標(biāo)函數(shù)取最小值時的自變量;min f 目標(biāo)函數(shù)的最小值;f 目標(biāo)函數(shù);a 極值區(qū)間左端點; b 極值

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

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

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