• % 寻找初始分割点 • x1=a+.382*(b-a); • x2=a+.618*(b-a);
• % 搜索主体 • while(abs(b-a)>eps) • % 计算分割点处 的函数值 • f1=fun(x1); • f2=fun(x2);
% 比较判断两个分割点处的 函数值，进而缩短区间长度 if(f1>f2) a=x1; x1=x2; x2=a+.618*(b-a); elseif(f1==f2) a=x1; b=x2; x1=a+.382*(b-a); x2=a+.618*(b-a); else b=x2; x2=x1; x1=a+.382*(b-a); end end % 返回搜索值 20 answ=(a+b)/2;
并假设
f ( x (1) ) f ( x ( 2 ) ),
f ( x ( 2 ) ) f ( x ( 3 ) ).
f ( x)
( x)
x* x (1 )
x
x ( 2)
x ( 3)
30
如何计算函数 ( x ) ?
设
( x ) a bx cx 2 ,
( x ) a bx cx
(1) (1) (1) 2
令
f ( x (1) ) f ( x( 2) ) f ( x( 3) )
( x ) a bx
( 2) ( 3)
( 2)
cx
( 2)2 ( 3)2
( x ) a bx
再求函数 ( x ) 的极小点， 解得
x b 2c
( 2 )2 ( 3 )2
k k k k

p
x
k
k
.
k
min f ( x) s.t . x R
.
一维最优化问题：
极值点的必要条件：
f '( x ) 0
5
1. 下单峰函数 定义：设 f ( x ) 是区间 [ a , b ] 上的一元函数，x 是 f ( x ) 在 [ a , b ] 上的极小点，且对任意的 x1 , x2 [ a , b ], x1 x2 , 有 （a）当 x 2 x 时，f ( x1 ) f ( x2 ); （b）当 x1 x 时，f ( x1 ) f ( x2 ) .
设 f ( x ) 在 [a1 , b1 ] 上单峰，极小点 x [a1 , b1 ]. 假设进行 第 k 次迭代前 x [ak , bk ], 取 k , k [a k , bk ], 规定 k k .
计算 f ( k ) 和 f ( k ) , 分两种情况： 1. 若 f (k ) f ( k ) , 则令 a k 1 k , bk 1 bk ; 2. 若 f ( k ) f ( k ) , 则令 a k 1 a k , bk 1 k . 如何确定 k 与 k？
(k )

( 3) 从 x (1) , x ( 2) , x ( 3)和 x 中选择 f ( x ) 的函数值最小的三个点及其
左、右两点， 重新标记为 x (1) , x ( 2 ) , x ( 3 ) 。 令 k : k 1 。 转（2） 。
(k )
32
作业
• 小结各种精确一维搜索算法
33
不精确一维线搜索
34
为什么不精确的搜索好？
• 距离最优解远的时候，精度太大 算法效率低 • 有些算法的收敛速度不依赖与搜索的精度 • 只要求有充分下降即可 这种类似与“充分”、“足够”等描述词汇， 在与计算相关的描述中，要特别在意，因为， 这里的“充分”，已经不再是理论上的要求， 这里的“充分”必须与“可计算”相关 （到底要多充分，就是这里的非精确搜索的准测） 35
( 3)
cx
解上述方程组，可得逼近函数 ( x ) 的系数b 和 c.
令
( x ) b 2cx 0,
( x x ) f ( x ) ( x x ) f ( x ) ( x x ) f ( x ( 3) ) 2 [ ( x ( 2 ) x ( 3 ) ) f ( x (1) ) ( x ( 3 ) x (1) ) f ( x ( 2 ) ) ( x (1) x ( 2 ) ) f ( x ( 3 ) ) ]
26
( 2) (4) 6. 令 h : h, x( 2) x( 4) , f ( x ) f ( x ),
转 2.
7. 令 x (3) x ( 2 ) , x( 2) x(1) , x(1) x( 4) , 停止计算。
区间 [ x (1) , x ( 3 ) ] 或[ x ( 3 ) , x (1) ] 即为包含极小点的区间。
4. 令 a k 1 a k ,
bk 1 k ,
k 1 k ,
18
k 1 a k 1 0.382(bk 1 a k 1 ), 计算 f (k 1 ), 令 k : k 1, 转 2。
• • • • •
• 一个以前很好的例子 function answ = goldsection(a,b,eps) % 黄金分割法实现一维搜索 % a ---- 搜索区间左端点 % b ---- 搜索区间右端点 % eps ---- 搜索精度
例：
x ( 0) x (1 ) x ( 2) x ( 3)
x(4) x(1) h x (1 ) x ( 2)
x ( 4) x (1 )
h : h x ( 4) x (1 )
x ( 0) x (1 ) x (1 ) x ( 2)
x ( 4) x ( 2) x ( 3)
27
极小点区间 ： [ x ( 3 ) , x ( 1) ]
ak 2 (bk ak )
如果令 2 1 ， 则uk 1 k ,因此 uk 1 不必重新计算 。
5 1 1 0.618 2 (2) 若在第k 次迭代时有f (k ) f ( k ) 。 同理可得。
2
17
算法步骤：
1. 给定初始区间 [a1 , b1 ], 精度要求 0. 令 1 a1 0.382 (b1 a1 ), 1 a1 0.618 (b1 a1 ), 并计算 f (1 ) 与 f ( 1 ). 令 k : 1.
2. 若 bk a k , 停止， 且
bk a k . 否则， 2 当 f ( k ) f ( k ) 时，转 3；当 f ( k ) f ( k ) 时，转 4. x
bk 1 bk ,
3. 令 a k 1 k ,
k 1 k ,
k 1 a k 1 0.618(bk 1 a k 1 ), 计算 f ( k 1 ), 令 k : k 1, 转 2。
15
要求其满足以下两个条 件：
1. bk k k a k
(1)
ak
k
k
bk
2. 每次迭代区间长度缩短比率相同，即 bk 1 a k 1 (bk a k ) ( 0)
( 2)
由式（ 1）与（2）可得：
k ak (1 )(bk ak ) k ak (bk ak )
( 3)
(4)
16
取值的确定？
通过确定 的取值，使上一次迭代剩余的迭代点恰与下一次 迭代的一个迭代点重合，从而减少算法的计算量。
(1) 设在第 k 次迭代时有 f ( k ) f ( uk ) , 则有
[ a k 1 , bk 1 ] [ a k , uk ]。
在第 k 1 次迭代时选取 k 1 , uk 1 , 则由（4）有 uk 1 a k 1 (bk 1 a k 1 )
• % CopyRight@XiaBo • % Date:2008.3.20
• %% 定义搜索函数fun • function f = fun(x) % 这里是一个简单的函数定义， 倘若在一个大型的优化计算中，这个函数一般是和第k 步的迭代点和下降方向有关的 • % 是一个关于步长的函数 • % x --- 待求步长值 • f = x^2-x+2; 19
令 k : k 1.
3. 若 f ( x ( 4 ) ) f ( x (1) ), 4. 令 x ( 2 ) x ( 1 ) ,
则转 4， 否则，转5.
f ( x (1) ) f ( x ( 4 ) ),
x(1) x( 4) , f ( x ( 2 ) ) f ( x (1) ), 令 h : 2h, 转 2. 5. 若 k 1, 则转 6； 否则，转7.
极小点区间： [ x ( 1) , x ( 3 ) ]
平分法 (优点和缺点都突出的方法)
能否看出 优点和缺点？
28
29
5. 抛物线插值
为什么非要是二次三项式？
思想 在极小点附近，用二次三项式 ( x ) 逼近目标函数 f ( x ),
令 ( x ) 与 f ( x ) 在三点 x (1) x ( 2 ) x ( 3 ) 处有相同的函数值，
的三点。一个方向不成功，就退回来，再沿相反方向寻找。
进退法的计算步骤（与教材的算法比较P20）
1. 给定初始点 x ( 0 ) R, 初始步长h0 0, 令 h h0 , x(1) x( 0) ,
计算 f ( x (1) ), 并令 k 0.
2. 令 x ( 4 ) x (1) h, 计算 f ( x ( 4 ) ),
黄金分割法的迭代效果：第k次后迭代后所得区间长度为
初始区间长度的 ( 5 1)k 倍 。
2
作业
21
22