擬牛頓法

擬牛頓法是一種以牛頓法為基礎設計的，求解非線性方程組或連續的最優化問題函數的零點或極大、極小值的算法。當牛頓法中所要求計算的雅可比矩陣或Hessian矩陣難以甚至無法計算時，擬牛頓法便可派上用場。

搜索極值

與牛頓法相同, 擬牛頓法是用一個二次函數以近似目標函數$f(x)$. $f(x)$的二階泰勒展開是

$f(x_k+\mathrm{\Delta }x)\approx f(x_k)+\mathrm{\nabla }f(x_k{)}^T\mathrm{\Delta }x+\frac{1}{2}\mathrm{\Delta }{x}^{T}B\mathrm{\Delta }x.$

其中, $\mathrm{\nabla }f$表示$f(x)$的梯度, $B$表示Hessian矩陣$𝐇[f(x)]$的近似. 梯度$\mathrm{\nabla }f$可進一步近似為下列形式

$\mathrm{\nabla }f(x_k+\mathrm{\Delta }x)\approx \mathrm{\nabla }f(x_k)+B\mathrm{\Delta }x.$

令上式等於$0$, 計算出Newton步長$\mathrm{\Delta }x$,

$\mathrm{\Delta }x=-B^{-1}\mathrm{\nabla }f(x_k).$

然後構造$𝐇[f(x)]$的近似$B$滿足

$\mathrm{\nabla }f(x_k+\mathrm{\Delta }x)=\mathrm{\nabla }f(x_k)+B\mathrm{\Delta }x.$

上式稱作割線方程組. 但當$f(x)$是定義在多維空間上的函數時, 從該式計算$B$將成為一個不定問題 (未知數個數比方程式個數多). 此時, 構造$B$, 根據Newton步長更新當前解的處理需要回歸到求解割線方程. 幾乎不同的擬牛頓法就有不同的選擇割線方程的方法. 而大多數的方法都假定$B$具有對稱性 (即滿足$B=B^{\text{T}}$). 另外, 下表所示的方法可用於求解$B_{k+1}$; 在此, $B_{k+1}$於某些範數與$B_k$盡量接近. 即對於某些正定矩陣$V$, 以以下方式更新$B$:

$B_{k+1}=\arg \underset{B}{\min }\Vert B-B_k{\Vert }_V.$

近似Hessian矩陣一般以單位矩陣等作為初期值. 最優化問題的解$x_k$由根據近似所得的$B_k$計算出的Newton步長更新得出.

以下為該算法的總結:

• $\mathrm{\Delta }{x}_k=-\alpha B_k^{-1}\mathrm{\nabla }f(x_k)$
• $x_{k+1}=x_k+\mathrm{\Delta }{x}_k$
• 計算新一個疊代點下的梯度$\mathrm{\nabla }f(x_{k+1})$
• 令$y_k=\mathrm{\nabla }f(x_{k+1})-\mathrm{\nabla }f(x_k)$
• 利用$y_k$, 直接近似Hessian矩陣的逆矩陣$B_{k+1}^{-1}$. 近似的方法如下表:

Method	$B_{k+1}=$	$H_{k+1}=B_{k+1}^{-1}=$
Template:Link-en	$(I-\frac{y_k\mathrm{\Delta }{x}_k^T}{y_k^T\mathrm{\Delta }{x}_k})B_k(I-\frac{\mathrm{\Delta }{x}_k{y}_k^T}{y_k^T\mathrm{\Delta }{x}_k})+\frac{y_k{y}_k^T}{y_k^T\mathrm{\Delta }{x}_k}$	$H_k+\frac{\mathrm{\Delta }{x}_k\mathrm{\Delta }{x}_k^T}{y_k^T\mathrm{\Delta }{x}_k}-\frac{H_k{y}_k{y}_k^T{H}_k^T}{y_k^T{H}_k{y}_k}$
Template:Link-en	$B_k+\frac{y_k{y}_k^T}{y_k^T\mathrm{\Delta }{x}_k}-\frac{B_k\mathrm{\Delta }{x}_k(B_k\mathrm{\Delta }{x}_k{)}^T}{\mathrm{\Delta }{x}_k^T{B}_k\mathrm{\Delta }{x}_k}$	${(I-\frac{y_k\mathrm{\Delta }{x}_k^T}{y_k^T\mathrm{\Delta }{x}_k})}^T{H}_k(I-\frac{y_k\mathrm{\Delta }{x}_k^T}{y_k^T\mathrm{\Delta }{x}_k})+\frac{\mathrm{\Delta }{x}_k\mathrm{\Delta }{x}_k^T}{y_k^T\mathrm{\Delta }{x}_k}$
Template:Link-en	$B_k+\frac{y_k-B_k\mathrm{\Delta }{x}_k}{\mathrm{\Delta }{x}_k^T\mathrm{\Delta }{x}_k}\mathrm{\Delta }{x}_k^T$	$H_k+\frac{(\mathrm{\Delta }{x}_k-H_k{y}_k)\mathrm{\Delta }{x}_k^T{H}_k}{\mathrm{\Delta }{x}_k^T{H}_k{y}_k}$
Broyden族	$(1-{\phi }_k)B_{k+1}^{BFGS}+{\phi }_k{B}_{k+1}^{DFP},\phi \in [0,1]$
Template:Link-en	$B_k+\frac{(y_k-B_k\mathrm{\Delta }{x}_k)(y_k-B_k\mathrm{\Delta }{x}_k{)}^T}{(y_k-B_k\mathrm{\Delta }{x}_k{)}^T\mathrm{\Delta }{x}_k}$	$H_k+\frac{(\mathrm{\Delta }{x}_k-H_k{y}_k)(\mathrm{\Delta }{x}_k-H_k{y}_k{)}^T}{(\mathrm{\Delta }{x}_k-H_k{y}_k{)}^T{y}_k}$

與逆矩陣的關聯

若$f$是一個凸二次函數，且Hessian矩陣$B$正定，總是希望由擬牛頓法生成的矩陣$H_k$收斂於Hessian矩陣的逆$H=B^{-1}$。這是基於疊代值更新最小 (least-change update) 的擬牛頓法系列的一個實例。

實現

擬牛頓法是現在普遍使用的一種最優化算法, 存在多種-{zh-hans:编程;zh-hant:程式}-语言的實現方法。

參見

• 牛頓法
• 應用於最優化的牛頓法