最优化方法课程设计斐波那契法分析与实现完整版

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 概述 最优化理论与算法是一个重要的数学分支，它所研究的问题是讨论在众多的方案中什么样的方案最优以及怎样找出最优方案.求解最优问题是一个艰难而具 有挑战性的过程，最优化方法涵盖了无约束最优化问题、凸集与凸函数、等式约 束最优化问题和不等式约束最优化问题等知识点.本次课程设计的题目是：斐波那契分析与实现. 斐波那契法的一维搜索过程