不满足迭代终止条件，继续搜索。 不满足迭代终止条件，继续搜索。
5）重新计算插入试点。 ）重新计算插入试点。
α 2 = α 1 = 4.292
f 2 = f 1 = − 1 .6227
α 1 = b − 0.618 (b − a ) = 5.708 − 0.618 ´ (5.708 − 2) = 3.4165
数值解法求解一般步骤
f (α )极小点 α * 所在 运用进退法确定单变量函数 1、运用进退法确定单变量函数
该区间应是单谷区间。 的搜 索区间 [ a, b]，该区间应是单谷区间。 单谷区间是指函数在区间内只有一个极小点。 单谷区间是指函数在区间内只有一个极小点。 是指函数在区间内只有一个极小点 在极小点左边的函数值应是严格下降，在极小 在极小点左边的函数值应是严格下降， 点右边的函数值应是严格上升， 点右边的函数值应是严格上升，即单谷区间内 的函数值具有的特征是： 的函数值具有的特征是：“高—低—高” 。 低 高
2.比较函数值 比较函数值, 比较函数值
f 2 < f1 ,向前试探 向前试探
α3 = α2 + h = 2
3. 比较函数值 比较函数值,
f 3 = f (α 3 ) = 0
f2 > f3
,步长加倍 向前试探 步长加倍,向前试探 步长加倍
h = 2 ×1 = 2 α1 = α 2 = 1
f 1 = f 2= 4
(1 ) (2 )
α 1 = b − 0.618(b − a ) α 2 = a + 0.618(b − a )
(1) (2)
α1 = a + 0.382(b − a ) α 2 = a + 0.618(b − a)
(1) (2)
黄金分割法的搜索过程
1. 给出搜索区间 给出搜索区间[a,b]及收敛精度 ，并置 λ =0.618。 及收敛精度e， 及收敛精度 。 2. 按照公式 按照公式(1)(2)计算插入点，并计算其函数值。 计算插入点，并计算其函数值。 计算插入点 3. 根据区间消去法原理，进行区间缩短。 根据区间消去法原理，进行区间缩短。 4. 检验区间是否缩短到足够短，如果不满足转步骤2。否则 检验区间是否缩短到足够短，如果不满足转步骤 。 转下步。 转下步。 5. 取区间两端点的平均值作为极小点的数值近似解。 取区间两端点的平均值作为极小点的数值近似解。
f (α ) = α − 7α + 10
2
1.取初始点为第一点 前进一步 得第二点 并计算函数值 取初始点为第一点,前进一步 得第二点,并计算函数值 取初始点为第一点 前进一步,得第二点 并计算函数值.
α1 = α 0 = 0 f 1 = f (α 1 ) = 10 α 2 = α 1 + h = 1 f 2 = f (α 2 ) = 4
第三章 一维搜索方法
第一节 概 述
k +1
x
=x +
k
αkd
k
(k = 1,2,...)
的极值时， 求多维目标函数 f ( X ) 的极值时，若迭代过程的出发 已确定， 出发， 点 X ( K ) 及搜索方向 d ( K ) 已确定，则从 X ( K ) 出发，沿方 向 d ( K ) 搜索新点的迭代格式为 X ( K +1) = X ( K ) + αd ( K ) 式中， 为步长因子。 式中， α 为步长因子。 α = α ( K ) ，使产生的新点 X ( K +1) 是方 选择一特定步长 上目标函数的极小点， 向 d ( K )上目标函数的极小点，即
算法的关键
插入点对称分布在搜索区间内插入的两个
试点在区间的位置相对于区间边界对称分布。 试点在区间的位置相对于区间边界对称分布。
αα 2 = α1b => aa1 = a2b
固定的区间收缩率区间收缩率是表示每次缩小所
得到的新区间长度与缩小前旧区间长度之比. 得到的新区间长度与缩小前旧区间长度之比.
min f ( X ( K ) + αd ( K ) ) = f ( X ( K ) + α ( K ) d ( K ) )
则称 α ( K ) 为方向
d (K )
上的最优步长因子。 上的最优步长因子。
二维函数f(x)沿方向 的一维搜索示例 沿方向s的一维搜索示例 二维函数 沿方向
最优步长因子 在搜索方向上， 在搜索方向上，使目标函数取得极小值的 步长因子，称为该方向上最优步长因子。 步长因子，称为该方向上最优步长因子。
f (a1) < f (b1 ) [a, b1 ]
f (a1 ) > f (b1 ) [a1 , b]
f (a1 ) = f (b1 ) [a1 , b1 ]
一维搜索方法分类
应用区间消去原理， 应用区间消去原理，需要在确定的搜索 内给出插入点。根据确定插入点的方法不同， 内给出插入点。根据确定插入点的方法不同， 一维搜索方法分为两大类： 一维搜索方法分为两大类： 试探法：黄金分割法、 试探法：黄金分割法、斐波那契法 插值法（函数逼近法）：二次插值法、 ）：二次插值法 插值法（函数逼近法）：二次插值法、三次 插值法、格点法等。 插值法、格点法等。
2）比较两试点函数值，缩短搜索区间.由于 ）比较两试点函数值，缩短搜索区间 由于
f1 < f 2
消去右区间
(α 2 , b]
3）确定新区间 ） b = α 2 = 5.708 [a,b]=[2,5.708] 4）判断迭代终止条件： ）判断迭代终止条件：
b − a = 5.708 − 2 = 3.708 > ε
保留区间λL 消去区间（ − λ）L 1 =λ = 保留区间λL 初始区间L
整理后得到一元二次方程 其解
λ + λ87 L 2
故黄金分割法又称为0.618法。 故黄金分割法又称为0.618法 0.618
插入的两个试点为: 插入的两个试点为
λ = 0 .6 1 8 α 1 = b − λ (b − a ) α 2 = a + λ (b − a )
f1 = f 2= 0
α 2 = α 3 = 4 f 2 = f 3 = −2 α 3 = α 2 + h = 8 f 3 = f (α 3 ) = 18
5. 比较函数值 比较函数值,
f1 > f 2 < f 3
所以a=2,b=8,即搜索区间为 即搜索区间为[a,b]=[2,8]. 所以 即搜索区间为
一维搜索 沿给定搜索方向， 沿给定搜索方向，求最优步长因子的 一元函数极值问题，称为一维搜索。 一元函数极值问题，称为一维搜索。
f (x
k +1
) = f ( x + α k d ) = φ (α )
k k
一维问题是多维问题的基础
求最佳步长因子方法 •解析解法 解析解法
先将f(x+ad)进行泰勒展开， 先将f(x+ad)进行泰勒展开，并取到二 f(x+ad)进行泰勒展开 阶项， 阶项，后对泰勒展开式利用微积分求极值方 法获得最佳步长因子。 法获得最佳步长因子。
X (0) = [0 0] , S ( 0) = [1 1]
T
T
2 F = x12 + x2 − 8 x1 − 12 x2 + 52
= 2α 2 − 20α + 52
α 的确定方法
dF 令 = 4α − 20 = 0 , 得 α ∗ = 5是最优步长 . dα
F* = 2
第二节 搜索区间的确定与区间消去法原理
f 1 = f (α 1 ) = 3.4165 2 − 7 ´ 3.4165 + 10 = − 2.2430
黄 金 分 割 法 的 程 序 框 图
第四节 一维搜索的插值法
1、插值方法与试探方法的比较 、 2、函数逼近法 、 将搜索区间内的若干试验点的函数值构造的 低次多项式（二次多项式） 低次多项式（二次多项式）作为函数的近似 表达式， 表达式，用这个多项式的极值作为原函数的 极值点的近似点。 极值点的近似点。 3、二次多项式逼近原函数的方法 、
牛顿法和抛物线法
一、牛顿法（切线法） 牛顿法（切线法）
•基本思想 基本思想
取原函数极小点的一个近似点， 取原函数极小点的一个近似点，在近似点附近用二次函数 泰勒展开并保留到二次项）逼近原函数， （泰勒展开并保留到二次项）逼近原函数，以逼近函数的极 小点作为原极小点的新近似点，依此类推,直到近似点满足控 小点作为原极小点的新近似点，依此类推 直到近似点满足控 制误差为止，取最后的近似点作为原函数的极小点。 制误差为止，取最后的近似点作为原函数的极小点。
外 推 法 程 序 框 图
-
例：应用外推法求函数 f ( x ) = x 2 − 6 x + 9的搜索区间，初始点 α 0 = 0， 初始步长 h0 = 1。
二、区间消去法原理 由外推法确定搜索区间[a,b]后，在区间 后 由外推法确定搜索区间 内插入两点a1和 （ ），计算 内插入两点 和b1（a<a1<b1<b），计算 ）， 插入点的函数值，并比较其大小， 插入点的函数值，并比较其大小，确定消去 的区间，从而得到缩短的搜索区间， 的区间，从而得到缩短的搜索区间，依次类 最后即可得到理论最小点的近似解。 推，最后即可得到理论最小点的近似解。
1 f ( x + α d ) ≈ f ( x) + α d ∇f ( x) + (α d )T G (α d ) 2
T
d ∇f ( x ) α =− T d Gd
T *
x
k +1
=x + α d
k *
k
(k = 1, 2,...)
•数值解法 数值解法
利用计算机通过反复迭代计算求得最佳 步长因子的近似值。 基本思路是： 步长因子的近似值。 基本思路是： 先确定步长因子（最优点）所在的区间， 先确定步长因子（最优点）所在的区间， 然后根据区间消去法远离不断缩小此区间， 然后根据区间消去法远离不断缩小此区间， 从而获得最优点的数值的近似解。 从而获得最优点的数值的近似解。 0.618法,抛物线法 三次插值法 法 抛物线法 三次插值法..... 抛物线法,三次插值法
