擬牛頓法及其相關(guān)解法

本文鏈接：/miaowei/52925.html最近在看條件隨機(jī)場(chǎng)中的優(yōu)化算法。其中就設(shè)計(jì)到了無約束化的最優(yōu)化方法，也就是牛頓法。在CRF（conditionalrandomfield）中，使用的是L-BFGS法。費(fèi)了好大的勁把算法的原理及推導(dǎo)算是看明白了，可是到了具體實(shí)現(xiàn)上，又碰到問題了，比如在求搜索方向的時(shí)候，使用H屮={I- -仇丫閭.）十p収呂?=vjHg+pe應(yīng)但是程序中如何實(shí)現(xiàn)呢？現(xiàn)在轉(zhuǎn)載一篇文章，看過之后，會(huì)非常受益。使用導(dǎo)數(shù)的最優(yōu)化算法中，擬牛頓法是目前為止最為行之有效的一種算法，具有收斂速度快、算法穩(wěn)定性強(qiáng)、編寫程序容易等優(yōu)點(diǎn)。在現(xiàn)今的大型計(jì)算程序中有著廣泛的應(yīng)用。本文試圖介紹擬牛頓法的基礎(chǔ)理論和若干進(jìn)展。牛頓法（NewtonMethod）牛頓法的基本思想是在極小點(diǎn)附近通過對(duì)目標(biāo)函數(shù)做二階Taylor展開，進(jìn)而找到’；的極小點(diǎn)的估計(jì)值［1］。一維情況下，也即令函數(shù)*打?yàn)辇R（『）=+f際〕（T—跌）+訂"際）（T—It）則其導(dǎo)數(shù)'’滿足了?盟=廣:叫+廣（咖仗一mJ=0因此——⑴將、+作為；極小點(diǎn)的一個(gè)進(jìn)一步的估計(jì)值。重復(fù)上述過程,可以產(chǎn)生一系列的極小點(diǎn)估值集合'。一定條件下，這個(gè)極小點(diǎn)序列：收斂于；的極值點(diǎn)。將上述討論擴(kuò)展到,維空間，類似的，對(duì)于，維函數(shù)*有f（xj4/'；XJ=fZ+WRx-和J十戲天—x^.jTV2/（x-觀j其中*和W人分別是目標(biāo)函數(shù)的的一階和二階導(dǎo)數(shù)，表現(xiàn)為匸維向量和.■■■'-.''■■■矩陣，而后者又稱為目標(biāo)函數(shù)*在x處的Hesse矩陣。設(shè)設(shè)；可逆，則可得與方程⑴類似的迭代公式：人 了 V<-:s V：s ⑵這就是原始牛頓法的迭代公式。原始牛頓法雖然具有二次終止性（即用于二次凸函數(shù)時(shí)，經(jīng)有限次迭代必達(dá)極小點(diǎn)），但是要求初始點(diǎn)需要盡量靠近極小點(diǎn)，否則有可能不收斂。因此人們又提出了阻尼牛頓法［1］。這種方法在算法形式上等同于所有流行的優(yōu)化方法，即確定搜索方向，再沿此方向進(jìn)行一維搜索，找出該方向上的極小點(diǎn)，然后在該點(diǎn)處重新確定搜索方向，重復(fù)上述過程，直至函數(shù)梯度小于預(yù)設(shè)判據(jù),。具體步驟列為算法1。算法1:(1)給定初始點(diǎn)H，設(shè)定收斂判據(jù)■，二⑵計(jì)算和.⑶若「’峠<-,則停止迭代，否則確定搜索方向』 \ % '、.⑷從出發(fā)，沿做一維搜索，n護(hù)f兇-+人山j(luò)=f(xk+Xk-dk)令 ?⑸設(shè)?； “I，轉(zhuǎn)步驟⑵?在一定程度上，阻尼牛頓法具有更強(qiáng)的穩(wěn)定性。擬牛頓法(Quasi-NewtonMethod)如同上一節(jié)指出，牛頓法雖然收斂速度快，但是計(jì)算過程中需要計(jì)算目標(biāo)函數(shù)的二階偏導(dǎo)數(shù)，難度較大。更為復(fù)雜的是目標(biāo)函數(shù)的Hesse矩陣無法保持正定，從而令牛頓法失效。為了解決這兩個(gè)問題，人們提出了擬牛頓法。這個(gè)方法的基本思想是不用二階偏導(dǎo)數(shù)而構(gòu)造出可以近似Hesse矩陣的逆的正定對(duì)稱陣，從而在"擬牛頓"的條件下優(yōu)化目標(biāo)函數(shù)。構(gòu)造方法的不同決定了不同的擬牛頓法。首先分析如何構(gòu)造矩陣可以近似Hesse矩陣的逆：設(shè)第k次迭代之后得到點(diǎn)，將目標(biāo)函數(shù) 在處展成Taylor級(jí)數(shù)，取二階近似，得到gf^k+1]+ -F Xj葉]]因此v/(x)RS ,j+V2孑(強(qiáng)+1)(兀-XjfcHj令鼻，則人 7人 匸:S S ⑶記科=X<+|-也一Yl= i-vy(XL.j同時(shí)設(shè)Hesse矩陣'、： 可逆，則方程(3)可以表示為rVJ;:s v⑷因此，只需計(jì)算目標(biāo)函數(shù)的一階導(dǎo)數(shù)，就可以依據(jù)方程(4)估計(jì)該處的Hesse矩陣的逆。也即，為了用不包含二階導(dǎo)數(shù)的矩陣H 近似牛頓法中的Hesse矩陣 的逆矩陣」丨必須滿足方程(5)也稱為擬牛頓條件。不加證明的，下面給出兩個(gè)最常用的H 構(gòu)造公式DFP公式設(shè)初始的矩陣】I為單位矩陣]，然后通過修正11給出H，即H忡=H,+AH,DFP算法中定義校正矩陣為\TT_軌撫氐皿,-陽4-球班-yiH1,y,因此]| ]|氏 ⑹可以驗(yàn)證，這樣產(chǎn)生的H 對(duì)于二次凸函數(shù)而言可以保證正定，且滿足擬牛頓條件。BFGS公式BFGS公式有時(shí)也稱為DFP公式的對(duì)偶公式。這是因?yàn)槠渫茖?dǎo)過程與方程(6)完全一樣只需要用矩陣汗取代“ ，同時(shí)將“和匸互換，最后可以得到]|H-占&十(7)這個(gè)公式要優(yōu)于DFP公式，因此目前得到了最為廣泛的應(yīng)用。利用方程(6)或(7)的擬牛頓法計(jì)算步驟列為算法2。算法2:⑴給定初始點(diǎn)x，設(shè)定收斂判據(jù)?，二人⑵設(shè)II1，計(jì)算出目標(biāo)函數(shù) 在處的梯度⑶確定搜索方向門：酥=H丄馱⑷從出發(fā)，沿訂做一維搜索，滿足fQu+人心1= +Xdu令尤卜十1=總-+九血⑸若 ?-，則停止迭代，得到最優(yōu)解* X ，否則進(jìn)行步驟(6).⑹若二厶 ，則令X ' ，回到步驟(2)，否則進(jìn)行步驟(7).⑺令' ， ' '，亠｛，利用方程(6)或(7)計(jì)算H ，設(shè)匸1，回到步驟(3)。限域擬牛頓法(LimitedStorageQuasi-NewtonMethod)算法2的步驟(3)中，為了確定第:次搜索方向，需要知道對(duì)稱正定矩陣］I，因此對(duì)于匸維的問題，存儲(chǔ)空間至少是'-，對(duì)于大型計(jì)算而言，這顯然是一個(gè)極大的缺點(diǎn)。作為比較，共軛梯度法只需要存儲(chǔ)3個(gè)」維向量。為了解決這個(gè)問題Nocedal首次提出了基于BFGS公式的限域擬牛頓法(L-BFGS)［2］。L-BFGS的基本思想是存儲(chǔ)有限次數(shù)(如…次)的更新矩陣3I，如果＞'-，的話就舍棄…次以前的工1-，也即L-BFGS的記憶只有…次。如果…，則L-BFGS等價(jià)于標(biāo)準(zhǔn)的BFGS公式。首先將方程(7)寫為乘法形式：H屮=(I -“y閭.］十陽閭.=訐印M+吋應(yīng)其中」…八是- 的矩陣。乘法形式下"舍棄"等價(jià)于置「 】，：?：。容易得出，給定…后，BFGS的矩陣更新可以寫為若? -，則Hb+1 HiVu-Vk-.Vk+vj-^：is：is.jV；…￥上(10)方程(9)和(10)稱為狹義BFGS矩陣(specialBFGSmatrices)。仔細(xì)分析這兩個(gè)方程以及-和「的定義，可以發(fā)現(xiàn)L-BFGS方法中構(gòu)造 只需要保留 個(gè)維向量：個(gè)、…個(gè)丫以及］I(對(duì)角陣)?？焖儆?jì)算I-L-BFGS算法中確定搜索方向H需要計(jì)算HM，下列算法可以高效地完成計(jì)算任務(wù)：算法3:IF丄■■-Then■=0;=

ELSE|■:-= …；丨：'：|〔|=■■-ENDIFc]'I: .- ；DO=( -1),0,-1儲(chǔ)存“；qq■■v；ENDDO1'II｛；DO=0,( -1)-.■：'.;':'VT；ENDDO完整的程序包可從下列網(wǎng)址下載：/~nocedal/software.html針對(duì)二次非凸函數(shù)的若干變形對(duì)于二次凸函數(shù)，BFGS算法具有良好的全局收斂性。但是對(duì)于二次非凸函數(shù)，也即目標(biāo)函數(shù)Hesse矩陣非正定的情況，無法保證按照BFGS算法構(gòu)造的擬牛頓方向必為下降方向。為了推廣BFGS公式的應(yīng)用范圍，很多工作提出了對(duì)BFGS公式稍作修改或變形的辦法。下面舉兩個(gè)例子。Li-Fukushima方法[3]Li和Fukushima提出新的構(gòu)造矩陣H的方法：日屮={I-皿旺疳冋([-皿疳胡)+日屮={I-皿旺疳冋([-皿疳胡)+伽就(11)其中的定義見算法2中步驟(7)，而除此之外，算法2中步驟(3)的一維搜索采用如下方式：給定兩個(gè)參數(shù)「「〔和匚「」一，找出最小的非負(fù)整數(shù)j，滿足fg十巧業(yè)）<打嚴(yán)）+G,以血：取：=；,步長(zhǎng)' '。Xiao-Wei-Wang方法［4］Xiao、Wei和Wang提出了計(jì)入目標(biāo)函數(shù)值?’久的另一種］I的構(gòu)造方法:護(hù)Y■' ，其中%= -f（粘十J+｛臥十I+亂］丁昌札II的構(gòu)造方法與方程（7）和（11）形式相同：日屮=（I-心劇丁舊川-仮口話+詁刊話相應(yīng)的v-而一維搜索則采用弱Wolfe-Powell準(zhǔn)則：給定兩個(gè)參數(shù)'：■-和■■'■ 1，找出步長(zhǎng)〔，滿足-』-（14）如果，=?滿足方程（13）、（14），則取一：=一?？梢钥闯觯@兩種方法只是改變了丫的定義方式，其他則與標(biāo)準(zhǔn)的BFGS方法完全一樣。因此將二者推廣到限域形式是非常直接的，這里不再給出算法。對(duì)于二次非凸函數(shù)的擬牛頓方法還在進(jìn)一步發(fā)展當(dāng)中，上述的兩個(gè)例子并不一定是最佳算法。一維搜索使用導(dǎo)數(shù)的優(yōu)化算法都涉及到沿優(yōu)化方向」的一維搜索。事實(shí)上一維搜索算法本身就一個(gè)非常重要的課題，分為精確一維搜索以及非精確一維搜索。標(biāo)準(zhǔn)的擬牛頓法或L-BFGS均采用精確一維搜索。與前者相比，非精確一維搜索雖然犧牲了部分精度，但是效率更高，調(diào)用函數(shù)的次數(shù)更少。因此Li-Fukushima方法和Xiao-Wei-Wang方法中均采用了這類算法。不加證明的，本節(jié)分別給出兩類范疇中各自的一個(gè)應(yīng)用最為廣泛的例子，分別是二點(diǎn)三次插值方法和Wolfe-Powell準(zhǔn)則。二點(diǎn)三次插值方法在精確一維搜索各種算法中，這種方法得到的評(píng)價(jià)最高。其基本思想是選取兩個(gè)初始點(diǎn)：和=，滿足' <：?J>o這樣的初始條件保證了在區(qū)間^1；：'一中存在極小點(diǎn)。利用這兩點(diǎn)處的函數(shù)值、’■-（記為「、二）和導(dǎo)數(shù)值?’'、?‘T（記為?’、」）構(gòu)造一個(gè)三次多項(xiàng)^5「，使得在：和亠處與目標(biāo)函數(shù)；有相同的函數(shù)值和導(dǎo)數(shù)值，則設(shè)■■' ■' - ，‘ - ■ ■-- ［那么通過4個(gè)邊界條件可以完全確定■■、、、

;4個(gè)參數(shù)。之后找出」:的零點(diǎn)-’，作為極小點(diǎn)的一個(gè)進(jìn)一步的估計(jì)。可以證明，由：出發(fā)，最佳估計(jì)值的計(jì)算公式為1 (15)為了避免每次都要求解4維線性方程組的麻煩，整個(gè)搜索過程可以采用算法4:算法4:⑴給定初始點(diǎn)：和，滿足< ，計(jì)算函數(shù)值’、二和導(dǎo)數(shù)值?’、二，并且?’<:>:，給定允許誤差：。(2)計(jì)算如下方程，得到最佳估計(jì)值-■:' 一-二，'■'.'2(16)F=F=k+h衛(wèi)—釣 芥;J(17)⑶若"一■:二，則停止計(jì)算，得到點(diǎn)：；否則進(jìn)行步驟(4)。⑷計(jì)算’：和「：。若：’心‘，則停止計(jì)算，得到點(diǎn)：,若?’； <：，則令； ''■' ■'' ■' ■';，轉(zhuǎn)步驟(2);若?’ ■' >:，則令■' ■-■' ' ■'，轉(zhuǎn)步驟(2)。禾I」用三次函數(shù)插值，方程(16)、(17)并不是唯一的方法，也可以利用下式計(jì)算、、三個(gè)參數(shù)：._了；打；hhzzhl.a~I：!'，-!'l；J—I：J.—糾-JIJ/j~/l-(18)c~然后利用(15)式尋找最佳點(diǎn)［5］o此外即使’-<：一般而言也可以用(15)式外推尋找-'(參見［5］)。Wolfe-Powell準(zhǔn)則不等式(13)、(14)給出了這種非精確一維搜索算法。如果我們將不等式(14)用下式替換：-'丨 二」(19)也即說心<顯+1比<—疔歸血-則不等式(13)、(19)稱為強(qiáng)Wolfe-Powell準(zhǔn)則。其重要性在于當(dāng)——…時(shí)，該方法過渡為精確一維搜索算法［6］。算法如下［5］算法5:(1)給定兩個(gè)參數(shù)'■ : 和■■■'■ 為初始點(diǎn)(相應(yīng)于， 八)，匚為猜想點(diǎn)(可設(shè)為1)。計(jì)算兩點(diǎn)處的函數(shù)值「、二和導(dǎo)數(shù)值給定最大循環(huán)次數(shù)'■■■■---,設(shè)二匸=二;⑵若二和二違反不等式(13)或者不等式(19)的右半段，則縮小搜索范圍的上限 ，否則轉(zhuǎn)步驟⑸；⑶若二＞■'，利用二次插值方法尋找最佳點(diǎn)＞■:Jj-fi-fi'i-rj-.riJ設(shè)：」 ，計(jì)算二和'」；設(shè) ，若 轉(zhuǎn)步驟(2),否則轉(zhuǎn)步驟(5)；若，二-，轉(zhuǎn)步驟(4)；⑷禾I」用式(16)、(17)(或者式(15)、(18))尋找最佳點(diǎn)I＞.。令■-=■.■■■■.，計(jì)算二和二；設(shè)= ，若 ，轉(zhuǎn)步驟(2),否則轉(zhuǎn)步驟(5)；⑸若滿足不等式(19)的左半段，則停止計(jì)算，得到最佳點(diǎn)否則轉(zhuǎn)步驟(6)；⑹禾I」用式(16)、(17)(或者式(15)、(18))尋找最佳點(diǎn)并計(jì)算二以及二；設(shè)二-若轉(zhuǎn)步驟(2),否則轉(zhuǎn)步驟(7)；(7)停止計(jì)算得到目前最佳估計(jì)值：J。需要補(bǔ)充說明的是步驟(4)可以有不同的估算方法，例如此外，點(diǎn)處的導(dǎo)數(shù)值-，5,因?yàn)樵谝痪S搜索中，相當(dāng)于待求步長(zhǎng)。在大多數(shù)情況下，-以及：=?可以取得很好的效果。Wolfe-Powell準(zhǔn)則的幾何意義可以參考文獻(xiàn)[5][6]。參考文獻(xiàn)【1】陳寶林《最優(yōu)化理論與算法(第二版)》(清華大學(xué)出版社2005)第9-10章.【2】J.Nocedal,Math.Comput.35,773(1980).【3】D.H.LiandM.Fukush