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

1、本文鏈接：最近在看條件隨機(jī)場(chǎng)中的優(yōu)化算法。其中就設(shè)計(jì)到了無(wú)約束化的最優(yōu)化方法，也就是牛頓法。 在CRF（conditional random field）中，使用的是L-BFGS法。費(fèi)了好大的勁把算法的原理及推導(dǎo)算是看明白了，可是到了具體實(shí)現(xiàn)上，又碰到問(wèn)題了，比如在求搜索方向的時(shí)候，使用     但是程序中如何實(shí)現(xiàn)呢？ 現(xiàn)在轉(zhuǎn)載一篇文章，看過(guò)之后，會(huì)非常受益。使用導(dǎo)數(shù)的最優(yōu)化算法中，擬牛頓法是目前為止最為行之有效的一種算法，具有收斂速度快、算法穩(wěn)定性強(qiáng)、編寫程序容易等優(yōu)點(diǎn)。在現(xiàn)今的大型計(jì)算程序中有著廣泛的應(yīng)用。本文試圖介紹擬牛頓法的基

2、礎(chǔ)理論和若干進(jìn)展。牛頓法 (Newton Method)牛頓法的基本思想是在極小點(diǎn)附近通過(guò)對(duì)目標(biāo)函數(shù)做二階Taylor展開，進(jìn)而找到的極小點(diǎn)的估計(jì)值1。一維情況下，也即令函數(shù)為則其導(dǎo)數(shù)滿足因此       (1)將作為極小點(diǎn)的一個(gè)進(jìn)一步的估計(jì)值。重復(fù)上述過(guò)程，可以產(chǎn)生一系列的極小點(diǎn)估值集合。一定條件下，這個(gè)極小點(diǎn)序列收斂于的極值點(diǎn)。將上述討論擴(kuò)展到維空間，類似的，對(duì)于維函數(shù)有其中和分別是目標(biāo)函數(shù)的的一階和二階導(dǎo)數(shù)，表現(xiàn)為維向量和  矩陣，而后者又稱為目標(biāo)函數(shù)在處的Hesse矩陣。 設(shè)可逆，則可得與方程(1)類似的迭

3、代公式：     (2)這就是原始牛頓法的迭代公式。原始牛頓法雖然具有二次終止性（即用于二次凸函數(shù)時(shí)，經(jīng)有限次迭代必達(dá)極小點(diǎn)），但是要求初始點(diǎn)需要盡量靠近極小點(diǎn)，否則有可能不收斂。因此人們又提出了阻尼牛頓法1。這種方法在算法形式上等同于所有流行的優(yōu)化方法，即確定搜索方向，再沿此方向進(jìn)行一維搜索，找出該方向上的極小點(diǎn)，然后在該點(diǎn)處重新確定搜索方向，重復(fù)上述過(guò)程，直至函數(shù)梯度小于預(yù)設(shè)判據(jù)。具體步驟列為算法1。 算法1：(1)  給定初始點(diǎn)，設(shè)定收斂判據(jù)，.(2)  計(jì)算和.(3)  若 <&#

4、160;，則停止迭代，否則確定搜索方向.(4)  從出發(fā)，沿做一維搜索，令.(5)  設(shè)，轉(zhuǎn)步驟(2). 在一定程度上，阻尼牛頓法具有更強(qiáng)的穩(wěn)定性。擬牛頓法 (Quasi-Newton Method) 如同上一節(jié)指出，牛頓法雖然收斂速度快，但是計(jì)算過(guò)程中需要計(jì)算目標(biāo)函數(shù)的二階偏導(dǎo)數(shù)，難度較大。更為復(fù)雜的是目標(biāo)函數(shù)的Hesse矩陣無(wú)法保持正定，從而令牛頓法失效。為了解決這兩個(gè)問(wèn)題，人們提出了擬牛頓法。這個(gè)方法的基本思想是不用二階偏導(dǎo)數(shù)而構(gòu)造出可以近似Hesse矩陣的逆的正定對(duì)稱陣， 從而在"擬牛頓"的條件下優(yōu)化目標(biāo)函數(shù)。構(gòu)造方法的不同決

5、定了不同的擬牛頓法。首先分析如何構(gòu)造矩陣可以近似Hesse矩陣的逆：設(shè)第k次迭代之后得到點(diǎn)，將目標(biāo)函數(shù)在處展成Taylor級(jí)數(shù)，取二階近似，得到因此令，則      (3)記同時(shí)設(shè)Hesse矩陣可逆，則方程(3)可以表示為      (4)因此，只需計(jì)算目標(biāo)函數(shù)的一階導(dǎo)數(shù)，就可以依據(jù)方程(4)估計(jì)該處的Hesse矩陣的逆。也即，為了用不包含二階導(dǎo)數(shù)的矩陣近似牛頓法中的Hesse矩陣的逆矩 陣，必須滿足      (5)方程(5)也稱為擬牛頓條件。

6、不加證明的，下面給出兩個(gè)最常用的構(gòu)造公式DFP公式設(shè)初始的矩陣為單位矩陣，然后通過(guò)修正給出，即DFP算法中定義校正矩陣為因此      (6)可以驗(yàn)證，這樣產(chǎn)生的對(duì)于二次凸函數(shù)而言可以保證正定，且滿足擬牛頓條件。BFGS公式BFGS公式有時(shí)也稱為DFP公式的對(duì)偶公式。這是因?yàn)槠渫茖?dǎo)過(guò)程與方程(6)完全一樣，只需要用矩陣取 代，同時(shí)將和 互換，最后可以得到       (7)這個(gè)公式要優(yōu)于DFP公式，因此目前得到了最為廣泛的應(yīng)用。利用方程(6)或(7)的擬牛頓法計(jì)算步驟列為算法

7、2。算法2：(1)  給定初始點(diǎn)，設(shè)定收斂判據(jù)，.(2)  設(shè)，計(jì)算出目標(biāo)函數(shù)在處的梯度.(3)  確定搜索方向：.(4)  從出發(fā)，沿做一維搜索，滿足令.(5)  若，則停止迭代，得到最優(yōu)解，否則進(jìn)行步驟(6).(6)  若，則令，回到步驟(2)，否則進(jìn)行步驟(7).(7)  令，利用方程(6)或(7)計(jì)算，設(shè)，回到步驟(3)。 限域擬牛頓法(Limited Storage Quasi-Newton Method) 算法2的步驟(3)中，為了確定第次搜索方向，需要知道對(duì)稱正定矩陣，因此 對(duì)于維的問(wèn)題，存

8、儲(chǔ)空間至少是，對(duì)于大型計(jì)算而言，這顯然是一個(gè)極大的缺點(diǎn)。作為比較，共軛梯度法只需要存儲(chǔ)3個(gè)維向量。為了解決這個(gè)問(wèn)題，Nocedal首次提出了基于BFGS公式的限域擬牛頓法(L-BFGS)2。L-BFGS的基本思想是存儲(chǔ)有限次數(shù)（如次）的更新矩陣，如果 > 的話就舍棄次以前的，也即L-BFGS的記憶只有次。如果，則L- BFGS等價(jià)于標(biāo)準(zhǔn)的BFGS公式。首先將方程(7)寫為乘法形式：      (8)其中，是  的矩陣。乘法形式下"舍棄"等價(jià)于置，。容易得出，給 定后，BFGS的矩

9、陣更新可以寫為若，則                                                       (9) 若

10、 > ，則                                             (10)方程(9)和(10)稱為狹義BFGS矩陣(special BFGS matrices)。仔細(xì)分析

11、這兩個(gè)方程以及和的定義，可以發(fā)現(xiàn)L-BFGS方法中構(gòu)造只需要保留個(gè)維向量：個(gè)、個(gè)以及（對(duì)角陣）?？焖儆?jì)算L-BFGS算法中確定搜索方向需要計(jì)算，下列算法可以高效地完成計(jì)算任務(wù)：算法3:IF  Then    = 0;  = ELSE    =   = ENDIF;DO  = (-1),0,-1         儲(chǔ)存;&

12、#160;  ENDDO;DO  = 0, (-1)         ENDDO完整的程序包可從下列網(wǎng)址下載：/nocedal/software.html針對(duì)二次非凸函數(shù)的若干變形對(duì)于二次凸函數(shù)，BFGS算法具有良好的全局收斂性。但是對(duì)于二次非凸函數(shù)，也即目標(biāo)函數(shù)Hesse矩陣非正定的情況，無(wú)法保證按照BFGS算法構(gòu)造的擬牛頓方向必為下降方向。為了推廣BFGS公式的應(yīng)用范圍，很多工作提出了對(duì)BFGS公式稍作

13、修改或變形的辦法。下面舉兩個(gè)例子。Li-Fukushima方法3Li和Fukushima提出新的構(gòu)造矩陣的方法：          (11)其中 的定義見算法2中步驟(7)，而除此之外，算法2中步驟(3)的一維搜索采用如下方式：給定兩個(gè)參數(shù)和，找出最小的非負(fù)整數(shù)j，滿足取，步長(zhǎng)。Xiao-Wei-Wang方法4Xiao、Wei和Wang提出了計(jì)入目標(biāo)函數(shù)值的另一種的構(gòu)造方法：設(shè)，其中的構(gòu)造方法與方程(7)和(11)形式相同：      

14、  (12)相應(yīng)的而一維搜索則采用弱Wolfe-Powell準(zhǔn)則：給定兩個(gè)參數(shù)和，找出步長(zhǎng)，滿足          (13)       (14)如果 = 滿足方程(13)、(14)，則取 = ?？梢钥闯觯@兩種方法只是改變了的定義方式，其他則與標(biāo)準(zhǔn)的BFGS方法完全一樣。因此將二者推廣到限域形式是非常直接的，這里不再給出算法。對(duì)于二次非凸函數(shù)的擬牛頓方法還在進(jìn)一步發(fā)展當(dāng)中，上述的兩個(gè)例子并不一定

15、是最佳算法。一維搜索使用導(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)和，滿足 <

16、;   <   > 。這樣的初始條件保證了在區(qū)間中存在極小點(diǎn)。利用這兩點(diǎn)處的函數(shù)值、（記為、）和導(dǎo)數(shù)值、（記為、）構(gòu)造一個(gè)三次多項(xiàng)式，使 得在和處與目標(biāo)函數(shù)有相同的函數(shù)值和導(dǎo)數(shù)值，則設(shè)，那么通過(guò)4個(gè)邊界條件可以完全確定、4個(gè)參數(shù)。之后找 出的零點(diǎn)，作為極小點(diǎn)的一個(gè)進(jìn)一步的估計(jì)?？梢宰C明，由出發(fā)，最佳估計(jì)值的計(jì)算公式為          (15)為了避免每次都要求解4維線性方程組的麻煩，整個(gè)搜索過(guò)程可以采用算法4：算法4：(1

17、)  給定初始點(diǎn)和，滿足 < ，計(jì)算函數(shù)值、和導(dǎo)數(shù)值、，并且 < ， > ，給定允許誤差。(2)  計(jì)算如下方程，得到最佳估計(jì)值：        (16)        (17)(3)  若，則停止計(jì)算，得到點(diǎn)；否則進(jìn)行步驟(4)。(4)  計(jì)算和。若，則停止計(jì)算，得到點(diǎn),若 < ，則令，轉(zhuǎn)步驟(2)；若 

18、;> ，則令，轉(zhuǎn)步驟(2)。 利用三次函數(shù)插值，方程(16)、(17)并不是唯一的方法，也可以利用下式計(jì)算、三個(gè)參數(shù)：         (18)然后利用(15)式尋找最佳點(diǎn)5。此外，即使 < ，一般而言也可以用(15)式外推尋找（參見5）。Wolfe-Powell準(zhǔn)則不等式(13)、(14)給出了這種非精確一維搜索算法。如果我們將不等式(14)用下式替換：     (19)也即 則不等式(13)、(19)稱為強(qiáng)Wo

19、lfe-Powell準(zhǔn)則。其重要性在于當(dāng)時(shí)，該方法過(guò)渡為精確一維搜索算法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è)；(2) 若和違反不等式(13)或者不等式(19)的右半段，則縮小搜索范圍的上限，否則轉(zhuǎn)步驟(5)；(3)  若 > ，利用二次插值方法尋找最佳點(diǎn)：設(shè)，計(jì)算和；設(shè)，若轉(zhuǎn)步驟(2)，否則轉(zhuǎn)步驟(5);若，轉(zhuǎn)步驟(4)；(4)  利用式(16)、(17)（或者式(15)、(18)）尋找最佳點(diǎn)。令，計(jì)算和；設(shè) = ，若，轉(zhuǎn)步驟(2)，否則轉(zhuǎn)步驟(5)；(5)  若滿足不等式(19)的左半段，則停止計(jì)算，得到最佳點(diǎn)；否則轉(zhuǎn)步驟(6)；(6)  利用式(16)、(17)（或者式(15)、(18)）尋找最佳點(diǎn)，并計(jì)算以及；設(shè)，若轉(zhuǎn)步驟(2)，否則轉(zhuǎn)步