擬牛頓法是一種以牛頓法為基礎設計的,求解非線性方程組或連續的最優化問題函數的零點或極大、極小值的算法。當牛頓法中所要求計算的雅可比矩陣或Hessian矩陣難以甚至無法計算時,擬牛頓法便可派上用場。
與牛頓法相同, 擬牛頓法是用一個二次函數以近似目標函數
.
的二階泰勒展開是
![{\displaystyle f(x_{k}+\Delta x)\approx f(x_{k})+\nabla f(x_{k})^{T}\Delta x+{\frac {1}{2}}\Delta x^{T}B\Delta x.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c98eaafd85327894f5fd48f1b73724e74f2c8b87)
其中,
表示
的梯度,
表示Hessian矩陣
的近似. 梯度
可進一步近似為下列形式
![{\displaystyle \nabla f(x_{k}+\Delta x)\approx \nabla f(x_{k})+B\Delta x.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a57391d9849d76dbd04d47453f8259d137e8968)
令上式等於
, 計算出Newton步長
,
![{\displaystyle \Delta x=-B^{-1}\nabla f(x_{k}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/74cbc9d344b2011645fc6df9f3d7c4bd79d073bb)
然後構造
的近似
滿足
![{\displaystyle \nabla f(x_{k}+\Delta x)=\nabla f(x_{k})+B\Delta x.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e1a36aa6b076a9ae5ae91f9441ad4ac82e9c7690)
上式稱作割線方程組. 但當
是定義在多維空間上的函數時, 從該式計算
將成為一個不定問題 (未知數個數比方程式個數多). 此時, 構造
, 根據Newton步長更新當前解的處理需要回歸到求解割線方程. 幾乎不同的擬牛頓法就有不同的選擇割線方程的方法. 而大多數的方法都假定
具有對稱性 (即滿足
). 另外, 下表所示的方法可用於求解
; 在此,
於某些範數與
盡量接近. 即對於某些正定矩陣
, 以以下方式更新
:
![{\displaystyle B_{k+1}=\arg \min _{B}\|B-B_{k}\|_{V}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2c6cd1898bafee488f0fe6f06e43ecc85f4400c8)
近似Hessian矩陣一般以單位矩陣等作為初期值[1]. 最優化問題的解
由根據近似所得的
計算出的Newton步長更新得出.
以下為該算法的總結:
![{\displaystyle \Delta x_{k}=-\alpha B_{k}^{-1}\nabla f(x_{k})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6776efbb54a0cc6e89d5ce497b908ee1a47c35d1)
![{\displaystyle x_{k+1}=x_{k}+\Delta x_{k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11f8f1a1f504263cd8360b3e7a68f0c7981eb5c8)
- 計算新一個疊代點下的梯度
![{\displaystyle \nabla f(x_{k+1})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b039aa8e8eb6096527a339957b636aba9437156e)
- 令
![{\displaystyle y_{k}=\nabla f(x_{k+1})-\nabla f(x_{k})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a3f552c14890748419975c737ec3f6e2dc870ff5)
- 利用
, 直接近似Hessian矩陣的逆矩陣
. 近似的方法如下表:
Method | | |
DFP法 | | |
BFGS法 | | |
Broyden法 | | |
Broyden族 | | |
SR1法 | | |
若
是一個凸二次函數,且Hessian矩陣
正定,我們總是希望由擬牛頓法生成的矩陣
收斂於Hessian矩陣的逆
。這是基於疊代值更新最小 (least-change update) 的擬牛頓法系列的一個實例。[2]
擬牛頓法是現在普遍使用的一種最優化算法, 存在多種编程语言的實現方法。
- ^ William H. Press. Numerical Recepes. Cambridge Press. 2007: 521-526. ISBN 978-0-521-88068-8.
- ^ Robert Mansel Gower; Peter Richtarik. Randomized Quasi-Newton Updates are Linearly Convergent Matrix Inversion Algorithms. 2015. arXiv:1602.01768
[math.NA].