一维搜索方法__论文.doc

一维搜索方法
摘要：一维搜索方法是求解一维目标函数的极值点的数值迭代方法，可归结为单变量的函数的极小化问题。虽然优化设计中的大部分问题是多维问题，但是一维优化方法是优化方法中最基本的方法，在数值迭代过程中都要进行一维搜索，因此，对一维搜索方法的研究有着重要的意义。
关键字：一维搜索、区间消去法、黄金分割法、插值法
一．一维搜索的概念
1．当采用数学规划法寻求多元函数的极值点时，一般要进行
一系列如下格式的迭代计算：
（k=0，1，2...）
其中为第k+1次迭代的搜索方向，为沿搜索的最佳步长因子（通常也称作最佳步长）。
2．当方向给定，求最佳步长就是求一元函数的极值问题，

它称作一维搜索。
3．求多元函数极值点，需要进行一系列的一维搜索。可见一维搜索是优化搜索方法的基础。
4．求解一元函数的极小点，可采用解析解法和数值解法。
⑴ 解析解法
① 利用一元函数的极值条件，求。
② 为了直接利用的函数式求解最佳步长因子。可把或它的简写形式进行泰勒展开，取到二阶项，即

将上式对进行微分并令其等于零，给出极值点应满足的条件

从而求得

这里是直接利用函数而不需要把它化成步长因子的函数不过，
此时需要计算点处的梯度和海赛矩阵G。
该方法的缺点是需要进行求导计算，对于函数关系复杂、求导困难或无法
导的情况，使用解析法将是非常不便的。
因此，在优化设计中，求解最佳步长因子主要采用数值解法，利用计算通过反复迭代计算求得最佳因子的近似值。
⑵数值解法
其基本思路是：首先确定所在的搜索区间，然后根据区间消去法原
理不断缩小此区间，从而获得数值近似解。
二．搜索区间的确定与区间消去法原理
1. 确定搜索区间的外推法
⑴ 单谷（峰）区间
在给定区间内仅有一个谷值（或有唯一的极小点）的函数称为单谷函数，
区间称为单谷区间。
①函数值：“大—小—大”
②图形：“高—低—高”
③单谷区间中一定能求得一个极小点。
说明：单谷区间内，函数可以有不可微点，也可以是不连续函数，单谷区间
函数图所图1所示。

图1 谷区间函数图
⑵ 外推方法
基本思想：对任选一个初始点a1及初始步长h，通过比较这两点函数值的大小，确定第三点位置，比较这三点的函数值大小，确定是否为“高—低—高”形态。如图2所示。
步骤：
①选定初始点a1，初始步长h=h0，计算y1=f(a1)和y2=f(a1+h)
②比较y1和y2；
a) 如果y1>y2，向右前进，加大步长h=2h0，转（3）向前；
b) 如果y1<y2，向左后退， h=-2h0，将a1和a2,y1和y2的值互换。转（3）
向后探测；
c) 如果y1=y2，极小点在a1和a1+h之间。
③ 产生新的探测点a3=a2+h，y3=f(a3)；
④ 比较函数值y2和y3：
a）如果y2>y3 ，加大步长h=2h，a1=a2,a2=a3,转（3）继续探测；
b）如果y2<y3，则初始区间得到：a=min[a1,a3],b=max[a1,a3]，函数最小
所在区间为[a,b]。

图2 外推法图
⑶下表显示外推法进行的步骤：
①前进搜索步骤表

②后退搜索步骤表

⑷ 搜索区间外推法程序框图

2.区间消去法原理
基本思想：
⑴搜索区间确定之后，采用区间消去法逐步缩短搜索区间，从而找到极小
的数值近似解。
⑵在搜索区间[a,b]内任取两点a1，b1且a1<b1计算其函数值得如下结论：
① 极小点必在区间[a,b1]
② 则取为[a1,b]缩短后的搜索区间。
③ 缩小的新区间为必在[a,b1]
④ 缩小的新区间为必在[a1,b]
3．一维搜索方法分类
根据插入点位置的确定方法，可以把一维搜索法分成两大类：
⑴试探法：即按照某种规律来确定区间内插入点的位置，如黄金分割法，
波纳契法等。
裴波纳契数列：1、1、2、3、5、8、13、21、34、55、89、144
⑵插值法（函数逼近法）：通过构造插值函数来逼近原函数，用插值函数的极小点作为区间的插入点，如二次插值法，三次插值法等。
三.一维搜索的试探方法——黄金分割法
1、前提
函数在区间[a,b]上是单谷函数。
2、点的插入原则
⑴要求插入点, 的位置相对于区间[a,b]两端点具有对称性.

⑵要求保留下来的区间内再插入一点所形成的新三段具有相同的比例分布。
3、点位置的确定方法

⑴两内分点值

⑵结论：所谓黄金分割是指将一线段分成两段的方法，使整段长与较长段的
长度比值等于较长段与较短段长度的比值即。
4、黄金分割法的搜索过程
（1）给出初始搜索区间[a,b]及收敛精度，将赋以0.618。
（2）按坐标点计算公式计算并计算其对应的函数值
（3）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。
（4）检查区间是否缩短到足够小和函数值收敛到足够近，如果条件不满足返
回到步骤（2）。
（5）如果条件满足，则取最后两试验点的平均值作为极小点的数值近似解。
（6）缩短区间的总次数（迭代次数）:

5、黄金分割法程序框图

四．一维搜索的插值方法
在某一确定的区间内寻求函数的极小点位置，虽然没有函数表达式，但能够给出若干点处的函数值。可以根据这些点处的函数值，利用插值方法建立函数的某种近似表达式，进而求出函数的极小点，并用它作为原来函数极小点的最小值，
这种方法称作插值方法，又叫函数逼近法。
1.牛顿法（切线法）
对于一维搜索函数，假定已经给出极小点的一个较好的近似点，
在点附近用一个二次函数来逼近函数

然后以该二次函数的极小点作为 极小点的一个新的近似点。根
据极值必要条件：

牛顿法的计算步骤：
① 给定初始点，控制误差，并令k=0
② 计算
③ 求
④ 若，则求得近似解，停止计算，否则作⑤。
⑤ 令k=k+1，转②。
例题 给定，试用牛顿法求其极小点
解：①给定初始点，控制误差=0.001
②

③
④
重复上边的过程，进行迭代，直到为止。可得到计算结果如下表所示:

K
值
0
1
2
3
4
ak
3
5.16667
4.33474
4.0396
4.00066
f'(ak)
-52
153.35183
32.30199
3.38299
0.00551
f"(ak)
-24
184.33332
109.44586
86.86992
84.04720
ak+1
5.16667
4.33474
4.03960
4.00066
4.00059

牛顿法的特点：
⑴优点：收敛速度快。
⑵缺点：每一点都要进行二阶导数，工作量大；
当用数值微分代替二阶导数，由于舍入误差会影响迭代速度；
要求初始点离极小点不太远，否则有可能使极小化发散或收敛到非极小点。
2、二次插值法（抛物线法）
基本思想：利用目标函数在不同点的函数值构成一个与原函数相近似的二次多项式，以函数的极值点（即的根）作为目标函数 的近似极值点，如下图所示。

⑴二次插值多项式的构成及其极值点
设在单谷区间中的三点 的相应函数值，则可以做出如下的二次插值多项式：

多项式的极值点可从极值的必要条件求得

同理：可由以下等式求得。

结论：
如果区间长度 足够小，则由
便得出我们所要求的近似极小点
如果不满足，必须缩小区间 ，根据区间消去法原理不断缩小区间。
⑵二次插值法程序框图

五．运用MATLAB求解一维搜索数值问题举例
用进退法确定函数的一优化搜索区间[a,b]。设初始点x=0,初始步长h=0。
MATLAB程序：
⑴ 首先你的建立三个M函数文件
① %typbound.m;
function [lowbound,upbound]=typbound(x0,step0,startopint,searchdirection)
step=step0;
f0=tryobjfun(x0,startopint,searchdirection);
x1=x0+step0;
f1=tryobjfun(x1,startopint,searchdirection);
if f1<=f0
while true
step=2*step;
x2=x1+step;
f2=tryobjfun(x2,startopint,searchdirection);
if f1<=f2
lowbound=x0;
upbound=x2;
break;
else
x0=x1;
x1=x2;
f0=f1;
f1=f2;
end
end
else
while true
step=2*step;
x2=x0-step;
f2=tryobjfun(x2,startopint,searchdirection);
if f0<=f2
lowbound=x2;
upbound=x1;
break;
else
x1=x0;
x0=x2;
f1=f0;
f0=f2;
end
end
end
② %tryobjfun.m
function f=tryobjfun(a,startopint,searchdirection)
f=objfun(startopint+a.*searchdirection);
③%确定函数，也就是你要确定搜索区间的目标函数
function f=objfun(x)
f=x(1)^3+x(2)^2-10*x(1)*x(2)+1;
⑵在命令窗口调用建立的函数
%0是初始探测点，0.01是初始探测步长，[0,0]是初始搜索点，[1,1]是方向
>>[low,up]=typbound(0,0.01,[0,0],[1,1])
运行结果：
low =
2.550000000000000
up =
10.230000000000000

参考文献
[1] 李万祥.工程优化设计与MATLAB实现[M].北京：清华大学出版社，2010.2
[2] 孙靖民.机械优化设计[M].北京：机械工业出版社，1998
[3] 吴祈宗.运筹学与最优化matlab编程[M].北京：机械工业出版社，2009.
[4] 李元科.工程最优化设计[M]. 北京：清华大学出版社，2006