跳转到内容

擬牛頓法

维基百科,自由的百科全书

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

搜索極值

[编辑]

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

其中, 表示梯度, 表示Hessian矩陣的近似. 梯度可進一步近似為下列形式

令上式等於, 計算出Newton步長,

然後構造的近似滿足

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

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

以下為該算法的總結:

  • 計算新一個疊代點下的梯度
  • 利用, 直接近似Hessian矩陣逆矩陣. 近似的方法如下表:
Method
DFP法英语DFP updating formula
BFGS法英语BFGS method
Broyden法英语Broyden's method
Broyden族
SR1法英语SR1 formula

與逆矩陣的關聯

[编辑]

是一個二次函數,且Hessian矩陣正定,總是希望由擬牛頓法生成的矩陣收斂於Hessian矩陣的逆。這是基於疊代值更新最小 (least-change update) 的擬牛頓法系列的一個實例。[2]

實現

[编辑]

擬牛頓法是現在普遍使用的一種最優化算法, 存在多種编程语言的實現方法。

參見

[编辑]

參考文獻

[编辑]
  1. ^ William H. Press. Numerical Recepes. Cambridge Press. 2007: 521-526. ISBN 978-0-521-88068-8. 
  2. ^ Robert Mansel Gower; Peter Richtarik. Randomized Quasi-Newton Updates are Linearly Convergent Matrix Inversion Algorithms. 2015. arXiv:1602.01768可免费查阅 [math.NA].