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

§5.1共軛方向法點列呈鋸齒形前進，收斂慢的缺點，同時又不像牛頓法中計算牛頓方向耗費大量的工作量，尤其是共軛方向法具有二次終止性.設(shè)G是nn對稱正定矩陣，d1d2是n維非零向量，若(d1)TGd20，則稱d1d2是G共軛的；如果Rn中一組非零向量d1,d2,,dm兩兩共軛，即(di)TGdj0(ij) 則稱向量組d1d2,dm是G共軛的.顯然，當(dāng)GI時，共軛性就變?yōu)檎恍?，因此共軛是正交概念的推廣.不難證明，若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次搜索后，就取一次負梯度方向，稱再開始.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進行線搜索，確定步長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，則初始方向為負梯度方向，此時方法變成共軛梯度法.§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雖然對稱，卻不一定滿足擬牛頓條件.因而重復(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對稱的限制，并將擬牛頓條件進一步放松為

Hk1yksk， （5.4.19）是一個參數(shù).為了使Huang族擬牛頓法用于二次正定函數(shù)時，所產(chǎ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與（，