改进的黄金分割法

1、沙理工大 好实验报告实验项目名称 改进的黄金分割法所属课程名称最优化实验类型算法编程实验日期2015年12月25日班级学号姓名成绩一、实验概述:【实验目的】1:了解黄金分割法所存在的缺点并对它进行改进。3:熟悉应用Matlab求解无约束最优化问题的编程方法.【实验原理】黄金分割法的基本思想是：通过取试探点和进行函数值的比较，使包含极小点 的搜索区 间不断缩短，当区间长度缩短到一定程度时，区间上各点的函数值均接 近极小值，从而各点可以看作为极小点的近似；也即是，依照“去坏留好”原则， 对称原则，以及等比收缩原则来逐步缩小搜索范围。当函数是凸函数时，我们可以利用函数的凸性，得到函数值的上界和下界，

2、进 而利用这 些信息，缩短函数不确定区间，达到优化算法的效果。很多人认为黄金分割法是搜索速度最快的方法，从程序编写角度来说，黄金分 割法每次只需要插入一个点，每次只需要计算一次函数值，易于理解。就对区间 缩短率来讲，黄金分 割法的缩短率是0.618,舍弃的区间是0.382。但是，如果 一个函数是凸函数，根据已知的函数值，可以找到它的最大值和最小值，这些信 息有利于得到最优解的位置，进而大大缩减不确定区间。假设f (x)是定义在区间S上的连续的，单变量可微的凸函数，给点初始不 确定区间l,u。下面介绍两种利用函数的凸性优化黄金分割的方法。利用凸函数 的一阶特征改进算法。通过凸函数的一阶特征，定理

3、1.3.11 设S u Rn为非空开凸集，f是定义 在S上的可微函数，则f为凸函数的充分必要条件是：f ( y) N f (x) + V f (x)t ( y - x), V x, y e S(1)证明：必要性设f是凸函数，于是对所有a，0 Wa W 1，有 f (a y + (1 - a )x Wa f ( y) + (1 - a)f (x)因此，对于0 0 , l,u。Stepl；函数在l,u两点处赋值f (l),f (u)；Step2:比较 f (l), f (u)两点函数值的大小，如果 f (l) f (u) , x = u - 0.618(u - l),否 贝上x = l + 0.6

4、18(u - l)，并给x点赋值f (x)；Step3:计算出f在l,u点的切线方程tl,tu ；Step4:函数f (x)与直线tl,tu的交点l ：U，即是新的迭代区间l,uStep5:循环，直到满足精度要求【实验结论】(结果)数值检验及结果分析对改进的黄金分割法，我们使用matlab2007进行了数值试验选用了以下数学 函数：检验函数 多项式函数：f (x) = a(x-b)2c ，其中a = 0.5,1,1.5,L,9.5,10 ； b = 1,2,L,10 ； c = -5, -4,L,5数值结果见表1；表1是多项式函数检验结果，其中a, it, Value表示最优解， 迭代步数和最

5、优值。表中列出黄金分割法与算法2.1的结果，所有算法均使用如 下终止条件：jd = 10” (-4)，迭代区间为-10,10。算法 函数黄金分割法改进你的黄金分割法citavalueitavalue1271.999982.6897e-10181.999952.18857e-92271.999987.23451e-20431.999956.71866e-183271.999981.94587e-29671.999944.40785e-264271.999985.23381e-39921.999948.94081e-355271.999981.40774e-481161.999945.16563e

6、-43评价一种算法的好坏当然不仅仅只看运算速度，如果其结果所取得精度不能达到预 定的要求也是不合要求的。从表中可以看出，算法2.2可以大大减少迭代的步数，但是函 数值的精确性却不太好，算法2.1对于第二类函数可以达到满意的精度要求，并且迭代的 步数更少。【实验小结】（收获体会）本次实验通过缩短不确定区间的方法，对黄金分割法进行了尝试性的修改，对 于简单的一维问题可能看不出修改后的差别，但是在实际应用中的多维问题的求 解时，往往都会用到一维 搜索方法，如果能够针对具体的问题采用合理的方法， 则对于问题的求解应该可以节省很多计算时间。三、指导教师评语及成绩：评语评语等级优良中及格不及格1.实验报告

7、按时完成，字迹清楚,文字叙述流畅，逻辑性强2.实验方案设计合理3.实验过程（实验步骤详细,记录完整,数据合理,分析透彻）4实验结论正确.成绩：指导教师签名： 批阅日期：function x,k=GSe(a,b,epsilon)while(b-af2)x0=a+0.618*(b-a);elsex0=b-0.618*(b-a);F0=feval(fun,x0);a0=(feval(fun,x0)-feval(fun, a)+feval(dfun,a)*a)/feval(dfun,a); b0=(feval(fun,x0)-feval(fun ,b)+feval(dfun,b)*a)/feval(d

8、fun,b);a=a0;b=b0;K=k+1;function f=fun(x)%原函数f=(x-2)八2;function df=dfun(x) % 导数 df=2*x-4;function gf=gfun(x) % 切线函数k=feval(dfun,x);b=feval(fun,x)-k*x;gf=k*x+b;附录2：实验报告填写说明实验项目名称：要求与实验教学大纲一致。实验目的：目的要明确，要抓住重点，符合实验教学大纲要求。实验原理：简要说明本实验项目所涉及的理论知识。实验环境：实验用的软、硬件环境。实验方案（思路、步骤和方法等）：这是实验报告极其重要的内容。概括整个实验过程。对于验证性实验，要写明依据何种原理、操作方法进行实验，要写明需要经过哪几个步 骤来实现其操作。对于设计性和综合性实验，在上述内容基础上还应该画出流程图、设 计思路和设计方法，再配以相应的文字说明。对于创新性实验，还应注明其创新点、特 色。实验过程（实验中涉及的