一维搜索方法.ppt

当方向给定,求最佳步长就是求一元函数:
的极值问题,这一过程被称为一维搜索.
一维搜索方法分类:
(a) 试探法; (b)插值法
一维搜索方法
当采用数学规划法寻求多元函数的极值点时,一般要进行一系列如下格式的迭代计算:
1
一维搜索的基本思想
O
f
(
a
)
b
x
*
x
a
(峰)区间
在给定区间内仅有一个谷值的函数称为单谷数,其区间称为单谷区间。
2. 找初始单谷区间是一维搜索的第一步.
第二步使区间缩小。
单谷区间中一定能求得一个极小点
函数值:“大-小-大”
图形:“高—低—高”
2
(1)选定初始点a, 初始步长h=h0,计算 y1=f(a1),
y2=f(a1+h)。
(2)比较y1和y2。(a)如y1>y2, 向右前进;加大步长 h=2 h ,转(3)向前。(b)如y1<y2, 向左后退;h=- h0,转(3)向后探测。
(c)如y1=y2,极小点在a1和a1+h之间。
基本思想:
对f(x)任选一个初始点a1及初始步长h, 通过比较这两点函数值的大小,确定第三点位置,比较这三点的函数值大小,确定是否为“高—低—高”形态。
确定初始单谷区间的进退法
步骤:
3
(3)产生新的探测点a3=a1+h,y3=f(a3);
(4)比较函数值 y2与y3:
(a)如y2<y3, 则初始区间得到;
h>0时,[a,b]=[a1,a3];
h<0时,[a,b]=[a3,a1];
(b)如y2>y3, 加大步长 h=2 h ,a1=a2, a2=a3,转(3)继续探测。
4
y1
y3→y2
y2→y1
a3→a2
a2→a1
a1
O
a
a3
h0
h0
2h0
y1←y2
a2←a3
a1←a2←a1
O
a
a3
2h0
h0
h0
y3
y1←y2←y1
y2←y3
a1←a2
确定初始单谷区间进退法示意图
5
f(a1)
f(b1)
f(a1)
f(b1)
f(a1)
f(b1)
a1
a1
a1
b1
b
a
a
b
a
b
b1
b1
f1=f(a1), f2=f(b1)
搜索区间确定之后,采用区间消去法逐步缩短搜索区间,从而找到极小点的数值近似解。
假定在搜索区间内[a,b] 任取两点a1,b1;
区间消去法原理
6
f(a1)
f(b1)
f(a1)
f(b1)
f(a1)
f(b1)
a1
a1
a1
b1
b
a
a
b
a
b
b1
b1
综合为两种情况:
①若则取为缩短后的搜索区间。
②若则取为缩短后的搜索区间。
f1=f(a1), f2=f(b1)
(1)如f1<f2, 则缩小的新区间为[a,b1];
(2)如f1>f2, 则缩小的新区间为[a1,b];
(3)如f1=f2, 则缩小的新区间为[a1,b1]
7
黄金分割法适用于[a,b]区间上的任何单谷函数求极小值问题。对函数除要求“单谷”外不作其他要求,甚至可以不连续。因此,这种方法的适应面相当广。
黄金分割法也是建立在区间消去法原理基础上的试探方法。
在搜索区间内[a,b]适当插入两点,将区间分成三段;
利用区间消去法,使搜索区间缩小,通过迭代计算,使搜索区间无限缩小,从而得到极小点的数值近似解。
黄金分割法
8
将区间分成三段
黄金分割法还要求在保留下来的区间内再插入一点所形成的区间新三段,与原来区间的三段具有相同的比例分布。
9
f(a1)
f(a2)
f(a1)
f(a2)
a1
a1
a2
a
b
a
b
a2
黄金分割法要求插入两点:
黄金分割法区间消去示意:
10