搜索極值
與牛頓法相同, 擬牛頓法是用一個二次函數以近似目標函數 . 的二階泰勒展開是
-
其中, 表示 的梯度, 表示Hessian矩陣 的近似. 梯度 可進一步近似為下列形式
-
令上式等於 , 計算出Newton步長 ,
-
然後構造 的近似 滿足
-
上式稱作割線方程組. 但當 是定義在多維空間上的函數時, 從該式計算 將成為一個不定問題 (未知數個數比方程式個數多). 此時, 構造 , 根據Newton步長更新當前解的處理需要回歸到求解割線方程. 幾乎不同的擬牛頓法就有不同的選擇割線方程的方法. 而大多數的方法都假定 具有對稱性 (即滿足 ). 另外, 下表所示的方法可用於求解 ; 在此, 於某些範數與 盡量接近. 即對於某些正定矩陣 , 以以下方式更新 :
-
近似Hessian矩陣一般以單位矩陣等作為初期值[1]. 最優化問題的解 由根據近似所得的 計算出的Newton步長更新得出.
以下為該算法的總結:
-
-
- 計算新一個疊代點下的梯度
- 令
- 利用 , 直接近似Hessian矩陣的逆矩陣 . 近似的方法如下表:
Method
|
|
|
DFP法
|
|
|
BFGS法
|
|
|
Broyden法
|
|
|
Broyden族
|
|
|
SR1法
|
|
|
與逆矩陣的關聯
實現
擬牛頓法是現在普遍使用的一種最優化算法, 存在多種程式語言的實現方法。
參見
參考文獻
- ^ 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].