当前位置:首页 >> 物理 >>

第三节一维搜索方法


第三节一维搜索方法
3.1 概述: 一维搜索方法:对任一次迭代,总是从已 知点
?
(k )

? (k )

x

出发,沿着给定的方向 s 搜索到目标函数的极小点
? x ( k ? 1)

称为一维搜索法
? ( k ?1)

由迭代公式 x
?
? ( k ?1) ? (k )

若设 x s 已知,则目标 函数 f ( x) 仅为最优步长? 的函数,即 (k ) f (x ) ? f ( x ? ? s ) ? f (? ) 对 f (? ) 求使得
?x ??
(k )

?

(k )

s

(k )

? (k )

? (k )

(k )

(k )

(k )

min f (?

(k )

) ? f (x

? (k )

? ?s

(k )

) ? min f (? ) 的最优步长?
*

(k )

? ? 的方法
*

称作一维搜索方法

2.求?
f (?
(k )

*

的基本思想及迭代公式
? (k )

(1)基本思想:通过有限次的数值迭代计算,使
) ? min



?

??

*

求最优步长 区间内,则有迭代计算

(2)迭代公式:设 ? * 在 ?? a ? b ?
k ?1 k
k ?1

公式 ? k ?1 ? ? k ? ?? k ?k ? 1,2 ?? n) 且在前后两次迭代计 算中,应保证 f (? ) ? f (? )当 ? ? ? ? ? 或 f (? ) ? f (? ) ? ? (? 1? 2为很小的正数)则停止迭代计算,且认为 ? ? ?
k 1

k ?1

k

2

*

k ?1

3.几何意义:从 x
(k )

? (k )

出发 ,沿

(k )

s

方向一维搜索,就是求

s

方向与等值线的切点此时的步长因子即为最优步长因子

常有的一维搜索方法:黄金分割法和二次分割法

3.2 函数的单峰区间及其确定 如图所示一维函数图象在 [a,e]区间有两个 局部极小点和两个局部极大点。无论求哪个极 值点,均需将原区间[a,e]划分出若干小区间,

即在区间 [a,b] [c,d]中有局部极小点而区间 [b,c] [d,e]中有局部极大点。这些子区间的共同 特点是都单峰区间。 所谓单峰区间,是指函数 在区间只有一个极值点

f(x)

a

b

c d

e

x

(1)单峰区间的确定——进退法(试探法) 确定单峰区间:目的是寻找一个包含一个有函数 极小点 x * 的区间,也是一维优化方法要解决的问题. 基本思想:欲求函数 f (x) 的单峰区间,先任选一个

初始点 x 及初始步长 h 然后进行前进或后退的试探 性搜索,找到三个点 x1 x 2 x3 其中两端点的函数值大 于中间点的函数值。即 f ( x1 ) ? f ( x2 ) ? f ( x3 ) 确定搜索区间 ?x1 x3 ? (2)进退算法步骤: 1.设有一维函数 f (x) 给定初始点 x 初始步长h.
0
0

2.令 x

1

? x0

x 2 ? x0 ? h

计算函数值

f1 ? f ( x1 )



f 2 ? f ( x2 )

3.比较 f1 和

f2

存在两种情况。
3 1

a)若 f1 > f 2 则说明极小点在的右方,应做前 进算法。于是步长加倍,第三个试点 x ? x ? 3h 计算f ? f ( x ? 3h) 比较 f , f i)若 f 2 ? f 3 则说明相邻三点的函数值形成了大—小 —大的特征;构成初始单峰区间,令 x3 ? x1 ? 3h
3 1

2

3

单峰区间即为 ?x1 , x3 ?
f (x)

0

x1

x1 ? h

x1 ? 3 h

x

ii)若
f1 ? f 2

f 2 ? f3

步长加倍继续作前进算法,即令h=2h,
x1 ? x2

f 2 ? f3

x2 ? x3

x3 ? x2 ? h

如此重复该过程,直到符合大—小—大的情况为止。

则说明极小点必在 x 1 的左方。 则作后退运算即步长改为负值,且缩短一定倍数. 如
1 4

b)若

f1 ? f 2

倍(

1

n, n??

2 h ? ?h, x ? x1 , x1 ? x2 , x2 ? x, f ? f1 ,
f1 ? f 2 f 2 ? f , x 3 ? x 2 ? h

),将x1 ,x2, f1, f2对调,令

计算

f3 ? f ( x3 )

x2

x1

1)f 2 ? f3 则初始单峰区间以找到 即?x3 , x1 ? 2) 则步长加倍继续后退 ,即令h=-2h,

继续比较 , 反复循环直到出现大—小—大情况为止

f1 ? f 2

f 2 ? f3

x1 ? x2

x2 ? x3

x3 ? x2 ? h

f 2,f3

程序框图如下:

开 始

输 入 ? , h ,h ? h
0 0

0

a 0 ? a1 a1 ? H

y1 ?

f ( a1 ) f (a 2 )

? a1

y2 ?

后 退

y 2 ? y1

h ? ?h a 3 ? a1 , y3 ? y1 前 进

a1 ? a 2 , a2 ? a3 ,

y1 ? y2 ?

y2 y3

a3 ? a 2 ? h,

y3 ?

f (a 3 )

是  
y3 ? y2



输 出
h ? 2h

a1 a 2 , a 3 y1 y 2 y3

结 束

3.3 黄金分割法(0.618法) 1、基本原理: 通过不断缩短搜索区间的长度来寻求一维函数 f (x ) 的极小点原理。

a

x1

x2

b

a

x1

x2

b

它是一种等比例缩短区间的直接搜索方法。

设目标函数 f (x) 在搜索区间 [a,b] 内 为单峰函数,区间长设为 l 在区间内按如下规则对称地取两点 x1和 x2
x1 ? a ? 0.382(b ? a) x2 ? a ? 0.618(b ? a)
f1 ? f ( x1 ) f 2 ? f ( x2 )
a x1 x2 b

计算他们的函数值

比较 f1 和 f 2 的大小有两种可能

1若

f1 ? f 2 极小点在区间 ?x1

b? 内,将 a ? x 产生 1

新区间[a b] ,区间缩短一次
x1 ? x2 f1 ? f 2 x2 ? a ? 0.618(b ? a)
x2 ? 内,将 b ? x2
f1 ? f 2 极小点在区间 ?a

2若

产生新区间 [a b] ,区间缩短一次
x2 ? x1 f 2 ? f1 x1 ? a ? 0.382(b ? a)
a x1 x2 b

3.判断新区间长度(b-a) 是否达到预先给定的
精度即
x ?
*

b?a ?? 时
1 2 ( a ? b) f
*

? f (x )
*

为近似极小点

4.若不能满足继续寻优(计算对称点)直到满足迭代精度为止。 收缩率

每次缩小所得的新区间长度与前区间长度之
比称为区间收缩率用 ? 表示。也称为缩短率,收缩率 为常数。 为加快区间收缩应保证区间收缩率不变。因此必 须在搜索区间内对称地取计算点 x1 x2 每次缩短区间都是取相等的区间收缩率即 ?1 ? ?2 ? ???

a

x1

x2

b

a

x1

x2

b

黄金分割法要求对称取点,则有 ax1 ? x2 b
由此可以看出无论删除那一段,保留区间长度相等

根据收缩率相等的原则

(1 ? ? ) L

?L

?

?L
L

则有
??

1? ?

?

? ? ? ?1 ? 0
2

??

5 ?1 2

? 0.618

所以黄金分割法有称0.618法 特点:程序结构简单容易理解可靠性好。但计算 效率偏低,使用于低维优化的一维搜索。

三、二次插值法(抛物线法)
(1)基本思想:在寻求目标函数 f (x ) 极小点的区间 内取三个点的函数值来构造一个二次插值多项式 p (x )用它的极小点近似地作为原目标函数的极小 点。若近似程度不满足精度要求时,可反复使用 此法随着区间的缩短,二次插值多项式的极小点 就逼近原目标函数的极小点一维函数 f (x ) 在搜索 区间[a b] 内为单峰函数,在区间内取三点 x1 x2 x3

三点的函数值为 f1 ? f ( x1 ) f 2 ? f ( x2 ) f 3 ? ( x3 ) 且 f ? f ? f 即满足函数值是大—小—大变化。原目 标函数曲线上的3点 ( x1 f1 ) ( x2 f 2 ) ( x3 f 3 ) 作为二次插值
? x3
3 1 2

且 x1 ? x2

多项式 p( x) ? ax ? bx ? c 的插值结点。 这里a b c为待定系数.可用下述线形方程组确定.
2

p ( x1 ) ? ax ? bx1 ? c ? f 1
2 1

p ( x 2 ) ? ax ? bx 2 ? c ? f 2
2 2

p ( x3 ) ? ax ? bx3 ? c ? f 3
2 3

解此方程组可得给定函数的表达式
a?? ( x 2 ? x1 ) f 1 ? ( x3 ? x1 ) f 2 ? ( x1 ? x 2 ) f 3 ( x1 ? x 2 )( x 2 ? x3 )( x3 ? x1 )
2 2 2 3 2 3 2 1 2 1 2 2

b? c?

( x ? x ) f1 ? ( x ? x ) f 2 ? ( x ? x ) f 3 ( x1 ? x 2 )( x 2 ? x3 )( x3 ? x1 ) ( x3 ? x 2 ) x 2 x3 ? ( x1 ? x3 ) x1 x3 f 2 ? ( x 2 ? x1 ) x1 x 2 f 3 ( x1 ? x 2 )( x 2 ? x3 )( x3 ? x1 )

p (x )的极小点 x * 2、求二次插值函数 p

插值多项式
p ( x) ? ax ? bx ? c
2

p (x )

的极小点为
x?? xp ?
*

?p ?x

? 2ax ? b ? 0

b 2a
2 2 2 2 2 2

1 ( x2 ? x3 ) f1 ? ( x3 ? x1 ) f 2 ? ( x1 ? x2 ) f3 2 ( x2 ? x3 ) f1 ? ( x3 ? x1 ) f 2 ? ( x1 ? x2 ) f3 f 3 ? f1 x3 ? x1 ( f 2 ? f1 ) ( x2 ? x1 ) ? c1

c1 ?

c2 ? xp ?
*

x2 ? x3 1 2 ( x1 ? x3 ?
*

c1 c2

)

f p ? f (xp )

当搜索区间满足精度要求时 x ? x ? ? x 而可能看作是 f (x) 在区间 [a b]上的近似最优点
2 * p * p

3、计算步骤 ⅰ确定初始搜索区间[a b] 和精度?(这里可以采 用进退法确定一个很小的插值区间 ?a b) ⅱ在区间内取三点 x x x
1 2 3

x1 ? a

x3 ? b

x2 ?

1 2

( x1 ? x3 )

计算函数值
f1 ? f ( x1 ) f 2 ? f ( x2 )
* p

f 3 ? f ( x3 )

ⅲ插值计算 x

(a)若分母为零即
f 2 ? f1 x 2 ? x1 ? f 3 ? f1 x3 ? x1

( x2 ? x3 ) f1 ? ( x3 ? x1 ) f 2 ? ( x1 ? x2 ) f 3 ? 0
1 1

则说明三个插值点 ( x , f )
x2
* p

( x2 , f 2 )

即 ( x , f )在同一
3 3

条直线上,此时可取中间插值点 其对应的函数值为近似极小值 (b)若( x ? x1 )( x3 ? x ) ? 0时,说明
* p * p

为近似 x

* p

f (x )

x

* p

已在区间之外。这种

情况只有当区间已缩小的很小和三个插值点十分 接近时,由于计算机的舍入误差才可能性。因而 可把 x 2 及其对应的目标函数的 f ? f ( x )
2 2

作为最优解输出 x ? x 2
*

f

*

? f (x2 )

④判断是否满足要求 说明搜索区间足够小 f ( x ) ? f 时输出目标函数最优解 x * f ( x ) p 否则 f ( x ) ? f 时输出目标函数最优解 x f ( x (a)若
* p
* p

x ? x2 ? ?
2

* p

* p

2

2

2

)

(b)若

则需比较点 x 和 x 在搜索区间的 相对位置及其对应的目标函数值的大小,以便 缩短搜索区间得到新的三点。
x p ? x2 ? ?
*

* p

2

二次插值法区间缩短的4种情况

开始

输 入 a , b,? a ? ? , b ? ? , 0 . 5 ?? ? ?
1 3 1 1 1 2 2 3 3

?? ?

2

y ? f (? ), y ? f (? ), y ? f (? )
3

C1 ?

y 3 ? y1 a 3 ? a1 ( y 2 ? y1 a 2 ? a1 ? C1 ) (a 2 ? a3 )

C2 ?

a p ? 0 .5 ( a 1 ? a 2 ? y P ? f (a p )

C1 C2

)



y2 ? y p y2

??




y2 ? y p





(a p ? a 2 )h ? 0



a ? a2 ,
*

y ? y2
*

a ? ap,
*

y ? yp
*

y2 ? y p
是 否 是

y2 ? y p


结束

a1 ? a 2 , y1 ? y 2 a1 ? a p , y1 ? y p

a3 ? a p y3 ? y p

a1 ? a y1 ? y

p

a3 ? a2 , y3 ? y2 a2 ? a p , y2 ? y p

p


赞助商链接
相关文章:
更多相关标签: