第 五 章 共轭梯度法 和拟牛顿法
§5.1 共轭方向法
共轭方向法是无约束最优化问题的一类重要算法 ， 它一方面克服了最速下降法中，迭代
点列呈锯齿形前进，收敛慢的缺点，同时又不像牛顿法中计算牛顿方向耗费大量的工作量，
尤其是共轭方向法具有 二次终止性 .
设 G 是 nn? 对称正定矩阵， 1d , 2d 是 n 维非零向量，若 12( ) 0Td Gd ? ， 则称 1d , 2d 是
G 共轭的 ；如果 n? 中一组非零向量 12, , , md d d? 两两共轭，即 ( ) 0i T jd Gd ? ()ij? 则
称向量组 12, , , md d d? 是 G 共轭的 .
显然， 当 GI? 时，共轭性就变为正交性， 因此 共轭是正交概念的推广 . 不难证明， 若
12, , , md d d? 是 G 共轭的 ，则它们 必定 线性无关 .
算法 5.1（ 正定二次函数的 共轭方向法）
步 1： 给出初始点 0x 和初始下降方向 0d ， 置 0k? ；
步 2： 求解
0min ( )kkf x d? ?? ?
，得最优解 k? ；
步 3： 令 1k k kkx x d?? ?? ，如果 1|| ( ) || 0kfx???，则停止迭代，输出 1kx? ；
步 4： 给出共轭方向 1kd? 满足 1( ) 0k T jd Gd? ? ， 0,1, ,jk? ? ，置 1kk??，转步 2.
定理 5.1.1 对于正定二次函数
1() 2 TTf x x G x r x c? ? ?， (5.1.1)
采用精确线搜索的 共轭方向法至多经过 n 步 就能达到目标函数的最优解，且 每个 迭代点 1ix?
是 ()fx在线性流形
0
0{ | , , 0 , 1 , , }
i j
jjjx x x d j i???? ? ? ? ?? ?? ? ?
(5.1.2)
中的极小点 .
第五章 共轭梯度法和拟牛顿法
68 最优化理论与方法 [乌力吉 ]
证 首 先证明对所有的 1in??，都有
1 0Tjigd? ? ， 0,1, ,ji? ? . (5.1.3)
事实上，由于 ()fx是二次函数，因而有
? ?11 k k kk k kg g G x x G d??? ? ? ? ?.
故 当 ji? 时，有
? ?1 1 11i TT j T j ji j k kkjg d g d g g d? ? ???? ? ??1 1 ( ) 0iT j k T jjkkjg d d G d?? ??? ? ?? ；
而 当 ji? 时，由精确搜索性质知 1 0Tjigd? ? .
再证算法的有限 步 终止 . 若有某个 1 0ig? ? （ 1in??），则结论 成立 ， 否则， 由上面已
证则必有 0Tjngd? ， 0,1, , 1jn??? . 由于 0 1 1, , , nd d d ?? 构成 n? 的一组基， 故 0ng? ，
这表明 至多经过 n 次精确 线搜索 即可获得最优解 .
最后 证明定理的后半部分 . 由于 ()fx是正定二次函数， 故函数
001
0( , , , ) ( )
i j
ijjt t t f x t d? ??? ??
是线性流形 (5.1.2)上的 严格 凸函数 . 由此可知，
101 01( , , , )m in ( , , , )ii it t t R t t t???? ?
的最优解就是它的
唯一 驻点，即
0
0( ) 0
i j T j
jjf x t d d?? ? ??
， 0,1, ,ji? ? (5.1.4)
的解 . 注意到在 1ix? 处 等式 (5.1.3)成立， 故 当 0 1 0 1( , , , ) ( , , , )iit t t ? ? ????时 ， 等式 (5.1.4)
成立，从而 01( , , , )it t t? ? 取得极小， 这表明 10
0
iij
jjx x d?? ????
是 ()fx在线性流形 (5.1.2)
上的极小点 .
§ 5.2 共轭梯度法
最优化理论与方法 [乌力吉 ] 69
§5.2 共轭梯度法
§5.2.1 共轭梯度的构造
下面考察正定二次函数
1() 2 TTf x x G x r x c? ? ?， (5.2.1)
其中 G 为 nn? 正定矩阵， 显然 ()g x Gx r??，且 ? ?1
1 k k kk k kg g G x x G d??? ? ? ? ?
.
针对正定二次函数 ()fx，构造共轭方向的思想如下：
（ 1）给定初始点 0x ，首先取 0 0dg?? ，令 1 0 00x x d??? ，其中 0? 为精确线搜索的
步长 . 由精确线搜索可知 ， 01 0 1 0TTg g g d? ? ?.
（ 2） 令 1010d g d??? ? ， 并 适当选择 0? ，使 得 10( ) 0Td Gd ? ， 则有
0 1 1 01 1 1
0 0 0 0 1 0 0 0()( ) ( ) ( )
TTT
T T Tg g gg G d g gd G d d g g g g? ?? ? ??
.
由 定理 5.1.1 可知， 12 0Tgd? ， 02 0Tgd? ， 故 由 0d 与 1d 的构造 知 210Tgg? ， 200Tgg? .
（ 3） 再令 2 0 12 0 1d g d d??? ? ? ?，适当选择 0? , 1? ，使得 2( ) 0Tid Gd ? ， 0,1i? ，
由此得
0 0?? ， 2 2 1 2 21 1
2 1 1 1
()( ) ( )TTg g g g gd g g g g? ????.
（ 4） 一般地，在第 k 次迭代中，令 1
0
kki
kiid g d?
?
?? ? ??
适当选取 i? ， 使得 ( ) 0k T id Gd ? ，
0,1, , 1ik??? . 由定理 5.1.1 知 0Tikgd? ， 0,1, , 1ik??? ，再由 ig 与 id 的关系得
0Tkigg? ， 0,1, , 1ik??? ，因此
1
1
11
0 , 1 , 2 , , 2 ,()
, 1 .( ) ( ) ( )
T i T
k k i i Ti
i T i i T kk
ii T
kk
ikg G d g g g
gg ikd G d d g g
gg
? ?
?
??
???? ?
? ? ? ? ??? ?
?
?
（ 5.2.2）
于是，我们得到 共轭梯度法的迭代公式为 1k k kkx x d?? ?? ，其中 kd 为共轭方向， k? 为
第五章 共轭梯度法和拟牛顿法
70 最优化理论与方法 [乌力吉 ]
最佳步长因 子 . 对二次函数 取 / ( )T k k T kkkg d d G d? ?? ， 而对非二次函数，则采用精确 线搜
索 得到 k? .
共轭方向的修正公式为
1 1kkkkd g d?? ?? ? ? ， （ 5.2.3）
其中， k? 由下面诸式之一计算：
（ 1） 11
1
()( ) ( )Tk k kk kT
kk
g g gd g g? ??
?
?? ? （ Crowder-Wolfe公式） （ 5.2.4）
（ 2） 11Tkk
k Tkkgggg? ???
（ Fletcher-Reeves 公式） （ 5.2.5）
（ 3） 11()Tk k k
k Tkkg g ggg? ????
（ Polak-Ribiere-Polyak 公式） （ 5.2.6）
（ 4） 11
()
Tkk
k kT kggdg? ????
（ Dixon 公式） （ 5.2.7）
（ 5） 11
1( ) ( )
Tkk
k kT kkggd g g? ???? ?
（ Dai-Yuan 公式） （ 5.2.8）
对二次函数而言，上述 五 个公式都是等价的 ， 而且求得的搜索方向均为共轭方向； 但对
非二次函数， 将导出互不相同的算法，而且据此求出的搜索方向不再保证是共轭的 . 事实上，
此时不存在一个常值正定矩阵 G ，共轭的提法都已无意义 .
§5.2.2 共轭梯度法的性质
定理 5.2.1 对于正定二次函数，采用精确 线搜索 的共轭梯度算法，必定经过 mn? 步
迭代后终止 . 且对 每个 1 im?? ，下列关系式成立：
（ 1） ( ) 0i T jd Gd ? ， 0,1, , 1ji??? ； （ 5.2.9）
（ 2） 0Tijgg? ， 0,1, , 1ji??? ； （ 5.2.10）
（ 3） ()i T Ti i id g g g?? ； （ 5.2.11）
（ 4） 0 1 0 0 0[ , , , ] [ , , , ]iig g g g G g G g???； （ 5.2.12）
§ 5.2 共轭梯度法
最优化理论与方法 [乌力吉 ] 71
（ 5） 01 0 0 0[ , , , ] [ , , , ]iid d d g G g G g???. （ 5.2.13）
证 先用归纳法 证明 (5.2.9)-(5.2.11).
对于 1i? ，容易验证 (5.2.9)-(5.2.11)成立 . 现假设这些关系式对某个 im? 成立，下面证
明对于 1i? ，这些关系式仍然成立 . 事实上，对 11 ()i i ii i i ig g G x x g G d??? ? ? ? ? ?左乘
()iTd ，并注意到 0( ) ( )T i Ti i ii i T i i T ig d g gd G d d G d? ? ? ? ?， 得
111( ) ( ) ( )T T i T T i T j ji j i j i j i j i jg g g g d G g g g d G d d? ? ? ???? ? ? ? ?.
当 ji? 时， 上式 成为
1 ( ) 0()
TT T i T iii
i j i i i T iggg g g g d G dd G d? ? ? ?
，
当 ji? 时，由归纳法假设可知
111( ) ( ) 0T T i T j ji j i j i jg g g g d G d d?? ???? ? ? ?，
于是 (5.2.10)得证 .
再由共轭梯度法的迭代公式及 i? 是最优步长 ，有
11 11( ) ( ) ( )jji T j T j i T j T i T ji i i i
j
ggd G d g G d d G d g d G d?? ? ??
??
?? ? ? ? ?，
当 ji? 时， 由 (5.2.10)和归纳法假设知 1( ) 0i T jd Gd? ? ； 当 ji? 时，由 (5.2.10)及 i? 和 i? 的
定义 知
1 1 1 1 1( ) ( ) ( ) 0TTi T i i T i i T ii i i i
i i i i
g g g gd G d d G d d G dg g g g? ? ? ? ?? ? ? ?，
于是 (5.2.9)得证 .
又由 id 的构造知， id 是 01, , , ig g g? 的线性组合，故有 (5.2.10)知
1 1 1 1 1 1 1( ) ( )i T T i T Ti i i i i i id g g g d g g g?? ? ? ? ? ? ?? ? ? ? ?，
于是 (5.2.11)得证 .
下面利用归纳法证 明 (5.2.12)与 (5.2.13).
当 1i? 时，由 01 0 0 0 0 0g g G d g G g??? ? ? ?易见 0 1 0 0[ , ] [ , ]g g g g? .再由 0 0dg??
第五章 共轭梯度法和拟牛顿法
72 最优化理论与方法 [乌力吉 ]
及 101 0 1 0 0d g d g g??? ? ? ? ? ?易见 01 0 1 0 0[ , ] [ , ] [ , ]d d g g g G g??.
故当 1i? 时， (5.2.12)与 (5.2.13)成立 .
假定 (5.2.12)与 (5.2.13)对 i 成立 . 下面证明 结论对 1i? 也成立 .
由于 1 ii i ig g Gd?? ?? ，而从归纳法假设知 0 0 0, [ , , , ]iiig d g G g G g? ?， 故有
11 0 0 0[ , , , ]iig g G g G g?? ? ?，
但
011 0 0 0[ , , , ] [ , , , ]iiig g G g G g d d d? ????，
若不然， 由 011 [ , , , ]iig d d d? ? ? 及 1 0Tjigd? ? ， 0,1, ,ji? ? ， 则必有 1 0ig? ? ，矛盾 . 因
此
10 1 1 0 0 0[ , , , ] [ , , , ]iig g g g G g G g?? ???,
再由 1 1iiiidgd?? ?? ? ? ，可得
0 1 1 10 1 1 0 0 0[ , , , ] [ , , , ] [ , , , ]iiid d d g g g g G g G g?????? ? ? .
注 （ 1） 上面定理中出现的这些生成子空间通称为 Krylov 子空间；
（ 2） 在共轭梯度法中， 1 1kkkkd g d?? ?? ? ? ，若采用精确 线搜索 ，则 k? 不论采用哪
种公式计算，都有
11 1 1 1 1 1 0T k T T k Tk k k k k k kg d g g g d g g??? ? ? ? ? ?? ? ? ? ? ?，
即 1kd? 总是下降方向，若不采用精确 线搜索 ，则不一定了；
（ 3） 对 Dixon 公式，使用不精确搜索准则
1T k T kkkg d g d?? ??
， (0,1)?? 能保证搜
索方向总是下降的 . 事实上，由
1 111 ()Tkkkkk kT
k
ggd g ddg? ???? ? ? ，
有
1 11 1 1 1 TkT k T kk k k Tk
k
gdg d g g gd? ?? ? ? ??? ? ?????，
而 由 1T k T kkkg d g d?? ?? 知 1T k T kkkg d g d? ?? ，从而
§ 5. 3 共轭梯度法的收敛性
最优化理论与方法 [乌力吉 ] 73
1 1TkkTk
k
gdgd? ?? ，
由此即得 11 0Tkkgd?? ? ， 故 1kd? 为下降方向；
（ 4） Fletcher－ Reeves 公式最为简洁，使用得最多；
（ 5） 共轭梯度算法用于非二次函数时，没有有限终止性质，一般经过 n 次搜索后，就
取一次负梯度方向，称再开始 . Polak-Ribiere-Polyak 具有自动再开始的特点，事实上，当
算法改进不大时，会出现 1kkgg? ? ，这时用 Polak-Ribiere-Polyak 公式计算出的 0k?? ，
从而导致 1 1k kdg? ??? .
算法 5.2（再开始 FR 共轭梯度法）
步 0： 给出初始点 0x ，容许误差 0?? ；
步 1： 计算 00 ()g f x? ，置 0k? ；
步 2： 若 0|| ||g ?? ，停止迭代，输出 0x ，否则，令 0 0dg?? ；
步 3： 求
0min ( )kkf x d? ?? ?
的最优解 k? ；
步 4： 令 1k k kkx x d?? ?? ， 1kk??；
步 5： 计算 ()kkg f x?? ，若 || ||kg ?? ，停止迭代，输出 kx ；
步 6： 若 kn? ，令 0 kxx? ，转步 1；
步 7： 计算 11/TTk k k kg g g g? ??? ， 1kkkd g d? ?? ? ? ；
步 8： 若 0Tkkgd? ，令 0 kxx? ，转步 1，否则转步 3.
§5. 3 共轭梯度法的收敛性
由 上一节的 讨论 可知 ，当共轭梯度算法用于正定二次函数时必定有限 步 终止 . 本节研究
将其用于一般非二次函数时的收敛性问题 .
§5. 3.1 共轭梯度法的 全局 收敛性
定理 5.3.1 设水平集 ? ?0( ) ( )L x f x f x??有界， f 是 n? 上连续 可微 的凸函数 . 如果
第五章 共轭梯度法和拟牛顿法
74 最优化理论与方法 [乌力吉 ]
{}kx 是由 采用精确线搜索的 Fletcher-Reeves 再开始 共轭梯度算法产生的迭代点列 ， 则
（ 1） { ( )} kfx 为单调下降序列，且 lim ( )k
k fx??
存在 .
（ 2） {}kx 的任意聚点都是最优解 .
证 （ 1） 在算法迭代过程中，由于每隔 n 次采用一次再开始措施 . 因而搜索方向 或为 共
轭梯度方向， 或为 最速下降方向 ， 但 无论 哪种情形都有
2 0Tkkkg d g? ? ?.
因而 { ( )}kfx 单调下降， 由于 L 有界，故 { ( )}kfx 有下界，因此 lim ( )k
k fx??
存在，记为 f .
（ 2） 由 { ( )}kfx 单调下降 知 {}kxL? ，故 {}kx 是有界 点列 .
设
1{}k Kx
是 {}kx 中 满足 1kkkkx x g?? ?? 的 点 kx （即再开始的点）全体构成的 子列 ，
由于
1{}k Kx
有界，故存在收敛子列
2{}k Kx
， 使得
2 ,lim
kk K k xx? ?? ? .
由于
21{}k Kx?
也是有界点列，故存在子列
31{}k Kx?
，使
3
1,lim kk K k xx?? ?? ? ，且
( ) ( ) l im ( ) kkf x f x f x f??? ? ?.
下面用反证法证明 ( ) 0fx??. 假设 不然，设 ( ) 0fx??，则对充分小的 ? ，有
( ( ) ) ( )f x f x f x?? ? ?，
注意 到对任意 0?? 和 3kK? ， 有
1( ) ( ) ( ) ( )k k k k kk k k kf x f x d f x g f x g? ? ?? ? ? ? ? ? ?，
令 k?? ，则有 ( ) ( ) ( )f x f x g f x?? ? ?，但这 与 ( ) ( )f x f x? 矛盾， 矛盾表明必
有 ( ) 0fx??. 于是， 由 ()fx的凸性 知 x 是 min ( )
nx fx??
的 最优解 .
进一步地，对点列 {}kx 的任一 聚点 ?x ，必存在 {}kx 的子列
0{}k Kx
，使得
0 , ?lim
kk K k xx? ?? ? ，
由此得
0 ,?( ) ( l i m ) l i m ( ) m i n ( )n
kkk K k k xf x f x f x f x? ? ? ? ? ?? ? ? ?，
这表明 ?x 也是 min ( )
nx fx??
的 最优解 .
注 从 这个定理的证明过程易见 ， 上述收敛 结果 对其它几种 再开始 共轭梯度算法也是成
§ 5. 3 共轭梯度法的收敛性
最优化理论与方法 [乌力吉 ] 75
立的 .
定理 5.3.2 设 ()fx二阶连续可微，水平集 ? ?0( ) ( )L x f x f x??有界 . 若 存在常数
0m? ，使得 不等式
2 2 ()Tm y y f x y??
对 任意 xL? 和 ny?? 成立， 则采用精确 线 搜索的 Polak-Ribbiere-Polyak 共轭梯度 法产生的
点列 {}kx 收敛 到 ()fx的唯一极小点 .
证 只 需 证明 存在正数 ? ，使得 不等式
T k kkkg d g d?? ? ? (5.3.1)
对 任意 k 成立即 可 . 这是 因为不等式 (5.3.1)成立 保证 定理 3.2.3 的夹角条件成立，故由定理
3.2.3 知， 必有 lim ( ) 0k
k fx????
，若 x 是 {}kx 的 聚点 ， 则 由 ()fx? 的连续性， 有 ( ) 0fx??.
再 由 ()fx在水平集 L 上一致凸知， {}kx 的聚点必唯一，若不然，设 ?x 是 {}kx 的另一聚点，
则也有 ?( ) 0fx??，于是
2? ? ? ?0 ( ) ( ( ) ( ) ) ( ) ( ) ( )TTx x f x f x x x f x x?? ? ? ? ? ? ? ? ?，
但这与一致凸的假设矛盾 . 故 {}kx 收敛到 ()fx的唯一极小点 . x .
下面证明不等式 (5.3.1)成立 .
由于采用了精确 线搜索 ，故有 2Tkkkg d g?? ， 因而 不等式 (5.3.1)等价于
kkgd?? . （ 5.3.2）
由于
11 1 1 1 1 11 1 1 1 10 ( ) ( )T k T k T k k T k kk k k k k kg d g d g d d G x t d d d t??? ? ? ? ? ?? ? ? ? ?? ? ? ? ??,
故有
21 11
1 1 1 1 111( ) ( )
Tk kk
k k T k k T kkk
ggdd G d d G d? ? ??
? ? ? ? ???? ? ?
， （ 5.3.3）
其中 1
1 1 1 10 ()k k k kG G x t d d t?? ? ? ????
. 再注意到
1 1 1 1 11 1 1 1 10 ()k k k kk k k k k kg g G x t d d d t G d? ? ?? ? ? ?? ? ? ? ?? ? ? ?? ，
第五章 共轭梯度法和拟牛顿法
76 最优化理论与方法 [乌力吉 ]
我们 有
111
11 211 1()
T T kk k k k k
kkTkk kg g g g G dgg g??
???
???? ????
，
结合 (5.3.3)， 得
1111
1 211 11()
T k kk k k k
k k T k kk
g G d g G d
d G d md?
????
? ?? ????
.
又由 L 有界 知 ，存在常数 0M? ， 使得 不等式 ()G x y M y? 对任意 xL? 和 ny??
成立， 故
1
1 2 11
kk k
k kk
g M d gM
m dmd?
?
? ????
，
由此得
11 ( 1 )kkk k k k kMMd g d g g gmm? ??? ? ? ? ? ?，
取 1(1 )Mm? ??? ，则不等式 (5.3.2)得证，从而 定理得证 .
定理 5.3.3 若 k? 由不精确 线搜索 的 Wolfe-Powell 准则产生， 则 Fletcher-Reeves 共轭梯
度算法具体下降性质 ，即 0Tkkgd? 对任意 k 成立 .
证明： 先 用归纳法证明不等式
2002
Tkkkjjk
jjk
gdg??
??? ? ? ? ???
（ 5.3.4）
成立， 其中 (0,1/ 2)?? 是 W-P 准则中的 ? .
当 0k? 时， （ 5.3.4）式 成为等式，故结论成立 . 假设对任何 0k? ， （ 5.3.4） 式成立 ，
现考虑 1k? 情形 . 由于
11 1 1 1 1
2 2 2 21 1 1() 11
T k T k T k T kk k k k k k
kk k k kg d g g d g d g dg g g g? ?
?? ? ? ? ?
? ? ?
??? ? ? ? ? ? ?
及
1TTk k k kg d g d?? ??
，故 有
11
2 2 2111
T k T k T kk k k
k k k
g d g d g dg g g????
?
? ? ? ? ? ?.
再由归纳法假设，有
§ 5. 3 共轭梯度法的收敛性
最优化理论与方法 [乌力吉 ] 77
1
20011
Tkkkjj k
jj k
gdg? ? ? ??
??? ? ? ? ? ? ???
1 11
22 001 1 1 2
T k T k kkjjkk
jj
g d g dgg ? ? ? ?? ??
???? ? ? ? ? ? ? ? ? ???
,
故不等式 (5.3.4)得证 . 由于 (0,1/ 2)?? ，故有
0
1 1 22 2 011k j
j
?? ??
?
??? ? ? ? ? ? ???? ，
从而由不等式 (5.3.4)，我们 得到 0Tkkgd? 对任意 k 成立 .
定理 5.3.4 设 ()fx二阶连续可微，水平集 ? ?0( ) ( )nL x f x f x? ? ?? 有界 . 设 k? 由
Wolfe-Powell 准则确定，那么 Fletcher-Reeves 共轭梯度算法产生的点列 全局收敛 ，即有
lim inf 0kk g?? ? . （ 5.3.5）
证 由 Wolfe-Powell 准则及 不等式 (5.3.4)得
211111T k T kk k kg d g d g?? ?????? ? ? ?，
结合 11kkkkd g d? ??? ? ? 及 2
1 211
1
T kkk
k Tkk
k
ggggg
g? ? ?? ???
，我们有
222 1 2 1112k T k kk k k kd g g d d??????? ? ?
222 2 22 1 2 11121 ()11 kkk k k k kg g d g d?????????? ? ? ? ???，
递推 下去， 可得
2 24
0
1( ) ( )1 kk kj
jd g g
?? ?
?
?? ? ?. （ 5.3.6）
下面用反证法证明 （ 5.3.5） 成立 . 若不然，则存在常数 0?? ，使得对充分大的 k ，都
有 0kg ??? .
由于 kg 在水平集 L 上有界，从 （ 5.3.6） 可知，存在常数 1c ，使得 2 1kd ck? . 因此
2 0 12c o s ( 2 ) ( )1
T k T k kk k kjkk
k k k k kjk k
g g gg d g dg d d d dg ??? ?
?
?? ? ? ? ? ? ? ?? ，
第五章 共轭梯度法和拟牛顿法
78 最优化理论与方法 [乌力吉 ]
2 2
2 2 2 22
1
1 2 1 2 1c os ( ) ( )11 k
k kk k k k
g c
c k kd? ? ?? ????? ? ?? ? ? ?
，
这表明 级数
2cos kk ??
发散 . 若设 M 为 ()Gx 在 L 上的上界，则 有
21T k T k kk k kg d g d M d?? ??，
结合 Wolfe-Powell 准则
1T k T kkkg d g d?? ??
，得
21T k T k T k kk k k kg d g d g d M d???? ? ?，
由此得
21 Tkkkk gdMd?? ???
.
于是， 由 Wolfe-Powell 准则 ，我们有
2 2 2 21 ( 1 ) ( 1 ) c o s c o sk k k k k kf f g fMM? ? ? ?? ? ?? ??? ? ? ?，
这表明 { ( )}kfx 单调下降 ，而由 ()fx 连续可微且水平集有界知 { ( )}kfx 有下界，故
lim ( )kk fx?? 存在 . 再由
2(1 ) 0M???? ? 及 22 1(1 ) c o s k k kffM?? ?? ?? ??，
推得
2cos k
k ??
收敛，矛盾 . 矛盾表明 定理结论成立 .
§5 .4 拟牛顿法
牛顿法具有 收敛速率 快的 优 点，但需要计算 Hesse 矩阵 及其 逆 矩阵 ， 单步 计算量大 . 本
章介绍的拟牛顿法将用较简单的方式得到 Hesse 矩阵或其逆的近似，一方面 减少了 计算量，
另一方面 保证了 较快的 收敛速率 ，这类算法是无约束最优化问题最重要的求解方法 .
§5.4.1 拟牛顿 法的基本思想
设 ()fx在 n? 上二次可微，为了获得 Hesse 矩阵 2( ) ( )G x f x?? 在 1kx? 处的近似， 考
察 ()fx? 在 1kx? 处 的 一阶 Taylor 展开式 111( ) ( )kkkg x g G x x ???? ? ?， 取 kxx? ，则 有
111()kkk k kg g G x x ???? ? ?，
§ 5.4 拟牛顿法
最优化理论与方法 [乌力吉 ] 79
令 1kkks x x???， 1k kky g g???， 则有
1k k ky G s?? 或 11k kkG y s?? ? .
因此，我们要求构造出的 Hesse 矩阵的近似 1kB? 或 Hesse 矩阵逆的近似 1kH? 应 分别满
足
1k k kB s y? ? 或 1k k kH ys? ? ， （ 5.4.1）
我们 称 其 为 拟牛顿条件 .
算法 5.3（拟牛顿 法 ）
步 1： 给出初始点 0x?? ， 初始近似矩阵 0HI? ， 容许误差 0?? ， 置 0k? ；
步 2： 若 kg ?? ，停止 计算，输出 kx ；
步 3： 计算 搜索方向 k kkHd g?? （或从 kkBd g?? 解出来）， 这就是 拟 牛顿方向 ；
步 4： 沿方向 kd 进行 线搜索 ，确定步长 0k?? ；
步 5： 置 1k k kkx x d?? ?? ；
步 6： 在 满足拟牛顿条件 下， 校正 kH 产生 1kH? 更接近 11kG?? ；
步 7： 置 1kk??，转步 2.
注 拟牛顿 算法 5.3 较之牛顿法有下述优点： （ 1） 仅需梯度 ， 牛顿法需 Hesse 矩阵 ； （ 2）
kH 保持正定，因而方向具有下降性质 ， 而牛顿法中 kG 可 能不定 ； （ 3） 每次迭代需 2()On 次
运算，而牛顿法需 3()On 次运算 .
正如牛顿法中牛顿方向 1kkGg?? 是在椭球范数 ||||
kG?
下的最速下降方向一样， kkHg? 也
可 看成是 在椭球范数
1||||kH??
下的最速下降方向，也就是在 空间某种特定度量（ 尺度 ） 意义下
的最速下降方向 . 由于每次迭代 kH 都在变化，因而度量也在变化 . 正因为如此， 常 称拟牛
顿 算 法为变尺度法 .
第五章 共轭梯度法和拟牛顿法
80 最优化理论与方法 [乌力吉 ]
§5.4.2 对称秩一校正公式（ SRI 校正）
设 kH 是 21()kfx?? 的近似 ， 希望对 kH 校正得到 1kH? ，即 1k k kH H E? ??，其中 kE 应
该是一个简单、容易构造且能校正矩阵中每个元素的矩阵，我们自然想到它应该是 一个秩一
矩阵， 这时， kH 的校正公式形如
1 TkkH H uv? ??. （ 5.4.2）
代入 拟牛顿条件 ，有 1 ()Tk k k k k kH y H y u v y s? ? ? ?，取适当的 v ，使得 0T kvy? ，则
有
k k k
T ks H yu vy??
， （ 5.4.3）
将 其 代入 （ 5.4.2） ， 得到校正公式
1 1 () Tk k k k kT kH H s H y vvy? ? ? ?
， （ 5.4.4）
称为一般 Broyden 秩一校正公式 . 特别地，取 kvy? 时，称为 Broyden 秩一校正公式 .
由于 Hesse 矩阵是对称的，故希望 1kH? 也对称，因而取 k k kv s H y?? ， 由此 得
1 ( ) ( )()
Tk k k k k k
kk Tk k k ks H y s H yHH s H y y? ???? ?
， （ 5.4.5）
称 为对称秩一校正 .
定理 5.4.1 设 0 1 1, , , ns s s ?? 线性无关，那么对于正定二次函数，对称秩一校正方法至多
1n? 步终止，即 1nHG?? .
证 首先 用归纳法证明拟牛顿条件的遗传性质，即
i j jHy s? ， 0,1, , 1ji??? .
当 1i? 时，直接由（ 5.4.5） 可知结论成立 . 假定结论对 1i? 成立，现考虑 1i? 情形，
此时
1
( ) ( )() Ti i i i i i j
i j i j Ti i i i
s H y s H y yH y H y s H y y
?
???? ?.
当 ji? 时，直接由 （ 5.4.5） 可得 . 而 当 ji? 时，由归纳法假设，有
§ 5.4 拟牛顿法
最优化理论与方法 [乌力吉 ] 81
( ) 0T T T T T T Ti i i j i j i i j i j i j i j i js H y y s y y H y s y y s s G s s G s? ? ? ? ? ? ? ?，
故当 ji? 时， 有 1i j i j jH y H y s? ??.
再根据以上所得遗传性质，有
n j jHy s? ， n j jHGs s? ， 0,1, , 1jn??? ，
由于 js 线性无关，故有 nHG I? ，即 1nHG?? .
注 证明中对 is 除了要求线性无关外，没有其他条件，因而简单取 i i is Hg?? 也是可以
的 . 这样完全不用一维搜索，并且由 1n n n ns H g G g?? ? ? ?，得到最优解 .
SRI 校正的缺点是不能保证 kH 的正定性，除非始终保持 ( ) 0Tk k k ks H y y??. 当用于
一般函数时，由 k kkd H g?? 算出的搜索方向不能保证是下降方向，这在一定程度上妨碍了
它的应用 .
§5.4.3 DFP 校正
考虑对称秩二校正 1 TTkkH H auu bvv? ? ? ?，代入 1k k kH y s? ? ， 得
TTk k k k kH y a u u y b vv y s? ? ?，
取 kus? ， kkv Hy? ，则 有 1T kau y ? ， 1T kbv y ?? ，由此得
11TT
k k ka u y s y??
， 11
TTk k k kb v y y H y? ? ? ?
，
于是，我们得到 校正公式
1
TTk k k k k k
kk TTk k k k ks s H y y HHH s y y H y? ? ? ?
， （ 5.4.6）
称 为 DFP（ Davidon-Fletcher-Powell） 校正公式 .
注 DFP 公式是最重要的拟牛顿校正公式，有很多重要性质 .
（ I） 对于 采用精确一维搜索正定二次函数：（ 1） 具有有限终止性； （ 2） 拟牛顿条件具
有遗传性质； （ 3） 当 0HI? 时，产生共轭方向和共轭梯度 .
（ II） 对于一般函数 ： （ 4） 校正保持正定性，因而算法具有下降性质； （ 5） 方法具有超
线性 收敛速率 ； （ 6） 当采用精确一维搜索时，对于凸函数，算法具有总体收敛性 .
第五章 共轭梯度法和拟牛顿法
82 最优化理论与方法 [乌力吉 ]
定理 5.4.2 当且仅当 0Tkksy? 时， DFP 校正公式保持正定性 .
证 用归纳法 证明 . 显然 初始 矩阵 0H 正定 . 假设 结论对 k 成立，即 kH 正定，并记 kH
的 Cholesky 分解为 TkH LL? .
下面 讨论 1k? 时的情形，设 , TTka L z b L y??， 则
22
1 ()()( ) [ ]
T T TTT T T Tk k k k k k k
kk T T T Tk k k k k k kH y y H s s s zabz H z z H z z z a ay H y s y b b s y? ? ? ? ? ? ?
， （ 5.4.7）
故 由 Cauchy 不等式 及 题设 0Tkksy? ，有 1 0T kz H z? ? . 当 0z? 时，等式 (5.4.7)右端第一项
等式成立当且仅当 a 与 b 平行 ，亦即当且仅当 z 与 ky 平行 . 而当 z 与 ky 平行 时，便有
,0kzy????. 此时 必有 2 2() 0T Tk kkT
kk
sz sysy ???. 因而，对任何 0z? ，均有 1 0T kz H z? ? ，
故 1kH? 正定 .
注 在 上面定理中，条件 0Tkksy? 是可以满足的 . 事实上， 由于 k kkd H g?? ， kkksd?? ，
由 kH 的正定性， 有 ( ) 0T k T Tk k k k k k k ks g d g g H g??? ? ? ?， 而
11()T T T Tk k k k k k k k ks y s g g s g s g??? ? ? ?.
当采用精确一维搜索时，有 1 0Tkkgs? ? ，从而 0Tkksy? .
而当采用非精确一维搜索（如 Wolfe-Powell 准则）时，只要适当提高搜索精度，就可
使 1Tkksg? 小到所要求的程度，从而有 0Tkksy? .
定理 5.4.3 （ DFP 算法 的二次终止性 ） 设 ()fx是二次正定函数 ， 若采用精确一维搜索，
则 DFP 算法是 具有遗传性质和方向共轭性质，即对于 0,1, , 1im??? ，有
1i j jH y s? ? ， 0,1, ,ji? ? ； 0Tijs Gs ? ， 0,1, , 1ji??? ，
DFP 算法 在 1mn??步迭代后终止 . 若 1mn??，则 1nHG?? .
证 用归纳法证明 . 当 0i? 时，结论显然成立 ，假设 结论对 i 成立 .
下面讨论 1i? 时 的情形， 注意到 1 0ig? ? ，由精确一维搜索及归纳法假设，对于 ji? ，
有
§ 5.4 拟牛顿法
最优化理论与方法 [乌力吉 ] 83
1 1 1 11 1 1( ) 0 0
i i iT T T T T T
i j j j k k j j j k j k jk j k j k jg s g s g g s g s y s s G s? ? ? ?? ? ? ? ? ?? ? ? ? ? ? ? ?? ? ?
，
由 11 1 1 1 1ii i i i is d H g???? ? ? ? ?? ? ? ?及 jjGs y? ，得
1 1 1 1 1 1 0T T Ti j i i i j i i js G s g H y g s??? ? ? ? ? ?? ? ? ? ?，
从而有 1 0Tijs Gs? ? ， 0,1, ,ji? ? ， 这就证明了 方向共轭性质 . 下面 证 遗传性质 ，即 证
2i j jH y s? ? ， 0,1, , 1ji??? .
由 拟牛顿条件可知， 2 1 1i i iH y s? ? ?? ， 而对于 ji? ，由 11 0TTi j i js y s Gs????及
1 1 1 1 0T T Ti i j i j i jy H y y s s G s? ? ? ?? ? ?，
有
1 1 1 1 1 12 1 1
1 1 1 1 1
TTi i j i i i i j
i j i j i j jTTi i i i i
s s y H y y H yH y H y H y ss y y H y? ? ? ? ? ?
? ? ?? ? ? ? ?? ? ? ? ?
.
注 由此定理可知， DFP 拟牛顿法是共轭方向法 . 若取 0HI? ，则初始方向为负梯度方
向，此时方法变成共轭梯度法 .
§5.4.4 BFGS 校正和 PSB 校正
若在 kH 的 DFP 校正公式
()
1
TTD F P k k k k k k
kk TTk k k k ks s H y y HHH s y y H y? ? ? ?
（ 5.4.8）
中实行代换： kkHB? ， kksy? ，即可得到关于 kB 的校正公式
()
1
TTB F G S k k k k k k
kk TTk k k k ky y B s s BBB y s s B s? ? ? ?
， （ 5.4.9）
称 为 kB 的 BFGS（ Broyden-Flecther-Goldforb-Shanno）校正公式 .
对上式 连续两次 应用秩一校正的求逆公式，又得到 kH 的 BFGS 校正公式：
()1 (1 T T T TB F G S k k k k k k k k k k kkk T T T
k k k k k k
y H y s s s y H H y sHH s y s y s y? ?? ? ? ?） （ 5.4.10a）
第五章 共轭梯度法和拟牛顿法
84 最优化理论与方法 [乌力吉 ]
2( ) ( ) ( )()
T T T Tk k k k k k k k k k k k
k k kTTk k k ks H y s s s H y s H y yH s ss y s y? ? ? ?? ? ?
（ 5.4.10b）
( ) ( )T T Tk k k k k kkT T T
k k k k k k
s y y s s sI H Is y s y s y? ? ? ?， （ 5.4.10c）
再将上式中 实行代换： kkHB? ， kksy? ，得 kB 的 DFP 公式
()1 (1 T T T TD F P k k k k k k k k k k kkk T T T
k k k k k k
s B s y y y s B B s yBB y s y s y s? ?? ? ? ?） （ 5.4.11a）
2( ) ( ) ( )()
T T T Tk k k k k k k k k k k k
k k kTTk k k ky B s y y y B s y B s sB y yy s y s? ? ? ?? ? ?
（ 5.4.11b）
( ) ( )T T Tk k k k k kkT T T
k k k k k k
y s s y y yI B Iy s y s y s? ? ? ?. （ 5.4.11c）
对 SRI 校正公式 ()1SRIkH?
()1 ( ) ( )() TS R I k k k k k kkk T
k k k k
s H y s H yHH s H y y? ???? ?， （ 5.4.12）
进行交换后得
1 ( ) ( )()
Tk k k k k k
kk Tk k k ky B s y B sBB y B s s? ???? ?
， （ 5.4.13）
再利用秩一求逆公式， 得到的 1kH? 就是 ()1SRIkH? ，因而 SRI 校正 是自对偶的 .
注 BFGS 校正是迄今为止最好的拟牛顿公式，它不仅具有 DFP 校正所拥有的各种性质，
而且当采用非精确一维搜索时，对于一般函数也具有总体收敛性，但这一结论对 DFP 校正
尚未获得证明 .
Powell 对一般的 Broyden 秩一校正公式采用对称化改造，得到了 PSB 公式 . 其基本思想
是在一般 Broyden 秩一校正公式的基础上，构造一个不断满足对称性和拟牛顿条件的矩阵序
列，然后求出这个矩阵序列的极限，则该极限矩阵是一个满足对称性和拟牛顿条件的矩阵，
从而产生出一个校正公式 .
设 nnB ??? 是对称矩阵，令
1 ()
T
Ty Bs cCB cs???
， 并 将其对称化， 即 令 11
2 2
TCCC ?? .
2C 虽然对称，却不一定满足拟牛顿条件 . 因而重复以上过程产生 矩阵 序列 {}kC ，其中
§ 5.4 拟牛顿法
最优化理论与方法 [乌力吉 ] 85
2 2 1 2 12 1 2 2 2() , 2TTk k kk k kTy C s c C CC C Ccs ??????? ? ?，
可以 证明这个矩阵序列是收敛的，其极限为
2( ) ( ) ( )()
T T T T
TTy B s c c y B s y B s sB B c cc s c s? ? ? ?? ? ?
，
加上下标，则得到一类秩二校正公式
1 2( ) ( ) ( )()
T T T Tk k k k k k k k k k k k
k k k kTTk k k ky B s c c y B s y B s sB B c cc s c s? ? ? ? ?? ? ?
， （ 5.4.14）
这个校正类包括了很多的校正公式，在 （ 5.4.14） 式中，若令 k k k kc y B s?? ， 则得到关于 kB
的对称秩一校正公式（ SR1 公式）；若令 kkcy? ，则得到关于 kB 的 DFP 校正公式；若令
1 11kk k k k
kk
wc y B sww????， 其中 TTk k k k k kw y s s B s? ，则得到关于 kB 的 BFGS 校正；
若令 kkcs? ，则得到 PSB 校正 公式
1 2( ) ( ) ( )()
T T T Tk k k k k k k k k k k k
k k k kTTk k k ky B s s s y B s y B s sB B s ss s s s? ? ? ? ?? ? ?
， （ 5.4.15）
这个校正在理论研究和实际计算中是十分重要的，其缺点是不能保证校正矩阵的正定性 . 值
得指出的是，通过交换 kkHB? ， kkys? ，可得到关于 1kH? 的类似校正公式 .
前面介绍了一些拟牛顿校正公式，以及派生新的拟牛顿法校正公式的方法（如对偶 方 法，
对称技术等） . 有时候，还可利用一些特殊的附加条件推出校正公式 .
BFGS 校正是由 DFP 校正公式经过替换与 秩一矩阵 求逆得到的校正公式 . 事实上对其它
校正公式也可采用类似方法获得新的校正公式 ， 这些新 的派生 公式 称 为原公式的对偶 ， 对偶
方法是 产 生新校正公式的一种 重要 方法 . 若一个校正公式的对偶还等于其自身，则称之为自
对偶 .
将一般的 Broyden 秩一校正公式反复采用对称化、应用秩一校正 使其满足拟牛顿条件，
生成一迭代序列，其极限构成一类新的秩一校正公式，而且很多常见的校正公式都含在这个
类中，特别地得到 PSB 校正公式 .
第五章 共轭梯 度法和拟牛顿法
86 最优化理论与方法 [乌力吉 ]
§5.4.5 Broyden 族 和 Huang 族
上节讨论的 DFP 校正和 BFGS 校正都是对称秩二校正，且都是通过 ky , ks 和 kH 来获得
校正矩阵 1kH? . 下面考虑 DFP 与 BFGS 的加权组合
1 1 1(1 ) D F P B F G Sk k kH H H? ??? ? ?? ? ?， （ 5.4.16）
其中 ? 为参数 ，称之为 Broyden 族校正 公式 . 显然 ，这样得到的校正公式必满足拟牛顿条件 .
容易 看出
1 1 1 ( 1 )D F P T B F G S Tk k k k k k kH H v v H v v? ??? ? ?? ? ? ? ?, （ 5.4.17）
其中 12( ) [ ]T k k k
k k k k TTk k k k ks H yv y H y s y y H y??
.
当 0?? 时， （ 5.4.16） 就是 DFP 校正 ； 当 1?? 时， （ 5.4.16） 就是 BFGS 校正 ； 当
()
Tkk
Tk k k ksys H y y? ? ?
时， （ 5.4.16） 就是 SRI 校正 ；而 当 1
1 ( / )TTk k k k ky H y s y? ? ?
时， （ 5.4.16）
就是 Hoshino 校正 .
类似地， 也 有关于 kB 的 Broyden 族校正
1 1 1(1 )D F P B F G Sk k kB B B? ??? ? ?? ? ? 11 ( 1 )B F G S T D F P Tk k k k k kB w w B w w????? ? ? ? ?， （ 5.4.18）
其中 12( ) [ ]T k k k
k k k k TTk k k k ky B sw s B s s y s B s??
.
注 由于 0Tkkvy? 和 0Tkkws? ，也可以直接验证 Broyden 族校正对任意的 ? 和 ? 都满
足拟牛顿条件 .
定理 5.4.4（ Broyden 族校正二次终止性定理 ）设 ()fx是正定二次函数， G 是其 Hesse
矩阵， 若 采用精确线性搜索， 则 Broyden 族校正具有遗传性质和方向共轭性质， 相应的算法
在 1mn??步迭代后终止 . 若 1mn??，则 1nHG?? .
证明略 .
定理 5.4.5（ Broyden 族校正的正定性 ）设参数 0?? ，当且仅当 0Tkksy? 时， Broyden
族校正公式保持正定性 .
§ 5.5 拟牛顿法的收敛性质
最优化理论与方法 [乌力吉 ] 87
证明略 .
Huang 族是比 Broyden 族更广泛的一类校正公式 . 在 Broyden 族中， {}kH 是对称的 且
满足拟牛顿条件 1k k kH y s? ? . 但 在 Huang 族中取消了对 kH 对称的限制，并将拟牛顿条件
进一步 放松为
1k k kH y s?? ? ， （ 5.4.19）
称 为 广义拟牛顿条件 ，其中 ? 是一个参数 . 为了使 Huang 族拟牛顿法 用 于二次正定函数 时，
所 产生的 搜索 方向共轭 ，进而 具有二次终止性 . 设 Huang 族校正公式 的形式为
1 TTk k k k k k kH H s u H y v? ? ? ?，
其中 ku , kv 满足
1 1 1 2 Tk k k ku a s a H y?? ， Tkkuy?? ， 2 1 2 2 Tk k k kv a s a H y?? ， 1Tkkvy?? .
在上面的方程组中， 含 有 三个自由参数 . 特别地，令 1?? , 12 21aa? ，则 只含一个自由参数 ，
若取 11a 为自由参数，则有
1
TT Tk k k k k k
k k k kTTk k k k ks s H y y HH H v vs y y H y ?? ? ? ? ?
， （ 5.4.20）
其中 12( ) [ ]T k k k
k k k k TTk k k k ks H yv y H y s y y H y??
，正好蜕变为 Broyden 族 校正公式，这 表明 Broyden
族是 Huang 族的子族 . 一般地 ， Huang 族中含有三个自由参数，可产生丰富的校正公式 .
注 （ 1） 若采用精确一维搜索，对于正定二次函数，所有 Huang 族变尺度算法产生相
同的迭代点列 ，而 对一般函数产生的点列只依赖于 ? .
（ 2） 当极小化正定二次函数时，若取 0HI? ，则 Huang 族校正公式产生的搜索方向
与 F-R 共轭梯度法相同，因而也是共轭方向法 .
§5.5 拟牛顿法的 收敛 性质
§5.5.1 一般拟牛顿算法超线性收敛的特征
假设 A （ 1） 设 ()fx在开凸集 nD?? 上 二阶连续可微；
第五章 共轭梯度法和拟牛顿法
88 最优化理论与方法 [乌力吉 ]
（ 2） ()fx存在一个严格局部极小点 xD? ，且 2 ( )fx? 正定；
（ 3） 2 ()fx? 在点 x 处局部 Lipschitz 连续，即 存在 x 的一个邻域 ( , )Nx? 和常数
0?? ， 使 对任意 , ( , )x y N x ?? ，满足
22( ) ( )f y f x y x?? ? ? ? ?.
定理 5.5.1 设 ()fx满足假设 A 中的 （ 1） 与 （ 2） ，又设 {}kB 为一非奇异矩阵序列 . 假
定对某 0xD? ，迭代序列
11()k k kkx x B f x??? ? ? （ 5.5.1）
恒在 D 中且 对每个 k 有 kxx? ，又设该序列收敛于 x ， 则当且仅当
21
1
[ ( ) ] ( )l i m 0kkk
kkk
B f x x x
xx
?
?? ? ?
? ? ? ?
?
（ 5.5.2）
时，序列 {}kx 超线性收敛到 x .
证 充分性 . 假设等式 (5.5.2)成立 . 由 (5.5.1)和 (5.5.2)可知，
2 1 1 2 1 1[ ( ) ] ( ) [ ( ) ( ) ( ) ( ) ] ( )k k k k k k kkB f x x x f x f x f x x x f x? ? ? ?? ? ? ? ? ? ? ? ? ? ? ?， （ 5.5.3）
于是，由定理 1.2.3，我们有
2 1 21 || [ ( ) ] || || ( ) ( ) ( ) |||| ( ) ||
|| || || || || ||
kkk k k k
k k k
B f x s f x f x f x sfxs s s?? ? ? ? ? ? ? ?? ??
2 1|| [ ( ) ] || ( || || || ||)
|| || 2 kkkkkB f x s x x x xs ? ???? ? ? ? ?
，
由于 lim k
k xx?? ?
，故由上式及 (5.5.2)，有 1|| ( ) ||lim 0
|| ||
k
k k
fxs ?
??
? ?. 又因为 lim|| || 0kk s?? ? ， 故
1( ) lim ( ) 0kkf x f x ???? ? ? ?.
注意到 2 ( )fx? 正定从而非奇异，由定理 1.2.4 知存在 0?? 和 k ，使当 kk? 时， 我们 有
1 1 1| | ( ) | | | | ( ) ( ) | | | | | |k k kf x f x f x x x?? ? ?? ? ? ? ? ? ?，
因此
§ 5.5 拟牛顿法的收敛性质
最优化理论与方法 [乌力吉 ] 89
11
11|| ( ) || || |||| || || || || || 1
kk k
k k k k krf x x xx x x x x x r??
??
??????? ? ? ? ?
，
其中 1|| || / || ||kkkr x x x x?? ? ?. 注意到上式不等式左端趋向于零，我们有 lim 0
kk r?? ?
，这
意味着 {}kx 超线性收敛到 x .
必要性 . 假设 {}kx 超线性收敛到 x ，由于 ( ) 0fx??， 由定理 1.2.4 知存在 0?? 和 k? ，
使当 kk?? 时， 有
1 1 1| | ( ) | | | | ( ) ( ) | | | | | |k k kf x f x f x x x?? ? ?? ? ? ? ? ? ?，
由此得
1 1 1 1
1| | | | | | ( ) | | 1 | | ( ) | | | | | |0 l i m l i m l i m| | | | | | | | | | | | | | | |
k k k k k
k k k k kk k kx x f x f x x xx x x x x x x x??
? ? ? ?
??? ?? ??? ? ? ?? ? ? ?? ? ? ?
，
注意到 {}kx 超线性收敛到 x 时，有 1|| ||lim 1
|| ||
kk
kk xxxx
?
??
? ?? ，故由 (5.5.3)可推知 (5.5.2)成立 .
定理 5.5.2 设 ()fx满足假设 A 中的（ 1）与（ 2） ，又设 {}kB 为一非奇异矩阵序列 . 设 对
某 0xD? ， 迭代序列
11 ()k k kkkx x B f x???? ? ? （ 5.5.4）
恒在 D 中且对每个 k 有 kxx? ，又设该序列收敛于 x . 如果 (5.5.2)式成立，则序列 {}kx 超
线性收敛到 x 且 ( ) 0fx??的 充分必要 条件是 {}k? 收敛到 1.
证 必要性 . 假设 {}kx 超线性收敛到 x 且 ( ) 0fx??，由定理 5.5.1 可知，
21
1
[ ( ) ] ( )l i m 0kkkk
kkk
B f x x x
xx
? ?
?? ? ?
? ? ? ?
?
.
（ 5.5.5）
因而 (5.5.2)意味着
1 1 1
11
( 1 ) ( ) ( 1 ) ( )l i m l i m 0k k kk k k k
k k k kkk
B x x f x
x x x x
? ? ?? ? ?
??? ? ? ? ? ?
? ? ? ? ???
??
.
（ 5.5.6）
由于 2 ( )fx? 非奇异，由定理 1.2.4 知存在 0?? 和 k ，使当 kk? 时，有
11|| ( ) || || ||kkf x x x???? ? ?，
第五章 共轭梯度法和拟牛顿法
90 最优化理论与方法 [乌力吉 ]
再 注意到 {}kx 超线性收敛到 x 时，有 1|| ||lim 1
|| ||
kk
kk xxxx
?
??
? ?? ，从而由 (5.5.6)可推得 {}k? 收
敛到 1.
充分性 . 假设 {}k? 收敛到 1，则从 (5.5.2)可推知 (5.5.5)成立，因此，由定理 5.5.1 可知，
{}kx 超线性收敛到 x 且 ( ) 0fx??.
注 （ 1） 要使算法超线性收敛，步长因子 k? 必趋近于 1； （ 2） 拟牛顿算法超线性收敛的
几何特征是：其位移 ks 在长度与方向上都必趋近于牛顿方向 Nks .
下面我们不加证明地给出一些收敛性结果 .
定理 5.5.3 设 ()fx满足假设 A 中的 （ 1） 与 （ 2） ， 又设 {}kB 为一非奇异矩阵序列 . 假
定对某 0xD? ，迭代序列
11 ()k k kkkx x B f x???? ? ?
恒在 D 中且对每个 k 有 kxx? ，又设该序列收敛于 x ， k? 由精确线性搜索产生，则当
21
1
[ ( ) ] ( )l i m 0kkk
kkk
B f x x x
xx
?
?? ? ?
? ? ? ?
?
成立时，一定有 lim 0
kk ??? ?
和 ( ) 0fx??，从而序列 {}kx 超线性收敛到 x .
定理 5.5.4 设 ()fx满足假设 A 中的（ 1）与（ 2），又设 {}kB 为一非奇异矩阵序列 . 假
定对某 0xD? ，迭代序列
11 ()k k kkkx x B f x???? ? ?
恒在 D 中且对每个 k 有 kxx? ，又设该序列收敛于 x ， k? 由不精确线性搜索的
Wolfe-Powell 准则产生，则当
21
1
[ ( ) ] ( )l i m 0kkk
kkk
B f x x x
xx
?
?? ? ?
? ? ? ?
?
成立时，一定有 lim 0
kk ??? ?
和 ( ) 0fx??，从而序列 {}kx 超线性收敛到 x .
§ 5.5 拟牛顿法的收敛性质
最优化理论与方法 [乌力吉 ] 91
§5.5.2 Broyden 秩一校正的局部超线性收敛性
定理 5.5.5 设 ()fx 满足假设 A，又设存在正常数 ,??，使得 0 xx??? 和
210 ( )H f x ??? ? ?， 则由 Broyden 秩一方法
11
1
( ) ,
() ,
k k k
k
T
k k k kkk
T
kk
x x B f x
y B s sBB
ss
??
?
? ? ? ??
? ????
?
产生的 迭代序列 {}kx 是有定义的，且超线性收敛 到 x .
定理 5.5.6 设 ()fx 满足假设 A，又设存在正常数 ,??，使得 0 xx??? 和
20 ( )B f x ??? ?，则由 Hesse 逆 Broyden 秩一方法
1
1
( ) ,
() ,
k k k
k
T
k k k kkk
T
kk
x x H f x
s H s yHH
ss
?
?
? ? ? ??
? ????
?
产生的 迭代序列 {}kx 是有定义的，且超线性收敛 到 x .
§5.5.3 DFP 和 BFGS 算法的局部超线性收敛性
定理 5.5.7 设 ()fx满足假设 A， 又设在 x 的一个邻域内， 不等式 1( , ) 1 / 3kkxx??? ? ?
成立， 其中 21( )fx? ??? ， 11( , ) m a x { , }k k k kx x x x x x? ??? ? ?. 则 存在 0?? 和
0?? ，使 当 0 xx???和 20 ( ) D FPB f x ?? ? ?时， DFP 方法
11
1 2
( ) ,
( ) ( ) ( ) ,
()
k k k
k
T T T T
k k k k k k k k k k k kk k k k
TT
k k k k
x x B f x
y B s y y y B s y B s sB B y y
y s y s
??
?
? ? ? ??
? ? ? ? ?? ? ??
?
产生的 迭代序列 {}kx 是有定义的，且超线性收敛 到 x .
类似于 Hesse 近似形式的 DFP 方法，可以建立对 Hesse 拟近似的 BFGS 方法的局部收
敛性定理 .
定理 5.5.8 设 ()fx满足假设 A，又设在 x 的一个邻域内，不等式 1( , ) 1 / 3kkxx??? ? ?
成立，其中 21( )fx? ??? ， 11( , ) m a x { , }k k k kx x x x x x? ??? ? ?. 则存在 0?? 和
第五章 共轭梯度法和拟牛顿法
92 最优化理论与方法 [乌力吉 ]
0?? ，使当 0 xx???和 210 ( ) B F G SH f x ??? ? ?时， BFGS 方法
1
1 2
( ) ,
( ) ( ) ( )
()
k k k
k
T T T T
k k k k k k k k k k k kk k k k
TT
k k k k
x x H f x
s H y s s s H y s H y sH H s s
s y s y
?
?
? ? ? ??
? ? ? ? ?? ? ??
?
有定义， 产生的 序列 {}kx 线性收敛 . 如果
0
k
k xx
?
? ? ? ???
，则 序列 {}kx 超线性收敛 到
x .
Byrd， Nocedal， Yuan 于 1987 证明了 Broyden 族的超线性收敛性 .
定理 5.5.9 设 ()fx在开凸集 nD?? 上二阶连续可微且一致凸， 且 2 ()fx? 在点 x 处
局部 lipschitz 连续 . 则对于任何正定矩阵 0B ，当线性搜索满足 Wolfe-Powell 准则时， Broyden
族 算法（ [0,1)?? ，即不包含 DFP 算法）所产生的极小化序列 {}kx 超线性收敛 到 x .
定理 5.5.10 设 ()fx在开凸集 nD?? 上二阶连续可微且一致凸，且 2 ()fx? 在点 x
处局部 lipschitz 连续 . 则对于任何正定矩阵 0B ，当采用精确线性搜索 时， Broyden 族 算法
所产生的极小化序列 {}kx 超线性收敛 到 x .
§5.5.4 拟牛顿法的全局 收敛性
Powell 于 1971 年 证明了当目标函数 ()fx是二阶连续可微 且 一致凸函数时，采用精确
搜索的 DFP 方法的 全局 收敛性及 2 ()fx? 满足 Lipschitz 条件时 的 超线性收敛性 . 1976 年 ，
他又 证明 了 ()fx为 二阶连续可微 凸函数 且 ()fx有下界 时 ， 采用 Wolfe-Powell 准则 的 BFGS
方法的全局收敛性和超线性收敛性 . 1985 年 Byrd， Nocedal， Yuan 将 Powell 的结果推广到除
DFP 以外的所有限制 Broyden 族算法 （ 即 [0,1)?? ） ，证明了全局收敛性及超线性收敛性 .
定理 5.5.11 设 ()fx在 水平集 0( ) { ( ) ( )}L x x f x f x??上二阶连续可微且一致凸 ， 则
采用 精确线性搜索的 DFP 方法产生的点列 {}kx 收敛到极小点 x .
定理 5.5.12 设 0x 和 0B 为任意给定的初始点和初始正定矩阵，又 设 ()fx 在 水平集
0( ) { ( ) ( )}L x x f x f x??上二阶连续可微且一致凸，则在不精确线性搜索 Wolfe-Powell 准
§ 5.5 拟牛顿法的收敛性质
最优化理论与方法 [乌力吉 ] 93
则下， Broyden 族算法 当 [0,1)?? 时 产生的点列 {}kx 收敛到极小点 x .
注 拟牛顿算法中 Broyden 族具有二次终止性和超线性收敛性，对于中小规模问题这是
一类最有效的求解方法，但由于求解过程要存贮一个 nn? 矩阵，求迭代方向要解一个线代
数方程组，使算法效率受影响，而共轭梯度法克服了这些缺陷，故常称共轭梯度法是大规模
无约束的最优化算法 .
第五章 共轭梯度法和拟牛顿法
94 最优化理论与方法 [乌力吉 ]
|
|
