最優(yōu)化理論 第四章 最速下降法與牛頓法

2.1的關(guān)鍵步驟——確定目標(biāo)函數(shù)的下降方向.§4.1最速下降法在§2.4f(xxk處下降，搜索方向dk必須滿足不等式

f(xk)Tdk0.向量f(xkdk的內(nèi)積f(xk)Tdk||f(xk)||||dk||cos， (4.1.1)其中是向量f(xk和dkdk是下降方向的充分必要條件為它與f(xk的夾角必須大于2，或者說(shuō)，它與f(xk的夾角必須小于2.k僅是負(fù)的，而且絕對(duì)值越大，目標(biāo)函數(shù)的下降越多. 因此，我們希望搜索方向dk是優(yōu)化問(wèn)k題mind0

f(xk)Td||d||

(4.1.2)(4.1.1)易見，dkf(xk||f(xk||是優(yōu)化問(wèn)題(4.1.2)的最優(yōu)解.因此，我們把dkf(xk稱為最速下降方向.§4.1.1最速下降算法降法，它是無(wú)約束最優(yōu)化算法中最簡(jiǎn)單、最基本的算法.4.1（最速下降法）1x0n，容許誤差0k0；2：計(jì)算f(xk，若||f(xk||xk；3：令dkf(xk；步4：由線搜索確定步長(zhǎng)因子k，譬如，取k使得f(xkdk)minf(xkdk)；k 0k5xk1xkdkkk12.k交的.kdkf(xk，對(duì)一元函數(shù)(f(xkdk，精確線搜索的最優(yōu)步長(zhǎng)因子k應(yīng)滿足(k0，即kkf(xkdk)Tdk0，xk1xkdk，又dk1f(xk1，故有kk(dk)Tdk10. (4.1.3)（迭代點(diǎn)列呈鋸齒狀趨于最優(yōu)解）.好的總體收斂性，但缺點(diǎn)是在實(shí)際應(yīng)用中收斂速率慢.§4.1.2 最速下降法的收斂性定理4.1.1 設(shè)fC1，則最速下降法產(chǎn)生的點(diǎn)列{xk}的每個(gè)聚點(diǎn)均為駐點(diǎn).K1x是{xk{xk}K1

limxkxdkf(xk，kK1KfC1知{f(xk)}K1

收斂，故{dk}K1K

有界，且limdkf(x3.2.2，有kK1f(x)T[f(x)]f(x)20，故有f(x0.定理4.1.2 若f(x)二階連續(xù)可微且2f(x)M則對(duì)任意給定的初始點(diǎn)x0n，最速下降法或有限終止，或limf(xk)，或limf(xk)0.k k證不妨設(shè)對(duì)任意k都有f(xk03.2.1，有12Mf(xk)f(xk1) f(xk)212M于是kkf(x0)f(xk)f(xi)f(xi1)1

f(xi)2. i0

2Mi0由于f(xk)}為單調(diào)下降序列，故或有l(wèi)imf(xk，或有l(wèi)imf(xk)0.k k定理4.1.3 設(shè)fC1則最速下降法采用不精確線搜索得到的點(diǎn)列{xk}的每個(gè)聚點(diǎn)均為駐點(diǎn).3.4.2可得.§4.1.3 最速下降法的收斂速率我們先來(lái)考察一般的正定二次函數(shù)f(x)1xTGxrTx，2其中G為n階對(duì)稱正定矩陣. 設(shè)x*是極小點(diǎn)，則f(x)可表示為f(x)1(xx*)TG(xx*)1(x*)TGx*，2 2f(x)1xTGx.2定理4.1.4 對(duì)極小化問(wèn)題minf(x)1xTGx，其中G為n階對(duì)稱正定矩陣，，xRn 2 1 nxk1x*xkxxk1x*xkx*1nf(xk1)f(x*)

()2

1n1 n ，1n

1 n.f(xk)f(x*)

)2

n證由于f(xGx，故k k k k xk1xkdkxkf(xk)xkGxk(IG)xk，其中f[(IG)xkf[(IG)xk對(duì)任意k k k k P(t)1kt，Q(t)utuRQ(0)Q(G)IuG，由此可知，當(dāng)0u0時(shí)，我們有f(xk1)f[(IG)xk]f(Q(G)xk)k Q(0)1(Q(G)xk)TG(Q(G)xk)

1 (Q(G)xk)TG(Q(G)xk).2Q(0) Q(0) 2Q2(0)設(shè)

是G的特征值，而ui(i12,n是對(duì)應(yīng)得標(biāo)準(zhǔn)特征向量（兩兩1 2 n正交的單位向量）.xk

nniii1

akui，代入上式，得f(xk1) 1

akQGuiTG

akQ(G)uj)2Q2(0)

ni1n

i jj1 1 (n

akQ(uiTG

akQ()uj)2Q2(0)

ni1n

i i j jj1 1 (n

akQ(uiT

akQ()uj)2Q2(0)

ni1n

i i j j jj1i i i i 2Q2(0)i1

(ak)2Q2().對(duì)Q(tut，通過(guò)令Q(11,Q(n1，我們來(lái)確定待定參數(shù)u，由此得1n,u 2 ，從而有Qt)t1n.

顯然Q(t單調(diào)增加，由Q(11,Q(n1及12,n，即得

于是，由

i i f(xk1)i i (0)i1

(ak)2Q2()

1 n2Q2(0)i1

(ak)2，i i 1n1k kiT

n kj 1 n

n n1kiT k j k21f(x

)2(iu

G(aj

)2(iu)(ajj

)2i(ai)，i1

i1

i1f(xk)

2我們有f(xk1) .又由于Q2(0)1 n

，因此，對(duì)任意k，都有Q2(0)

n2f(xk1)1 n1n

f(xk). (4.1.4)由于01n1f(xk)0f()(k)f(x)1nxk0x*(k)，即點(diǎn)列{xkx*0.(4.1.4)得到第一個(gè)估計(jì)式f(xk1)f(x*)

f(xk1) 2 1 n.f(xk)f(x*)

f(xk)

n記ekxkx*，由G的對(duì)稱正定性，對(duì)任意k，我們有(ek)Tek(ek)TGek(ek)Tek，n 1x*0(ek)TGekxk)TGxk2f(xk)k，有(ek)Tek2f(xk)(ek)Tek.n 1(4.1.4)，可得

(ek1)Tek1

2f(x

2xk1x*2xk1x* n 11 n，xkx*2

(ek)Tek

2f(xk)1

.如果令1n

GG1

，即為矩陣G的條件數(shù)，則上式可寫成xk1xk1x*xkx*(1)(1).4.1.5f(x3.2.7的假設(shè)條件，若最速下降算法產(chǎn)生的點(diǎn)列{xk收斂x*R線性的.3.2.7的自然推論.§4.2牛頓法§4.2.1牛頓迭代公式f(xxkTaylor展開式的極小xk1f(x的一個(gè)更佳近似解，由此產(chǎn)生算法的基本迭代格式.xk2f(xkf(xxkTaylor展開式為q(k)(s)f(xk)f(xk)Ts1sT2f(xk)s，2sxxk，極小化q(ks)得sk2f(xk)1f(xk，由此得到牛頓法的基本迭代格式xk1xk2f(xk)1f(xk). (4.2.1)g(xG(x)f(x)的梯度f(wàn)(x)Hessiank矩陣2f(xgk

f(xk)，G

2f(xk).k注（1）牛頓法可視為橢球范數(shù)|2f(xkk

下的最速下降法. 事實(shí)上，歐氏空間Rn中一般范數(shù)||||下的方向?qū)?shù)定義為：tsdftsds

t0

f(xkts)f(xk)

f(xk)Tss，ss它顯然與范數(shù)||||有關(guān).不難理解，minssRn

f(xk)Ts

的最優(yōu)解就是函數(shù)f(x在xk處對(duì)應(yīng)于范數(shù)||||的最速下降方向，且這個(gè)解與所取的范數(shù)有關(guān).G若取橢球范數(shù)||||Gk

，則對(duì)任意sRn，有T 1

(G1g

G1g sgTsksGksGkgkkks k k kgTsksGksGksGk

k kGk

GkG1g ，sGkksGkk k 這意味著G1k

為方向?qū)?shù)的下界. 另一方面，若取sG1gk Gk s2s

，則有g(shù)Ts gTG1g (G1g)TG(G1g) G k k k k k k k k k kG1g ，s sGk Gk

s sGk

k kGk這表明方向?qū)?shù)能夠達(dá)到下界G1g

是關(guān)于橢球范數(shù)||||

的最速下降方向.

k kGk

k k k Gk（2）無(wú)約束最優(yōu)化問(wèn)題的牛頓法也可以理解為非線性方程組的牛頓法，這是因?yàn)榍蠼鈓infx的經(jīng)典方法實(shí)際上是在尋找f(x的一個(gè)駐點(diǎn)，即求解非線性方程組f(x)0.xRn設(shè)xk是當(dāng)前迭代點(diǎn)，若f(xk0xk是方程組的解，否則將f(xxk處線性化，得

f(x)f(xk)2f(xk)(xxk)0，將上述線性方程組的解xxk2f(xk)1f(xk作為f(x)0牛頓迭代公式（4.2.1）.§4.2.2牛頓法的收斂性定理4.2.1fC2xkx*，而f(x*02f(x*)正定.若Hessian矩陣2f(xLipschitz條件，則由牛頓法產(chǎn)生的序列{xkx*，且具有二階收斂速率.fC2，2f(xLipschitzxkx*時(shí)，由定理1.2.1可知，存在0，使得||f(x*)f(xk

)2

f(x

k)(x*xk

||x*xk2

||2，fC2，2f(x*可逆（正定矩陣必定可逆）1.1.1x*的充分小鄰域內(nèi)，2f(xM0，滿足||2f(x)1||M.xk充分靠近極小x*時(shí)，對(duì)任意k，我們有||xk1x*||||xk2f(xk)1f(xk)x*||||2f(xk)1||||f(xk)(x*xk)2f(xk)||M||f(x*)||||x*xk||2 2 M2

||x*xk

||2，M||x*xk||r1，則有2.

0(k，即迭代點(diǎn)列{xk收斂，k索；而牛頓法的缺點(diǎn)是不能保證全局收斂，當(dāng)G不正定時(shí)，甚至不能保證dk是下降方向，算法需要計(jì)算Hessian矩陣，單步計(jì)算量大.k§4.2.3 阻尼牛頓法搜索過(guò)程.4.2（阻尼牛頓法）1x0Rn，容許誤差0，置k0；2gk，若gkx；k3：確定牛頓方向，從牛頓方程Gkdgk

解出dk；4：沿dk進(jìn)行線搜索，使得f(xkdkminf(xkdk)；k k 0k5xk1xkdk，置kk12.k4.2.2fRnRx0Rn，存在常數(shù)m0，使得f(x)L(x0{xf(x)f(x0上滿足不等式uT2f(x)umu2，uRn，k則采用精確線搜索的阻尼牛頓法產(chǎn)生的迭代點(diǎn)列{xk或者對(duì)某個(gè)kg0，或者{xk收f(shuō)x*.kk證不妨設(shè)對(duì)任意kg0.由定理的條件知，f(xL(x0f(x)kL(x0f(xL(x0f(x的極小點(diǎn).下面證明{xk}f(x的駐點(diǎn).由f(x)L(x0)L(x0)是有界閉凸集，再由f(xk)單調(diào)下降，可知K{xkL(x0，故{xkxL(x0及子列{xk}，使得K1lim

xkx. 再由f(xk)單調(diào)有界知limf(xk k

f(x，特別地，有l(wèi)im

f(xk)f(x).L(x0是有界閉集，故f(x)L(x0上一致連續(xù)，且由fC2知，存在常數(shù)M0L(x0上有G(x)M，因此，對(duì)任意k，有g(shù)Tdk

k)TGdk

(dk)TGdk mmdk2kkk2cos k k k ，mdk2kkk2kg dkk

g

Gdk

Mdk M由此知

k2

M

. 3.2.3，有f(xk)g2

0，從而f(x)0xf(x的駐點(diǎn)，它也是極小點(diǎn).x0.xkx，則存在正數(shù)和一個(gè)子x0K序列{xk}K2

，使對(duì)一切kK2，有

xk

0

.注意到{xk}K2K

是有界點(diǎn)列，故存在收斂K子列{xk}K3

(K3K2

limlim

f(xk)f(?)，32.，可得f(?)0，從而?也是f(x)?xf(x的極小點(diǎn)唯一矛盾，故必有{xkx.§4.3牛頓法的修正策略kG1不存在；kk k Gk k

G1g

可能不是下降方向..§4.3.1 Goldstein—Price修正方案當(dāng)Gk非正定時(shí)，采用最速下降方向gk替代牛頓方向.若進(jìn)一步將搜索方向與負(fù)梯度方向的角度準(zhǔn)則結(jié)合起來(lái)，則有dk

dk,g

,dkN N kgk,

否則,這里dkG1g，這樣搜索方向dk總滿足cosdkg

.N k k k.牛頓法的局部快速收斂性質(zhì).§4.3.2 Goldfeld修正方案若Gk不正定，則用GkGkvkI來(lái)修正Gk.通過(guò)適當(dāng)選取vk0，可以使Gk正定.事實(shí)上，只要將vk取得稍大于Gk的最小特征值的模即可.利用特征值的圓盤定理可以求得最小特征值的模的估計(jì) mini min(Gk)ii(Gk)ij. i 1in

ji 用此方法可求出vkvkGk與Gk相差甚遠(yuǎn)，這是一個(gè)缺陷.而實(shí)際求出Gk的全部特征值計(jì)算量又太大，因此，這個(gè)方法更多的是理論的價(jià)值.§4.3.3 基于GkCholesky分解的方案先作GkCholesky分解GLDL，然后令kTkGLDLT，kDdiag(d11,dnndiimaxdii,diiD為給定的小正數(shù).k這種處理方法簡(jiǎn)單，但有下列缺陷：當(dāng)Gk不可逆或GkGkCholesky分解不存在.即使Gk的分解存在，其計(jì)算過(guò)程也可能數(shù)值不穩(wěn)定.計(jì)算過(guò)程中小的誤差會(huì)導(dǎo)致結(jié)果的巨大差別，同時(shí)還可能出現(xiàn)Gk與Gk的差別很大.§4.3.4 GillMurray修正方案Gill—Murray修正法也稱為強(qiáng)迫矩陣正定的Cholesky分解法，它在Gk的分解過(guò)程中進(jìn)行適當(dāng)修正，使dLDLT不是ii k真正的Gk，而是Gk的近似Gk.其要點(diǎn)在于：在分解過(guò)程中，增加了保證分解得到的因子矩陣元素一致有界的措施.在過(guò)程完成時(shí)，得到

E，k kE是非負(fù)對(duì)角矩陣.dii及因子矩陣元素一致有界，必須對(duì)Gk的元素進(jìn)行調(diào)整，否則算法進(jìn)行不下去，但必須指出的是，所有調(diào)整都只涉及Gk的對(duì)角元素，通常是將其增大，這就保證了即Gk與Gk僅差一個(gè)對(duì)角矩陣.可以證明，當(dāng)Gk充分正定時(shí)，有GkGk.Gill—Murray修正牛頓法有如下收斂性質(zhì).設(shè)f(x)在Rnx0使L(x0xf(x)f(x0為有界閉凸集，x1L(x0，則由Gill—Murray修正牛頓法產(chǎn)生的點(diǎn)列{xk滿足：若{xk是有限點(diǎn)列時(shí)，它的最后一個(gè)點(diǎn)必為f(x的駐點(diǎn)；若{xk是無(wú)窮點(diǎn)列時(shí)，它必有聚點(diǎn)，且任一聚點(diǎn)均為f(x的駐點(diǎn).§4.4 負(fù)曲率方向法§4.4.1負(fù)曲率方向負(fù)曲率方向法是修正牛頓法的又一種形式.當(dāng)2f(xk到下降方向，尤其在鞍點(diǎn)處，即f(xk)0，而2f(xk不是半正定時(shí)，若采用負(fù)曲率方向作為搜索方向，可以使目標(biāo)函數(shù)下降.f(xD上二階連續(xù)可微，若2f(xxD稱為不xddT2f(x)d0df(x)x處的負(fù)d是負(fù)曲率方向，顯然dsTf(x0dTf(x0，dT2f(x)d0，則稱向量對(duì)sdxx不是一個(gè)不定點(diǎn)，則滿足：sTf(x)0，dTf(x0，dT2f(x)d0的向量對(duì)(sd)x處的下降對(duì).

sf

若2fx)0,否則,其中u是對(duì)應(yīng)于2f(x的負(fù)特征值的特征向量，則向量對(duì)(sd)x處的一個(gè)下降對(duì).由定義易見，當(dāng)且僅當(dāng)f(x)0且2f(x0x處不存在下降對(duì).因此，一旦在該點(diǎn)不存在下降對(duì)，那么該點(diǎn)必滿足極小點(diǎn)的二階必要條件（但仍不一定是極小點(diǎn)）.若x*是鞍點(diǎn)，則負(fù)曲率方向必為下降方向. 事實(shí)上，設(shè)d為負(fù)曲率方向，由f(x*d)f(x*)f(x*)Td12dT2f(x*)d(d2)2容易看出，當(dāng)很小時(shí)，有f(x*d)f(x*).x為一般點(diǎn)，且負(fù)曲率方向d滿足dTf(x)0，則d與d均為下降方向.若dTf(x0，則ddTf(x0，則d是下降方向..而唯一難找到下降方向的情形f(x0且2f(x0時(shí).Gill-MurrayCholesky分解與負(fù)曲率方向相結(jié)合.當(dāng)Gk不正定時(shí)，采用修改Choleskygk0時(shí)，采用負(fù)曲率方向使函數(shù)值下降.Fiacco-