改进的黄金分割法

《改进的黄金分割法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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

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

3、面介绍两种利用函数的凸性优化黄金分割的方法。利用凸函数的一阶特征改进算法。通过凸函数的一阶特征，定理1.3.11[5]：设S⊂Rn为非空开凸集，f是定义在S上的可微函数，则f为凸函数的充分必要条件是：f(y)≥f(x)+∇f(x)T(y−x),∀x,y∈S（1）证明：必要性设f是凸函数，于是对所有α，0≤α≤1，有f(αy+(1−α)x≤αf(y)+(1−α)f(x)因此，对于0<α≤1，f(x+α(y−x))−f(x)≤f(y)−f(x)α6令α→0，得∇f(x)T(y−x)≤f(y)−f(x)充分性假设（1）成立，任取x1

4、,x2∈S，0≤α≤1。令x=αx1+(1−α)x2，我们有f(x1)≥f(x)+∇f(x)T(x1−x),f(x2)≥f(x)+∇f(x)T(x2−x)于是得到：αf(x1)+(1−α)f(x2)≥f(x)+∇f(x)T[αx1+(1−α)x2−x]=f(αx1+(1−α)x2)所以f(x)是凸函数。这个定理表明了根据局部导数的线性近似是函数的低估，即凸函数图形位于图形上任一点切线的上方。根据这个定理，所以函数的最小值一定在切线的上方。利用凸函数的一阶特征以及已知的最小函数值就可以确定不确定区间。函数两个端点处的切线和最小函

5、数值的交点，即为缩小的不确定区间。【实验环境】Windowsxp,matlab2007二、实验内容：【实验方案】该算法的基本思想是：已知函数f(x)在区间端点l,u两点的函数值f(l),f(u)，并比较两点函数值的大小，如果f(l)≤f(u)，最小值点为x=u−0.618(u−l)。否则，就取x=l+0.618(u−l)，并给该点的函数赋值f(x)；下一步求出函数在l,u两点处的切线函数；最小函数f(x)与两切线的交点l′,u′，即是新的迭代区间[l,u]。由定理1.3.11，我们知道函数值一定在切线的上方，所以最小值也在新的

6、迭代区间内，如图1所示：6【实验过程】（实验步骤、记录、数据、分析）Step0:确定，l,u。Step1；函数在l,u两点处赋值f(l),f(u)；Step2:比较f(l),f(u)两点函数值的大小，如果f(l)≤f(u)，x=u−0.618(u−l)，否则：x=l+0.618(u−l)，并给x点赋值f(x)；Step3:计算出f在l,u点的切线方程tl,tu；Step4:函数f(x)与直线tl,tu的交点l′,u′，即是新的迭代区间[l,u]Step5:循环，直到满足精度要求【实验结论】（结果）数值检验及结果分析对改进的黄金

7、分割法，我们使用matlab2007进行了数值试验选用了以下数学函数：检验函数多项式函数：，其中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表示最优解，迭代步数和最优值。表中列出黄金分割法与算法2.1的结果，所有算法均使用如下终止条件：jd=10^(−4)，迭代区间为[−10,10]。6算法函数黄金分割法改进你的黄金分割法citavalueitavalue1271.999982.6897e-10181.999952.18

8、857e-92271.999987.23451e-20431.999956.71866e-183271.999981.94587e-29671.999944.40785e-264271.999985.23381e-39921.999948.94081e-355271.9999