第四章无约束最优化方法
§ 4.1 最速下降法问题提出问题,在点 kx 处,沿什么方向,
kdxf
下降最快?
分析,0 kkTkkkk dodgxfdxf
考查,?c o skkkTk dgdg?
显然当 1cos 时，
kTkdg 取极小值．
因此,kk gd
结论,负梯度方向使xf 下降最快,亦即最速下降方向．
最速下降法算法
Step1,给出 0:,10,0 kRx n?
Step2,计算,
kxf?
如果, kxf 停．
Step3,计算下降方向,
kk gd
Step4,计算步长因子,
k?
Step5,令,
1 kkkk dxx 转步２,
分析,设 cxbGxxxf TT
2
1 是正定二次函数,
由精确的线搜索确定的k?
k
T
k
k
T
k
k Gdd
dg
特别当,kk gd
k
T
k
k
T
k
k Ggg
gg
例 1,用最速下降法求解：
Txxxxf 1,92921m in 02221
解, TxxG
x
x
xg 0,0
90
01
9
*
2
1?
TT xfgx 9,91,9 000
8.0
2.7
0
00
00
01 gGgg
ggxx
T
T
2.7
2.7
1g
22
2
1
11
11
12 8.01
8.09g
Ggg
ggxx
T
T
,2,1,8.01
9?
kx kkk
分析,(1) 8.0limlim 1
*
*
1
k
k
k
k
k
k x
x
xx
xx
因此,最速下降法是整体收敛的，
且是线性收敛的．
(2) 两个相邻的搜索方向是正交的．
02.7,2.79,9 1010 dddd TTT
收敛性分析定理 1,设xf? 在
0xfxfRxL n
上存在且一致连续,则最速下降法产生的序列满足或者对某个 k 有,0?
kg
或者,
kxf
.0?kg
证明,对于最速下降法，,0?
k?
由以上定理立得．
收敛性分析定理 2,设xf 二次连续可微,且,2 Mxf
其中 M 是个正常数,对任何给定的初始点,
0x
最速下降算法或有限终止,或者,lim
kk xf
或者,0lim?
kk g
证明,用以上的结论：
21 2 1 kkk gMxfxf
最速下降法优点
(1) 程序设计简单，计算量小，存储量小，
对初始点没有特别要求．
(2) 有着很好的整体收敛性，即使对一般的目标函数，它也整体收敛．
最速下降法缺点
(1) 最速下降法是线性收敛的，并且有时是很慢的线性收敛．
原因,①
kk gd 仅反映xf 在 kx 处的局部性质．
②,01 kTk dg 相继两次迭代中搜索方向是正交的．
小结
(1) 最速下降法是基本算法之一，而非有效的实用算法．
最速下降法的本质是用线性函数来近似目标函数,要想得到快速算法，需要考虑对目标函数的高阶逼近．
§ 4.2 牛顿法基本思想利用目标函数xf 在点
kx
处的二阶 Taylor
展开式去近似目标函数,用二次函数的极小点去逼近目标函数的极小点．
算法构造问题：
设xf 二阶连续可微，,nk Rx,kk xfg
海色阵kk xfG 2 正定．
如何从?1 kk xx
kTkkkkk xxgfxqxxxfxf
kkTk xxGxx 21
因为
kG
正定,则xq
k
有唯一极小点,用这个极小点作为,1?kx
所以要求, 0
1kk xq
即, 0
1 kkkk gxxG
kkkk gGxx 11因此：
这就是 牛顿法迭代公式,
注,这里,,1 1 kkkk gGd
牛顿法算法
Step1,给出 0:,10,0 kRx n?
Step2,计算,
kxf?
如果, kxf 停．
Step3,否则计算,
kG
Step4,令,1 kkk dxx 转步２,
并且求解方程
,kkk gdG 得出,kd
例 1,用牛顿法求解：
Txxxxf 1,92921m in 02221
解, TxxG
x
x
xg 0,0
90
01
9
*
2
1?
*
1
0
1
001 0
0
9
9
90
01
1
9
xgGxx
牛顿法收敛定理定理 1,设xf 二次连续可微,*x 是xf 的局部极小点,*xf? 正定,假定xf 的海色阵
kk xfG 2 满足 Lipschitz条件，即存在
,0 使得对于所有 nji,1 有：
1,,nijij RyxyxyGxG
其中xG
ij
是海色阵
kG
的ji,元素,则当 0x
充分靠近 *x 时,对于一切,k 牛顿迭代有意义，
迭代序列
kx
收敛到,*x 并且具有二阶收敛速度．
牛顿法优点
(1)
(2) 对正定二次函数，迭代一次就可以得到极小点．
如果 *G 正定且初始点选取合适,算法二阶收敛．
牛顿法缺点
(1)
(2)
对多数问题算法不是整体收敛的．
每次都需要计算,
kG
计算量大．
(3)每次都需要解 ;
kk gdG
方程组有时奇异或病态的,无法确定,
kd
或
kd
不是下降方向．
(4)收敛到鞍点或极大点的可能性并不小．
阻尼牛顿法算法
Step1,给出 0:,10,0 kRx n?
Step2,计算,
kxf?
如果, kxf 停．
Step3,否则计算,
kG
Step4,沿并且求解方程
,kk gdG 得出,kd
kd
进行线搜索,得出,
k?
Step5,令,1 kkkk dxx 转 Step2.
阻尼牛顿法收敛定理定理 2,设xf 二阶连续可微,又设对任意的,
0 nRx?
存在常数,0?m 使得xf 在
0xfxfxL
上满足,
0
22,,xLxRmxf nT
则在精确线搜索条件下,阻尼牛顿法产生的点列
kx 满足：
(1)当
kx
是有限点列时,其最后一个点为xf
的唯一极小点．
(2)当
kx
是无限点列时,收敛到xf 的唯一极小点．
阻尼牛顿法收敛定理定理 3,设xf 二阶连续可微,又设对任意的,
0 nRx?
存在常数,0?m 使得xf 在
0xfxfxL
上满足,
0
22,,xLxRmxf nT
则在 Wolfe不精确线搜索条件下,阻尼牛顿法产生的点列
kx
满足：
0lim kk xf
且
kx
收敛到xf 的唯一极小点．
例 2,用阻尼牛顿法求解：
Txxxxxxf 0,01m in 0222141
解：
21
10
2
0
00 Gg
显然 0G 不是正定的,但,
01
121
0G
于是,
0
2
0
1
00 gGd
沿方向 0d 进行线搜索,,116 4
00 dxf
得其极小点,00 从而迭代不能继续下去．
带保护的牛顿法算法给出 0:,,,210 kRx n
Step1:
kG
若 为奇异的，转 Step8，否则，
Step2,令,1
kkk gGd
Step3,若,
1 kkkTk dgdg
为奇异的，转,否则，
则转 Step8，否则，
Step4,若,
1 kkkTk dgdg
则转 Step9，否则，
Step5,沿方向
kd
进行线搜索,求出,k?
并令,
1 kkkk dxx
Step6,若,
21kg
停；
Step7,令,1 kk 转 Step1；
Step8,令,
kk gd 转 Step5；
Step9,令,
kk dd 转 Step5.
例 3,用带保护的牛顿法求解：
Txxxxxxf 0,01m in 0222141
解：
21
10
2
0
00 Gg
显然 0G 不是正定的,但,
01
121
0G
于是,
0
2
0
1
00 gGd
因为，,000?dg T 故令，,
2
0
00
gd
沿 0d 进行线搜索得：,
2
1
0
0,
1
0
11
xfx
第二次迭代,
21
10,
0
1
11 Gg
而,
1
2
1
1
11 gGd
使,0211dg T 故令
1
2
1
2
1d
沿 1d 进行线搜索,得出,3 4 7 9 4 2 2.01
于是, 5 8 2 4 4 5 1.0
3 4 7 9 4 2 2.1
6 9 5 8 8 4 4.0
22
xfx
此时,
0
1073.0 7
2g
Gill-Murray稳定牛顿法当
kG
正定时,总有 Cholesky分解：
Tkkkk LDLG?
当
kG
不是正定时,Gill-Murray(1974)提出了强迫正定的修改 Cholesky分解,使得：
,kkTkkkk EGLDLG
其中
kE
是对角阵,然后解：
,kTkkkk gdLDLdG
问题 1,如何建立有效的算法？
从二次模型到一般模型问题 2,什么样的算法有效呢？
二次终止性
§ 4.3 共轭方向法与共轭梯度法算法特点
（１）建立在二次模型上，具有二次终止性．
（２）有效的算法，克服了最速下降法的慢收敛性，又避免了牛顿法的计算量大和局部收性的缺点．
（３）算法简单，易于编程，需存储空间小等优点，是求解大规模问题的主要方法．
共轭方向及其性质定义 1,设
mddd,,,21?
是 nR 中任一组非零向量,如果,jiGdd
jTi,0
则称
mddd,,,21?
是关于 G 共轭的．
注,若,IG? 则是正交的，因此共轭是正交的推广．
定理 1,设 G 为 n 阶正定阵,非零向量组
mddd,,,21?
关于 G 共轭,则必线性无关．
推论 1,设 G 为 n 阶正定阵,非零向量组
nddd,,,21?
关于 G 共轭,则向量构成 nR
的一组基．
推论 2:设 G 为 n 阶正定阵,非零向量组
nddd,,,21?
关于 G 共轭,若向量 v 与
nddd,,,21?
关于 G 共轭,则,0?v
共轭方向法算法
Step1,给出 0:,10,0 kRx n?
计算
00 xgg?
和初始下降方向,
0d
Step2,如果,kg 停止迭代．
Step3,计算,,1?kk x? 使得,1 kkkk dxx
Step4,采用某种共轭方向法计算
1?kd
使得：
.,,1,0,01 kjGdd jTk
Step5,令,1, kk 转 Step2.
共轭方向法基本定理定义 2,设 n 维向量组
kddd,,,21?
线性无关，
,1 nRx? 向量集合
k
i
iiik RdxH
1
1
1
为 1x 与
kddd,,,21?
生成的 k 维超平面．
引理 1,设xf 是连续可微的严格凸函数，
n 维向量组
kddd?,,21
线性无关，,
1 nRx?
则：
i
k
i
ik dxx?
1
11?
是xf 在
kH
上唯一极小点的充要条件是：
kidg iTk?,2,1,01
h
证,构造,
k
i
iik dxfh
1
121,,,
分析,是(1) k 维严格凸函数．
(2)
1?kx
是xf 在
kH
上的极小点的充要条件是T
k,,21
是
kh,,21
在 kR 上的极小点．
定理 2,设 G 为 n 阶正定阵,向量组
kddd?,,21
关于 G 共轭,对正定二次函数,
2
1 cxbGxxxf TT
由任意 1x 开始,依次进行 k 次精确线搜索：
,,2,1,1 kidxx iiii则：
（１） kidg iTk?,2,1,01
（２）
1?kx 是xf 在 kH 上的极小点．
推论,当 nk? 时，
1?nx 为正定二次函数在 nR
上的极小点．
共轭梯度法记：
11 kkkk dgd?
左乘,
1Gd Tk?
并使
11
1
1
k
T
k
k
T
k
k Gdd
Gdg?
,01 kTk dGd 得：
（ Hestenes-Stiefel公式）
取：
00 gd
共轭梯度法基本性质定理 3,对于正定二次函数,采用精确线搜索的共轭梯度法在 nm? 步后终止,且对
ni1 成立下列关系式：
,1,,1,0,0 ijGdd jTi?
,1,,1,0,0 ijgg jTi?
,iTiiTi gggd
,1,1,00 ijdg jTi?
（共轭性）
（正交性）
（下降条件）
系数的其他形式
（１） FR公式
11
1
k
T
k
k
T
k
k gg
gg? （ 1964）
（ 2） PRP公式
11
1
1
k
T
k
kk
T
k
k gg
ggg? （ 1969）
FR共轭梯度法算法
Step1,给出 0:,10,0 kRx n?
Step2,计算,kk xfg 如果,kg 停．
Step3,11 kkkk dgd?
10
1
111
k
k
gg
gg
k
T
k
k
T
k
k?
Step4,由精确线搜索求,
k?
Step5:,1,1 kkdxx kkkk?转 Step2.
例 4,用 FR共轭梯度法求解：
Txxxxxxxf 4,222123m in 01212221
解,化成 cxbGxxxf TT
2
1 形式
2
1
2
1
21 0,211
13
,
2
1
x
x
x
x
xxxf
4
2
0x
6
12
00 bGxg
(1)
6
12
0d
17
5
00
00
0 Gdd
dg
T
T
17
38
17
26
0001 dxx?
17
12
17
6
11 bGxg
789.01?g
(2)
289
1
00
11
0 gg
gg
T
T
289
210
289
90
0011 dgd?
17
10
11
11
1 Gdd
dg
T
T
1
1
1112 dxx?
02?g
1
1
2
* xx
例 5,用 FR共轭梯度法求解：
TT dxxxxf 0,11,12121m in 002221
解,化成 cxbGxxxf TT
2
1 形式
2
1
21 10
01
,
2
1
x
x
xxxf
1
1
0x
1
1
00 bGxg
(1)
0
1
0d
1
00
00
0 Gdd
dg
T
T
1
0
0001 dxx?
1
0
11 bGxg 11?g
(2)
2
1
00
11
0 gg
gg
T
T
1
2
1
0011 dgd?
5
4
11
11
1 Gdd
dg
T
T
5
1
5
2
1112 dxx?
FR共轭梯度法收敛定理定理 4,假定xf 在有界水平集
0xfxfRxL n
上连续可微,且有下界,那么采用精确线搜索下的
FR共轭梯度法产生的点列
kx
至少有一个聚点是驻点，即：
(1) 当
kx
是有穷点列时,其最后一个点是
xf 的驻点．
(2)当
kx
是无穷点列时,它必有聚点,且任一聚点都是xf 的驻点．
再开始 FR共轭梯度法算法
Step1,给出 0:,10,0 kRx n?
Step2,计算,00 xfg 如果,0g 停，
Step4:
否则,
00 gd
Step3,由精确线搜索求,
k?
并令：
.1,1 kkdxx kkkk?
计算,
kk xfg
若,1.0
2
1
k
k
T
k
g
gg
令,:
0 kxx? 转 Step2;
如果,kg 停,
Step5,若,nk? 令,:
0 kxx?
转 step2.
Step6,计算
11
11
1,
kkkk
k
T
k
k
T
k
k dgdgg
gg
Step7,如果,0?
kTk gd 令,:0 kxx? 转 step2,
否则 转 step3.
作业,FR共轭梯度法（上机）
上机实现 FR共轭梯度法．
并求解 Rosenbrock函数,初始点选,1,2.1
0
Tx
线搜索分别采用黄金分割法与强 Wolfe线搜索，并对比．
§ 4.4 拟牛顿法基本思想本质上是基于逼近牛顿法的方法．
牛顿法每次都计算,
kG
1959年,Davidon提出设想仅用每次迭代中得到的梯度信息来近似海色阵，基于此导致了一类非常成功的拟牛顿法．
本节介绍 Broyden族拟牛顿法：
DFP算法和 BFGS算法．
算法原理最速下降法和阻尼牛顿法的迭代公式可统一为：
kkkkk gHxx 1
思考,要使上面的算法比最速下降法快，比牛顿法计算简单，且整体收敛性好，关键在于构造矩阵列.
kH
要求,
kH
的选取既能逐步逼近,1?
kG
又无需计算二阶导数,且具备以下条件：
C1：
kH
是对称正定阵．
C2：
1?kH
由
kH
经简单修正而得：
kkk EHH 1
C3：
kH
满足下面的拟牛顿方程．（推导如下）
设xf 是二次连续可微的，
111111 21 kkTkkTkk xxGxxxxgxfxf
111 kkk xxGgxg
令：,
kxx?
则,
kkkkk ggxxG 111
令,kkkkkk ggyxxs 11,
因此,kkk ysG1 （对二次函数为等式）
若 11kG 非奇异,kkk syG11
设想,kkk syH1 （拟牛顿方程）
这样
1?kH 就可很好的近似,11kG
拟牛顿算法
Step1,给出 0:,10,,00 kHRx n?
Step2,计算,0g
Step3:
kkk gHd
Step4,精确线搜索求,
k?
Step5,kkkk dxx 1
Step6,计算,1?kg 若,1kg 停； 否则转 Step7.
Step7,校正,
1 kk HH
使拟牛顿方程成立．
Step8:,1 kk 转 Step3.
DFP校正公式
kkk EHH 1
TTk vvuuE vu,是 n 维待定向量．
要求：
kkk syH 1
所以：
kkTkTkk syvvyuuyH
令：
kkk yHvsu,
得,11 kTkT yvyu
因此：
kk
T
kk
T
k
T
kk
T yHyyvsyyu
1111
所以：
k
T
k
T
kk
kk
T
k
k
T
kkk
kk sy
ss
yHy
HyyHHH
1 （ DFP校正公式）
例 6,用 DFP算法求解：
1212221 422m in xxxxxxf
4
00 1010
01
1
1
Hx取解,
42
22
42
422
21
21 xG
xx
xx
xg
(1)
2
4
2
4
0000 gHdg
32040 200 dxf
410 0
2
1
5.0
2
10001 gdxx?
4
3
5.0
1
010010 ggyxxs
4138
3884
100
1
00
00
000
0000
01 sy
ss
yHy
HyyHHH
T
T
T
T
(2)
6
8
5
1
111 gHd
4505.5458 12
2
4
0
0
2
4
2
*
21112 xxgdxx?
注,
（１） DFP算法具有二次终止性．
（２）搜索方向是共轭方向：
5
6
5
8
2
4
42
22
10 ddG
010?Gdd T
DFP校正公式的正定继承性引理 2,设,
sy
ss
Hyy
HH y yHH
T
T
T
T
H 为正定阵,nn RsRy,且,0,0 sy 则：
H 为正定阵的充要条件是,0?sy T
定理 5,在 DFP算法中,如果
0H
正定，
则整个矩阵列
kH
都正定．
DFP算法的二次终止性推论,在上面定理条件下：
（ 1） DFP算法至多经过 n 次迭代就可得到极小点，即存在nkk0 有,.*xx
k?
（ 2） 若,10,* nkxx
k 则,1 GH n
BFGS校正公式
kkk ysB 1
kk
T
k
k
T
kkk
k
T
k
T
kk
kk sBs
BssB
sy
yyBB
1
(称为关于
kB
的 BFGS校正公式或互补 DFP公式 )
由上式可得：
1 9 7 0)( 1
k
T
k
T
kk
k
T
k
T
k
k
k
T
k
T
kkB F G S
K ys
ss
ys
sy
IH
ys
ysIH k?
k
T
k
T
kk
k
T
k
T
kk
k
k
T
k
T
kkD F P
K sy
yy
sy
ysIH
sy
syIB?
)(
1
对称秩一校正公式
kkk EHH 1 Tk uvE?
要求：
kkk syH 1
要求 Hesse逆近似也是对称的，
kkTkk syuvyH
即, kkkkT yHsuyv
Tkkk
k
Tkk vyHsyvHH
1
1
取：
kkk yHsv
kTkkk
T
kkkkkk
kk yyHs
yHsyHsHH
1
因此：
注,
（ 1）通常不能保证
（ 2）分母可能取零,修正公式不再有意义．
kH 的正定性．
（ 3）逼近 1?kG 程度高,近来用于信赖域算法，
取得了很好的效果．
Broyden族
kk
T
k
kk
k
T
k
k
kk
T
kk yHy
yH
ys
syHyv 2/1
取
B F G SkD F Pkk HHH 111 1
19671 Tkk
kk
T
k
k
T
kkk
k
T
k
T
kk
kk vvyHy
HyyH
ys
ssHH
注：,0 得 DFP校正．注：
,1 得 BFGS校正．
,kTkkk
k
T
k
yyHs
ys
得对称秩一校正．
其中：
Broyden族算法性质定理 6,设xf 在 nR 上连续可微,给定,,
00 Hx
在精确线搜索下,由 Broyden族算法产生的点列
kx
与参数? 无关．
结论,可将 DFP算法的性质推广到整个 Broyden族作 业
(1)用 FR共轭梯度法求解：
5
5
2m in 02221 xxxxf
(2)用 DFP算法求解：
1
2
242m in 012221 xxxxxf
§ 4.1 最速下降法问题提出问题,在点 kx 处,沿什么方向,
kdxf
下降最快?
分析,0 kkTkkkk dodgxfdxf
考查,?c o skkkTk dgdg?
显然当 1cos 时，
kTkdg 取极小值．
因此,kk gd
结论,负梯度方向使xf 下降最快,亦即最速下降方向．
最速下降法算法
Step1,给出 0:,10,0 kRx n?
Step2,计算,
kxf?
如果, kxf 停．
Step3,计算下降方向,
kk gd
Step4,计算步长因子,
k?
Step5,令,
1 kkkk dxx 转步２,
分析,设 cxbGxxxf TT
2
1 是正定二次函数,
由精确的线搜索确定的k?
k
T
k
k
T
k
k Gdd
dg
特别当,kk gd
k
T
k
k
T
k
k Ggg
gg
例 1,用最速下降法求解：
Txxxxf 1,92921m in 02221
解, TxxG
x
x
xg 0,0
90
01
9
*
2
1?
TT xfgx 9,91,9 000
8.0
2.7
0
00
00
01 gGgg
ggxx
T
T
2.7
2.7
1g
22
2
1
11
11
12 8.01
8.09g
Ggg
ggxx
T
T
,2,1,8.01
9?
kx kkk
分析,(1) 8.0limlim 1
*
*
1
k
k
k
k
k
k x
x
xx
xx
因此,最速下降法是整体收敛的，
且是线性收敛的．
(2) 两个相邻的搜索方向是正交的．
02.7,2.79,9 1010 dddd TTT
收敛性分析定理 1,设xf? 在
0xfxfRxL n
上存在且一致连续,则最速下降法产生的序列满足或者对某个 k 有,0?
kg
或者,
kxf
.0?kg
证明,对于最速下降法，,0?
k?
由以上定理立得．
收敛性分析定理 2,设xf 二次连续可微,且,2 Mxf
其中 M 是个正常数,对任何给定的初始点,
0x
最速下降算法或有限终止,或者,lim
kk xf
或者,0lim?
kk g
证明,用以上的结论：
21 2 1 kkk gMxfxf
最速下降法优点
(1) 程序设计简单，计算量小，存储量小，
对初始点没有特别要求．
(2) 有着很好的整体收敛性，即使对一般的目标函数，它也整体收敛．
最速下降法缺点
(1) 最速下降法是线性收敛的，并且有时是很慢的线性收敛．
原因,①
kk gd 仅反映xf 在 kx 处的局部性质．
②,01 kTk dg 相继两次迭代中搜索方向是正交的．
小结
(1) 最速下降法是基本算法之一，而非有效的实用算法．
最速下降法的本质是用线性函数来近似目标函数,要想得到快速算法，需要考虑对目标函数的高阶逼近．
§ 4.2 牛顿法基本思想利用目标函数xf 在点
kx
处的二阶 Taylor
展开式去近似目标函数,用二次函数的极小点去逼近目标函数的极小点．
算法构造问题：
设xf 二阶连续可微，,nk Rx,kk xfg
海色阵kk xfG 2 正定．
如何从?1 kk xx
kTkkkkk xxgfxqxxxfxf
kkTk xxGxx 21
因为
kG
正定,则xq
k
有唯一极小点,用这个极小点作为,1?kx
所以要求, 0
1kk xq
即, 0
1 kkkk gxxG
kkkk gGxx 11因此：
这就是 牛顿法迭代公式,
注,这里,,1 1 kkkk gGd
牛顿法算法
Step1,给出 0:,10,0 kRx n?
Step2,计算,
kxf?
如果, kxf 停．
Step3,否则计算,
kG
Step4,令,1 kkk dxx 转步２,
并且求解方程
,kkk gdG 得出,kd
例 1,用牛顿法求解：
Txxxxf 1,92921m in 02221
解, TxxG
x
x
xg 0,0
90
01
9
*
2
1?
*
1
0
1
001 0
0
9
9
90
01
1
9
xgGxx
牛顿法收敛定理定理 1,设xf 二次连续可微,*x 是xf 的局部极小点,*xf? 正定,假定xf 的海色阵
kk xfG 2 满足 Lipschitz条件，即存在
,0 使得对于所有 nji,1 有：
1,,nijij RyxyxyGxG
其中xG
ij
是海色阵
kG
的ji,元素,则当 0x
充分靠近 *x 时,对于一切,k 牛顿迭代有意义，
迭代序列
kx
收敛到,*x 并且具有二阶收敛速度．
牛顿法优点
(1)
(2) 对正定二次函数，迭代一次就可以得到极小点．
如果 *G 正定且初始点选取合适,算法二阶收敛．
牛顿法缺点
(1)
(2)
对多数问题算法不是整体收敛的．
每次都需要计算,
kG
计算量大．
(3)每次都需要解 ;
kk gdG
方程组有时奇异或病态的,无法确定,
kd
或
kd
不是下降方向．
(4)收敛到鞍点或极大点的可能性并不小．
阻尼牛顿法算法
Step1,给出 0:,10,0 kRx n?
Step2,计算,
kxf?
如果, kxf 停．
Step3,否则计算,
kG
Step4,沿并且求解方程
,kk gdG 得出,kd
kd
进行线搜索,得出,
k?
Step5,令,1 kkkk dxx 转 Step2.
阻尼牛顿法收敛定理定理 2,设xf 二阶连续可微,又设对任意的,
0 nRx?
存在常数,0?m 使得xf 在
0xfxfxL
上满足,
0
22,,xLxRmxf nT
则在精确线搜索条件下,阻尼牛顿法产生的点列
kx 满足：
(1)当
kx
是有限点列时,其最后一个点为xf
的唯一极小点．
(2)当
kx
是无限点列时,收敛到xf 的唯一极小点．
阻尼牛顿法收敛定理定理 3,设xf 二阶连续可微,又设对任意的,
0 nRx?
存在常数,0?m 使得xf 在
0xfxfxL
上满足,
0
22,,xLxRmxf nT
则在 Wolfe不精确线搜索条件下,阻尼牛顿法产生的点列
kx
满足：
0lim kk xf
且
kx
收敛到xf 的唯一极小点．
例 2,用阻尼牛顿法求解：
Txxxxxxf 0,01m in 0222141
解：
21
10
2
0
00 Gg
显然 0G 不是正定的,但,
01
121
0G
于是,
0
2
0
1
00 gGd
沿方向 0d 进行线搜索,,116 4
00 dxf
得其极小点,00 从而迭代不能继续下去．
带保护的牛顿法算法给出 0:,,,210 kRx n
Step1:
kG
若 为奇异的，转 Step8，否则，
Step2,令,1
kkk gGd
Step3,若,
1 kkkTk dgdg
为奇异的，转,否则，
则转 Step8，否则，
Step4,若,
1 kkkTk dgdg
则转 Step9，否则，
Step5,沿方向
kd
进行线搜索,求出,k?
并令,
1 kkkk dxx
Step6,若,
21kg
停；
Step7,令,1 kk 转 Step1；
Step8,令,
kk gd 转 Step5；
Step9,令,
kk dd 转 Step5.
例 3,用带保护的牛顿法求解：
Txxxxxxf 0,01m in 0222141
解：
21
10
2
0
00 Gg
显然 0G 不是正定的,但,
01
121
0G
于是,
0
2
0
1
00 gGd
因为，,000?dg T 故令，,
2
0
00
gd
沿 0d 进行线搜索得：,
2
1
0
0,
1
0
11
xfx
第二次迭代,
21
10,
0
1
11 Gg
而,
1
2
1
1
11 gGd
使,0211dg T 故令
1
2
1
2
1d
沿 1d 进行线搜索,得出,3 4 7 9 4 2 2.01
于是, 5 8 2 4 4 5 1.0
3 4 7 9 4 2 2.1
6 9 5 8 8 4 4.0
22
xfx
此时,
0
1073.0 7
2g
Gill-Murray稳定牛顿法当
kG
正定时,总有 Cholesky分解：
Tkkkk LDLG?
当
kG
不是正定时,Gill-Murray(1974)提出了强迫正定的修改 Cholesky分解,使得：
,kkTkkkk EGLDLG
其中
kE
是对角阵,然后解：
,kTkkkk gdLDLdG
问题 1,如何建立有效的算法？
从二次模型到一般模型问题 2,什么样的算法有效呢？
二次终止性
§ 4.3 共轭方向法与共轭梯度法算法特点
（１）建立在二次模型上，具有二次终止性．
（２）有效的算法，克服了最速下降法的慢收敛性，又避免了牛顿法的计算量大和局部收性的缺点．
（３）算法简单，易于编程，需存储空间小等优点，是求解大规模问题的主要方法．
共轭方向及其性质定义 1,设
mddd,,,21?
是 nR 中任一组非零向量,如果,jiGdd
jTi,0
则称
mddd,,,21?
是关于 G 共轭的．
注,若,IG? 则是正交的，因此共轭是正交的推广．
定理 1,设 G 为 n 阶正定阵,非零向量组
mddd,,,21?
关于 G 共轭,则必线性无关．
推论 1,设 G 为 n 阶正定阵,非零向量组
nddd,,,21?
关于 G 共轭,则向量构成 nR
的一组基．
推论 2:设 G 为 n 阶正定阵,非零向量组
nddd,,,21?
关于 G 共轭,若向量 v 与
nddd,,,21?
关于 G 共轭,则,0?v
共轭方向法算法
Step1,给出 0:,10,0 kRx n?
计算
00 xgg?
和初始下降方向,
0d
Step2,如果,kg 停止迭代．
Step3,计算,,1?kk x? 使得,1 kkkk dxx
Step4,采用某种共轭方向法计算
1?kd
使得：
.,,1,0,01 kjGdd jTk
Step5,令,1, kk 转 Step2.
共轭方向法基本定理定义 2,设 n 维向量组
kddd,,,21?
线性无关，
,1 nRx? 向量集合
k
i
iiik RdxH
1
1
1
为 1x 与
kddd,,,21?
生成的 k 维超平面．
引理 1,设xf 是连续可微的严格凸函数，
n 维向量组
kddd?,,21
线性无关，,
1 nRx?
则：
i
k
i
ik dxx?
1
11?
是xf 在
kH
上唯一极小点的充要条件是：
kidg iTk?,2,1,01
h
证,构造,
k
i
iik dxfh
1
121,,,
分析,是(1) k 维严格凸函数．
(2)
1?kx
是xf 在
kH
上的极小点的充要条件是T
k,,21
是
kh,,21
在 kR 上的极小点．
定理 2,设 G 为 n 阶正定阵,向量组
kddd?,,21
关于 G 共轭,对正定二次函数,
2
1 cxbGxxxf TT
由任意 1x 开始,依次进行 k 次精确线搜索：
,,2,1,1 kidxx iiii则：
（１） kidg iTk?,2,1,01
（２）
1?kx 是xf 在 kH 上的极小点．
推论,当 nk? 时，
1?nx 为正定二次函数在 nR
上的极小点．
共轭梯度法记：
11 kkkk dgd?
左乘,
1Gd Tk?
并使
11
1
1
k
T
k
k
T
k
k Gdd
Gdg?
,01 kTk dGd 得：
（ Hestenes-Stiefel公式）
取：
00 gd
共轭梯度法基本性质定理 3,对于正定二次函数,采用精确线搜索的共轭梯度法在 nm? 步后终止,且对
ni1 成立下列关系式：
,1,,1,0,0 ijGdd jTi?
,1,,1,0,0 ijgg jTi?
,iTiiTi gggd
,1,1,00 ijdg jTi?
（共轭性）
（正交性）
（下降条件）
系数的其他形式
（１） FR公式
11
1
k
T
k
k
T
k
k gg
gg? （ 1964）
（ 2） PRP公式
11
1
1
k
T
k
kk
T
k
k gg
ggg? （ 1969）
FR共轭梯度法算法
Step1,给出 0:,10,0 kRx n?
Step2,计算,kk xfg 如果,kg 停．
Step3,11 kkkk dgd?
10
1
111
k
k
gg
gg
k
T
k
k
T
k
k?
Step4,由精确线搜索求,
k?
Step5:,1,1 kkdxx kkkk?转 Step2.
例 4,用 FR共轭梯度法求解：
Txxxxxxxf 4,222123m in 01212221
解,化成 cxbGxxxf TT
2
1 形式
2
1
2
1
21 0,211
13
,
2
1
x
x
x
x
xxxf
4
2
0x
6
12
00 bGxg
(1)
6
12
0d
17
5
00
00
0 Gdd
dg
T
T
17
38
17
26
0001 dxx?
17
12
17
6
11 bGxg
789.01?g
(2)
289
1
00
11
0 gg
gg
T
T
289
210
289
90
0011 dgd?
17
10
11
11
1 Gdd
dg
T
T
1
1
1112 dxx?
02?g
1
1
2
* xx
例 5,用 FR共轭梯度法求解：
TT dxxxxf 0,11,12121m in 002221
解,化成 cxbGxxxf TT
2
1 形式
2
1
21 10
01
,
2
1
x
x
xxxf
1
1
0x
1
1
00 bGxg
(1)
0
1
0d
1
00
00
0 Gdd
dg
T
T
1
0
0001 dxx?
1
0
11 bGxg 11?g
(2)
2
1
00
11
0 gg
gg
T
T
1
2
1
0011 dgd?
5
4
11
11
1 Gdd
dg
T
T
5
1
5
2
1112 dxx?
FR共轭梯度法收敛定理定理 4,假定xf 在有界水平集
0xfxfRxL n
上连续可微,且有下界,那么采用精确线搜索下的
FR共轭梯度法产生的点列
kx
至少有一个聚点是驻点，即：
(1) 当
kx
是有穷点列时,其最后一个点是
xf 的驻点．
(2)当
kx
是无穷点列时,它必有聚点,且任一聚点都是xf 的驻点．
再开始 FR共轭梯度法算法
Step1,给出 0:,10,0 kRx n?
Step2,计算,00 xfg 如果,0g 停，
Step4:
否则,
00 gd
Step3,由精确线搜索求,
k?
并令：
.1,1 kkdxx kkkk?
计算,
kk xfg
若,1.0
2
1
k
k
T
k
g
gg
令,:
0 kxx? 转 Step2;
如果,kg 停,
Step5,若,nk? 令,:
0 kxx?
转 step2.
Step6,计算
11
11
1,
kkkk
k
T
k
k
T
k
k dgdgg
gg
Step7,如果,0?
kTk gd 令,:0 kxx? 转 step2,
否则 转 step3.
作业,FR共轭梯度法（上机）
上机实现 FR共轭梯度法．
并求解 Rosenbrock函数,初始点选,1,2.1
0
Tx
线搜索分别采用黄金分割法与强 Wolfe线搜索，并对比．
§ 4.4 拟牛顿法基本思想本质上是基于逼近牛顿法的方法．
牛顿法每次都计算,
kG
1959年,Davidon提出设想仅用每次迭代中得到的梯度信息来近似海色阵，基于此导致了一类非常成功的拟牛顿法．
本节介绍 Broyden族拟牛顿法：
DFP算法和 BFGS算法．
算法原理最速下降法和阻尼牛顿法的迭代公式可统一为：
kkkkk gHxx 1
思考,要使上面的算法比最速下降法快，比牛顿法计算简单，且整体收敛性好，关键在于构造矩阵列.
kH
要求,
kH
的选取既能逐步逼近,1?
kG
又无需计算二阶导数,且具备以下条件：
C1：
kH
是对称正定阵．
C2：
1?kH
由
kH
经简单修正而得：
kkk EHH 1
C3：
kH
满足下面的拟牛顿方程．（推导如下）
设xf 是二次连续可微的，
111111 21 kkTkkTkk xxGxxxxgxfxf
111 kkk xxGgxg
令：,
kxx?
则,
kkkkk ggxxG 111
令,kkkkkk ggyxxs 11,
因此,kkk ysG1 （对二次函数为等式）
若 11kG 非奇异,kkk syG11
设想,kkk syH1 （拟牛顿方程）
这样
1?kH 就可很好的近似,11kG
拟牛顿算法
Step1,给出 0:,10,,00 kHRx n?
Step2,计算,0g
Step3:
kkk gHd
Step4,精确线搜索求,
k?
Step5,kkkk dxx 1
Step6,计算,1?kg 若,1kg 停； 否则转 Step7.
Step7,校正,
1 kk HH
使拟牛顿方程成立．
Step8:,1 kk 转 Step3.
DFP校正公式
kkk EHH 1
TTk vvuuE vu,是 n 维待定向量．
要求：
kkk syH 1
所以：
kkTkTkk syvvyuuyH
令：
kkk yHvsu,
得,11 kTkT yvyu
因此：
kk
T
kk
T
k
T
kk
T yHyyvsyyu
1111
所以：
k
T
k
T
kk
kk
T
k
k
T
kkk
kk sy
ss
yHy
HyyHHH
1 （ DFP校正公式）
例 6,用 DFP算法求解：
1212221 422m in xxxxxxf
4
00 1010
01
1
1
Hx取解,
42
22
42
422
21
21 xG
xx
xx
xg
(1)
2
4
2
4
0000 gHdg
32040 200 dxf
410 0
2
1
5.0
2
10001 gdxx?
4
3
5.0
1
010010 ggyxxs
4138
3884
100
1
00
00
000
0000
01 sy
ss
yHy
HyyHHH
T
T
T
T
(2)
6
8
5
1
111 gHd
4505.5458 12
2
4
0
0
2
4
2
*
21112 xxgdxx?
注,
（１） DFP算法具有二次终止性．
（２）搜索方向是共轭方向：
5
6
5
8
2
4
42
22
10 ddG
010?Gdd T
DFP校正公式的正定继承性引理 2,设,
sy
ss
Hyy
HH y yHH
T
T
T
T
H 为正定阵,nn RsRy,且,0,0 sy 则：
H 为正定阵的充要条件是,0?sy T
定理 5,在 DFP算法中,如果
0H
正定，
则整个矩阵列
kH
都正定．
DFP算法的二次终止性推论,在上面定理条件下：
（ 1） DFP算法至多经过 n 次迭代就可得到极小点，即存在nkk0 有,.*xx
k?
（ 2） 若,10,* nkxx
k 则,1 GH n
BFGS校正公式
kkk ysB 1
kk
T
k
k
T
kkk
k
T
k
T
kk
kk sBs
BssB
sy
yyBB
1
(称为关于
kB
的 BFGS校正公式或互补 DFP公式 )
由上式可得：
1 9 7 0)( 1
k
T
k
T
kk
k
T
k
T
k
k
k
T
k
T
kkB F G S
K ys
ss
ys
sy
IH
ys
ysIH k?
k
T
k
T
kk
k
T
k
T
kk
k
k
T
k
T
kkD F P
K sy
yy
sy
ysIH
sy
syIB?
)(
1
对称秩一校正公式
kkk EHH 1 Tk uvE?
要求：
kkk syH 1
要求 Hesse逆近似也是对称的，
kkTkk syuvyH
即, kkkkT yHsuyv
Tkkk
k
Tkk vyHsyvHH
1
1
取：
kkk yHsv
kTkkk
T
kkkkkk
kk yyHs
yHsyHsHH
1
因此：
注,
（ 1）通常不能保证
（ 2）分母可能取零,修正公式不再有意义．
kH 的正定性．
（ 3）逼近 1?kG 程度高,近来用于信赖域算法，
取得了很好的效果．
Broyden族
kk
T
k
kk
k
T
k
k
kk
T
kk yHy
yH
ys
syHyv 2/1
取
B F G SkD F Pkk HHH 111 1
19671 Tkk
kk
T
k
k
T
kkk
k
T
k
T
kk
kk vvyHy
HyyH
ys
ssHH
注：,0 得 DFP校正．注：
,1 得 BFGS校正．
,kTkkk
k
T
k
yyHs
ys
得对称秩一校正．
其中：
Broyden族算法性质定理 6,设xf 在 nR 上连续可微,给定,,
00 Hx
在精确线搜索下,由 Broyden族算法产生的点列
kx
与参数? 无关．
结论,可将 DFP算法的性质推广到整个 Broyden族作 业
(1)用 FR共轭梯度法求解：
5
5
2m in 02221 xxxxf
(2)用 DFP算法求解：
1
2
242m in 012221 xxxxxf
