擬牛頓法及其相關解法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、是最佳算法。一維搜索使用導數(shù)的優(yōu)化算法都涉及到沿優(yōu)化方向的一維搜索。事實上一維搜索算法本身就一個非常重要的課題，分為精確一維搜索以及非精確一維搜索。標準的擬牛頓法或L-BFGS均采用精確一維搜索。與前者相比，非精確一維搜索雖然犧牲了部分精度，但是效率更高，調用函數(shù)的次數(shù)更少。因此 Li-Fukushima方法和Xiao-Wei-Wang方法中均采用了這類算法。不加證明的，本節(jié)分別給出兩類范疇中各自的一個應用最為廣泛的例子， 分別是二點三次插值方法和Wolfe-Powell準則。二點三次插值方法在精確一維搜索各種算法中，這種方法得到的評價最高。其基本思想是選取兩個初始點和，滿足 <

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

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

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

19、lfe-Powell準則。其重要性在于當時，該方法過渡為精確一維搜索算法6。算法如下5算法5：(1)  給定兩個參數(shù)和，為初始點（相應于），為猜想點（可設為1）。計算兩點處的函數(shù)值、和導數(shù)值、。給定最大循環(huán)次 數(shù)，設；(2) 若和違反不等式(13)或者不等式(19)的右半段，則縮小搜索范圍的上限，否則轉步驟(5)；(3)  若 > ，利用二次插值方法尋找最佳點：設，計算和；設，若轉步驟(2)，否則轉步驟(5);若，轉步驟(4)；(4)  利用式(16)、(17)（或者式(15)、(18)）尋找最佳點。令，計算和；設 = ，若，轉步驟(2)，否則轉步驟(5)；(5)  若滿足不等式(19)的左半段，則停止計算，得到最佳點；否則轉步驟(6)；(6)  利用式(16)、(17)（或者式(15)、(18)）尋找最佳點，并計算以及；設，若轉步驟(2)，否則轉步