最优化理论 第五章 共轭梯度法和拟牛顿法

§5.1共轭方向法点列呈锯齿形前进，收敛慢的缺点，同时又不像牛顿法中计算牛顿方向耗费大量的工作量，尤其是共轭方向法具有二次终止性.设G是nn对称正定矩阵，d1d2是n维非零向量，若(d1)TGd20，则称d1d2是G共轭的；如果Rn中一组非零向量d1,d2,,dm两两共轭，即(di)TGdj0(ij) 则称向量组d1d2,dm是G共轭的.显然，当GI时，共轭性就变为正交性，因此共轭是正交概念的推广.不难证明，若d1d2,dm是G共轭的，则它们必定线性无关.正定二次函数的共轭方向法）1x0和初始下降方向d0，置k0；2：求解minf(xkdk，得最优解；0 kk3xk1xkdk，如果||f(xk1||0xk1；k4：给出共轭方向dk1满足(dk1)TGdj0j0,1,k，置kk12.定理5.1.1 定二次函数f(x)1xTGxrTxc， (5.1.1)2f(x在线性流形{x{xR|xxd,j 0 j j

(5.1.2)j0中的极小点.证首先证明对所有的in1，都有gTgi1

i. (5.1.3)f(x是二次函数，因而有k g gGxk1xkk ji时，有Ti iTT j T j j T j

kT jgi1d

gj1d

gk1gkdkj1

gj1d

k(dkj1

)Gd

0；i1jigTdj0i1.gi10（in1gTdj0j0,1,n1.d0d1,dn1Rng0，n n这表明至多经过n次精确线搜索即可获得最优解.最后证明定理的后半部分. 由于f(x)是正定二次函数，故函数i(t,t,,t)f(x0tdj)i01 i jj0是线性流形(5.1.2)上的严格凸函数.由此可知，

min

(t0,t1,,ti)的最优解就是它的唯一驻点，即ff(xtd)d0，j0,1,,i0 jT jj

(5.1.4)j0的解.xi1处等式(5.1.3)成立，故当(t,t,,t),,,时，等式(5.1.4)01 i 0 1 ii成立，从而(t,t,,txi1x0djf(x)在线性流形(5.1.2)i01 i

jj0上的极小点.§5.2 共轭梯度法§5.2.1共轭梯度的构造

f(x)1xTGxrTxc， (5.2.1)2k1 k 其中G为nn正定矩阵，显然g(x)Gxr，且g gGxk1xkk1 k f(x)，构造共轭方向的思想如下：x0，首先取d

0gx1x0d0，其中为精确线搜索的0 0 步长.gTggTd00 0 10 1令d1gd0，使得(d1)TGd00，则有1 0gTGd0

0gT(g

g)

gTg0 1 1 1 0 11.(d0)TGd0 (d0)T(gg) gTg1 0 005.1.1gTd10gTd00，故由d0与d1gTg0gTg0.2 2 21 202 0 1 0 （3）d2gd0d1,，使得(d2TGdi02 0 1 0 由此得

gT(gg)gTg0 0，1

2 2 1 22.(d1)T(gg) gTg2 1 11（4kdk

di(dk)TGdi0，k i ii0i0,1,k1.由定理5.1.1gTdi0i0,1,k1，再由gdi的关系得kkgTg0i0,1,k1k

0,

i1,2,,k2, gTGdi gT(g g) k k i1 i

gTg

（5.2.2）i (di)TGdi (di)T(g

kk

ik1.i1 i

gTg

xk1xkkdkdk为共轭方向，k为k 最佳步长因子.对二次函数取gTdk/(dk)TGdkk 索得到k.共轭方向的修正公式为

dk1g dk， （5.2.3）gT(g （1）k k

（5.2.4）(dk)T(g

gk)gTgggT（2）kggTkk

（Fletcher-Reeves公式） （5.2.5）gT(g g)ggT（3）kggTkk

（Polak-Ribiere-Polyak公式） （5.2.6）（4）k

Tgg

（Dixon公式） （5.2.7）k(dk)TgkgTg（5）k

（Dai-Yuan公式） （5.2.8）(dk)T(g

gk).事实上，此时不存在一个常值正定矩阵G，共轭的提法都已无意义.§5.2.2共轭梯度法的性质定理5.2.1 对于正定二次函数，采用精确线搜索的共轭梯度算法，必定经过mn步迭代后终止.且对每个1im，下列关系式成立：（1）(di)TGdj0，j0,1,,i1； （5.2.9）i （2）gTg0，j0,1,,i1； （i i i （3）(di)TggTg；i i （4）

[g,g,,g][g,Gg,,Gig

]； （5.2.12）0 1 i 0 0 00 0 （5）[d0,d1,,di][g,Gg,,Gig].0 0 (5.2.9)-(5.2.11).对于i1，容易验证(5.2.9)-(5.2.11)成立.现假设这些关系式对某个im成立，下面证i1 i i 明对于i1，这些关系式仍然成立. 事实上，对g gG(xi1xi)gi1 i i iT gTdi

gTg(d)

，并注意到 i i i 0，得i (di)TGdi (di)TGdigTg

gTg

(di)TGg

gTg

(di)TG(dj

dj1).j i j i j i j i j1ji时，上式成为

ggTggi1

Tggjgg

gTg i i (di)TGdi0，(di)TGdiji时，由归纳法假设可知gTggTg(di)TG(dj dj1)0，j i j i j1于是(5.2.10)得证.i是最优步长，有(di1)TGdjgTGdj(di)TGdjgT

gjgj1(di)TGdj，i1

i i1 ji ji时，由(5.2.10)和归纳法假设知(di1)TGdj0ji时，由(5.2.10)及i i1i1(d)Gd

(d)Gdi1i1(d)i1i1T i(d)Gdi1i1(d)i1

GdiT iGd

gTg

iT igg gg ggi i i i于是(5.2.9)得证.又由didigg,g的线性组合，故有(5.2.10)知(di1)Tg

0 1 gTg

(di)Tg

gTg ，i1

i1

i1

i

i1

i1于是(5.2.11)得证.(5.2.12)与(5.2.13).当i1ggGd0gGg易见[gg[g,Gg.再由d0g1 0 0 0 0 0 0 1 0 0 0及d1gd0gg易见[d0d1]g

,g][g,Gg].1 0 1 00故当i1时，(5.2.12)与(5.2.13)成立.

0 1 0 0假定(5.2.12)与(5.2.13)对i成立. 下面证明结论对i1也成立.i1 i i i 0 0 由于g gGdi，而从归纳法假设知g,di[g,i1 i i i 0 0 i1 0 0 g [g,Gg,,i1 0 0 但i1 0 0 g [g,Gg,,Gig][d0,d1,,i1 0 0 g

i1

[d0d1,digT

0,1,ig

i1

0，矛盾.因ii1i1 0 0 [g0,i1 0 0

][g,Gg,,Gi1g],i1 再由di1g di1 0 i1 0 0 [d0,d1,,di1][g0 i1 0 0

][g,Gg,,Gi1g].注（1）Krylovk 在共轭梯度法中，dk1g dk

gTdk1gTg

gT

dkgTg

0，1

1

k

1

1k即dk1总是下降方向，若不采用精确线搜索，则不一定了；k对Dixon公式，使用不精确搜索准则

T gdk1gd

gTdk，0,1能保证搜索方向总是下降的. 事实上，由

gk1

Tgg

gk1dk，k(dk)Tgk有 gTdkgTdk1gTg1，kk

k1k1

gTdk而由gTdkgTdk知gTdkgTdk，从而k1 k kgTdkgT

1，gTdkkkdk10，故dkFletcher－Reeves共轭梯度算法用于非二次函数时，没有有限终止性质，一般经过n次搜索后，就取一次负梯度方向，称再开始.Polak-Ribiere-Polyak具有自动再开始的特点，事实上，当gk1gk，这时用Polak-Ribiere-Polyakk0，从而导致dk1FR共轭梯度法）0x0，容许误差0；01gf(x0，置k0；00 2：若||g||x0，否则，令d0g0 3：求minf(xkdk的最优解；0 kk4xk1xkdkkk1；kk 5gf(xk，若||g||xkk 6：若knx0xk1；步7：计算gTg/gTg ，dkg

dk1；kk kk8gTdk0x0xk13.k§53共轭梯度法的收敛性.本节研究将其用于一般非二次函数时的收敛性问题.§5.3.1共轭梯度法的全局收敛性定理5.3.1 设水平集Lxf(x)f(x0)有界，f是Rn上连续可微的凸函数.如果{xkFletcher-Reeves再开始共轭梯度算法产生的迭代点列，则f(xk)}为单调下降序列，且limf(xk存在.k{xk的任意聚点都是最优解.（1）在算法迭代过程中，由于每隔n次采用一次再开始措施.因而搜索方向或为共轭梯度方向，或为最速下降方向，但无论哪种情形都有kkgTdkg20.kk因而f(xk)}L有界，故f(xk)}有下界，因此limf(xkf*.k（2）由f(xk)}单调下降知{xkL，故{xk是有界点列.K k设{xk}是{xkxk1xkgK k1K由于{xk}K1

有界，故存在收敛子列{xk}K2K

lim

xkx*.K由于{xk1}K2

也是有界点列，故存在子列{xk1}K3K

，使lim

xk1x，且f(x*)f(x)limf(xk)f*.k下面用反证法证明f(x*)0. 假设不然，设f(x*)0，则对充分小的，有f(x*f(x*f(x*，注意到对任意0kK3，有k kk f(xk1)f(xkdk)f(xkg)f(xkk kk kf(x

f(x*g*)

f(x*f(x*

f(x矛盾，矛盾表明必有f(x*)0.f(xx*是minf(x的最优解.xRnK{xkxˆ{xk的子列{xk}K0

lim

由此得

f(ˆ)f(m

xk)limf(xk)minf(x)，xˆ也是minf(x的最优解.xRn

k

xRn注从这个定理的证明过程易见，上述收敛结果对其它几种再开始共轭梯度算法也是成立的.定理5.3.2 设f(x)二阶连续可微，水平集Lxf(x)m0，使得不等式

fx0有界.若存在常数my2yT2f(x)yPolak-Ribbiere-Polyak共轭梯度法产生的点列{xkf(x)的唯一极小点.gTdkg

dk

(5.3.1)k k对任意k成立即可. 成立保证定理3.2.3的夹角条件成立，故由定理3.2.3limf(xk)0k

x*是{xkf(xf(x*)0.则也有f(ˆ)00(x*ˆTf()f(ˆ)(x*ˆT2f(x*ˆ)，但这与一致凸的假设矛盾. 故{xk}收敛到f(x)的唯一极小点.x*.(5.3.1)成立.k gTdkk

2，因而不等式(5.3.1)等价于kgkdk

. （5.3.2）由于gT

dk1gTdk1gTdk1

1(dk1)TG(x

k1dt,故有

k gT

dk1

k10 k1g 2

， （5.3.3）(dk1)TG dk1 (dk1)TG1其中k10G(k1kdk1t. 注到11gg G(xk1t

dk1dt

G k k1

我们有

gT(gg )

gTG 2k1k k k1k ，2gTg

gk1结合(5.3.3)，得

T k1gG k kgG (dk1)TG

2 .gk k1Gdkgk k1Gdk1LM0G(xyMyxLyRn成立，故 gk

Mdk1MgkmMgkmk1

mdk12由此得

dkg

dk1g g (1M)g ，k

k k m kMm1M)1，则不等式(5.3.2)得证，从而定理得证.Mmmk若Wolfe-PowellFletcher-Reeves共轭梯gTdk0对任意k成立.k证明：先用归纳法证明不等式kj

gTdk k jk

（5.3.4）g2gj0 k

j0成立，其中(0,12)W-P准则中的.当k0时（5.3.4）式成为等式，故结论成立.假设对任何k0（5.34）式成立，现考虑k1情形. 由于dk1

gT(g

)

gTdk

gTdk2222k 1k12222ggk1g

gk1

gk1 kgTdgTd

，故有k1k kk

gTdk

gTdk1

gTdk1k 1k .ggg2 2 2gggk k再由归纳法假设，有k k 1 j1

jgTdk1k1k

j0gTdk1

gkgTdk k

22j2k1 1k 12,2ggk1g

2k

j0故不等式(5.3.4)得证. 由于(0,1/2)，故有kk2jj0

2 1 1

1

0，k从而由不等式(5.3.4)gTdk0对任意k成立.k定理5.3.4 设f(x)二阶连续可微，水平集LxRn

kf(xf(x0有界.设由k共轭梯度算法产生的点列全局收敛，即有kliminfgkk

0. （5.3.5）证由Wolfe-Powell准则及不等式(5.3.4)得kgTdk1k

gTdk1g2gg2

gk1 ，12g212结合dkg

dk1

kk k

k

T

gk12kdk 2k

2

Tk1 2gd gd

dk1221221

1

2 2 12gk gk

( )g1

k1d ，递推下去，可得

212dk ( )g1

kk4(gjj0j

2). （5.3.6）下面用反证法证明（5.3.5）成立.若不然，则存在常数0，使得对充分大的k，都有gk0.2由于g在水平集L上有界，从（5.3.6）可知，存在常数c，使得dk ck.因此2kgTdk

gTdkgk

1 1gkdkgkdkk gkdkgkdkcosk k k (2)

( ) ，kgdkg dk 2 kgdk

j0

112 g2 12 2 1cos2

( )2k ( )2

c ，k 1

k2 1

ck 2 kk k

k 1 kk这表明级数cos2kk

发散. 若设M为G(x)

上的上界，则有2gTdkgTdkMdk ，2k k结合Wolfe-PowellgTdkgTdk，得k1 kgTdkgTdkgTdkMdk2，k k1 k k由此得

k

1k2Mdkk2

gTdk.于是，由Wolfe-Powell准则，我们有fk1

fk

(1)M

kfk

(1)2cos2，M kk这表明f(xk)}单调下降，而由f(x)连续可微且水平集有界知f(xkklimf(xk存在.再由k(120及M

(1)M

kfkfk1，k推得cos2kk

收敛，矛盾.矛盾表明定理结论成立.§54拟牛顿法牛顿法具有收敛速率快的优点，但需要计算Hesse矩阵及其逆矩阵，单步计算量大.本Hesse矩阵或其逆的近似，一方面减少了计算量，另一方面保证了较快的收敛速率，这类算法是无约束最优化问题最重要的求解方法.§5.4.1拟牛顿法的基本思想f(x在RnHesse矩阵G(x2f(xxk1处的近似，考察f(x)xk1Taylorg(x)g

(xxk1)xxk，则有gkgk1

(xkxk1)，k k 令sxk1xk，yk k 1sk 或

G1y

s.kHesseBk1HesseHk1应分别满足y 或

Hk1yks

， （5.4.1）我们称其为拟牛顿条件.5.3（拟牛顿法）01x0R，初始近似矩阵HI，容许误差0，置k0；0k2：若gkx；步3：计算搜索方向dkHkgk（kdgkk4：沿方向dk进行线搜索，确定步长0；kk5xk1xkdk；k6HkH

更接近G1；7：置kk注3（Hese（）Hkk每次迭代需(n2)次k 运算，而牛顿法需O(n3次运算.正如牛顿法中牛顿方向Gk

G是在椭球范数||||Gk

下的最速下降方向一样，Hkgk也可看成是在椭球范数||||

HkH的最速下降方向.由于每次迭代Hk都在变化，因而度量也在变化.正因为如此，常称拟牛顿算法为变尺度法.§5.4.2对称秩一校正公式（SRI校正）H是2f(xk)1HH

k k

k k kHk的校正公式形如k1 H HuvTk1 k1k kk k k 代入拟牛顿条件，有H yHyu(vTy)s，取适当k1k kk k k 有uskHkykvTy

， （5.4.3）k5.4.kHk1k

Hk

1 (svTy

kHkyk

)vT， （5.4.4）称为一般Broyden秩一校正公式.特别地，取vyk时，称为Broyden秩一校正公式.由于HesseHk1也对称，因而取vskHkyk，由此得(sHy)(sHy)THk1Hkk kk k kk ， （5.4.5）(sHy)Tyk kk k称为对称秩一校正.5.4.1s0s1,sn1线性无关，那么对于正定二次函数，对称秩一校正方法至多nn1HG1.nHiyjsj，j0,1,,i1.当i1时，直接由（5.4.5）可知结论成立.假定结论对i1成立，现考虑i1情形，此时(sHy)(s

Hy)TyH yHy

i ii i ii j.i1j ij

(sHy)Tyi ii iji时，直接由（5.4.5）可得.ji时，由归纳法假设，有(sHy)TysTyyTHysTyyTssTGssTGs0，i ii j i j i ij i j ij i j i jjiHi1yjHiyjsj.再根据以上所得遗传性质，有j n HnyjsjHnGsjsjj0,1,n1，sHGIHGj n n nn sisiHigi也是可以sHgn nn k k kk SRIH的正定性，除非始终保持(sHy)Tk k kk kk§5.4.3 DFP校正1 k k 考虑对称秩二校正H HauuT1 k k kk k k k k kHyauuTybvvTys，取usvHy，则有auTykk k k k k ka 1 1 ，b 1 1 ，k kk k kuTy sTy vk kk k k于是，我们得到校正公式

ssT HyyTHsy yHyT Hk1Hkkkkksy yHyT kk k kk称为DFP（Davidon-Fletcher-Powell）校正公式.注DFP公式是最重要的拟牛顿校正公式，有很多重要性质.（1）（）（）当H0I（（（k定理5.4.2 当且仅当sTy0时，DFPk证用归纳法证明. 显然初始矩阵H0正定.假设结论对k成立，即Hk正定，并记HkkCholeskyHLLT.kk下面讨论k1时的情形，设aLTz,bLTy，则kT T

TssT

T (aTb)2

(sTz)2zHk1zz

(Hkkkk k)zz

kkz[aa

]k （5.4）k kk kk kyTHy sTk kk kk k故由Cauchy不等式及题设sTy0，有zTH z0.当z0时，等式(5.4.7)右端第一项kk 等式成立当且仅当ab平行，亦即当且仅当zyk平行.zyk平行时，便有 (sz)2z y,0.此时必有k

0.因而对任何z0均有zTH z0，ssyHk1正定.

T kkkk

sTy0dkHg，sdk，kk kk k kHsTg(dk)TggTHg

0，而k kk k k kk kksTysT(g g)sTg sTg.kk k k1 k kk1 kkgTs0sTy0.k1k kk而当采用非精确一维搜索（如Wolfe-Powell准则）时，只要适当提高搜索精度，就可k

sTy0.k5.4.3（DFP算法的二次终止性f(xkDFP算法是具有遗传性质和方向共轭性质，即对于i0,1,m1，有Hi1y

，j0,1,,i；sTGs0，j0,1,,i1，i nDFP算法在mn1步迭代后终止.若mn1HG1i n证用归纳法证明.当i0时，结论显然成立，假设结论对i成立.有i i ii1gTi1

gT

s(gg)TsgTsyTs0sTGs

0，j j k1j j k1k j j kj k

kj1

kj1

i1

i1

Hi1g

i1

及Gs

jyj，得sTGs

gTH

gTs

0，i1

j

j

i1ji1jsTi1j

0j0,1,i，这就证明了方向共轭性质.下面证遗传性质，即证Hi2yjsj，j0,1,,i1.由拟牛顿条件可知，H y s i，由sTy

0及i2i1yTH

i1yTs

i10，

j i1 ji1i1

j

j i1 j有ssT

y H y yTH yH yH y

i1i1j i1i1i1

i1

jH ys.i2j i1

sTy yTH

i1j ji1

i1

i1

i1

i1注由此定理可知，DFPH0I，则初始方向为负梯度方向，此时方法变成共轭梯度法.§5.4.4 PSB校正HkDFP校正公式(DFP)

ssT HyyTHHk1

Hkkkkkk ksy yHyT sy yHyT

（5.4.8）HkBkskykBk的校正公式)

yyT BssTB

Bkkkkkkk， （5.4.9）ys sBsT ys sBsT 校正公式.HkBFGS校正公式：)

yTHy ssT

syTHHysT

Hk(1k k

kk k kkk

（5.4.10a）sy sysy sy sykk kk kk (sHy)sTs(sHy)T(sHy)Ty THk k kk k k k kk k kk

（5.4.10b）sTy (sTy)2kk kksyT

ysT

ssTsy sy syT T (Ikk)Hk(Ikksy sy syT T kk kk kkHkBkskykBkDFP公式(DFP)

sTBs yyT

ysTBBsyT

(1kkk）kk

kkk kkk

（5.4.11a）ys ysys ys yskk kk kk (yBs)yTy(yBs)T(yBs)Ts Tk kk k k k kk k kk kykyk

（5.4.11b）yTs (yTs)2kk kkysT

syT

yyTys ys ysT T (Ikk)Bk(Ikkys ys ysT T kk kk kkSRIH(SRI)

(sHy)(sHy)THk1

Hkk kk k kk ， （5.4.12）(sHy)Tyk kk k进行交换后得

(yBs)(yBs)Tk kk k kk ， （5.4.13）k kk (yBk kk

H(SRISRI校正是自对偶的.注BFGSDFPPowell对一般的BroydenPSB公式.其基本思想是在一般Broyden列，然后求出这个矩阵序列的极限，则该极限矩阵是一个满足对称性和拟牛顿条件的矩阵，.BRnn

(yBs)cTCB C

CCT1 1.1 cTs 2 2C2虽然对称，却不一定满足拟牛顿条件.因而重复以上过程产生矩阵序列{Ck}，其中(yCs)cT C CTC C

2k ,C 2k1 2k1，2k1 2k

cTs

2k2 2可以证明这个矩阵序列是收敛的，其极限为(yBs)cTc(yBs)TBB cTs

(yBs)sT T(cTs)2 cc，加上下标，则得到一类秩二校正公式(yBs)cTc(yBs)T (yBs)sT Tk kk k k k kk k kk kckck，（5.4.14）cTs (cTs)2kk kk（1；若令kkk的DPc 1 y wk

Bs，其中w ，则得到关于B的BFGS校正；k w1k

yTs sBsTkyTs sBsTkk kkkk k若令cksk，则得到PSB校正公式(yBs)sTs(yBs)T

(yBs)sT T

k kk k k k kksTs

k kk (sTs)2kk kk.值HkBkykskHk1的类似校正公式.（如对偶方法，对称技术等）.有时候，还可利用一些特殊的附加条件推出校正公式.BFGS校正是由DFP校正公式经过替换与秩一矩阵求逆得到的校正公式.事实上对其它.若一个校正公式的对偶还等于其自身，则称之为自对偶.秩一校正公式反复采用对称化、应用秩一校正使其满足拟牛顿条件，类中，特别地得到PSB校正公式.§5.4.5 Huang族skHk来获得Hk1.下面考虑DFPBFGS的加权组合H (1)HDFPHBFGS， （5.4.16）k1

k1

k1容易看出

H HDFPvvTHBFGS(1)vvT, （5.4.17）1

kk 1 kk1 s Hy其中vyTHy

)2[k kk].sy yHsy yHy

T Tkk k kk当0（5.416）就是DP校正；当1（5.416）就是BGS校正；当s s k (sHy

)Ty

（.4.1RI

11(yTHy

（5.4.）)k kk k k kk kk就是Hoshino校正.族校正B BDFP(1)BBFGSBBFGSwwTBDFP(1)wwT，（5.4.18）

1

kk 1 kk1 y Bs其中w(sTBs)2[ k kk].sy ssy sBs

T Tkk kkk注由于vTy0wTs0，也可以直接验证Broyden族校正对任意的和都满kk kk足拟牛顿条件.n5.4.4（Broyden族校正二次终止性定理）f(xGHessemn1步迭代后终止.若mn1HG1.n证明略.k5.4.5（Broyden族校正的正定性）设参数0sTy0时，Broydenk证明略.HuangBroyden族更广泛的一类校正公式.Broyden族中，{Hk}是对称的且Hk1yksk.但在HuangHk对称的限制，并将拟牛顿条件进一步放松为

Hk1yksk， （5.4.19）是一个参数.为了使Huang族拟牛顿法用于二次正定函数时，所产生的搜索方向共轭，进而具有二次终止性.设Huang族校正公式的形式为k kk kkk kk kkk

suTHyvT，其中ukvk满足uas

aHTy，uTy

，vas

aHTy，vTy1.k 11k

12 kk k

k 21k

22 kk kk.1a12a21若取a11为自由参数，则有

ssT

HyyTH Tsy yHyT Hk1Hkkkkkk sy yHyT kk k kk

， （5.4.20）1 s Hy其中vyTHy

)2[k sy yHsy yHy

T Tkk k kk族是Huang族的子族.一般地，Huang族中含有三个自由参数，可产生丰富的校正公式.注（1）若采用精确一维搜索，对于正定二次函数，所有Huang族变尺度算法产生相.（2）H0I，则Huang族校正公式产生的搜索方向与F-R共轭梯度法相同，因而也是共轭方向法.§5.5 拟牛顿法的收敛性质§5.5.1一般拟牛顿算法超线性收敛的特征假设A（1）f(xDRn上二阶连续可微；f(xx*D，且2f(x*正定；2f(xx*处局部Lipschitzx*N(x*,和常数0x,yN(x*,，满足2f(y)2f(x)yx.定理55.1 设f(x)满假设A中（2又设k}一非异阵列.假定对某x0D，迭代序列kxk1xkB1f(xk)k

（5.5.1）D中且对每个kxkx*x*，则当且仅当[B[B2f(x*)](xk1xk)kxk1xkk时，序列{xkx*.

0 （5.5.2）证充分性.假设等式(5.5.2)成立.由(5.5.1)和(5.5.2)可知，2 k1 k k1 k 2 k1 k k1[kf((x x)f(x )f(x)f((x x]f(x )（.5.）1.2.3，我们有||f(xk1)|| ||[B2f(x*)]s|| ||f(xk1)f(xk)2f(x*)s|| k k k||sk|| ||sk|| ||sk||||[B

(x*)]s

k

k k||sk|| 2

(||x || ||x x*||)，由于limxkk

(5.5.2)limk

||f(xk1)||||sk||

0.又因为lim||s||0，故kkkf(x*)limf(xk1)0.k注意到2f(x*1.2.40和k，使当kk时，我们有||f(xk1)||||f(xk1)f(x*)||||xk1x*||，因此||f(xk1)|| ||xk1x*|| r其中r

k，k||xk1xk|| ||xkx*||||xk1x*|| 1rk||xk1x*||||xkx*||.注意到上式不等式左端趋向于零，我们有limr

k意味着{xkx*.

kk.假设{xk}x*f()01.240和，使当kk时，有||f(xk1)||||f(xk1)f(x*)||||xk1x*||，由此得

||xk1x*|| ||f(xk1)|| 1 ||f(xk1)||||xk1xk||0limkk

lim||xk

limx*|| ||xk1xk||

xk|| ||xk

，x*||注意到{x

x*时，有limk

x*||

1，故由(5.5.3)可推知(5.5.2)成立.定理552设f(x)满足假设A2k}.设对x0D，迭代序列

xk1xk

kB1f(xkk

（5.5.4）D中且对每个kxkx*x*.如果(5.5.2){xk超x*且f(x*0的充分必要条件是{k1.证必要性.假设{xkx*且f(x*05.5.1可知，k kxk1xk

lim[B[B2f(x*)](xk1xk)kkxk1xk

0. （5.5.5）limk

lim((11)B(xk1xk)k kxk1xk

0. （5.5.6）由于2f(x*1.2.40和k，使当kk时，有||f(xk1)||||xk1x*||，再注意到{xk

x*时，有lim

xk1xk||k

{k收k

||xx*||1..假设k}收敛到15.5.25.555.51{xkx*且f(x*)0.注（）k（ssN.k k.定理.53设f(x)A中的1与（，又设k}.假x0D，迭代序列

xk1xk

kB1f(xkkkD中且对每个kxkx*x*，由精确线性搜索产生，则当k[B2[B2f(x*)](xk1xk)kxk1xkkk成立时，一定有limkk

0和f(x*)0，从而序列{xkx*.定理.54设f(x)A中的1与（，