《最优化方法》课程教学资源（题解）第二次 一维最优化

维最优化 维最优化问题 2.黄金分割法 3.进退法 4.抛物线搜索法 5.三次插值法

一 维 最 优 化 2. 黄金分割法 3. 进退法 4. 抛物线搜索法 5. 三次插值法 1. 一维最优化问题

维最优化问题 下降迭代算法中最优步长的确定 f(xx+2d)=min∫(x+M) k 维最优化问题:minf(x) st.x∈R 极值点的必要条件:f(x)=0

一. 一维最优化问题 下降迭代算法中最优步长的确定 ( ) min ( ) k k k k k f x  d f x d  + = + k . x k d . k 一维最优化问题： min f (x) s.t. x R 极值点的必要条件： f '(x) = 0

黄金分割法(0.618法) 1.单峰函数 定义:设f(x)是区间[a,b上的一元函数,x是f(x)在a,b 上的极小点,且对任意的x1,x2∈a,b,x1f(x2); b)当x≥x时,f(x1)<f(x2) 则称f(x)是单峰函数。 12

二. 黄金分割法（0.618法） 1. 单峰函数 定义：设 f (x) 是区间 [a,b] 上的一元函数， x 是 f (x) 在 [a,b] 上的极小点，且对任意的 , [ , ], , x1 x2  a b x1  x2 有 （a）当 x2  x 时， ( ) ( ); 1 x2 f x  f （b）当 x1  x 时， ( ) ( ). 1 x2 f x  f a . . b . x . . 1 x 2 x 则称 是单峰函数。 f (x) .

性质:通过计算区间[a,b内两个不同点的函数值,就可以 确定一个包含极小点的子区间。 定理设f(x)是区间|a,b上的一元函数,x是f(x)在[a,b 上的极小点。任取点cf(d,则x∈[c,b]; (2)如果∫(c)≤f(d),则x∈[a,dl。 d b

性质：通过计算区间 [a,b] 内两个不同点的函数值，就可以 确定一个包含极小点的子区间。 定理 设 是区间 [a,b] 上的一元函数， x 是 f (x) 在 [a,b] 上的极小点。任取点 f (x) cd [a,b], 则有 （1）如果 f (c)  f (d) ，则 x[c ,b]; （2）如果 f (c)  f (d), 则 x[a,d ]。 a . . b . x . . c d

2.黄金分割法 思想通过选取试探点使包含极小点的区间不断缩短, 直到区间长度小到一定程度,此时区间上各点的函数 值均接近极小值。 下面推导黄金分割法的计算公式。 设∫(x)在{a1,b1上单峰,极小点x∈{a1,b1l假设进行 第k次迭代前x∈Ia,b,取λ,Hk∈Ia,b,规定λf(),则令a1=A1,b1=b2; 2若f()≤f(4k),则令a1=an,b1=4 如何确定λ4与12

2. 黄金分割法 思想 通过选取试探点使包含极小点的区间不断缩短， 直到区间长度小到一定程度，此时区间上各点的函数 值均接近极小值。 下面推导黄金分割法的计算公式。 设 f (x) 在[a1 ,b1 ]上单峰， [ , ]. 极小点 x a1 b1 假设进行 第 k 次迭代前 [ , ], x  ak bk , [ , ], 取 k  k  ak bk 规定 . k   k ( ) ( ) , k k 计算 f  和 f  分两种情况： 1. ( ) ( ) , k k 若 f   f  , 则令 ak+1 = k ; bk+1 = bk 2. ( ) ( ) , k k 若 f   f  , 则令 ak+1 = ak . bk+1 =  k 如何确定k 与  k？

要求其满足以下两个条件: k k k k k 2.每次迭代区间长度缩短比率相同,即 b+-ak+1=a(b4-ak)(a>0) 由式(1)与(2)可得: 2+ k (1-a)(b4-ak) +a(

bk − k =  k − ak 1. 2. 每次迭代区间长度缩短比率相同，即 ( ) ( 0) bk+1 − ak+1 = bk − ak   (1) (2) 由式（1）与（2）可得：    = + − = + − − ( ) (1 )( ) k k k k k k k k a b a a b a     (3) (4) 要求其满足以下两个条件： k a k b k uk

a取值的确定? 通过确定a的取值,使上一次迭代剩余的迭代点恰与下一次 迭代的一个迭代点重合,从而减少算法的计算量。 (1)设在第k次迭代时有f(A)≤f(u),则有 k+190k+1 在第k+1次迭代时选取41,k41,则由(4有 uk=ak++abk+-akD a ta 如果令a2=1-a,则uk+1=x,因此uk+不必重新计算 5-1 c2=1-a→a ≈0.618 2 (2)若在第k次迭代时有∫(λ1)>∫(u)。同理可得

 取值的确定？ 通过确定 的取值，使上一次迭代剩余的迭代点恰与下一次 迭代的一个迭代点重合，从而减少算法的计算量。  (1) ( ) ( ) , k uk 设在第k 次迭代时有 f   f 则有 [ak+1 ,bk+1 ] = [ak ,uk ]。 1 , , 在第 k + 次迭代时选取  k+1 uk+1 则由（4）有 ( ) uk+1 = ak+1 + bk+1 − ak+1 ( ) 2 = ak + bk − ak 如果令 2 = 1−，则uk+1 = k ,因此 uk+1 不必重新计算。 0.618 2 5 1 1 2  −  = −  = (2) 若在第 k 次迭代时有 f ( k )  f (uk )。 同理可得

算法步骤 1.给定初始区间{a1,b1,精度要求E>0. 令1=a1+0.382(b-a1),=a1+0.618(b1-a1), 并计算f(4)与f(A1).令k 2.若b1-af()时,转3;当∫()≤∫()时,转4. 令a1=,b=b, Ak+=ak++0.618(bk*1-ak+1),计算∫(1),令k:=k+1,转2。 k g k+1 k+1 x1=ak++0.382(b+-ak+),计算∫(λ+),令k:=k+1,转2

算法步骤： 1. [ , ], 0. 给定初始区间 a1 b1 精度要求   令 k := 1. 0.382 ( ), 令 1 = a1 + b1 − a1 0.618 ( ), 1 = a1 + b1 − a1 ( ) ( ). 1 1 并计算 f 与 f 2. −   , 若 bk ak 停止， . 2 bk ak x + 且 = 否则， 当 f (k )  f ( k )时，转 3；当 ( ) ( )时，转 4. k k f   f  3. , 令 ak+1 = k , bk+1 = bk , k+1 =  k 0.618( ),  k+1 = ak+1 + bk+1 − ak+1 ( ), k+1 计算 f  转 2。 4. , 令 ak+1 = ak , bk+1 =  k ,  k+1 = k 0.382( ), k+1 = ak+1 + bk+1 − ak+1 ( ), k+1 计算 f  令 k := k + 1, 令 k := k + 1, 转 2

黄金分割法的迭代效果:第k次后迭代后所得区间长度为 初始区间长度的(2 其它的试探点算法: Fibonacci算法

黄金分割法的迭代效果：第k次后迭代后所得区间长度为 初始区间长度的 ) k 倍。 2 5 1 ( − 其它的试探点算法：Fibonacci算法

进退法 如何确定包含极小点的一个区间? 思想从一点出发按一定的步长,试图确定出函数值呈现“高-低-高” 的三点。一个方向不成功,就退回来,再沿相反方向寻找。 进退法的计算步骤 l.给定初始点x0)∈R,初始步长>0,令h=l,x①=x0 计算∫(x),并令k=0 2.令x{)=x(+h,计算∫(x(),令k:=k+1 3.若∫(x(4)<f(x),则转4,否则,转5 4.令x 2)X x(,f(x(2)=∫(x(),f(x)=f(x+), 令h:=2h,转2 5.若k=1,则转6;否则,转7

三．进退法 思想 从一点出发,按一定的步长, 试图确定出函数值呈现“高 - 低 - 高” 的三点。一个方向不成功，就退回来，再沿相反方向寻找。 进退法的计算步骤 1. , (0) 给定初始点 x  R 0, 初始步长 h0  , 令 h = h0 , (1) (0) x = x ( ), (1) 计算 f x 并令 k = 0. 2. , (4) (1) 令 x = x + h ( ), (4) 计算 f x 令 k := k + 1. 3. ( ) ( ), (4) (1) 若 f x  f x 则转 4， 否则，转5. 4. , (2) (1) 令 x = x , (1) (4) x = x ( ) ( ), (2) (1) f x = f x ( ) ( ), (1) (4) f x = f x 令 h:= 2h, 转 2. 如何确定包含极小点的一个区间？ 5. 若 k = 1, 则转 6； 否则，转7