3一维优化方法

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
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)
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个等分 点的目标函数值. 再通过比较,找出其中的最小点，则该 点的两个邻近点围成缩短了的新区间。
否
y1≥y2
是
h=2h
x1 x2 x3
x
x1 x2 x3
前进计算
f
x1=x2 y1=y2 x2=x3 y2=y3
a=x3、b=x1
x3=x2+h、y3=f(x3)
是 y2≥y3
否是
否
h>0
a=x1、b=x3
x1 x2 x
x3 x2 x1 x3 x2 x1
后退计算
结束
2020/11/27
6
3 1.用进退法确定函数f (x) 3x3 8x 9的一维优化初始区间,给定 初始点x1 0, 初始进退距h0 0.1.
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
是
x 0.5(a b)
止
f f (x)
* 也可采用迭代次数是否大 于或等于 k 作终止准则。
y1 y2 x a x1 x2 b
x1 x2 b
y1 y2
x
a x1 x2 b
a x1 x2
2020/11/27
14
§3-5 二次插值法
一）基本思路
用三点二次插值多项式来逼近原函数。
Ⅰ
Ⅱ
原函数
f1
f2
x3=xp f3=fp
输出
二次插值法缩小区间流程图
2020/11/27
17
四）终止判别条件
采用点距准则（前后两个插值点的距离不 超过误差限）：
xp x p0
• 第一次迭代不能判别，且要设置一单元
x
p
0
存放前次所得的
x
p
。
2020/11/27
18
五）迭代步骤
给定 x1、x3、ε f1=f(x1)，f3=f(x3), x2=0.5(x1+x3)，f2=f(x2)
F* 2
2020/11/27
3
Байду номын сангаас 三）一维搜索的步骤
1)确定一个包含最优点的初始搜索区间
特点：高--低--高
f
2)将含最优点的区间不断缩小
o
a
bx
当该区间的长度小于预先给定的一个很小的正数 ，
则可认为该区间中的某点(如中点)是最优点。
* 区间缩短率：
新区间长度
原区间长度
2020/11/27
4
§3-2 确定初始搜索区间的进退算法
第三章 一维搜索方法
1）确定初始搜索区间的进退算法； 2）格点法； 3）黄金分割法； 4）二次插值法； 5）三次两点插值法。
2020/11/27
1
§3-1 问题的提出
一）一维问题是多维问题的基础 X (k1) X (k) S (k)
* X (在k) 上次迭代中已求得， S (由k) 某种逻辑方式（如负梯度方向、共轭方
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)
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
一）基本思路
—试探后作前进或后退计算。
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)
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)
x1, x2, xP , x3
x4=0.5(x1+x2)
f4=f(x4)
否
x1, x4 , x2 , x3
是
f4>f2
否 x1=xp
x1=x4 f1=f4
x3=x2 f3=f2 x2=x4
f1=fp
f2=f4
f2>fp
是
x3=x2 f3=f2 x2=xp f2=fp
f2<fp
否 是
x1=x2 f1=f2 x2=xp f2=fp
解：
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
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
f
a
2020/11/27
xmx1 m xm1 b
x
9
二）每轮迭代区间的缩短率
2
n 1
三）特点
1）思路简单，编程容易，宜于离散型优化问题； 2）计算量大，不宜用于高维优化问题。
2020/11/27
10
§3-4 黄 金 分 割 法
一）基本思路
将区间按一定的比例缩小，且正常迭代时 每缩短一次区间只需计算一次函数值。
计算 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 )
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
K=K+1
xp0=xp
K=0
A=f1(x2-x3)+f2(x3-x1)+f3(x1-x2)
否
是
计算xp，fp
A=0
(xp-x1)(x3-xp)≤0
缩短区间
否
否
是
K>0
否
xp-xp0 ≤ε
是
x*=x2, f*=f2
是
x*=xp,f*=fp
xp
1 2
f1(x22 x32 ) f2 (x32 x12 ) f3(x12 x22 ) f1(x2 x3) f2 (x3 x1) f3(x1 x2 )
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
二）插值多项式
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,ε
求出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
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
向等）给定，每次迭代可归结为以 为变量的一维问题。
如： F(X ) x12 x22 8x1 12x2 52
当
X (0) 0 0T , S(0) 1 1T
X
0 0
1 1
则 F x12 x22 8x1 12x2 52 22 20 52
2020/11/27
2
二） 的确定方法
结束
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