跳至內容

應用於最佳化的牛頓法

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書
最速下降法 (綠色) 與牛頓法 (紅色) 在求最小值問題上的比較 (帶有步長). 可見牛頓法根據曲率選擇了一條「捷徑」.

牛頓法微積分學中, 通過疊代以求解可微函數零點的一種演算法 (即求使得). 而在最佳化中, 牛頓法通常被運用於求解一個二次可微函數一階導數的零點 (即求使得), 同時也是駐點. 因此從另一個角度而言,應用於最佳化的牛頓法是搜尋函數的最小值或最大值的一種演算法。


一維問題的牛頓法主要步驟如下: 取一個點初值, 依如下公式疊代:

直至滿足一定條件 (如, 其中為一個給定的足夠小的常數) 後, 演算法終止。


方法描述

在一維問題中, 牛頓法將構造一個以為首項, 收斂的數列, 其中使得成立.

處的二階泰勒展開式為:

我們希望找到使的一個駐點。則將上式對進行求導:

上述方程的解滿足

收斂於的駐點.

幾何意義

牛頓法的幾何意義為: 在每一次疊代中,均以一個二次函數去逼近. 具體而言: 在一維問題中,已知, , , 設二次函數表逹式為, 依下列方程求解未知數

然後二次函數極值點即為下一個疊代點,

而在高維問題中, 上述的極值點也可以是鞍點. 值得一提的是, 如果恰為一個二次函數, 則其極值點只需一次疊代中即可找到.


高維問題求解

上述的一維問題的疊代法可以被推廣至多維問題. 只需將導數替換為梯度 (), 並將二階導數的倒數替換為Hessian矩陣逆矩陣 (), 即:

通常, 使用牛頓法時會加入一個步長變數作微調以使每一步疊代都滿足Wolfe條件, 即,

這個方法被稱為無約束牛頓法, 通常用於第一步之後的疊代.

只要牛頓法適用, 其收斂於最小值或最大值的速度均頗快於最速下降法. 事實上, 對於每一個極小值, 都存在一個鄰域使得, 只要Hessian矩陣可逆的且是一個關於Lipschitz連續函數, 以為初值, 步長的牛頓法是二次收斂的.


求一個高維問題的Hessian矩陣逆矩陣是一件頗費工夫的事情. 在實際應用中, 通常會用向量作為線性方程組

的解. 這個求解過程中, 透過使用各種矩陣分解方法同近似求解方法, 求解速度可以大大提升. 然而, 這些矩陣分解方法或近似求解方法的使用需要滿足一定條件; 例如, Cholesky分解共軛梯度法只有在正定矩陣時才適用. 這看似是一個限制, 但有時也能充當檢驗答案的工具; 例如, 在一個最小化問題 () 中, 求出一個使得不是正定矩陣, 那麽只是的一個鞍點而非極小值點.


另一方面, 一個有約束的問題的求解過程可能會遇到當前解陷入一個鞍點的情況, 這時的Hessian矩陣對稱不定的; 此時則要使用其他方法, 例如Cholesky分解的變形共軛梯度法等的方法, 來疊代得出.


此外, 為規避求Hessian矩陣的繁瑣, 也存在多種擬牛頓法, 通過調整梯度以求出Hessian矩陣的近似.


如果Hessian矩陣接近一個奇異矩陣, 則其逆矩陣會變得數值不穩定且疊代不會收斂. 此種情形下, 前人探索出了很多成功的方法來解決問題. 目標之一是通過引入修正矩陣使得對稱正定的. 其中一種方法是將對角化, 選擇使有相同的特徵向量, 但每一個的負特徵值都被替換成


一個應用於萊文貝格-馬夸特方法 (其中用到了近似的Hessian矩陣) 的方法是引入一個帶系數的單位矩陣, 系數在每一步疊代中調整. 對於較大的及較小的Hessian矩陣, 疊代將變得與以為步長的最速下降法相似, 這將使得疊代收斂變慢, 但在Hessian矩陣不定半定的情況下, 收斂更穩定.

參閱

參考文獻

外部連結