来的曲线，用简单曲线的极小值点代替原曲线的极小点。
Newton法、二次插值法、三次插值法
第三章 常用的一维搜索算法
本章主要内容：
§1 搜索算法概述 §2 “成功-失败”法 §3 0.618法（黄金分割法） §4 牛顿法 §5 插值法
常用的一维直接法有消去法和近似法两类。它们都是从某 个初始搜索区间出发，利用单峰函数的消去性质，逐步缩小 搜索区间，直到满足精度要求为止。
据迭代点 的可行性
下降算法： k , f ( x k 1 ) f ( x k ) 每一迭代点的目标函数 根据目标函数 值都在下降 的下降特性 非单调下降算法： k , f ( x k 1 ) f ( x k ), k klk k l , f ( x ) f ( x )
如何确定包含极小点在内的初始区间 ?
进退算法 (或称成功-失败法)
（一）基本思想：
由单峰函数的性质可知，函数值在极小点左边严格下降，在右边严格上升。
从某个初始点出发，沿函数值下降的方向前进，直至发现函数值上升为止。 由两边高，中间低的三点，可确定极小点所在的初始区间。
f(x)
a x0 x1 x*
x2
k
若算法是有效的，则它产生的解序列收敛于该问题的最优解。 计算机只能进行有限次迭代，一般很难得到准确解，而只能得 到近似解。当达到满足的精度要求后，即可停止迭代。
迭代法的终止条件
停止迭代时要满足的条件称为终止条件。 理想的终止条件是
f ( x) f ( x*) ，
或者
x x * .
f(x)
f(x)
f(x)
f(x)
a
b
x
a
a b
x
a
b
b
x
x
连续单峰函数
不连续单峰函数
非单峰函数离散单峰函数
单峰函数具有一个重要的消去性质
定理：设f(x)是区间[a,b]上的一个单峰函数，x*∈[a,b]是其极小点， x1 和x2是 [a, b]上的任意两点，且a<x1 <x2<b，那么比较f(x1)与f(x2)的值后，可得出如下 结论：
线搜索迭代法的框架分析----一维搜索
(3) 第三种方法的思路是：沿搜索方向使目标函数值下降最多， 即沿射线
x x d
k
k
求目标函数 f(x) 的极小：
λk : arg min f ( xk d k )
k k f ( x d ) 这项工作是求以 λ 为变量的一元函数
的极小点
第三章 常用的一维搜索算法
本章主要内容：
§1 搜索算法概述 §2 “成功-失败”法 §3 0.618法（黄金分割法） §4 牛顿法 §5 插值法
搜索算法概述
n元函数 f : D Rn R
定理(必要条件) 设 f : D Rn R (1) x 为D的一个内点; (2) f ( x ) 在 x 可微; (3) x 为 f ( x ) 的极值点; 则 f x 0 。 定理(充分条件)
λk ，故常称这一过程为（精确）一维搜索或
（精确）线搜索或一维最优化，确定的步长为最佳步长。
（精确）一维搜索的一个重要性质
在搜索方向上所得最优点处的梯度和该搜索方向正交。
k 1 x f ( x ) 按下述 具有一阶连续偏导数， 定理 设目标函数
规则产生
k k λ arg min f ( x d ) k k 1 k k x x d k
每次迭代在某区域内搜索下个迭代点， 近30年来发展起来的一类方法
线搜索迭代法的基本思想
现假定已迭代到点 x 则从
k
,
若 x 是一局部极小点，
k
x k 出发沿任何方向移动,
都不能使目标函数值下降。 若从
xk
出发至少存在一个方向 d k
可使目标函数值有所下降， 如图1示
图1
线搜索迭代法的基本思想
若从
k
,
x k 1 x k x
k
,
（3）根据目标函数梯度的模足够小
f ( x k )
迭代法的收敛速度
设序列 x
k
收敛于
x
k 1
x* ，若存在与迭代次数 k 无关的数

0 和 1，使k从某个k0开始，都有
x* x x*
k
(1)
整体下降，局部上升
迭代法的分类
根据是否计算目标函 数和约束函数的导数 直接法：不需要导数信息 仅利用函数值，简单易用 非直接法： 需要导数信息
利用导数信息，收敛性结果更强
线搜索方法：迭代点沿某方向产生 每次迭代沿某个方向搜索下个迭代点， 根据迭代点是否 最常见研究最多的方法 沿某个方向产生 迭代点在某区域内搜索产生 信赖域方法：
k 称为步长或步长因子。
图1
线搜索迭代法的步骤
0 x (1) 选定某一初始点 ，并令 k: 0;
(2) 确定搜索方向 d
k
k
;
k
(3) 从 x 出发，沿方向 d 求步长 λ k ，以产生下一个迭代点
x
k 1
;
(4) 检查得到的新点
x k 1 是否为极小点或近似极小点。
若是，则停止迭代。 否则，令 k : k 1 ，转回(2)继续进行迭代。 在以上步骤中，选取搜索方向是最关键的一步。 各种算法的区分，主要在于搜索方向 d k 的不同。
k
成立，就称 x 收敛的阶为
k
，或者称 x 阶收敛。 当 2 时，称为二阶收敛，也可说 x 具有二阶收敛速度。
k
当 1 2 时，称超线性收敛。 当
1 ，且 0 1 时，称线性收敛或一阶收敛。
迭代法的一般框架
(a) 找初始点
找初始点 是
则有 f ( xk 1 )T d k 0. 证明：构造函数 ( ) f ( xk d k )，则得 λk min λ 即
λk 是函数 ( ) 的极小点，所以
k
0 ' (λk ) ' (λ) λ f ( x k λd k )T d k
(c) 迭代格式：不同的 d k 对应不同的算法，各种算法的区 分，主要在于确定搜索方向的方法不同。 后面介绍各种
算法时会给出一个明确的选取 d k的方法。 在确定了迭代方向后，下一步就要确定迭代步长 λ k ，常 见的方法有3种。 (1) 令它等于某一常数(例如令λk 1 )，这样做不能保证目标 函数值下降。 (2) 第二种称为可接受点算法，只要能使目标函数值下降，可 任意选取步长。
问题是 x* 未知
迭代法的终止条件
实用的终止条件是根据相继两次迭代的结果 （1）根据相继两次迭代的绝对误差
f ( x k 1 ) f ( x k ) , x k 1 x k ,
（2）根据相继两次迭代的相对误差
f ( x k 1 ) f ( x k ) f (x )
b
x
（二）算法 1、选定初始点a 和步长h; 2、计算并比较f(a)和f(a+h)；有前进(1)和后退(2)两种情况： (1) 前进运算：若f(a) ≥f(a+h), 则步长加倍，计算f(a+3h)。若f(a+h) ≤f(a+3h)， 令 a1=a, a2=a+3h, 停止运算；否则将步长加倍，并重复上述运算。 (2) 后退运算：若f(a) < f(a+h), 则将步长改为－h，计算f(a－h)，若f(a－h) ≥ f(a)，令 a1=a－h, a2=a+h, 停止运算；否则将步长加倍，继续后退。
——仅仅找区间！若进一步找最小点， 参阅P44!
f(x)
f(x)
a a+h
a+3h
a+7h
x
a-7h
a-3h a-h a a+h
x
a
(三) 几点说明 缺点：效率低； 优点：可以求搜索区间； 注意：h 选择要适当，初始步长不能选得太小。
“成功—失败”法----算例
例 ：利用“成功-失败”法求函数 f ( x) x3 2 x 1 的搜索区间， 1 1 取初始点 x ，步长 h . 2 2 1 1 x h , 解：取初始点 ，步长 2 2 1 15 1 1 f ( x) f ( ) , f ( x h) f ( ) f (0) 1, 2 8 2 2 因为f ( x) f ( x h)，搜索成功，步长加倍； 1 1 计算 f ( x h+2h) f ( x 3h) f ( 3 ) f (1) 0, 2 2 因为f ( x h) f ( x 3h)， 搜索成功，步长加倍； 1 1 计算 f ( x 3h +4h) f ( x 7 h) f ( 7 ) f (3) 22, 2 2 因为f ( x 3h) f ( x 7h)， 搜索失败，停止迭代； 得到搜索区间为 [ x h, x 7h] [0,3].
迭代法的基本思想
首先给定一个初始估计 x 为了求函数f(x)的最优解， 然后按某种规划(即算法)找出比
0
x0更好的解 x1，f ( x1 ) f ( x0 ) 1 2 再按此种规则找出比 x 更好的解 x ，
*
k 如此即可得到一个解的序列 {x }，
若这个解序列有极限 x ， lim x k x* 0， 则称它收敛于x*。
（I） 若f(x1)≥f(x2)，x*∈[x1,b] (II) 若f(x1) < f(x2), x*∈[a,x2]
f(x)
f(x)