第 三 章 一维搜索
如前所述，最优化算法的迭代格式为
1k k kkx x d?? ?? ，
因而算法的关键就是选择合适的搜索方向，然后再确定步长因子 k? . 若设
( ) ( )kkf x d? ? ???，
则确定步长的策略 是从 kx 出发，沿 kd 方向搜索，希望找到 k? ，使得 ( ) (0)k?? ?? ，这就
是所谓的一维搜索或线搜索 (line search)问题 .
如果 求得的 k? ， 满足
0( ) m in ( )k k k kkf x d f x d????? ? ?
或
0( ) min ( )k ?? ? ? ???
，
则称 其 为精确一维搜索 ， 相应的 k? 称为最优步长因子 .
如果选取 的 k? ，使目标函数获得可以接受的改善，即
( ) ( ) 0k k kkf x f x d?? ? ?，
则称 其 为非精确一维搜索 .
§3.1 一维搜索的基本框架
一维搜索 问题 实际上 就是 一元函数 求 极值问题，其基本的解决框架是：
（ 1） 确定包含最优解的初始搜索区间；
（ 2） 采用某些区间分割技术或插值方法不断缩小搜索区间，最后得到 可以接受的 解 .
设 :? ???， [0, )? ? ?? 是函数 ()?? 的最小值点，即
0( ) m in ( )?? ? ? ???
. 若存在
闭区间 [ , ] [0, )ab? ?? ，使 [ , ]ab? ? ，则称 [, ]ab 为一维极小化问题
0min ( )? ???
的搜索区
间 .
确定初始搜索区间的 一种简单方法是 进退法 ，其 基本思想 是 从 某 一点出发，按一定步长
探测，试图找到函数值呈 “高－低－高 ”变化的三点 . 若一个方向不成功，就退回来，再沿相
第三章 一维搜索
30 最优化理论与方法 [乌力吉 ]
反方向探测 .
算法 3.1（确定初始搜索区间的进退法）
步 1： 取初始步长 h ，置初始值 1 0?? ， 11()? ??? ，并置 0k? ；
步 2： 置 1 h????， ()? ??? ， 1kk??；
步 3： 若 1??? ，则置 2 1 2 1,? ? ? ???， 11,? ? ? ???， 2hh? ， 1kk??，转步 2；
步 4： 若 1k? ，则置 22,? ? ? ???， hh?? ，转步 2，否则取 2min{ , }a ??? ，
2max{ , }b ??? ，停止计算 .
确定了初始搜索区间 [, ]ab 后， 接下来 就是采用具体的一维搜索方法确定出 ? . 为此，
我们 先给出如下概念 .
设 :? ???， [ , ]ab?? . 若存在 [ , ]ab? ? ，使得函数 ()?? 在 [ , ]a? 上单调减少，
而在 [ , ]b? 上单调增加 ，则称 [, ]ab 是函数 ()?? 的单峰区间， ()?? 是 [, ]ab 上的单峰函数 .
容易看出，如果 ()?? 是区间 [, ]ab 上的一个单峰函数， 12, [ , ]ab??? ，且 12??? . 则
有
（ 1）当 12( ) ( )? ? ? ?? 时， 2[ , ]a? 是 ()?? 的单峰区间；
（ 2）当 12( ) ( )? ? ? ?? 时， 1[ , ]b? 是 ()?? 的单峰区间 .
下面我们 将介绍几种常用的一维搜索方法，这些方法主要是针对单峰函数设计的 .
§3.2 精确一维搜索的收敛理论
§3.2.1 采用精确 线 搜索 下降算法的收敛性
我们首先给出 下降 算法 2.1 在点 kx 处沿下降方向 kd 进行精确一维搜索时，函数值下降
量的估计 .
定理 3.2.1 设 kd 是 ()fx在 kx 处的下降方向， k? 是
0min ( )kkf x d? ?? ?
的解， 如果存在
正数 M ，使得不等式
§ 3.2 精确一维搜索的收敛理论
最优化理论与方法 [乌力吉 ] 31
2 ()kkf x d M?? ? ?
对任意 0?? 成立， 则有 不等式
2 21( ) ( ) ( ) c o s , ( )2k k k k k kkf x f x d f x d f xM?? ? ? ? ? ?.
证 由定理假设， 对任意 0?? ， 有
2 2( ) ( ) ( ) 2k k k k T k kf x d f x f x d M d???? ? ? ? ?，
特别地，上述不等式 对其 右端 二次函数 的极小点
2
()k T k
k
f x d
Md?
??? 也成立，而且只要 搜索
方向 kd 是 ()fx在 kx 处的下降方向，即 ( ) 0k T kf x d??， 就有 0?? . 因此，当 kd 是 ()fx
在 kx 处的下降方向时，我们有
2 2( ) ( ) ( ) ( ) ( ) 2k k k k k k k T k k
kf x f x d f x f x d f x d M d?? ? ?? ? ? ? ? ? ? ? ?
222
2 2 2
1 ( ( ) ) 1 ( ( ) )()22
()
k T k k T kk
k k k
f x d f x dfxM
M d f x d
??? ? ?
?
2 21 ( ) c o s , ( )2 k k kf x d f xM? ? ? ?.
定理 3.2.2 设 ()fx在 开集 nD?? 上连续可微， 设 xD? 是 采用精确线搜索的 下降算
法（即保证 1( ) ( )kkf x f x? ? 和 ( ) 0k T kf x d??对任意 k 成立）产生的点列 {}kx 的一个聚点，
1K 是满足
1lim
kxKxx? ? 的指标集 . 如果 存在 0M? ，使得 || ||kdM? 对任意 1kK? 成立，设 d
是序列 {}kd 的 任一 聚点，则 有
( ) 0Tf x d??.
进一步 地 ，若 ()fx在 D 上二次连续可微，则还有
2 ( ) 0TTd f x d??.
证 设 21KK? 是满足
2lim
kkKdd?? 的指标集，下面用反证法证明 .
第三章 一维搜索
32 最优化理论与方法 [乌力吉 ]
假设 定理结论不成立，即 ( ) 0Tf x d??，由于 ( ) 0k T kf x d??，注意到 2kK? 时， 有
22lim , lim
kkx K k Kx x d d????，
可得 ( ) 0Tf x d??. 结合前面 的假设 可知 ， 必 存在正数 0?? ，使得
( ) 0Tf x d ?? ? ? ?，
再 依据 极限的定义，必 存在 x 的邻域 ()Nx和指标集 32KK? ，使得当 ()x Nx? ， 3kK?
时，有
( ) / 2 0Tkf x d ?? ? ? ?.
由于
1lim
kxKxx? ? ， || ||kdM? ，故存在一个充分小的正数 ?? ，使得对所有 ?0 ????及
所有 3kK? ，都有 ()kkx d N x???， 于是
3
110
0( ) ( ) [ ( ) ( ) ] [ ( ) ( ) ]
k k k k
k k Kf x f x f x f x f x f x
? ??
??? ? ? ? ???
33
? ? ?[ ( ) ( ) ] ( )k k k k k T kkk K k Kf x d f x f x d d? ? ? ???? ? ? ? ? ???(0 1)k???
3
?( / 2 )kK ???? ? ? ? ?? ，
但这 与 0( ) ( )f x f x? 为有限值 矛盾， 矛盾表明 必有 ( ) 0Tf x d??.
同样地，若 2 ( ) 0Td f x d??不成立，则必有 2 ( ) 0Td f x d ?? ? ? ?. 类似地，有
30
?( ) ( ) [ ( ) ( ) ]k k kkKf x f x f x d f x??? ? ? ??
3
2 2?()? ?[ ( ) ( ) ( ) ]
2k T k k T k k kkkK f x d d f x d d?? ? ??? ? ? ? ??
(0 1)k???
33
222? ?( ) ( )?( ) ( ) ( )
2 2 2k T k k kkk K k Kd f x d d? ? ?????? ? ? ? ? ? ? ???
，
此矛盾表明必有 2 ( ) 0Td f x d??.
定理 3.2.3 设 ()fx? 在水平集 0{ ( ) ( )}L x f x f x??上存在且一致连续， 采用精确线
搜索的 下降 算法产生的方向 kd 与 ()kfx?? 的夹角 k? 满足：
/2k? ? ???，
§ 3.2 精确一维搜索的收敛理论
最优化理论与方法 [乌力吉 ] 33
其中 ? 是一个给定的 小于 /2? 的 正数， 则或者对某个 k 有 ( ) 0kfx??，或者有
lim ( )kk fx?? ???，或者有 lim || ( ) || 0kk fx?? ??.
证 若 对某个 k 有 ( ) 0kfx??，或者有 lim ( )k
k fx?? ???
，则结论成立 . 故不妨设对任意
k 都 有 ( ) 0kfx??且 下降序列 { ( )}kfx 有下界，因此 lim ( )k
k fx??
存在 ， 从而有
1lim [ ( ) ( ) ] 0kkk f x f x??? ??.
下面用反证法证明 lim || ( ) || 0k
k fx?? ??
.
假设 lim || ( ) || 0k
k fx?? ??
不成立， 即存在正数 0?? 和无限指标集 1K ， 使 对任意 1kK? 都
有 || ( ) ||kfx ???成立， 故对任意 1kK? ，都有
1( ) || || ( ) || c o s c o s ( / 2 ) s| i| nkk T k k kf x d d f x ? ? ? ? ? ? ?? ? ? ? ? ? ? ?.
由于
( ) ( ) ( )k k k k T kf x d f x f d? ? ?? ? ? ? （ k? 位于 kx 与 kkxd?? 之间）
( ) ( ) [ ( ) ( ) ]k k T k k k T kf x f x d f f x d? ? ?? ? ? ? ? ? ?
()( ) | | | | ( ) ( ) ||
||| || |k k
k T kk k kf x df x d f f x
d?????? ? ? ? ? ?????
，
再 注意到 ()fx? 在 L 上一致连续，故存在 ? ，使得当 0 |||| kd????时，有
1|| ( ) ( ) | /2|kkf f x??? ? ? ?，
若在上面的不等式中取
|| ||kd???
，则 对任意 1kK? ，都有
1()( ) ( )
|| ()| | | | 2||
k k T kkk
kkd f x df x f xdd ??? ?? ? ? ?11() 2kfx ????
，
故 对任意 1kK? ， 有
1 11( ) ( ) ( )|| | 2|kkk k kdf x f x f xd? ? ?? ? ? ? ?，
但 这 与 1lim [ ( ) ( ) ] 0kk
k f x f x??? ??
矛盾 ，矛盾表明 必有 lim || ( ) || 0k
k fx?? ??
.
第三章 一维搜索
34 最优化理论与方法 [乌力吉 ]
§3.2.2 采用精确 线 搜索下降算法的 收敛速率
引理 3.2.4 设函数 ()?? 在闭区间 [0, ]b 上二次连续可微，且 (0) 0?? ? . 若 ()?? 在
[0, ]b 上的极小点 为 (0, )b? ? ，则 (0) / M????? ， 其中 正数 M 满足 [0, ]max ( )bM ? ??? ??? .
证 构造辅助函 数 ( ) (0 ) M? ? ? ????，它有唯一零点 (0) / M?????? . 注意到
00( ) ( 0 ) ( ) ( 0 ) ( )d M d??? ? ? ? ? ? ? ? ? ?? ? ?? ?? ? ? ? ???
，
即 ()??? 的图像总位于 ()??之下，再由 ()??是单调上升函数 可知， ()??? 的零点 ? 必位
于 ()??零点 ?? 的右边 ， 即
(0) / M? ? ??? ? ?? .
引理 3.2.5 设 ()fx在 n? 上二阶连续可微，则对任意 x , nd?? 和 ??? ，有
1220( ) ( ) ( ) ( 1 ) [ ( ) ]TTf x d f x f x d t d f x t d d d t? ? ? ?? ? ? ? ? ? ? ??.
证 11
00( ) ( ) [ ( ) ] [ ( ) ] ( 1 )Tf x d f x d f x t d f x t d d d t? ? ? ?? ? ? ? ? ? ? ? ???
110 0( 1 ) ( ) ( 1 ) [ ( ) ]TTt f x t d d t d f x t d d? ? ? ?? ? ? ? ? ? ? ? ??
1220( ) [ ( ) ] ( 1 )TTf x d d f x t d d t d t? ? ?? ? ? ? ? ??.
引理 3.2.6 设 ()fx在极小点 x 的邻域内二阶连续可微 ，若 存在 0?? 和 0 mM?? ，
使当 xx???时，对任意 ny?? ，都有
222 ()Tm y y f x y M y? ? ?，
则 当 xx???时， 必 有
2211 ( ) ( ) 22m x x f x f x M x x? ? ? ? ?，
( ) f x m x x? ? ?.
证 由引理 3.2.5，我们有
1 20( ) ( ) ( ) ( ) ( 1 ) [ ( ) ( ( 1 ) ) ( ) ]TTf x f x f x x x t x x f tx t x x x d t? ? ? ? ? ? ? ? ? ? ??，
§ 3.2 精确一维搜索的收敛理论
最优化理论与方法 [乌力吉 ] 35
由于 ( ) 0fx??，再利用 引理条件 ，我们立刻得到
2211 ( ) ( ) 22m x x f x f x M x x? ? ? ? ?.
又 由于
1 20( ) ( ) ( ) ( ( 1 ) ) ( ) ]f x f x f x f tx t x x x d t? ? ? ? ? ? ? ? ? ??，
故 有
( ) ( ) ( )Tf x x x x x f x? ? ? ? ?
1 20 ( ) ( ( 1 ) ) ( ) ]Tx x f tx t x x x d t? ? ? ? ? ?? 2m x x??，
由此即得 ( ) f x m x x? ? ?.
定理 3.2.7 设 采用精确线搜索的 下降 算法产生的 点 列 {}kx 收敛到 ()fx的极小点 x ，
若 ()fx在 x 的某一邻域内二阶连续可微， 搜索方向 kd 与 ()kfx?? 的夹角 /2k? ? ???，
且存在 0?? 和 0 mM?? ，使当 xx???时， 对任意 ny?? ，都有
222 ()Tm y y f x y M y? ? ?，
则 {}kx 局部 R? 线 性收敛 .
证 由于 lim k
k xx?? ?
， 故当 k 充分大时，有 / 2kxx ???， 1 / 2kxx ?? ??. 我
们不妨假设搜索方 向 kd 都是单位向量从而有界，则 存在 0?? ，使得
1( ) k k k kkx d x x x d? ? ? ??? ? ? ? ? ? ?.
记 ( ) ( )kkf x d? ? ???， 由于
( ) kkkx d x? ? ?? ? ? ?， kxx???，
故当 0 k? ? ?? ? ? 时，有
( ) ( [0 , 1 ] )k k k kkx d x x d x? ? ? ? ?? ? ? ? ? ? ?
( ) ( ) ( 1 ) ( )k k kkx x d x x? ? ? ? ?? ? ? ? ? ? ?
( ) ( 1 ) ( ) ( 1 )k k kkx d x x x? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ?，
第三章 一维搜索
36 最优化理论与方法 [乌力吉 ]
又注意到 (0 ) ( ) 0k T kf x d?? ? ? ?，且
22( ) ( ) ( )k T k k k kd f x d d M d M? ? ??? ? ? ? ? ? ( [0, ])k? ? ???，
由引理 3.2.4 知 ， ( ) ( )kkf x d? ? ???在 [0, ]k??? 上的极小点 k? 满足
( ) c o s ( )( 0 ) ( ) kkk T k k
kk
f x f xf x dM M M M????? ???? ? ?? ? ? ? ?? ，
其中 ? 为 cosk? 的下限 ，由假设知 0?? .
若记 ( ) / k
k f x M????
，则有 kkk?????? . 令 k k kkx x d??? ， 由于 kx 位于 kx 与
1k k kkx x d?? ?? 决定的线段上， 因此，必有
? ?1 m a x , k k kx x x x x x ??? ? ? ? ?，
于是， 由引理 3.2.5 和引理 3.2.6， 我们有
1( ) ( ) ( ) ( ) ( ) ( )k k k k k k k kkkf x f x f x d f x f x d f x??? ? ? ? ? ? ? ?
1220( ) ( 1 ) ( ) ( )k T k k T k k kk k kf x d t d f x t d d d t? ? ?? ? ? ? ? ??
21( ( ) ) 2k T kkkf x d M??? ? ?? ?
21( ) c o s 2kk k kf x M? ? ?? ? ? ? 21() 2kkkf x M? ? ?? ? ? ?
22
2
( ) ( )1( ) ( ) 2kf x f xf x MMM?????? ? ? ?
22222( ) kkf x m x xMM??? ? ? ? ? ?
2 222 [ ( ) ( ) ] ( ) [ ( ) ( ) ]2 kk mm f x f x f x f xM M M? ? ? ? ? ?，
由此得
1 1 2( ) ( ) ( ) ( ) ( ) ( ) [ 1 ( ) ] [ ( ) ( ) ]k k k k kmf x f x f x f x f x f x f x f xM???? ? ? ? ? ? ? ?，
令 12 2[1 ( ) ]mM?? ?? ，显然 01???， 且有
§ 3.3 精确一维搜索方法
最优化理论与方法 [乌力吉 ] 37
2 1 2 0( ) ( ) [ ( ) ( ) ] [ ( ) ( ) ]k k kf x f x f x f x f x f x???? ? ? ? ??? ? ?，
再由引理 3.2.6，我们有
2 2 0 2 222 [ ( ) ( ) ] [ ( ) ( ) ]k k k kx x f x f x f x f xmm ? ? ?? ? ? ? ? ?，
其中 02 [ ( ) ( )]f x f x
m? ??
. 上式可进一步改写为 kkxx ????， 由此即得迭代点列
{}kx 线性收敛 .
§3.3 精确 一维 搜索 方法
§3.3.1 0.618 法
0.618 法和 Fibonacci 法的基本思想都是通过取试探点并进行函数值比较，然后不断缩小
搜索区间，当区间长度缩到一定程度后，区间内各点均可作为近似解 . 这类方法十分简便，
仅需计算函数值，尤其适合于非光滑及导数表达式复杂或写不出的情形 .
设 ( ) ( )kkf x d? ? ???是搜索区间 11[ , ]ab 上的单峰函 数 . 记其在第 k 次迭代时搜索区
间为 [ , ]kkab ，现取两个试探点 k? , k? [ , ]kkab? ，且 kk??? ，计算 ()k?? 和 ()k?? . 根据
前面关于单峰函数的性质：
（ 1） 若 ( ) ( )kk? ? ? ?? ，则 最优解 [ , ]kka??? ，这时 令 1kkaa? ? ， 1kkb ?? ? ；
（ 2） 若 ( ) ( )kk? ? ? ?? ，则 最优解 [ , ]kkb??? ，这时 令 1kka ?? ? ， 1kkbb? ? .
由于 两个试探点 k? 和 k? 中必定有一个落入缩短的区间 11[ , ]kkab??， 我们 希望在下一次
迭代时利用这个已经计算的点，并且希望每次迭代后得到的搜索区间长度缩短率相同，为此
我们 要求 k? 和 k? 满足下列条件：
（ 1） k? 和 k? 到搜索 区间的端点等距，即 k k k kba??? ? ? ；
（ 2） 每次迭代，搜索区间长度的缩短率相同 . 即
11 ()k k k kb a b a???? ? ?，
其中 ? 是与 k 无关的常数；
第三章 一维搜索
38 最优化理论与方法 [乌力吉 ]
因此有 ()k k k k k kb a b a? ? ?? ? ? ? ?， 由此得
(1 )( )k k k ka b a??? ? ? ?， ()k k kb a??? ? ?.
不妨 设 11[ , ] [ , ]k k k ka b a ??? ? ， 此时 k? 含在 11[ , ]kkab??中 . 这时新的 试探点 1k?? 满足：
1 1 1 1( ) ( )k k k k k k ka b a a a? ? ? ?? ? ? ?? ? ? ? ? ?
2[ ( ) ] ( )k k k k k k k ka a b a a a b a? ? ?? ? ? ? ? ? ? ?，
为了减少计算量，我们希望 1k?? 与 k? 重合，这样，新的试探点 1k?? 处的函数值就不必重新
计算，即要求 2 1???? ；根据对称性， 对 11[ , ] [ , ]k k k ka b b??? ? 的情形也有类似结论 . 解方
程 2 1???? ，并取正值， 得
15 0.6 182? ????.
由此， 0.618 法的计算公式具体为：
0 . 3 8 2 ( ) , 0 . 6 1 8 ( )k k k k k k k ka b a a b a??? ? ? ? ? ?.
0.618 法也称黄金分割法 .
算法 3.2（ 0.618 法）
步 1： 确定初始搜索区间 11[ , ]ab 和容许误差 0?? ，计算初始两个试探点
1 1 1 1 1 1 1 10 . 3 8 2 ( ) , 0 . 6 1 8 ( )a b a a b a??? ? ? ? ? ?，
令 11()? ??? 和 21()? ??? ， 置 1k? ；
步 2： 若 12??? ， 则 转步 3，否则转步 4；
步 3： 若 kkb ????， 则 停止计算 ， 输出 k? ，否则令 1kka ?? ? ， 1kkbb? ? ， 1kk??? ? ，
1 ()k? ??? ， 1 1 1 10 .6 1 8 ( )k k k ka b a? ? ? ? ?? ? ?， 令 21()k? ? ? ?? ， 转步 5；
步 4： 若 kka????，则停止计算，输出 k? ，否则令 1kkaa? ? ， 1kkb ?? ? ， 1kk??? ? ，
2 ()k? ??? ， 1 1 1 10 .3 8 2 ( )k k k ka b a? ? ? ? ?? ? ?， 令 11()k? ? ??? ，转步 5；
步 5： 置 1kk??，转步 2.
§ 3.3 精确一维搜索方法
最优化理论与方法 [乌力吉 ] 39
0.618 法要求一维搜索的函数是单峰，而实际上很多情形都不是单峰 . 这个 时候往往容
易丢掉最优点 . Hopfinger?? (1976)提出了一种改进措施 . 每次两个内点与两个边界点的函数
值都进行比较 . 当函数值最小的点为左端点或第二个点时，丢弃右端点，否则丢弃左端点 . 经
过这样修改后，算法要相对可靠些，即在缩短搜索区间时，丢掉极小点的可能性减小了 ，但
仍不能保证迭代过程不丢掉极小点 .
§3.3.2 Fibonacci 法
通过选择试探点，并利用试探点处的函数值信息，可以不断缩短搜索区间 . 在函数值计
算总次数一定的情况下，最初搜索区间与最终搜索区间长度 的比值越大，说明选点方式越好，
最优的选点方式应使这个比值达到最大 ，这就是 Fibonacci 法的动机 .
设函数值计算总次数为 n ，最初区间长度为 nL ，最终区间长度为 1，因此最优取点方式
应使 nL 达到最大，下面先来估计 nL 的上确界 .
设 iL 的上确界为 iU ，即 iU 表示当允许计算 i 次函数值时，初始区间长度的上确界（当
然最终区间长度为 1） ， 1,2, ,in? ??? . 显然，要缩短区间 长度 至少需计算两次函数值 . 因此 ，
如果只允许计算零次或一次函数值，区间不会得到缩短，故有 011UU??.
下面考虑允许计算 n 次函数值时，初始区间 [, ]ab 的长度的上确界 nU . 设最初的两个试
探点为 11??? ，那么余下还可计算 2n? 次函数值，而极小点可能位于 1[, ]a? 或 1[ , ]b? .
（ 1） 若极小点位于 1[, ]a? 中，由于我们仅可在此区间中再计算 2n? 次函数值 ， 故有
12naU? ??? ；
（ 2） 若极小点位于 1[ , ]b? 中，由于除可再计算 2n? 次函数值外，还可利用 1? 处的函
数值 ， 因而
11nbU? ??? ；
由此立即得 12n n nL b a U U??? ? ? ?，从而 12n nU U U????.
大家知道， 由递归关系
011FF??， 12n n nF F F????， ( 2,3, )n? ?
第三章 一维搜索
40 最优化理论与方法 [乌力吉 ]
给出的数列称为 Fabonacci 数列， 从 上一段分析 看出 ，显然有 nnUF? .
因此若某种取点方式能保证在计算函数值 n 次后，能将长度为 nF 的初始区间缩短为 1，
或等价地，把搜索区间缩减为最初区间的 1/nF ，那么就有理由认为这种取点方式是最优的 .
Fabonacci 法 就是 根据 Fabonacci 数列来构造、选取试验点，它恰好具有上述所希望的性质 . 因
而是最优选点方式，故称之为优选法 .
Fabonacci 法中探测点的取法 如下：
1
11( 1 ) ( ) ( )
n k n kk k k k k k k
n k n k
FFa b a a b a? ? ? ?
? ? ? ?? ? ? ? ? ? ?
，
1 ()
nkk k k k
nk
Fa b aF? ?
??? ? ?
， 1, 2, , 1kn??? ，
由此即知经过 n 次函数值计算后，最终区间缩为初始区间的 1/nF . 而 当 n?? 时，
Fibonacci 法与 0.618 法的区间收缩率相同，因而 Fibonacci 法也是线性收敛的 .
由于 Fibonacci 法选点方式是最优的，而 0.618 法与其近似，故应用上将它们统称为优
选法 .
§3.3.3 二分法
二分法是求 ( ) 0??? ? 的根的一种简单方法 . 它每 次将区间对分，再利用连续函数的零
点定理，确定应该保留的半区间，区间收缩率为常数 1/2 ，因此它也具有线性 收敛速率 . 但
当 ()??? 的表达式很难求 或 ()?? 不可微时，方法的应用遇到困难 .
二分法的优点是每次缩小一半搜索区间，收敛速率快，但需要函数的一阶导数信息 .
算法 3.3（ 二分 法）
步 1： 确定初始搜索区间 11[ , ]ab 和容许误差 0?? ， 计算试探点 1 1 1( ) / 2ab? ?? ， 置
1k? ；
步 2： 若 kkba???，则停止计算，输出 k? ；
步 3： 计算 ''( )k?? ， 若 ''( ) 0k??? ，则令 1kkaa? ? ， 1kkb ?? ? ，否则令 1kka ?? ? ，
1kkbb? ? ；
§ 3.3 精确一维搜索方法
最优化理论与方法 [乌力吉 ] 41
步 4： 令 1 1 1( ) / 2k k kab? ? ? ???， 置 1kk??，转步 2.
§3.3.4 一点二次插值法（ 牛顿插值法 ）
其基本思想是用 ()?? 在 当前 点 k? 的 Taylor 二阶展开式 来 近似 代替 ()?? ， 再 以 Taylor
二阶 展开式的极小点 1k?? 作为 ()?? 极小点 更好的 近似 解 . 设
21( ) ( ) ( ) ( ) ( ) ( )2k k k k kq ? ? ? ? ? ? ? ? ? ? ?? ??? ? ? ? ?.
令 1 1 1( ) ( ) ( ) ( ) 0q ? ? ? ? ? ? ?? ? ??? ? ? ?，解之得 ()
()kk k???? ???????
. 因此，牛顿法的
迭代公式为
1 () , 0 , 1 ,()kkk k k???? ??? ?? ? ? ?????
. （ 3.3.1）
注 牛顿 插值 法不仅算法简单 ，而且具有 局部 二阶 收敛速率 ，缺点是需要计算二阶导数 ，
仅有局部收敛性， 特别是 当 ( ) 0k???? ? 时，有 1( ) ( )kk? ? ? ?? ? .
§3.3.5 二点二次插值法
（一） 设已给两点 1? , 2? ，利用 1()?? , 2()?? 以及 1()??? 或 2()??? 进行插值 . 设二次
插值函数形式为
2()q a b c? ? ?? ? ?.
令
2
1 1 1 1
2
2 2 2 2
1 1 1
( ) ( ) ,
( ) ( ) ,
''( ) 2 ( ) ,
q a b c
q a b c
q a b
? ? ? ? ?
? ? ? ? ?
? ? ? ?
? ? ? ? ??
? ? ? ??
? ?? ? ??
由此 解得
1 2 1 1 2
2
12
1 2 1 1 2
11 2
12
( ) ( ) ( ) ( ) ,
()
( ) ( ) ( ) ( )( ) ,
()
a
b
? ? ? ? ? ? ? ?
??
? ? ? ? ? ? ? ?? ? ?
??
?? ? ?? ?
? ???
? ?? ? ?
? ???
? ???
故 ()q? 的驻点为
第三章 一维搜索
42 最优化理论与方法 [乌力吉 ]
1 2 11
121
12
( ) ( )
2 ( ) ( )2 ( )
b
a
? ? ? ???
? ? ? ???
??
??? ? ? ?
???? ???
???
.
由此得到其 一般迭代格式为
11
1
1
( ) ( )
( ) ( )2 ( )
k k kkk
kkk
kk
? ? ? ???
? ? ? ???
??
??
?
?
????
???? ???
???
， 1,2,k? ??? . （ 3.3.2）
注 要保证 1( ) ( )kk? ? ? ?? ? ，必须要求 0a? ，即
1 1 2 1 2( ) ( ) ( ) ( )? ? ? ? ? ? ? ??? ? ?.
算法 3.4（两点二次插值法 I）
步 1： 给出初始点 1? ，初始步长 0h? ，步长缩减因子 (0,1)?? ，容许误差 0?? ；计
算 11()? ??? ， 11'' ''( )? ? ?? ；
步 2： 若 1''( ) 0??? ，则 置 hh?? ；
步 3： 置 21h????， 计算 22()? ??? ；
步 4： 若 2 1 1 2 1''( )? ? ? ? ?? ? ?，则 置 2hh? ，转步 3；
步 5： 计算
21 2 1
1 2 1 1 2 1''( )2 [ ''( ) ]? ? ??? ? ? ? ? ???? ? ? ?
， ()? ?? ， '' ''( )? ? ?? ；
步 6： 若 | ''|??? ，则 停止计算，输出 ? ，否则 置 1??? ， 1??? ， 1''''??? ， hh?? ，
转步 2.
（二）设已给两点 1? , 2? ， 利用 1()?? 或 2()?? 以及 1()??? 和 2()??? 进行插值 . 令
2
1 1 1 1
1 1 1
2 2 2
( ) ( ) ,
( ) 2 ( ) ,
( ) 2 ( ) ,
q a b c
q a b
q a b
? ? ? ? ?
? ? ? ?
? ? ? ?
? ? ? ? ??
??? ? ??
? ? ? ??
解之得
1211 ()2 ( ) ( )ba ??? ? ? ?? ? ? ?? ?? ? ? ? ???.
§ 3.3 精确一维搜索方法
最优化理论与方法 [乌力吉 ] 43
由此得到 一般迭代格式 为
11
1 ( ) , 1 , 2 ,( ) ( )
kkk k k k??? ? ? ?? ? ? ???
?
? ?? ? ? ??????. （ 3.3.3）
注 要保证 1( ) ( )kk? ? ? ?? ? ，必须要求 11( ) ( ( ) ( ) ) 0k k k k? ? ? ? ? ?????? ? ?.
与牛顿法 (3.3.1)比较，在 迭代格式 (3.3.2)中，
1
1
1
( ) ( )2 ( )
()
kkk
kk
k
kk
? ? ? ???
?? ??
??
?
?
?
???? ???
??? ???
? ，
其 逼近误差为 3
11 ( )( )3 k k k? ? ? ? ??????
；而 迭代格式 (3.3.3)中，
1
1
( ) ( ) ()kk k
kk
? ? ? ? ???? ?
?
??? ???? ，
其 逼近误差为 3
11 ( )( )2 k k k? ? ? ? ??????
.
可见后一种逼近程度略差一些 ，但我们可以证明如下命题 .
设 ()?? 三阶连续可微， ? 满足 ( ) 0 , ( ) 0? ? ? ?? ????，则二点二次插值公式产生
的序列 {}k? 收敛到 ? ，且 收敛速率 的阶为 151.6182? ? .
§3.3.6 三 点二次插值法
设已给两点 1? , 2? ， 3? ，对二次插值函数
2()q a b c? ? ?? ? ?
利用 1()?? , 2()?? 以及 3()?? 进行插值 . 再 用插值多项式的驻点近似 ()?? 的 驻点 . 其 一般
迭代格式 为
2 1 1 21 2 1
1 2 2 1 2 1
( ) ( ) ( )11()2 2 ( ) ( ) ( )k k k k k kk k k
k k k k k k k k k
? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ?? ? ? ?? ? ?
? ? ? ? ? ?
? ? ?? ? ? ? ? ? ? ?. （ 3.3.4）
三点二次插值法具有如下收敛性质 .
设 ()?? 四阶连续可微， ? 满足 ( ) 0 , ( ) 0? ? ? ?? ????，则上述插值法产生的序列
第三章 一维搜索
44 最优化理论与方法 [乌力吉 ]
{}k? 收敛到 ? ，且 收敛速率 的阶约为 1.32.
算法 3.5（三点二次插值法）
步 1： 用 进退法 确定 “高－低－高 ”三个点 1 2 3? ? ???， 计算 ()ii? ??? ， 1,2,3i? ，
给出 容许误差 0?? ；
步 2： 计算 1 2 3 2 3 1 3 1 22 [ ( ) ( ) ( ) ]A ? ? ? ? ? ? ? ? ?? ? ? ? ? ?，若 0A? ，则输出 2? ；
步 3： 计算
2 2 2 2 2 21 2 3 2 3 1 3 1 2[ ( ) ( ) ( ) ] / A? ? ? ? ? ? ? ? ? ?? ? ? ? ? ?，
若 13( )( ) 0? ? ? ?? ? ?，停止计算，则输出 2? ；
步 4： 若 2||? ? ???， 则停止计算，输出 ? ；
步 5： 计算 ()? ??? ， 若 12( )( ) 0? ? ? ?? ? ?，则转步 6，否则转步 7；
步 6： 若 2??? ，则置 1 2 1 2,? ? ? ???， 22,? ? ? ???，否则置 33,? ? ? ???， 转
步 2.
步 7： 若 2??? ，则置 3 2 3 2,? ? ? ???， 22,? ? ? ???，否则置 11,? ? ? ???，转
步 2.
§3.4 不精确一维搜索方法
一维搜索是最优化算法的基本组成部分 . 前述的精确一维搜索往往需要花费大量计算
量，导 致整个算法不是十分有效 . 另外，在很多算法如牛顿算法和拟牛顿算法，其 收敛速率
也并不依赖于精确一维搜索 . 因此，另一种变通的方法是在每次一维搜索过程中，保证目标
函数都有 一个 满意的下降就够了，这就是所谓的不精确一维搜索 .
在进行不精确一维搜索时，怎样才叫达到了满意的程度，从而结束一维搜索，必须要有
便于操作的准则 .
下面介绍一些最常用的准则，为简单计，仍以单峰函数为考察对象 .
§3.4.1 Armijo-Goldstain 准则
针对函数值究竟下降多少才算满意， Armijo 在 1966 年提出一个 评价 准则 . 令
§ 3.4 不精确一维搜索方法
最优化理论与方法 [乌力吉 ] 45
( ) ( )kkf x d? ? ???， 并假设 kd 是 ()fx在 kx 处的下降方向，即有 ''(0) 0? ? .
由于 ()? ??? 在点 0?? 处的切线为 (0) ''(0)? ? ? ??? ，故对任意数 (0,1)?? ，
(0 ) ''(0 )? ? ?? ??? 是曲线 ()? ??? 的经过点 (0, (0))? 的一条割线， 基于这个事实，
Armijo 提出如下准则，一个可以接受 的 步长应该满足 ：
( ) (0 ) (0 )kk? ? ? ?? ? ???或 ( ) ( ) ( )k k k k T kkkf x d f x f x d? ? ?? ? ? ?， (3.4.1)
其中 0 1/ 2??? 是给定的数 . 其几何直观就是所取的点 kkkxd?? 处函数的图像在相应割
线图像的下方，这时我们就认为函数值的下降量是可以接受的 .
Goldstain 发现 Armijo 准则并不能排除步长 k? 可能会很小，以至于迭代点及目标函数的
改进量 都 不大，影响算法的整体效率 . 为此，他提出如下补充准则：
( ) (0 ) (1 ) (0 )kk? ? ? ? ? ? ?? ? ?或 ( ) ( ) ( 1 ) ( )k k k k T kkkf x d f x f x d? ? ?? ? ? ? ?， (3.4.2)
其中 ? 同 Armijo 准则 .
同时满足 (3.4.1)和 (3.4.2)的步长 k? 称为可接受步长，可接受步长全体构成的区间 称为可
接受区间 . ? 一旦给定，可接受区间也随之确定，而且 ? 越接近于 0，可接受区间越大， 反
之，若 ? 越趋近于 1/2 ，则可接受区间越小 .
算法 3.6（ Armijo-Goldstein 方法）
步 1： 计算 (0)? 和 (0)?? ，给出 (0,1/ 2)?? , 1t? ， 在搜索区间 max[0, ]? 中 给 定初始点
0? ， 令 0 0a? , 0 maxb ?? , 0k? .
步 2： 计算 ()k?? ，若
( ) (0 ) (0 )kk? ? ? ?? ? ???，
则 转 步 3；否则 令 1kkaa? ? , 1kkb ?? ? ， 转 步 4.
步 3： 若
( ) (0 ) (1 ) (0 )kk? ? ? ? ? ? ?? ? ?，
则 停止迭代，输出 k? ；否则 令 1kka ?? ? , 1kkbb? ? ， 转 步 4.
第三章 一维搜索
46 最优化理论与方法 [乌力吉 ]
步 4： 若 1kb? ??? ，则 取 11
1 2kkk ab? ??? ??
， 否则 取 1kkt??? ? . 令 1kk??， 转步
2.
§3.4.2 Wolfe-Powell 准则
Armijo-Goldstain 准则有时候会将最佳步长因子排斥在可接受区间之外 . 为此，
Wolfe-Powell 给出了一个简单的替代准则：
( ) (0 ) (0 )kk? ? ? ?? ? ???或 ( ) ( ) ( )k k k k T kkkf x d f x f x d? ? ?? ? ? ?， (3.4.1)
( ) (0)k? ? ????? 或 ( ) ( )k k T k k T kkkf x d d f x d??? ? ? ?, ( ,1)??? . (3.4.3)
准则 (3.4.3)的几何解释 是 在可接受点处的切线斜率大于或等于初始斜率的 ? 倍 . 由于
( ,1)??? ，因而 可接受 点处的切线 更平坦些 .
若将 Wolfe-Powell 准则中 (3.4.3)式换为
( ) ( )k k T k k T kkf x d d f x d??? ? ? ? ?, (3.4.4)
则当 ? 的值 越小， Wolfe-Powell 准则 越接近精确搜索，工作量也越大 . 应该指出的是不精确
搜索，不要求过小的 ? ，应用上通常取 0.1?? ， 0.4?? .
Wolfe-Powell 准则下可接受步长因子存在 的，我们有如下命题 .
定理 3.4.1 设 连续可微函数 ()fx有下界，且 ( ) 0k T kf x d??，则必定存在步长因子 k? ，
使得 Wolfe-Powell 准则 (3.4.1)和 (3.4.4)满足 .
证 令 ( ) ( )kkf x d? ? ???，则 ( ) ( )k k T kf x d d? ? ?? ??. 令 1? 满足 1? ? ???，
考虑集合
1{ 0 | (0 ) ( ) 0 }A ? ? ? ? ???? ? ? ?.
由于 ()?? 有下界，且 (0 ) ( ) 0k T kf x d?? ? ? ?， 故 A 非空 . 事实上，若 A?? ，即对所有
0?? ，都有 1( ) (0 ) 0? ? ? ?????， 因而
10( ) ( 0 ) ( ) ( 0 )d?? ? ? ? ? ? ? ? ???? ? ??
，
当 ??? 时，可推得 ()????? ，这与 ()fx有下界矛盾， 故 A?? .
§ 3.4 不精确一维搜索方法
最优化理论与方法 [乌力吉 ] 47
令 ? ?inf | A? ? ???， 则显然 0?? ， 故当 [0, ]??? 时， 有 1( ) (0 ) 0? ? ? ?????. 由
? 的定义 及 ()??? 的连续性， 必有 1( ) (0)? ? ????? ， 故
10 ( ) (0 ) (0 )? ? ? ? ??? ? ?? ? ?，
再由 ()??? 的连续性 知 ，必定存在 1 0?? ，当 11[ , ]? ? ? ? ?? ? ?时，有 0 ( ) (0)? ? ??????，
从而有
( ) (0)? ? ? ???? 或 ( ) ( )k k T k k T kf x d d f x d??? ? ? ? ?， ( ,1]??? .
再由 1( ) (0 ) 0? ? ? ?????，可得
10( ) ( 0 ) ( ) ( 0 )d?? ? ? ? ? ? ? ????? ? ??
，
故有
1( ) (0 ) (0 ) (0 ) (0 )? ? ? ? ? ? ? ? ? ???? ? ? ?，
由 ()?? 的连续性 知 ，存在 2 0?? ，当 22[ , ]? ? ? ? ?? ? ?时， 有
( ) ( 0) ( 0)? ? ? ?? ? ???或 ) ( ) ( )k k k k T kf x d f x f x d? ? ?? ? ? ?.
令 12min{ , }? ? ?? ，则当 [ , ]? ? ? ? ?? ? ?时， 准则 (3.4.1)和 (3.4.4)同时 成立 .
算法 3.7（ Wolfe-Powell 方法）
步 1： 给 定参数 (0,1/ 2)?? ,??? ，令 0a? ， 计算 ()a? 和 ()a?? ， 给定初始 试探 点
0 a?? ， 置 0k? .
步 2： 计算 ()k?? ，若 ( ) (0 ) (0 )kk? ? ? ?? ? ???，则转步 3；否则 计算 ()a? ，并取
1
2( ) ''( )
2 [ ( ) ( ) ''( ) ( ) ]kk kkaaa a a a??? ? ? ? ? ?? ??? ? ? ?
，
令 kb ?? ， 转步 4.
步 3： 计算 ''( )k?? ，若 ( ) (0)k? ? ????? ， 则 停止迭代 并 输出 k? ；否则 ，如果
( ) ( ( ) ( ) ) 0kkaa? ? ? ???? ? ?，
则 取
第三章 一维搜索
48 最优化理论与方法 [乌力吉 ]
1 ()( ) ( )kk k kk a a?? ? ? ?? ? ?? ? ??? ???
，
令 ka ?? ， ( ) ( )ka ?????? ；否则，当 右边界 b 未定时，取 1kkh??? ??，并令
2hh? ；当右边界 b 已 定时，取 1 ( ) / 2kkb??? ??.
步 4： 令 1kk??，转步 2.
注 这里 k? 的迭代 用了两点二次插值公式， 主要 是 考虑到 插值法 的 局部 超线性 收敛性 ，
以及 单步 计算成本 低廉 的 特性 .
在第二步采用了两点二次插值公式（一）， 成本 仅需 计算 ()a? ， 且 当 程序运行到这一步
时， 有
( ) (0 ) (0 )kk? ? ? ?? ? ???，
若 0a? ， 则 显然满足 1( ) ( )kk? ? ? ?? ? 的条件； 若 0a? ， 则由 程序 步骤 可知 ， 这时
( ) (0) 0a? ??????, ( ) (0) (0)aa? ? ? ????，
故 由 ??? 和 k a?? 可知
( ) ( ) (0 ) ( ) (0 )kkaa? ? ? ? ? ? ? ?? ? ? ?
(0 ) ( ) ( ) (0 ) ( ) ( )kka a a a?? ? ? ? ? ?? ??? ? ? ? ? ?，
仍然满足 1( ) ( )kk? ? ? ?? ? 的条件，且保证 1k a?? ? .
在第 三 步采用了两点二次插值 公式（ 二 ），当程序运行到这一步时，有
( ) (0 ) (0 )kk? ? ? ?? ? ???， ( ) (0 ) 0k? ???????，
因此， 非凸函数并 不一定满足 1( ) ( )kk? ? ? ?? ? 的条件， 也不能 保证 1kk??? ? . 为此，在程
序中我们加入了 ( )( ( ) ( ))kkaa? ? ? ?????大于零 与否 的 判定条件 .
§3.4.3 简单准则和后退方法
在 牛顿类算法中，我们 有时仅采用 Armijo 准则
( ) ( ) ( )k k k k T kkkf x d f x f x d? ? ?? ? ? ?， (3.4.1)
§ 3.4 不精确一维搜索方法
最优化理论与方法 [乌力吉 ] 49
称之为简单准则，而后退方法则是建立在这种准则之下的一种不精确搜索算法 . 其基本思想
是 置 1?? ，若 kkxd?? 满足（ 3.4.1） ，则 令 k??? ，结束迭代；否则置 ? ??? ， 继续检
验其是否满足（ 3.4.1）， 直到 kkxd?? 满足（ 3.4.1），其中 01???是常数，一般取 1/2?? .
§3.4.4 不精确一维搜索的收敛性定理
在下面的理论分析中，我们总要求 搜索方向 kd 与 ()kfx?? 的 夹角 /2k? ? ???对每个
k 都成立，其中 (0, / 2)??? 是 常数 .
定理 3.4.2 设在 下降 算法 2.1 中步长 k? 满足 Armijo-Goldstein 准则或 Wolfe-Powell 准则，
若 ()fx? 在水平集 ? ?0| ( ) ( )L x f x f x??上一致连续 ， 则或者对某个 k 有 ( ) 0kfx??，或
者有 lim ( )k
k fx?? ???
，或者有 lim || ( ) || 0k
k fx?? ??
.
证 若对某个 k 有 ( ) 0kfx??，或者有 lim ( )k
k fx?? ???
，则结论成立 . 故不妨设对任意
k 都 有 ( ) 0kfx??且 下降序列 { ( )}kfx 有下界，因此 lim ( )k
k fx??
存在，从而有
1lim [ ( ) ( ) ] 0kkk f x f x??? ??，
于是，由 Armijo 准则可知， ( ) 0 ( )k T kk f x d k?? ? ? ? ?.
下面用反证法证明 lim || ( ) || 0k
k fx?? ??
.
假设 lim || ( ) || 0k
k fx?? ??
不成立， 即存在正数 0?? 和无限指标集 1K ，使对任意 1kK? 都
有 ()kfx ???成立，故对任意 1kK? ， 由 /2k? ? ??? ，有
c o s c o s ( ) s in2k ?? ? ?? ? ?，
再由
( ) ( ) c o s 0k T k k kk k kf x d f x d? ? ?? ? ? ? ? ?，
我们有
10 , ( , )kk d k K k? ? ? ? ?
.
另一方面，由 ()kfx? 的一致连续性 ，我们有
第三章 一维搜索
50 最优化理论与方法 [乌力吉 ]
1( ) ( ) ( ) ( )k k k T k kkkf x f x f x d d? ? ?? ? ? ? ?，
故有
1 ()( ) ( ) 1
( ) ( )
kkk k
k T k k T k
df x f xf x d f x d?????? ??? ? ? ?，
注意到 当 1kK? ， k?? 时，有
( ) ( ) 0
( ) ( )
k k kk k k
k T k k T kkkkk
d d d
f x d f x dd
? ? ? ? ?
???? ? ?? ? ? ?
，
由此得
1( ) ( ) 1
()
kk
k T kkf x f xf x d?
?? ?
??
，
但 这 与 Goldstein 准则 (3.4.2)矛盾，矛盾表明 lim || ( ) || 0k
k fx?? ??
.
类似的，若采用 Wolfe-Powell 准则， 则 由 ()kfx? 的连续性， 有
( ) ( ) ( )k k T k k T k kk k k kf x d d f x d d? ? ? ? ?? ? ? ? ?，
由此得
1() 1 ( , )()
k k T kkk
k T kkf x d d k K kf x d????? ? ? ? ??
，
但 这与 Wolfe—Powell 准则 (3.4.3)矛盾，矛盾表明 lim || ( ) || 0k
k fx?? ??
.
定理 3.4.3 设 在下降算法 2.1 中步长 k? 满足 Armijo 准则 (3.4.1)，若 存在正常数 ,,mM? ，
使对任意 , nyz?? ，有
222 ()Tm y y f x y M y? ? ?，
? ? 2( ) ( ) ( )Ty z f y f z y z?? ? ? ? ? ?，
则
2( ) ( ) 1k k k kkkf x f x d dMm????? ? ? ?.
证 若 ( ) 0k k T kkf x d d?? ? ?，则
§ 3.4 不精确一维搜索方法
最优化理论与方法 [乌力吉 ] 51
0( ) ( ) ( )kk k k k k T kkf x f x d f x td d d t??? ? ? ? ? ??
0 [ ( ) ( ) ]k k k k k T kkf x d f x td d d t? ?? ? ? ? ? ??
20 ()k kk t d dt? ?????
2212 1kkddMm??? ? ??? ?.
若 ( ) 0k k T kkf x d d?? ? ?， 由 ( ) 0k T kf x d??知， 则 必存在 0k????，使得
( ) 0k k T kf x d d?? ? ?，
在 kkxd?? 处将函数 Taylor 二阶 展开， 并利用命题的条件，我们 有
21( ) ( ) 2k k k kf x f x d M d??? ? ?，
21( ) ( ) ( )2k k k k kkkf x d f x d m d? ? ? ?? ? ? ? ?，
故 由 ( ) ( )k k kkf x d f x???可知， 22()kkkM d m d? ? ???，由此解得
11 kMm??? ? ，
于是， 由 k? 满足 armijo 准则， 我们有
( ) ( ) ( ) [ ( ) ( ) ]k k k k T k k k k T kk k kf x f x d f x d f x d f x d? ? ? ? ? ?? ? ? ? ? ? ? ? ? ?
22 1kkkkddMm??? ? ? ? ??? ?.
定理 3.4.4 设函数 ()fx 连续可微， ()fx? 满足 Lipschitz 条件 . 若 ()kkf x d?? 对
0?? 有下界，则对满足 Wolfe-Powell 准则的任何 0k?? ，均有
2 2( 1 )( ) ( ) ( ) c o s , ( )k k k k k kkf x f x d f x d f xM??? ?? ? ? ? ? ?.
证明略 .
第三章 一维搜索
52 最优化理论与方法 [乌力吉 ]
|
|
