(綠色) 與牛頓法 (紅色) 在求最小值問題上的比較 (帶有步長). 可見牛頓法根據曲率選擇了一條「捷徑」。]]
牛頓法是微積分學中, 通過疊代以求解可微函數f的零點的一種算法 (即求x使得f(x)=0). 而在最佳化中, 牛頓法通常被運用於求解一個二次可微函數f的一階導數f^\prime的零點（即求x使得f^\prime(x)=0）, 同時也是f的駐點. 因此從另一個角度而言，應用於最佳化的牛頓法是搜索函數f(x)的最小值或最大值的一種算法。
一維問題的牛頓法主要步驟如下:
取一個點x_0為初值, 依如下公式疊代:
:x_{n+1}=x_n-\frac{f^\prime(x_n)}{f^{\prime\prime}(x_n)},
直至滿足一定條件 (如f^\prime(x_n)=0或x_{n+1}-x_n, 其中\varepsilon為一個給定的足夠小的常數) 後, 算法終止。
方法描述
在一維問題中, 牛頓法將構造一個以x_0為首項, 收斂到x^的數列\{x_n\}, 其中x^使得f^\prime(x^*)=0成立.
f(x)在x=x_n處的二階泰勒展開式f_T(x)為:
:f_T(x)=f_T(x_n+\Delta x)\approx f(x_n)+f^\prime(x_n)\Delta x+\frac{1}{2}f^{\prime\prime}(x_n)\Delta x^2.
我們希望找到\Delta x使x_n+\Delta x為f_T(x)的一個駐點。則將上式對\Delta x進行求導:
:0=\frac{\text{d}}{\text{d}\Delta x}(f(x_n)+f^\prime(x_n)\Delta x+\frac{1}{2}f^{\prime\prime}(x_n)\Delta x^2)=f^\prime(x_n)+f^{\prime\prime}(x_n)\Delta x.
上述方程的解\Delta x=-\frac{f^\prime(x_n)}{f^{\prime\prime}(x_n)}滿足
:x_{n+1}=x_{n}+\Delta x=x_n-\frac{f^\prime(x_n)}{f^{\prime\prime}(x_n)}
收斂於f_T(x)的駐點x^*.
幾何意義
牛頓法的幾何意義為: 在每一次疊代中，均以一個二次函數去逼近f(x). 具體而言:
在一維問題中，已知x_n, f(x_n), f^\prime(x_n)及f^{\prime\prime}(x_n), 設二次函數表逹式為ax^2+bx+c, 依下列方程求解未知數a,\ b,\ c,
:ax_n^2+bx_n+c=f(x_n),
:2ax_n+b=f^\prime(x_n),
:2a=f^{\prime\prime}(x_n).
然後二次函數ax^2+bx+c的極值點即為下一個疊代點,
:x_{n+1}=-\frac{b}{2a}.
而在高維問題中, 上述的極值點也可以是鞍點. 值得一提的是, 如果f(x)恰為一個二次函數, 則其極值點只需一次疊代中即可找到.
高維問題求解
上述的一維問題的疊代法可以被推廣至多維問題. 只需將導數替換為梯度 (\nabla f(x)), 並將二階導數的倒數替換為Hessian矩陣的逆矩陣 (\mathbf{H}f(x)), 即:
:x_{n+1}=x_n-[\mathbf{H}f(x_n)]^{-1}\nabla f(x_n), n\ge 0.
通常, 使用牛頓法時會加入一個步長變量\gamma\in(0,1)作微調以使每一步疊代都滿足Wolfe條件, 即,
:x_{n+1}=x_n-\gamma[\mathbf{H}f(x_n)]^{-1}\nabla f(x_n).
這個方法被稱為無約束牛頓法, 通常用於第一步之後的疊代.
只要牛頓法適用, 其收斂於最小值或最大值的速度均頗快於最速下降法. 事實上, 對於每一個極小值, 都存在一個鄰域N使得, 只要Hessian矩陣是可逆的且是一個關於x\in N的Lipschitz連續函數, 以x_0\in N為初值, 步長\gamma=1的牛頓法是二次收斂的.
求一個高維問題的Hessian矩陣的逆矩陣是一件頗費工夫的事情. 在實際應用中, 通常會用向量\Delta x=x_{n+1}-x_n作為線性方程組
:[\mathbf{H}f(x_n)]\Delta x=-\nabla f(x_n)
的解. 這個求解過程中, 透過使用各種矩陣分解方法同近似求解方法, 求解速度可以大大提升. 然而, 這些矩陣分解方法或近似求解方法的使用需要滿足一定條件; 例如, Cholesky分解同共軛梯度法只有在\mathbf{H}f(x)是正定矩陣時才適用. 這看似是一個限制, 但有時也能充當檢驗答案的工具; 例如, 在一個最小化問題 (\text{min }f(x)) 中, 求出一個x^\prime使得\nabla f(x^\prime)=0但\mathbf{H}f(x)不是正定矩陣, 那麽(x^\prime,f(x^\prime))只是f(x)的一個鞍點而非極小值點.
另一方面, 一個有約束的問題的求解過程可能會遇到當前解陷入一個鞍點的情況, 這時的Hessian矩陣是對稱不定的; 此時則要使用其他方法, 例如Cholesky分解的\mathbf{LDL}^\mathbf{T}變形或共軛梯度法等的方法, 來疊代得出x_{n+1}.
此外, 為規避求Hessian矩陣的繁瑣, 也存在多種擬牛頓法, 通過調整梯度以求出Hessian矩陣的近似.
如果Hessian矩陣\mathbf{H}f(x)接近一個奇異矩陣, 則其逆矩陣會變得數值不穩定且疊代不會收斂. 此種情形下, 前人探索出了很多成功的方法來解決問題. 目標之一是通過引入修正矩陣B_n使得\mathbf{H}f(x_n):= \mathbf{H}f(x_n) + B_n是對稱正定的. 其中一種方法是將\mathbf{H}f(x_n)對角化, 選擇B_n使\mathbf{H}f(x_n) + B_n有相同的特徵向量, 但每一個\mathbf{H}f(x_n)的負特徵值都被替換成\epsilon>0.
一個應用於萊文貝格－馬夸特方法 (其中用到了近似的Hessian矩陣) 的方法是引入一個帶係數的單位矩陣\mu\mathbf{I}, 係數在每一步疊代中調整. 對於較大的\mu及較小的Hessian矩陣, 疊代將變得與以\mu^{-1}為步長的最速下降法相似, 這將使得疊代收斂變慢, 但在Hessian矩陣不定或半定的情況下, 收斂更穩定.
參閱
*擬牛頓法
*最速下降法
*高斯–牛頓算法
*萊文貝格－馬夸特方法
*置信域方法
*最佳化
*Nelder–Mead方法
參考文獻
*
*
*
*
外部連結
*
评论 (0)