最優(yōu)化理論 第五章 共軛梯度法和擬牛頓法

§5.1共軛方向法點列呈鋸齒形前進(jìn)，收斂慢的缺點，同時又不像牛頓法中計算牛頓方向耗費大量的工作量，尤其是共軛方向法具有二次終止性.設(shè)G是nn對稱正定矩陣，d1d2是n維非零向量，若(d1)TGd20，則稱d1d2是G共軛的；如果Rn中一組非零向量d1,d2,,dm兩兩共軛，即(di)TGdj0(ij) 則稱向量組d1d2,dm是G共軛的.顯然，當(dāng)GI時，共軛性就變?yōu)檎恍裕虼斯曹検钦桓拍畹耐茝V.不難證明，若d1d2,dm是G共軛的，則它們必定線性無關(guān).正定二次函數(shù)的共軛方向法）1x0和初始下降方向d0，置k0；2：求解minf(xkdk，得最優(yōu)解；0 kk3xk1xkdk，如果||f(xk1||0xk1；k4：給出共軛方向dk1滿足(dk1)TGdj0j0,1,k，置kk12.定理5.1.1 定二次函數(shù)f(x)1xTGxrTxc， (5.1.1)2f(x在線性流形{x{xR|xxd,j 0 j j

(5.1.2)j0中的極小點.證首先證明對所有的in1，都有g(shù)Tgi1

i. (5.1.3)f(x是二次函數(shù)，因而有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這表明至多經(jīng)過n次精確線搜索即可獲得最優(yōu)解.最后證明定理的后半部分. 由于f(x)是正定二次函數(shù)，故函數(shù)i(t,t,,t)f(x0tdj)i01 i jj0是線性流形(5.1.2)上的嚴(yán)格凸函數(shù).由此可知，

min

(t0,t1,,ti)的最優(yōu)解就是它的唯一駐點，即ff(xtd)d0，j0,1,,i0 jT jj

(5.1.4)j0的解.xi1處等式(5.1.3)成立，故當(dāng)(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共軛梯度的構(gòu)造

f(x)1xTGxrTxc， (5.2.1)2k1 k 其中G為nn正定矩陣，顯然g(x)Gxr，且g gGxk1xkk1 k f(x)，構(gòu)造共軛方向的思想如下：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的關(guān)系得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 最佳步長因子.對二次函數(shù)取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共軛梯度法的性質(zhì)定理5.2.1 對于正定二次函數(shù)，采用精確線搜索的共軛梯度算法，必定經(jīng)過mn步迭代后終止.且對每個1im，下列關(guān)系式成立：（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)成立.現(xiàn)假設(shè)這些關(guān)系式對某個im成立，下面證i1 i i 明對于i1，這些關(guān)系式仍然成立. 事實上，對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時，由歸納法假設(shè)可知gTggTg(di)TG(dj dj1)0，j i j i j1于是(5.2.10)得證.i是最優(yōu)步長，有(di1)TGdjgTGdj(di)TGdjgT

gjgj1(di)TGdj，i1

i i1 ji ji時，由(5.2.10)和歸納法假設(shè)知(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).當(dāng)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故當(dāng)i1時，(5.2.12)與(5.2.13)成立.

0 1 0 0假定(5.2.12)與(5.2.13)對i成立. 下面證明結(jié)論對i1也成立.i1 i i i 0 0 由于g gGdi，而從歸納法假設(shè)知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公式，使用不精確搜索準(zhǔn)則

T gdk1gd

gTdk，0,1能保證搜索方向總是下降的. 事實上，由

gk1

Tgg

gk1dk，k(dk)Tgk有 gTdkgTdk1gTg1，kk

k1k1

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

1，gTdkkkdk10，故dkFletcher－Reeves共軛梯度算法用于非二次函數(shù)時，沒有有限終止性質(zhì)，一般經(jīng)過n次搜索后，就取一次負(fù)梯度方向，稱再開始.Polak-Ribiere-Polyak具有自動再開始的特點，事實上，當(dāng)gk1gk，這時用Polak-Ribiere-Polyakk0，從而導(dǎo)致dk1FR共軛梯度法）0x0，容許誤差0；01gf(x0，置k0；00 2：若||g||x0，否則，令d0g0 3：求minf(xkdk的最優(yōu)解；0 kk4xk1xkdkkk1；kk 5gf(xk，若||g||xkk 6：若knx0xk1；步7：計算gTg/gTg ，dkg

dk1；kk kk8gTdk0x0xk13.k§53共軛梯度法的收斂性.本節(jié)研究將其用于一般非二次函數(shù)時的收斂性問題.§5.3.1共軛梯度法的全局收斂性定理5.3.1 設(shè)水平集Lxf(x)f(x0)有界，f是Rn上連續(xù)可微的凸函數(shù).如果{xkFletcher-Reeves再開始共軛梯度算法產(chǎn)生的迭代點列，則f(xk)}為單調(diào)下降序列，且limf(xk存在.k{xk的任意聚點都是最優(yōu)解.（1）在算法迭代過程中，由于每隔n次采用一次再開始措施.因而搜索方向或為共軛梯度方向，或為最速下降方向，但無論哪種情形都有kkgTdkg20.kk因而f(xk)}L有界，故f(xk)}有下界，因此limf(xkf*.k（2）由f(xk)}單調(diào)下降知{xkL，故{xk是有界點列.K k設(shè){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. 假設(shè)不然，設(shè)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的最優(yōu)解.xRnK{xkx?{xk的子列{xk}K0

lim

由此得

f(?)f(m

xk)limf(xk)minf(x)，x?也是minf(x的最優(yōu)解.xRn

k

xRn注從這個定理的證明過程易見，上述收斂結(jié)果對其它幾種再開始共軛梯度算法也是成立的.定理5.3.2 設(shè)f(x)二階連續(xù)可微，水平集Lxf(x)m0，使得不等式

fx0有界.若存在常數(shù)my2yT2f(x)yPolak-Ribbiere-Polyak共軛梯度法產(chǎn)生的點列{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*?)，但這與一致凸的假設(shè)矛盾. 故{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結(jié)合(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準(zhǔn)則中的.當(dāng)k0時（5.3.4）式成為等式，故結(jié)論成立.假設(shè)對任何k0（5.34）式成立，現(xiàn)考慮k1情形. 由于dk1

gT(g

)

gTdk

gTdk2222k 1k12222ggk1g

gk1

gk1 kgTdgTd

，故有k1k kk

gTdk

gTdk1

gTdk1k 1k .ggg2 2 2gggk k再由歸納法假設(shè)，有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 設(shè)f(x)二階連續(xù)可微，水平集LxRn

kf(xf(x0有界.設(shè)由k共軛梯度算法產(chǎn)生的點列全局收斂，即有kliminfgkk

0. （5.3.5）證由Wolfe-Powell準(zhǔn)則及不等式(5.3.4)得kgTdk1k

gTdk1g2gg2

gk1 ，12g212結(jié)合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）成立.若不然，則存在常數(shù)0，使得對充分大的k，都有g(shù)k0.2由于g在水平集L上有界，從（5.3.6）可知，存在常數(shù)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這表明級數(shù)cos2kk

發(fā)散. 若設(shè)M為G(x)

上的上界，則有2gTdkgTdkMdk ，2k k結(jié)合Wolfe-PowellgTdkgTdk，得k1 kgTdkgTdkgTdkMdk2，k k1 k k由此得

k

1k2Mdkk2

gTdk.于是，由Wolfe-Powell準(zhǔn)則，我們有fk1

fk

(1)M

kfk

(1)2cos2，M kk這表明f(xk)}單調(diào)下降，而由f(x)連續(xù)可微且水平集有界知f(xkklimf(xk存在.再由k(120及M

(1)M

kfkfk1，k推得cos2kk

收斂，矛盾.矛盾表明定理結(jié)論成立.§54擬牛頓法牛頓法具有收斂速率快的優(yōu)點，但需要計算Hesse矩陣及其逆矩陣，單步計算量大.本Hesse矩陣或其逆的近似，一方面減少了計算量，另一方面保證了較快的收斂速率，這類算法是無約束最優(yōu)化問題最重要的求解方法.§5.4.1擬牛頓法的基本思想f(x在RnHesse矩陣G(x2f(xxk1處的近似，考察f(x)xk1Taylorg(x)g

(xxk1)xxk，則有g(shù)kgk1

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

G1y

s.kHesseBk1HesseHk1應(yīng)分別滿足y 或

Hk1yks

， （5.4.1）我們稱其為擬牛頓條件.5.3（擬牛頓法）01x0R，初始近似矩陣HI，容許誤差0，置k0；0k2：若gkx；步3：計算搜索方向dkHkgk（kdgkk4：沿方向dk進(jìn)行線搜索，確定步長0；kk5xk1xkdk；k6HkH

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

G是在橢球范數(shù)||||Gk

下的最速下降方向一樣，Hkgk也可看成是在橢球范數(shù)||||

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，取適當(dāng)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線性無關(guān)，那么對于正定二次函數(shù)，對稱秩一校正方法至多nn1HG1.nHiyjsj，j0,1,,i1.當(dāng)i1時，直接由（5.4.5）可知結(jié)論成立.假定結(jié)論對i1成立，現(xiàn)考慮i1情形，此時(sHy)(s

Hy)TyH yHy

i ii i ii j.i1j ij

(sHy)Tyi ii iji時，直接由（5.4.5）可得.ji時，由歸納法假設(shè)，有(sHy)TysTyyTHysTyyTssTGssTGs0，i ii j i j i ij i j ij i j i jjiHi1yjHiyjsj.再根據(jù)以上所得遺傳性質(zhì)，有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公式是最重要的擬牛頓校正公式，有很多重要性質(zhì).（1）（）（）當(dāng)H0I（（（k定理5.4.2 當(dāng)且僅當(dāng)sTy0時，DFPk證用歸納法證明. 顯然初始矩陣H0正定.假設(shè)結(jié)論對k成立，即Hk正定，并記HkkCholeskyHLLT.kk下面討論k1時的情形，設(shè)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不等式及題設(shè)sTy0，有zTH z0.當(dāng)z0時，等式(5.4.7)右端第一項kk 等式成立當(dāng)且僅當(dāng)ab平行，亦即當(dāng)且僅當(dāng)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而當(dāng)采用非精確一維搜索（如Wolfe-Powell準(zhǔn)則）時，只要適當(dāng)提高搜索精度，就可k

sTy0.k5.4.3（DFP算法的二次終止性f(xkDFP算法是具有遺傳性質(zhì)和方向共軛性質(zhì)，即對于i0,1,m1，有Hi1y

，j0,1,,i；sTGs0，j0,1,,i1，i nDFP算法在mn1步迭代后終止.若mn1HG1i n證用歸納法證明.當(dāng)i0時，結(jié)論顯然成立，假設(shè)結(jié)論對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，這就證明了方向共軛性質(zhì).下面證遺傳性質(zhì)，即證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，則初始方向為負(fù)梯度方向，此時方法變成共軛梯度法.§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進(jìn)行交換后得

(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雖然對稱，卻不一定滿足擬牛頓條件.因而重復(fù)以上過程產(chǎn)生矩陣序列{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，加上下標(biāo)，則得到一類秩二校正公式(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 ，則得到關(guān)于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的類似校正公式.（如對偶方法，對稱技術(shù)等）.有時候，還可利用一些特殊的附加條件推出校正公式.BFGS校正是由DFP校正公式經(jīng)過替換與秩一矩陣求逆得到的校正公式.事實上對其它.若一個校正公式的對偶還等于其自身，則稱之為自對偶.秩一校正公式反復(fù)采用對稱化、應(yīng)用秩一校正使其滿足擬牛頓條件，類中，特別地得到PSB校正公式.§5.4.5 Huang族skHk來獲得Hk1.下面考慮DFPBFGS的加權(quán)組合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當(dāng)0（5.416）就是DP校正；當(dāng)1（5.416）就是BGS校正；當(dāng)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族校正的正定性）設(shè)參數(shù)0sTy0時，Broydenk證明略.HuangBroyden族更廣泛的一類校正公式.Broyden族中，{Hk}是對稱的且Hk1yksk.但在HuangHk對稱的限制，并將擬牛頓條件進(jìn)一步放松為

Hk1yksk， （5.4.19）是一個參數(shù).為了使Huang族擬牛頓法用于二次正定函數(shù)時，所產(chǎn)生的搜索方向共軛，進(jìn)而具有二次終止性.設(shè)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為自由參數(shù)，則有

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族中含有三個自由參數(shù)，可產(chǎn)生豐富的校正公式.注（1）若采用精確一維搜索，對于正定二次函數(shù)，所有Huang族變尺度算法產(chǎn)生相.（2）H0I，則Huang族校正公式產(chǎn)生的搜索方向與F-R共軛梯度法相同，因而也是共軛方向法.§5.5 擬牛頓法的收斂性質(zhì)§5.5.1一般擬牛頓算法超線性收斂的特征假設(shè)A（1）f(xDRn上二階連續(xù)可微；f(xx*D，且2f(x*正定；2f(xx*處局部Lipschitzx*N(x*,和常數(shù)0x,yN(x*,，滿足2f(y)2f(x)yx.定理55.1 設(shè)f(x)滿假設(shè)A中（2又設(shè)k}一非異陣列.假定對某x0D，迭代序列kxk1xkB1f(xk)k

（5.5.1）D中且對每個kxkx*x*，則當(dāng)且僅當(dāng)[B[B2f(x*)](xk1xk)kxk1xkk時，序列{xkx*.

0 （5.5.2）證充分性.假設(shè)等式(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，使當(dāng)kk時，我們有||f(xk1)||||f(xk1)f(x*)||||xk1x*||，因此||f(xk1)|| ||xk1x*|| r其中r

k，k||xk1xk|| ||xkx*||||xk1x*|| 1rk||xk1x*||||xkx*||.注意到上式不等式左端趨向于零，我們有l(wèi)imr

k意味著{xkx*.

kk.假設(shè){xk}x*f()01.240和，使當(dāng)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*時，有l(wèi)imk

x*||

1，故由(5.5.3)可推知(5.5.2)成立.定理552設(shè)f(x)滿足假設(shè)A2k}.設(shè)對x0D，迭代序列

xk1xk

kB1f(xkk

（5.5.4）D中且對每個kxkx*x*.如果(5.5.2){xk超x*且f(x*0的充分必要條件是{k1.證必要性.假設(shè){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，使當(dāng)kk時，有||f(xk1)||||xk1x*||，再注意到{xk

x*時，有l(wèi)im

xk1xk||k

{k收k

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

xk1xk

kB1f(xkkkD中且對每個kxkx*x*，由精確線性搜索產(chǎn)生，則當(dāng)k[B2[B2f(x*)](xk1xk)kxk1xkkk成立時，一定有l(wèi)imkk

0和f(x*)0，從而序列{xkx*.定理.54設(shè)f(x)A中的1與（，