文档介绍：§3-1 引言
当采用数学规划法寻求多元函数的极值点时,一般要进行一系列如下格式的迭代计算:
当方向给定,求最佳步长就是求一元函数:
的极值问题,这一过程被称为一维搜索.
一维搜索也称直线搜索。这种方法不仅对于解决一维最优化本身具有实际意义,而且也是解多维最优化问题的重要支柱。(搜索步长求解)
一维搜索方法解析法高等数学已学过,即利用一维函数的极值条件:
一维搜索方法数值解法使讲解的重点!
一维搜索方法数值解法分类
1、单谷(峰)区间
在给定区间内仅有一个谷值的函数称为单谷数,其区间称为单谷区间。
§3-2 确定最优解所在区间的进退法
一、一维搜索的基本思想
O
f
(
a
)
b
x
*
x
a
函数值:“大-小-大”
图形:“高—低—高”
单谷区间中一定能求得一个极小点
2. 找初始单谷区间是一维搜索的第一步;
第二步使区间缩小。
二、确定初始单谷区间的进退法
基本思想:
对f(x)任选一个初始点a1及初始步长h, 通过比较这两点函数值的大小,确定第三点位置,比较这三点的函数值大小,确定是否为“高—低—高”形态。
步骤:
(1)选定初始点a1, 初始步长h=h0 > 0,计算 y1=f(a1),
y2=f(a1+h)。
(2)比较y1和y2。
(a)如y1>y2, 向右前进;加大步长 h=2 h ,转(3)向前;
(b)如y1<y2, 向左后退;h=- h0, 将a1与a2,y1与y2的
值互换。转(3)向后探测;
(c)如y1=y2,极小点在a1和a1+h之间。
(3)产生新的探测点a3=a2+h,y3=f(a3);
(4) 比较函数值 y2与y3:
(b)如y2>y3, 加大步长 h=2 h(也可不变) ,
a1=a2, a2=a3, 转(3)继续探测。
(a)如y2<y3, 则初始区间得到:
a=min[a1,a3], b=max[a3,a1],函数最小值所在的区间为[a, b] 。
确定初始单谷区间进退法示意图
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
进退法程序框图
搜索区间确定之后,采用区间消去法逐步缩短搜索区间,从而找到极小点的数值近似解。
假定在搜索区间内[a,b] 任取两点a1,b1;
f1=f(a1), f2=f(b1)
§3-3 一维搜索的区间消去方法
一、基本思想
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]
f(a1)
f(b1)
f(a1)
f(b1)
f(a1)
f(b1)
a1
a1
a1
b1
b
a
a
b
a
b
b1
b1
综合为两种情况:
①若则取为缩短后的搜索区间。
②若则取为缩短后的搜索区间。
一些照片: