梯度下降法牛頓迭代法共軛梯度法

1、蟲乞=(Xr+i Xr ) = akPk(2)逐步修改猜測。這里向雖 玖 代表一個搜索方向，一個大于零的純量 J 為學(xué)習(xí)速度，它確泄了學(xué)習(xí) 步長。當用= Jr+a只 進行最優(yōu)點迭代時，函數(shù)應(yīng)該在每次迭代時都減小，即FnvFQXQ考慮(x) = F(*) + VF(x)7 4疋(乂 疋)+ 丄(乂 X*)7 *()x=x.(X X*) +(3)的F（X）在Xr的一階泰勒級數(shù)展開：F（Xg ） = F% + AXQ = F（X.） + 斗其中，g為在舊猜測值兀處的梯度gk 三 VF（X）X=XA,要使 F（X“）VF（XQ只需要（4）中右端第二項小于0,即g；AX =akg1k?k PGM-ANN

2、-2009-C09性能優(yōu)化）優(yōu)化的目的是求岀目標函數(shù)的最大值點或者最小值點，這里討論的是迭代的方法梯度下降法首先，給左一個初始猜測值，然后按照等式(1)Xr+i = Xk +a迅選擇較小的正數(shù)a-這就隱含gPk 0o滿足g：Rv0的任意向量成為一個下降方向。如果沿著此方向取足夠小步長，函數(shù)一妃遞減。并且，最速F降的情況發(fā)生在最小的時候，容易知道，當時g：人最小，此時，方向向量與梯度方向相反。在(1)式中，令人=g-則有(7)Xp+1 =Xk 一gk對于式(7)中學(xué)習(xí)速率的選取通常有兩種方法：一種是選擇固左的學(xué)習(xí)速率另一種方法是使基于 學(xué)習(xí)速率匕的性能指數(shù)或目標函數(shù)F(Xk+J在每次迭代中最小化

3、，即沿著梯度反方向?qū)崿F(xiàn)最小化： X灼=Xk 一-注意：1、對于較小的學(xué)習(xí)速度最速下降軌跡的路徑總是與輪廓線正交，這是因為梯度與輪廓線總是正交的。2、如果改變學(xué)習(xí)速度，學(xué)習(xí)速度太大，算法會變得不穩(wěn)立，振蕩不會衰減，反而會增大。3、穩(wěn)泄的學(xué)習(xí)速率對于任意函數(shù)，確立最大可行的學(xué)習(xí)速度是不可能的，但對于二次函數(shù)，可以確宦個上界。令特征函數(shù)為：)=技加+心+那么梯度為VF(X) = AX + d代入最速下降法公式(7)中X&+i = Xk -akgk = Xk -ak(AXk +d) = U-akA ) Xk -akd(9)在動態(tài)系統(tǒng)中，如果矩陣I-aA的特征值小于1,則該系統(tǒng)是穩(wěn)左的?？捎煤丈仃嘇的

4、特征值來表示該矩陣的特征值，假設(shè)A的特征值和特征向量分別為人，入,入和氐皿2,Z”，那么/ - aA =(/- 6/2. )zf(10)于是，最速下降法的穩(wěn)泄條件為|/ -問| 1(11)如果二次函數(shù)有一個強極小點，則其特征值為正數(shù)，上式可以化為6/ 4Z由于該式對于赫森矩陣的所有特征值都成立則(12)a - 兀max分析：最大的穩(wěn)泄學(xué)習(xí)速度與二次函數(shù)的最大的曲率成反比。曲率說明梯度變化的快慢。如果梯度變化太快, 可能會導(dǎo)致跳過極小點，進而使新的迭代點的梯度的值大于原迭代點的梯度的值(但方向相反)。這會導(dǎo)致每次 迭代的步長增大。4、沿直線最小化選擇學(xué)習(xí)速率的另一種方法是縱使得每次迭代的性能指數(shù)

5、最小化，即選擇倉使得下式最?。篎(X 人 + ak Pk)對任意函數(shù)的這種最小化需要線性搜索。對二次函數(shù)解析線性最小化是可能的。上式對心的導(dǎo)數(shù)為：產(chǎn)尺蜀+紐切二商住門”+丹燈尸住山必R(13)令式(13)導(dǎo)數(shù)為零求得VF(X/Ix.x_宀、PrV2F(X)lY.XA Pk PAP；這里後為X&的赫森矩陣：4=，F(xiàn)(x)lx諾牛頓法牛頓法基于二階泰勒級數(shù)：F(X&+|) = F(Xk +AX,) F(XJ + g；AX* +1AX；4AX&(15)牛頓法的原理是求F(X)的二次近似的駐點，求這個二次函數(shù)對的梯度并令它等于，則有=(解得：AXk =8k于是，牛頓法定義為Xk+1 = Xt-A；,(

6、17)注意：牛頓法總是用一個二次函數(shù)逼近F(X),然后求英駐點，因此此方法總能夠一步找到二次函數(shù)的極小點，如果原函數(shù)為二次函數(shù)(有強極小點)，它就能夠?qū)崿F(xiàn)一步極小化如果F(X)不是二次函數(shù)，則牛頓法一般不能在一步內(nèi)收斂，是否收斂取決于具體的函數(shù)和初始點盡管牛頓法的收斂速度通常比最速下降法快，但其表現(xiàn)很復(fù)雜，除了收斂到鞍點的問題外，算法還可能喪蕩 和發(fā)散，如果學(xué)習(xí)速率不太快或每步都實現(xiàn)線性極小化，最速下降法能保證收斂牛頓法的另一個問題是需要對赫森矩陣及英逆陣的汁算和存儲共軌梯度法牛頓法有一個性質(zhì)成為二次終結(jié)法(quadratic temination),即它能在有限迭代次數(shù)內(nèi)使得二次函數(shù)極小 化

7、，但這需要計算和存儲二階導(dǎo)數(shù)，當參數(shù)個數(shù)很大時，計算所有二階導(dǎo)數(shù)是很困難的。假定對下述二次函數(shù)確定極小點：F(x) = X1 AX + d1 X+c(18)當且僅當PAPj=O,k$j時，稱向量集合人對于一個正泄赫森矩陣A兩兩共牠。因為對稱矩陣的特征向量是兩兩正交的。已經(jīng)證明，如果存在沿著一個共輒方向集伯出化丄的精確線性搜索序列，就能夠在最多n此搜索內(nèi)實現(xiàn) 具有n個參數(shù)的二次函數(shù)的精確極小化。注意到對于二次函數(shù)，有F(X) = AX + d,(19)V2F(X) = A由于Agk =-gk= AAX,又有AXr =(X-Xk) = akPk，選擇縱使函數(shù)F(X)在R方向上極小化,則共軌條件可重寫稱aRAPj = HX：APj =片=0左羊 j(20)注意，第一次搜索方向仇是任意的，而片是與厶乩垂直的任意向量。所以共軌向量集的數(shù)疑是無限的。通常從最速下降法的方向開始搜索：P. = g0每次迭代都要構(gòu)造一個與g,Ag|,正交的向呈:人?？梢詫⒌问胶喕癁镻嚴-21)通常選擇aSt R81 St -p. RA = A，D 或幾=或 A =綜上，算法可以歸納為：1、選擇如幾=-go的與梯度相反的方向作為第一次搜索方向2、根據(jù)AX如=(Xg-=進行下一步搜索，確定心以使函數(shù)沿搜索方向極小化3、根據(jù)確定下一個搜索方向，計算0如4、如果算法不收斂，回到第2步算法比較梯度下降法