擬牛頓法是一種以牛頓法為基礎設計的，求解非線性方程組或連續的最優化問題函數的零點或極大、極小值的算法。當牛頓法中所要求計算的雅可比矩陣或Hessian矩陣難以甚至無法計算時，擬牛頓法便可派上用場。
搜索極值
與牛頓法相同, 擬牛頓法是用一個二次函數以近似目標函數f(x). f(x)的二階泰勒展開是
: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.
其中, \nabla f表示f(x)的梯度, B表示Hessian矩陣\mathbf{H}[f(x)]的近似. 梯度\nabla f可進一步近似為下列形式
:\nabla f(x_k + \Delta x) \approx \nabla f(x_k) + B \Delta x.
令上式等於0, 計算出Newton步長\Delta x,
: \Delta x = - B^{-1} \nabla f(x_k).
然後構造\mathbf{H}[f(x)]的近似B滿足
:\nabla f(x_k + \Delta x) = \nabla f(x_k) + B \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 \min_B \| B - B_k \|_V.
近似Hessian矩陣一般以單位矩陣等作為初期值. 最優化問題的解x_k由根據近似所得的B_k計算出的Newton步長更新得出.
以下為該算法的總結:
- \Delta x_k = -\alpha B_k^{-1} \nabla f(x_k)
- x_{k+1} = x_k + \Delta x_k
- 計算新一個疊代點下的梯度\nabla f(x_{k+1})
- 令y_k = \nabla f(x_{k+1}) - \nabla f(x_k)
- 利用y_k, 直接近似Hessian矩陣的逆矩陣B_{k+1}^{-1}. 近似的方法如下表:
與逆矩陣的關聯
若f是一個凸二次函數，且Hessian矩陣B正定，總是希望由擬牛頓法生成的矩陣H_k收斂於Hessian矩陣的逆H=B^{-1}。這是基於疊代值更新最小 (least-change update) 的擬牛頓法系列的一個實例。
實現
擬牛頓法是現在普遍使用的一種最優化算法, 存在多種程式}-语言的實現方法。
參見
- 牛頓法
- 應用於最優化的牛頓法
參考文獻
评论 (0)