最优化一维搜索方法 ppt课件

机械优化设计
第三章
一维搜索方法
一、一维搜索的概念 二、搜索区间的确定与区间消去法原理 三、一维搜索的试探方法——黄金分割法 一维搜索的试探方法——黄金分割法 —— 四、一维搜索的插值方法
机械优化设计 一、一维搜索的概念
当采用数学规划法寻求多元函数的极值点时， 当采用数学规划法寻求多元函数的极值点时，一般要进行 一系列如下格式的迭代计算： 一系列如下格式的迭代计算：
X k +1 = X k + α k d k ( k = 0,1, 2 ⋅⋅⋅)
给定， 当方向 d k 给定，求最佳步长 α k 就是求一元函数
f ( x k +1 ) = f ( x k + α k d k ) = ϕ (α k )
的极值问题。这一过程被称为一维搜索。 的极值问题。这一过程被称为一维搜索。 一维搜索
机械优化设计
三、一维搜索的试探方法——黄金分割法 一维搜索的试探方法——黄金分割法 ——
1、前提 函数在区间 [ a, b] 上是单谷函数。 上是单谷函数。 2、点的插入原则 （1）要求插入点 α1 , α 2 的位置相对于区间[ a , b ] 两端点具有对称性。 两端点具有对称性。 α1 = b − λ (b − a) α 2 = a + λ (b − a ) （2）要求保留下来的区间内再插入一点所形成 的新三段具有相同的比例分布。 的新三段具有相同的比例分布。
可得初始搜索区间
[a ,
b ] = [0 . 3,
1 . 5 ].
机械优化设计
例题2.用外推法确定函数f ( x) = 3x 3 − 8 x + 9的一维优化初始区间, 给定 初始点x1 = 1.8, 初始进退距h0 = 0.1.

■ 二次插值法
求解一维目标函数 f (X)最优解的过程，称为一维优化（或一维 搜索），所使用的方法称为一维优化方法。 一维优化方法，它不仅可用来解决一维目标函数的求优问题， 且常用于多维优化问题在既定方向上寻求最优步长的一维搜索。 由前数值迭代法可知，求某目标函数的最优值时，迭代过程每 一步的格式都是从某一定点 X (k ) 出发，沿着某一使目标函数下降的 规定方向S (k ) 搜索，以找出此方向的极小点 X ( k 1)。这一过程是各种 最优化方法的一种基本过程。
在此过程中因 X (k ) 、 S (k ) 已确定，要使目标函数值为最小，只需 找到一个合适的步长 (k )就可以了。 这也就是说，在任何一次迭代计算过程中，当起步点 X (k )和搜索 方向 S (k )确定之后，就把求多维目标函数极小值这个多维问题，化解 为求一个变量（步长因子α ）的最优值 (k ) 的一维问题。 如图3-1 所示。
■ 然后采用缩小区间或插值逼近的方法得到最优步长，即求出该 搜索区间内的最优步长α*和一维极小点 X *。
常用的一维搜索方法主要有： 分数法 黄金分割法( 0.618法 ) 二次插值 三次插值法等 本节介绍最常用的黄金分割法和二次插值法。
3.1 搜索区间的确定
根据函数的变化情况，可将区间分为单峰区间和多峰区间。 所谓单峰区间，就是在该区间内的函数变化只有一个峰值，即函 数的极小值，如图3-2所示。 设区间 [α1，α3] 为单峰区间， 而α2 为该区间内的一点， 若有 α1<α2<α3 或 α1>α2>α3 成立，则必有 f(α1)> f(α2)< f(α3) 同时成立。 图3-2 单峰区间 即在单峰区间内的极小值点 X* 的左侧： 函数值呈下降趋势， 而在极小值点 X* 的右侧： 函数值呈上升趋势。 也就是说，单峰区间的函数值呈 “高-低-高” 的变化特征。

( 1 )＝ ( 2 )＝0.264， f1＝－1.125
新点 ( 2 )＝a 0.618( b a )＝0.354, f 2＝f ( ( 2 ) ) ＝-1.103 (4) 比较函数值，缩短搜索区间 f1 f 2 a 0.118, b ( 2 ) 0.354 判断迭代终止条件: b - a 0.354 0.118 0.236 继续缩短
区间为[a, b] [－0. 5,0.5]，取迭代精度＝0.15。
解：(1) 在初始区间[a, b]内取点并计算函数值。
( 1 )＝b 0.618( b a )＝ 0.118, f1＝f ( ( 1 ) ) ＝－0.854 ( 2 )＝a 0.618( b a )＝0.118,
( 1 )＝b 0.618( b a ) ( 2 )＝a 0.618( b a )
计算f ( ( 1 ) )和f ( ( 2 ) )，令f ( ( 1 ) ) f1 , f ( ( 2 ) ) f 2
( 2 ) 比较函数值，缩小搜索区间 a. f1 f 2 ,则丢掉区间( ( 2 ) ,b ] 部分，取[ a , ( 2 ) ]为 新区间[ a1 , b1 ],在计算中作置换：
(2)+h (3)。计算（ ），令（ ） f3 f f
(3) (3)
(1) 若f 3 f1，则[a,b]=[(3) ,(2)]，停止计算。 (2) 若f 3 f1，则 2h h，(2) (1)，f 2 f1，
(3) (2)，f 3 f 2 (2) h (3)，计算（ ），令（ ） f3 , f f
h 2 1 2 1＝ 2＝1,
2＝ 3＝2 , 3＝ 2 h＝4

(b a)，故
Fn
b
a 。由Fn即可从斐波那契数列表或按F0
F1
1, Fn
Fn1
Fn2 (n
2, 3,
)
推算出相应的n。
3）确定试点并计算相应的函数值，在区间a, b内的两个试点：
x2
a
Fn1 Fn
(b
a),
x1
b
Fn1 Fn
(b
a),
f1 f (x1),
f2 f (x2 )
第三章 一维搜索方法
1.若f (a1) f (b1)，则取[a,b1]为缩短后的搜索区间； 2.若f (a1) f (b1)，则取[a1,b]为缩短后的搜索区间。
第三章 一维搜索方法
第二节 搜索区间的确定与区间消去法原理
间 接
假定在搜索区间[a, b]内取一点x, 并计算它的导数值 f '(x)，可能出现三种情况：
x2 a b x1, f2 f (x2 )
5）检查迭代终止条件：bn1 an1
，若满足，则输出最优解x*
1 (a b), 2
ห้องสมุดไป่ตู้
f*
f (x*)，
若不满足，则转入（4），继续进行迭代。
1. f (a1) f (b1)，由于函数的单峰性， 极小点一定在[a, b1 ]内； 2. f (a1) f (b1)，极小点一定在[a1,b]内； 3. f (a1) f (b1)，极小点一定在[a1,b1]内。
第三章 一维搜索方法
第二节 搜索区间的确定与区间消去法原理
直 接 法
假定在搜索区间[a,b]内任取两点a1和b1，且a1 b1， 并计算f (a1)和f (b1)，可能出现三种情况：
f (x1) f (x) f (x2)