9. 一维搜索-试探法6
我们要求两个试探点k 和k 满足下列条件 : (1), k 和k 到搜索区间 ak , bk 的端点等距,即 bk k k ak , (2.3)
(2), 每次迭代,搜索区间长度的缩短率相同,即 bk 1 ak 1 r (bk ak ), (2.4)
由d 0,当k充分大时, 必有d ( k ) 0, 于是由(9.1.5)
k
y ( k ) x( k ) d
(k )
(9.1.6)
9. 一维搜索-概念5
yx 令k ,则k d y x d f ( y ( k ) ) f ( x ( k ) k d ( k ) ) (9.1.7) (9.1.5)中令k 并注意到(9.1.7), 有 (9.1.8) (9.1.9) 根据M的定义,对每个k 及k 0 , 有 由于f 连续, 令k ,则由(9.1.9)得 f ( y) f ( x d ) 故 即知 f ( x d ) min f ( x d )
9. 一维搜索-试探法2
单峰函数的一个等价定义：
设f : R R,[a, b] R, 若* [a, b]，使得f ( x )在 [a, *]上严格递减, 在[*, b]上严格递增, 则称[a, b] 是函数f ( x )的单峰区间, f ( x )是[a, b]上的单峰函数.
单峰函数具有一些很有用的性质:如果f是[a,b] 上单峰函数,则可通过计算此区间内两不同点 的函数值,就能确定一个包含极小点的子区间, 从而缩小了搜索区间.
精度要求>0.计算最初两试探点1，1： 1 a1 0.382(b1 a1 )， 1 a1 0.618(b1 a1 )， 计算(1 )和 (1 ).
步2 :比较函数值.若( k ) (k ), 则转步3， 否则，( k ) (k )转步4
为进一步缩短区间.需取试探点k 1和k 1.由(2.6)
k 1 ak 1 r (bk 1 ak 1 ) =ak r( k ak )
=ak r(ak r(bk ak ) ak ), =ak r 2 (bk ak ) (2.8)
9. 一维搜索-试探法8
(2)若f ( x (1) ) f ( x (2) ), 则x [ x (2) , b], f ( x) f ( x (1) ),
9. 一维搜索-试探法4
证明:仅证(1),反证,如若不然,存在点x*[a, x(1)],使 f ( x*) f ( x (2) )
显然x (1)不是极小点此时要么极小点 . x [a, x (1) ] 要么x [ x (1) , b]. 若x [a, x ], 则f ( x ) f ( x ), 矛盾.
(1) (1) (2)
若x [ x (1) ,b], 则f ( x* ) f ( x (1) ) f ( x (2) ), 矛盾.
根据以上定理,只需选择两个点就可缩短包含极小点的 区间 : (1)若f ( x (1) ) f ( x (2) ), 则极小点x [ x (1) ,b]; (2)若f ( x (1) ) f ( x (2) ), 则极小点x [a, x (2) ].
由( 2.3ቤተ መጻሕፍቲ ባይዱ和(2.4)得到
k ak (1 r)(bk ak ) , k ak r (bk ak ),
(2.5) (2.6)
9. 一维搜索-试探法7
今考虑( 2.1)的情形,此时新的搜索区间为 [ak 1 , bk 1 ] [ak , k ] (2.7)
2 1 (2.9) 则 k 1 =ak +(1- )(bk ak ) k (2.10) 这样新的试探点k 1就不用重新计算只要取k ,于是
若令 每次迭代中(除第一次)只需取一个试探点. 类似的,如考虑(2.2)的情形,新的试探点k 1 =k , 它也不需重新计算. 解方程(2.9)立得区间长度缩短率 = -1 5 -1+ 5 由于 >0,故取 = 0.618 2 2
步5:k: k 1, 转步2。
9. 一维搜索-试探法13
2.2 Fibonacci法 Fibonacci法是与0.618法类似的一种分割方法。 它与0.618法的主要区别之一在于：搜索区间 长度的缩短率不是采用黄金分割数，而是采用 Fibonacci数： Fn 1 Fn Fn 1 , F0 F1 1, n 1,2,... Fbinacci法中计算公式为：
0
y M ( x, d )
9. 一维搜索-试探法1
•9.2.1, 0.618法
Df 9.2.1设f 是定义在闭区间[a, b] 上的一元实函数, x 是f 在[a, b]上 的极小点, 且对x (1) , x (2) [a, b], x (1) x (2) , 有 当x (2) x时f ( x (1) ) f ( x (2) ) 当x x (1)时f ( x (1) ) f ( x (2) ) 则称f 是在闭区间[a, b]上的单峰函数.
9. 一维搜索-试探法3
Th9.2.1 设f 是区间[a, b]上的单峰函数, x (1) , x (2) [a, b]. 且x (1) x (2) , 则 (1)若f ( x ) f ( x ), 则x [a, x ], f ( x) f ( x )
(1) (2) (1) (2)
步4:若 k ak , 停止计算,输出 k ; 否则,令 ak+1 : ak , bk+1 : k , k 1 : k , ( k+1 ) : ( k ), k+1 ak+1 0.382(bk+1 ak+1 )， 计算( k 1 ), 转步5
k ak (1
ak
Fn k Fn k 1
)(bk ak )
Fn k 1 Fn k 1 Fn k Fn k 1
(bk ak ), k 1,2,.., n 1 (bk ak ), k 1,2,..., n -1
k ak
9. 一维搜索-试探法14
显然, 这里Fn-k /Fn-k+1相当于0.618法(1.5)-(1.6)中的, 每次的缩短率满足 Fnk bk 1 ak 1 (bk ak ) Fnk 1
这里n时计算函数值的次数,即要求经过n次计算函数 值后, 最后区间的长度不超过 ,即 由于 bn an
注意到上述迭代算法中,当方向确定后, 涉及到求一个 步长 k , 使得目标函数值减小(极小化问题), 这就是在一 直线上求目标函数的极小点,即极小化f ( xk k d k ).这称 为 对变量的一维搜索问题,或称为线搜索.
9. 一维搜索-概念2
设目标函数为f ( x), 过点x ( k )沿方向d ( k )的直线可用点集 来表示: L {x | x x ( k ) d ( k ) ,- } 求f ( x)在直线L上的极小点就转化为求 (9.1.1) (9.1.2)
• 一维搜索算法的闭性
假设一维搜索是以x为起点,沿方向为d的进行的, 并定义为算法映射M Df 9.1.1 算法映射M : R n R n R n定义为
M ( x, d ) { y | y x d , 满足 f ( x d ) min f ( x d )}
F1 F2 F1 F2
bn an
( bn1 an1 )
Fn-1 2 F ... F3 Fn (b1 a1 ) 1 Fn
(b1 a1 )
9. 一维搜索-试探法15
故 1 b1 a1 (b1 a1 ) Fn （1.20） Fn 给出最终区间长度得的上界 ，由(1.20)求出Fibonacci数 Fn , 再跟据Fn 确定出n, 从而搜索一直进行到第n个搜索点 为止. 注意到
2
9. 一维搜索-试探法10
其几何意义:黄金分割率对应的点在单位长区间[0,1] 中的位置相当于其对称点1-在区间[0,]中的位置
ak Step 2
k
ak+l
k
bk
k+l
bk+l
k+l
Step 3
bk+l
ak+l
k+l
k+l
9. 一维搜索-试探法11
算法(0.618法) 步1:选取初始数据,确定初始搜索区间[a1 ,b1 ]和
0
(9.1.4)
9. 一维搜索-概念4
Th9.1.1 设f是定义在Rn的连续函数,d0,则(9.1.4)定 义的算法映射M在(x,d)处是闭的
证 : 设序列{x ( k ) }和{d ( k ) }满足 ( x ( k ) , d ( k ) ) ( x, d ); y ( k ) y, y ( k ) M ( x ( k ) , d ( k ) ) 下证 y M ( x, d ) , 注意到, 对每个k ,k 0 , 使 y ( k ) x ( k ) k d ( k ) (9.1.5)
9. 一维搜索-试探法5
0.618法的基本思想:通过取试探点使包含极小点的 区间(不确定区间)不断缩小,当区间长度小到一定 程度时,区间上各点的函数值均接近极小值,此时 该区间内任一点都可以作为极小点的近似值.
设 ( )是搜索区间[a1 , b1 ]上的单峰函数.设在第k次迭代时 搜索区间为[ak , bk ].取两个试探点k , k [ak , bk ], k k . 计算 (k )和 ( k ), 根据Th1 : (1), 若 (k ) ( k ), 令ak 1 ak , bk 1 k , (2), 若 (k ) ( k ), 令ak 1 k , bk 1 bk , (2.1) (2.2)