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

《梯度下降法、牛頓迭代法、共軛梯度法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、梯度下降法、牛頓迭代法、共軛梯度法（參見：神經(jīng)網(wǎng)絡(luò)->PGM-ANN-2009-C09性能優(yōu)化）優(yōu)化的目的是求出目標(biāo)函數(shù)的最大值點(diǎn)或者最小值點(diǎn)，這里討論的是迭代的方法梯度下降法首先，給定一個(gè)初始猜測(cè)值，然后按照等式（1）或（2）逐步修改猜測(cè)。這里向量代表一個(gè)搜索方向，一個(gè)大于零的純量為學(xué)習(xí)速度，它確定了學(xué)習(xí)步長(zhǎng)。當(dāng)用進(jìn)行最優(yōu)點(diǎn)迭代時(shí)，函數(shù)應(yīng)該在每次迭代時(shí)都減小，即考慮（3）的在的一階泰勒級(jí)數(shù)展開：（4）其中，為在舊猜測(cè)值處的梯度（5）要使只需要（4）中右端第二項(xiàng)小于0，即（6）選擇較小的正數(shù)。這就隱含。滿足的任意向量成為一個(gè)下降方向。如果沿著此方向取足夠小步長(zhǎng)，函數(shù)一定遞減。并且，

2、最速下降的情況發(fā)生在最小的時(shí)候，容易知道，當(dāng)時(shí)最小，此時(shí)，方向向量與梯度方向相反。在（1）式中，令，則有（7）對(duì)于式（7）中學(xué)習(xí)速率的選取通常有兩種方法：一種是選擇固定的學(xué)習(xí)速率，另一種方法是使基于學(xué)習(xí)速率的性能指數(shù)或目標(biāo)函數(shù)在每次迭代中最小化，即沿著梯度反方向?qū)崿F(xiàn)最小化：。注意：1、對(duì)于較小的學(xué)習(xí)速度最速下降軌跡的路徑總是與輪廓線正交，這是因?yàn)樘荻扰c輪廓線總是正交的。2、如果改變學(xué)習(xí)速度，學(xué)習(xí)速度太大，算法會(huì)變得不穩(wěn)定，振蕩不會(huì)衰減，反而會(huì)增大。3、穩(wěn)定的學(xué)習(xí)速率對(duì)于任意函數(shù)，確定最大可行的學(xué)習(xí)速度是不可能的，但對(duì)于二次函數(shù)，可以確定一個(gè)上界。令特征函數(shù)為：（8）那么梯度為代入最

3、速下降法公式（7）中（9）在動(dòng)態(tài)系統(tǒng)中，如果矩陣的特征值小于1，則該系統(tǒng)是穩(wěn)定的。可用赫森矩陣A的特征值來表示該矩陣的特征值，假設(shè)A的特征值和特征向量分別為和，那么（10）于是，最速下降法的穩(wěn)定條件為（11）如果二次函數(shù)有一個(gè)強(qiáng)極小點(diǎn)，則其特征值為正數(shù)，上式可以化為由于該式對(duì)于赫森矩陣的所有特征值都成立則（12）分析：最大的穩(wěn)定學(xué)習(xí)速度與二次函數(shù)的最大的曲率成反比。曲率說明梯度變化的快慢。如果梯度變化太快，可能會(huì)導(dǎo)致跳過極小點(diǎn)，進(jìn)而使新的迭代點(diǎn)的梯度的值大于原迭代點(diǎn)的梯度的值（但方向相反）。這會(huì)導(dǎo)致每次迭代的步長(zhǎng)增大。3、沿直線最小化選擇學(xué)習(xí)速率的另一種方法是使得每次迭代的性能指數(shù)

4、最小化，即選擇使得下式最小：對(duì)任意函數(shù)的這種最小化需要線性搜索。對(duì)二次函數(shù)解析線性最小化是可能的。上式對(duì)的導(dǎo)數(shù)為：（13）令式（13）導(dǎo)數(shù)為零求得（14）這里為的赫森矩陣：牛頓法牛頓法基于二階泰勒級(jí)數(shù)：（15）牛頓法的原理是求的二次近似的駐點(diǎn)，求這個(gè)二次函數(shù)對(duì)的梯度并令它等于0，則有（16）解得：于是，牛頓法定義為（17）注意：牛頓法總是用一個(gè)二次函數(shù)逼近,然后求其駐點(diǎn)，因此此方法總能夠一步找到二次函數(shù)的極小點(diǎn)，如果原函數(shù)為二次函數(shù)（有強(qiáng)極小點(diǎn)），它就能夠?qū)崿F(xiàn)一步極小化如果不是二次函數(shù)，則牛頓法一般不能在一步內(nèi)收斂，是否收斂取決于具體的函數(shù)和初始點(diǎn)盡管牛頓法的收斂速度通常比最速下降

5、法快，但其表現(xiàn)很復(fù)雜，除了收斂到鞍點(diǎn)的問題外，算法還可能震蕩和發(fā)散，如果學(xué)習(xí)速率不太快或每步都實(shí)現(xiàn)線性極小化，最速下降法能保證收斂牛頓法的另一個(gè)問題是需要對(duì)赫森矩陣及其逆陣的計(jì)算和存儲(chǔ)共軛梯度法牛頓法有一個(gè)性質(zhì)成為二次終結(jié)法（quadratictemination），即它能在有限迭代次數(shù)內(nèi)使得二次函數(shù)極小化，但這需要計(jì)算和存儲(chǔ)二階導(dǎo)數(shù)，當(dāng)參數(shù)個(gè)數(shù)很大時(shí)，計(jì)算所有二階導(dǎo)數(shù)是很困難的。假定對(duì)下述二次函數(shù)確定極小點(diǎn)：（18）當(dāng)且僅當(dāng)時(shí)，稱向量集合對(duì)于一個(gè)正定赫森矩陣A兩兩共軛。因?yàn)閷?duì)稱矩陣的特征向量是兩兩正交的。已經(jīng)證明，如果存在沿著一個(gè)共軛方向集的精確線性搜索序列，就能夠在最多n此搜索

6、內(nèi)實(shí)現(xiàn)具有n個(gè)參數(shù)的二次函數(shù)的精確極小化。注意到對(duì)于二次函數(shù)，有（19）由于，又有，選擇使函數(shù)在方向上極小化，則共軛條件可重寫稱（20）注意，第一次搜索方向是任意的，而是與垂直的任意向量。所以共軛向量集的數(shù)量是無限的。通常從最速下降法的方向開始搜索：每次迭代都要構(gòu)造一個(gè)與正交的向量。可以將迭代形式簡(jiǎn)化為（21）通常選擇或或綜上，算法可以歸納為：1、選擇如的與梯度相反的方向作為第一次搜索方向2、根據(jù)進(jìn)行下一步搜索，確定以使函數(shù)沿搜索方向極小化3、根據(jù)確定下一個(gè)搜索方向，計(jì)算4、如果算法不收斂，回到第2步算法比較梯度下降法形式簡(jiǎn)單，一般情況下都能夠保證收斂，但是收斂速度慢牛頓法對(duì)于二次

7、目標(biāo)函數(shù)收斂速度快，但是不能夠保證收斂，而且需要對(duì)赫森矩陣及其逆陣的計(jì)算和存儲(chǔ)共軛梯度法結(jié)合了前面兩種方法的性質(zhì)，收斂速度快，不需要對(duì)赫森矩陣及其逆陣的計(jì)算和存儲(chǔ)，但是形式比前兩者復(fù)雜