实 验 报 告
实验项目名称 改进的黄金分割法
所属课程名称 最优化
实 验 类 型 算法编程
实 验 日 期 2015年 12月 25日
班 级
学 号
姓 名
成 绩
1
一、实验概述：
【实验目的】
1：了解黄金分割法所存在的缺点并对它进行改进。
3：熟悉应用 Matlab求解无约束最优化问题的编程方法.
【实验原理】
黄金分割法的基本思想是：通过取试探点和进行函数值的比较,使包含极小
点的搜索区 间不断缩短,当区间长度缩短到一定程度时,区间上各点的函数值均
接近极小值,从而各点可 以看作为极小点的近似；也即是，依照“去坏留好”原
则，对称原则，以及等比收缩原则来逐 步缩小搜索范围。
当函数是凸函数时，我们可以利用函数的凸性,得到函数值的上界和下界，进
而利用这 些信息，缩短函数不确定区间，达到优化算法的效果。
很多人认为黄金分割法是搜索速度最快的方法，从程序编写角度来说，黄金分
割法每次 只需要插入一个点，每次只需要计算一次函数值，易于理解。就对区间
缩短率来讲，黄金分 割法的缩短率是 ，舍弃的区间是 。但是，如果
一个函数是凸函数，根据已知的函数值，可以找到它的最大值和最小值，这 些信
息有利于得到最优解的位置，进而大大缩减不确定区间。
假设 f (x) 是定义在区间 S 上的连续的，单变量可微的凸函数，给点初始
不确定区间[l,u] 。下面介绍两种利用函数的凸性优化黄金分割的方法。利用凸
2
函数的一阶特征改进算法。
通过凸函数的一阶特征，定理 [5]：设 S ∀ R n 为非空开凸集， 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)
α
令α → 0 ，得 ∀f (x)T ( y ∀ x) ≤ f ( y) ∀ f (x)
充分性假设（1）成立，任取 x1 , 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) 是凸函数。这个定理表明了根据局部导数的线性近似是函数的低
估，即凸函数图形位于图形上任一 点切线的上方。
根据这个定理，所以函数的最小值一定在切线的上方。利用凸函数的一阶特征
以及已知 的最小函数值就可以确定不确定区间。函数两个端点处的切线和最小函
数值的交点，即为缩 小的不确定区间。
3
【实验环境】
Windows xp,matlab 2007
二、实验内容：
【实验方案】
该算法的基本思想是：已知函数 f (x) 在区间端点 l,u 两点的函数值 f
(l), f (u) ，并比 较两点函数值的大小，如果 f (l) ≤ f (u) ，最小值点为
x = u ∀ (u ∀ l) 。否则，就取 x = l + (u ∀ l) ，并给该点的函数
赋值 f (x) ；下一步求出函数在 l,u 两点处的切线函 数；最小函数 f (x) 与
两切线的交点 l ′,u′ ，即是新的迭代区间[l,u] 。由定理 ，我们知
道函数值一定在切线的上方，所以最小值也在新的迭代区间内，如图 1 所示：
4
【实验过程】（实验步骤、记录、数据、分析）
Step0: 确定 ，l,u。0∀∀
Step1；函数在 l,u 两点处赋值 f (l), f (u) ；
Step2: 比较 f (l), f (u) 两点函数值的大小，如果 f (l) ≤ f (u) ， x = u ∀
(u ∀ l) ， 否则： x = l + (u ∀ l) ，并给 x 点赋值 f (x) ；
Step3: 计算出 f 在 l,u 点的切线方程 tl,tu ；
Step4: 函数 f (x) 与直线 tl,tu 的交点 l ′,u′ ，即是新的迭代区间[l,u]
Step5: 循环，直到满足精度要求
5
【实验结论】（结果）
数值检验及结果分析
对改进的黄金分割法，我们使用 matlab2007进行了数值试验选用了以下数
学函数：
检验函数 多项式函数： ，其中cbxaxf 2)()( ∀∀
a = ,1,,L,,10 ； b = 1,2,L,10 ； c = ∀5,∀4,L,5
数值结果见表 1；表 1是多项式函数检验结果，其中 a, it, Value 表示最优解，
迭代步数和最优值。表中列出黄金分割法与算法 的结 果，所有算法均使用如
下终止条件： jd = 10^ (∀4) ，迭代区间为[∀10,10] 。
算法
函数
黄金分割法 改进你的黄金分割法
c it a value it a value
1 27
-10
18 -9
2 27 -20 43 -18
3 27 -29 67 -26
4 27 -39 92 -35
5 27 -48 116 -43
评价一种算法的好坏当然不仅仅只看运算速度，如果其结果所取得精度不能达到
预
定的 要求也是不合要求的。从表中可以看出，算法 可以大大减少迭代的步数，但是函
数值的 精确性却不太好，算法 对于第二类函数可以达到满意的精度要求，并且迭代的
步数更少。
6
【实验小结】（收获体会）
本次实验通过缩短不确定区间的方法，对黄金分割法进行了尝试性的修改，对
于简单的一维 问题可能看不出修改后的差别，但是在实际应用中的多维问题的求
解时，往往都会用到一维 搜索方法，如果能够针对具体的问题采用合理的方法，
则对于问题的求解应该可以节省很多 计算时间。
三、指导教师评语及成绩：
评语等级
评 语
优 良 中
及
格
不及格
1.实验报告按时完成,字迹清楚,文字叙述流畅,逻辑性强
2.实验方案设计合理
3.实验过程（实验步骤详细,记录完整,数据合理,分析透
彻）
4实验结论正确.
7
成 绩：
指导教师签名：
批阅日期：
附录 1：源 程 序
function [x,k]=GSe(a,b,epsilon)
while(b-a<epsilon)
K=0
f1=feval(fun,a);
f2=feval(fun,b);
F1=feval(gfun,a);
F2=feval(gfun,b);
if( f1>f2)
x0=a+*(b-a);
else
x0=*(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(dfun,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;
8
附录 2：实验报告填写说明
1．实验项目名称：要求与实验教学大纲一致。
2．实验目的：目的要明确，要抓住重点，符合实验教学大纲要求。
3．实验原理：简要说明本实验项目所涉及的理论知识。
4．实验环境：实验用的软、硬件环境。
5．实验方案（思路、步骤和方法等）：这是实验报告极其重要的内容。概括整个实验过
程。
对于验证性实验，要写明依据何种原理、操作方法进行实验，要写明需要经过哪几个步
骤来实现其操作。对于设计性和综合性实验，在上述内容基础上还应该画出流程图、设
计思路和设计方法，再配以相应的文字说明。对于创新性实验，还应注明其创新点、特
色。
6．实验过程（实验中涉及的记录、数据、分析）：写明具体实验方案的具体实施步骤，包
括实验过程中的记录、数据和相应的分析。
7．实验结论（结果）：根据实验过程中得到的结果，做出结论。
8．实验小结：本次实验心得体会、思考和建议。
9．指导教师评语及成绩：指导教师依据学生的实际报告内容，给出本次实验报告的评价。
