f (b)
bx
p(x) A(x a)3 B(x a)2 C(x a) D p/ (x) 3A(x a)2 2B(x a) C
2020/11/27
21
三）插值多项式系数
A
(b
a)[
f
/ (b)
f / (a)] (b a)3
2[
f
(a)
f
(b)]
B
3[
f
(b)
f
(a)] (b a)[ (b a)2
解：
kh 0.1
1 0.2
x1 y1 09
x2 y2 0.1 8.203
x3 y3 0.3 6.681
2 0.4 0.1 8.203 0.3 6.681 0.7 4.429
3 0.8 0.3 6.681 0.7 4.429 1.5 7.125
可得初始搜索区间 a, b 0.3, 1.5.
2020/11/27
3A
应取“+” 号
故有
xp a B
B2 3AC a
3A
B
C B2 3AC
2020/11/27
23
五）缩短区间的方法
a
xp
b
* 1）当 f '(xp ) 0,则b xp;
2）当 f '(xp ) 0,则a xp.
六）终止准则
f / (xp )
2020/11/27
24
七）迭代步骤 输入a,b,ε
f3
x1
x
p
x2
x3
2020/11/27
15
二）二次插值曲线的极小点 插值多项式： p(x) ax2 bx c
1）求驻点 dp 2ax b 0 dx
2）求系数a和b
xp
b 2a
ax12 bx1 c f1 ax22 bx2 c f2 ax32 bx3 c f3
a f1(x2 x3) f2(x3 x1) f3(x1 x2) (x1 x2 )(x2 x3)(x3 x1) b f1(x22 x32 ) f2 (x32 x12 ) f3(x12 x22 ) (x1 x2 )(x2 x3)(x3 x1)
求出a、b后得
xp
1 2
f1(x22 x32 ) f2 (x32 x12 ) f3(x12 x22 ) f1(x2 x3) f2 (x3 x1) f3(x1 x2 )
2020/11/27
16
三）区间的缩短
输入
x1, x2 , x3
xP 否
否
xp<x2
是
xp>x2
是 x1, xP , x2, x3
f2 f1 f3 f1 这表明此时三个插值点共线。 x2 x1 x3 x1
f2
f3
f1
x1
x2
x3
ⅱ) (xP x1)(x3 xP ) 0
f1
x1
2020/11/27
f2
f3
x2 x3
20
§3-5 三次两点插值法
一）插值条件
根据两点处的目标函数值和一阶导数插值。
f
f (a) a
二）插值多项式
b xp, f (b) f (xp ), f (b) f (xp )
计算 f (x*p ), f (x*p )
否
f (x*p ) 0 是
否
f (x*p )
x xp , f f (xp )
是
结束
2020/11/27
25
2
2020/11/27
12
②关于缩小区间总次数的证明
证： 0.618 k (b a)
0.618k
ba k ln 0.618 ln
ba
即
k
ln[
ln
/(b a)] 0.618
(或k
lg[ /(b a)])
lg 0.618
2020/11/27
13
二)迭代步骤
f
给定 a,b,
x1 a 0.382 (b a), y1 f (x1)
x2 a 0.618(b a), y2 f (x2 )
是
y1 y2 否 a x1, x1 x2 , y1 y2
b x2, x2 x1, y2 y1 x1 a 0.382(b a), y1 f (x1)
x2 a 0.618(b a), y2 f (x2 )
f
否
ba
1.8 12.096
1.6 8.488
1.2 4.584
x3 y3
1.6 8.488 1.2 4.584 0.4 5.992
可得初始搜索区间 a, b 0.4, 1.6.
2020/11/27
8
§3-3 格点法
一）基本思路
先将搜索区间分成若干等分，计算出当中的n个等分 点的目标函数值. 再通过比较,找出其中的最小点，则该 点的两个邻近点围成缩短了的新区间。
一）基本思路
—试探后作前进或后退计算。
f
f
x1 x2 x3
x
x1 x2 x3
前进计算
2020/11/27
x1 x2 x
x3 x2 x1 x3 x2 x1
后退计算
5
二) 迭代步骤
给定x1、h0 h=h0
初始进退距
f
y1 y2 y3
h= -h
x3=x1 y3=y1
y1=f(x1)、x2=x1+h、y2=f(x2)
F* 2
2020/11/27
3
三）一维搜索的步骤
1)确定一个包含最优点的初始搜索区间
特点：高--低--高
f
2)将含最优点的区间不断缩小
o
a
bx
当该区间的长度小于预先给定的一个很小的正数 ，
则可认为该区间中的某点(如中点)是最优点。
* 区间缩短率：
新区间长度
原区间长度
2020/11/27
4
§3-2 确定初始搜索区间的进退算法
f
a
2020/11/27
xmx1 m xm1 b
x
9
二）每轮迭代区间的缩短率
2
n 1
三）特点
1）思路简单，编程容易，宜于离散型优化问题； 2）计算量大，不宜用于高维优化问题。
2020 金 分 割 法
一）基本思路
将区间按一定的比例缩小，且正常迭代时 每缩短一次区间只需计算一次函数值。
7
3 2.用进退法确定函数f (x) 3x3 8x 9的一维优化初始区间,给定 初始点x1 1.8, 初始进退距h0 0.1.
解：
kh
x1
y1
0.1 1.8 12.096 1
-0.2 1.9 14.377
2 -0.4 1.8 12.096
3 -0.8 1.6 8.488
x2
y2
1.9 14.377
1）取下降步长：
X (0) 0 0T , S(0) 1 1T
F x12 x22 8x1 12x2 52
2 2 20 52
--能使目标函数值下降的步长；
上例中，
F (0) 52, 取 3, 得F (1) 10 F (0) ,
故 3是下降步长.
2）取最优步长：
上例中，
令 dF 4 20 0,得 5是最优步长. d
第三章 一维搜索方法
1）确定初始搜索区间的进退算法； 2）格点法； 3）黄金分割法； 4）二次插值法； 5）三次两点插值法。
2020/11/27
1
§3-1 问题的提出
一）一维问题是多维问题的基础 X (k1) X (k) S (k)
* X (在k) 上次迭代中已求得， S (由k) 某种逻辑方式（如负梯度方向、共轭方
计算 f (a), f (b), f (a), f (b)
计算A，B，C，D
A=0
否
A>0
是 xp a C /(2B)
是 xp a (B B2 3AC ) /(3A)
否
xp a (B B2 3AC ) /(3A)
a xp, f (a) f (xp ), f (a) f (xp )
1） 0.618
2）缩短区间的总次数
k ln[ /(b a)]
ln 0.618
为预先给定的误差限。
2020/11/27
11
*①关于 0.618的证明
证：
1
l
l
f
l
(1 )l
(1 )l
2
(1 )l l
1
令 1 2 得：
2 1 0
a
x1 x2
(1 )l l
l
bx
其正根为：
5 1 0.618033988
f
/ (b)
2
f
/ (a)]
C f / (a)
D f (a)
2020/11/27
22
四）插值函数的极小点
由 p/ (x) 3A(x a)2 2B(x a) C 0
得
2B 4B2 12 AC B B2 3AC
xa
6A
3A
* 如何选取？
因有极小，其二阶导数应大于0：
p'' (x) 6 A(x a) 2B 0 xa B
结束
2020/11/27
本书认 为是由于 区间缩到 很小时因 计算机舍 入误差引 起，可取 中间点输 出。
19
ⅰ)A=0
f1(x2 x3 ) f2 (x3 x1) f3 (x1 x2 ) 0
f1[( x2 x1) (x3 x1)] f2 (x3 x1) f3(x1 x2 ) 0
x1, x2, xP , x3
x4=0.5(x1+x2)