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

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

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

f(xk)Td||d||

(4.1.2)(4.1.1)易見，dkf(xk||f(xk||是優(yōu)化問題(4.1.2)的最優(yōu)解.因此，我們把dkf(xk稱為最速下降方向.§4.1.1最速下降算法降法，它是無約束最優(yōu)化算法中最簡單、最基本的算法.4.1（最速下降法）1x0n，容許誤差0k0；2：計算f(xk，若||f(xk||xk；3：令dkf(xk；步4：由線搜索確定步長因子k，譬如，取k使得f(xkdk)minf(xkdk)；k 0k5xk1xkdkkk12.k交的.kdkf(xk，對一元函數(f(xkdk，精確線搜索的最優(yōu)步長因子k應滿足(k0，即kkf(xkdk)Tdk0，xk1xkdk，又dk1f(xk1，故有kk(dk)Tdk10. (4.1.3)（迭代點列呈鋸齒狀趨于最優(yōu)解）.好的總體收斂性，但缺點是在實際應用中收斂速率慢.§4.1.2 最速下降法的收斂性定理4.1.1 設fC1，則最速下降法產生的點列{xk}的每個聚點均為駐點.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則對任意給定的初始點x0n，最速下降法或有限終止，或limf(xk)，或limf(xk)0.k k證不妨設對任意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)}為單調下降序列，故或有l(wèi)imf(xk，或有l(wèi)imf(xk)0.k k定理4.1.3 設fC1則最速下降法采用不精確線搜索得到的點列{xk}的每個聚點均為駐點.3.4.2可得.§4.1.3 最速下降法的收斂速率我們先來考察一般的正定二次函數f(x)1xTGxrTx，2其中G為n階對稱正定矩陣. 設x*是極小點，則f(x)可表示為f(x)1(xx*)TG(xx*)1(x*)TGx*，2 2f(x)1xTGx.2定理4.1.4 對極小化問題minf(x)1xTGx，其中G為n階對稱正定矩陣，，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對任意k k k k P(t)1kt，Q(t)utuRQ(0)Q(G)IuG，由此可知，當0u0時，我們有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)設

是G的特征值，而ui(i12,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().對Q(tut，通過令Q(11,Q(n1，我們來確定待定參數u，由此得1n,u 2 ，從而有Qt)t1n.

顯然Q(t單調增加，由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

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

n2f(xk1)1 n1n

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

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

f(xk)

n記ekxkx*，由G的對稱正定性，對任意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的條件數，則上式可寫成xk1xk1x*xkx*(1)(1).4.1.5f(x3.2.7的假設條件，若最速下降算法產生的點列{xk收斂x*R線性的.3.2.7的自然推論.§4.2牛頓法§4.2.1牛頓迭代公式f(xxkTaylor展開式的極小xk1f(x的一個更佳近似解，由此產生算法的基本迭代格式.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(x)Hessiank矩陣2f(xgk

f(xk)，G

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

下的最速下降法. 事實上，歐氏空間Rn中一般范數||||下的方向導數定義為：tsdftsds

t0

f(xkts)f(xk)

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

f(xk)Ts

的最優(yōu)解就是函數f(x在xk處對應于范數||||的最速下降方向，且這個解與所取的范數有關.G若取橢球范數||||Gk

，則對任意sRn，有T 1

(G1g

G1g sgTsksGksGkgkkks k k kgTsksGksGksGk

k kGk

GkG1g ，sGkksGkk k 這意味著G1k

為方向導數的下界. 另一方面，若取sG1gk Gk s2s

，則有gTs gTG1g (G1g)TG(G1g) G k k k k k k k k k kG1g ，s sGk Gk

s sGk

k kGk這表明方向導數能夠達到下界G1g

是關于橢球范數||||

的最速下降方向.

k kGk

k k k Gk（2）無約束最優(yōu)化問題的牛頓法也可以理解為非線性方程組的牛頓法，這是因為求解minfx的經典方法實際上是在尋找f(x的一個駐點，即求解非線性方程組f(x)0.xRn設xk是當前迭代點，若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條件，則由牛頓法產生的序列{xkx*，且具有二階收斂速率.fC2，2f(xLipschitzxkx*時，由定理1.2.1可知，存在0，使得||f(x*)f(xk

)2

f(x

k)(x*xk

||x*xk2

||2，fC2，2f(x*可逆（正定矩陣必定可逆）1.1.1x*的充分小鄰域內，2f(xM0，滿足||2f(x)1||M.xk充分靠近極小x*時，對任意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，即迭代點列{xk收斂，k索；而牛頓法的缺點是不能保證全局收斂，當G不正定時，甚至不能保證dk是下降方向，算法需要計算Hessian矩陣，單步計算量大.k§4.2.3 阻尼牛頓法搜索過程.4.2（阻尼牛頓法）1x0Rn，容許誤差0，置k0；2gk，若gkx；k3：確定牛頓方向，從牛頓方程Gkdgk

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

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

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

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

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的駐點，它也是極小點.x0.xkx，則存在正數和一個子x0K序列{xk}K2

，使對一切kK2，有

xk

0

.注意到{xk}K2K

是有界點列，故存在收斂K子列{xk}K3

(K3K2

limlim

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

G1g

可能不是下降方向..§4.3.1 Goldstein—Price修正方案當Gk非正定時，采用最速下降方向gk替代牛頓方向.若進一步將搜索方向與負梯度方向的角度準則結合起來，則有dk

dk,g

,dkN N kgk,

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

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

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

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

sf

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