查看“︁擬牛頓法”︁的源代码

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

== 搜索極值 ==

與牛頓法相同, 擬牛頓法是用一個[[二次函數]]以近似目標函數<math>f(x)</math>. <math>f(x)</math>的二階[[泰勒展開]]是
:<math>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. </math>
其中, <math>\nabla f</math>表示<math>f(x)</math>的[[梯度]], <math>B</math>表示[[Hessian矩陣]]<math>\mathbf{H}[f(x)]</math>的近似. 梯度<math>\nabla f</math>可進一步近似為下列形式
:<math>\nabla f(x_k + \Delta x) \approx \nabla f(x_k) + B \Delta x. </math>
令上式等於<math>0</math>, 計算出Newton步長<math>\Delta x</math>, 
:<math> \Delta x = - B^{-1} \nabla f(x_k). </math>
然後構造<math>\mathbf{H}[f(x)]</math>的近似<math>B</math>滿足
:<math>\nabla f(x_k + \Delta x) = \nabla f(x_k) + B \Delta x. </math>
上式稱作割線方程組. 但當<math>f(x)</math>是定義在多維空間上的函數時, 從該式計算<math>B</math>將成為一個''[[不定方程組|不定]]問題'' (未知數個數比方程式個數多). 此時, 構造<math>B</math>, 根據Newton步長更新當前解的處理需要回歸到求解割線方程. 幾乎不同的擬牛頓法就有不同的選擇割線方程的方法. 而大多數的方法都假定<math>B</math>具有[[對稱矩陣|對稱性]] (即滿足<math>B=B^\text{T}</math>). 另外, 下表所示的方法可用於求解<math>B_{k+1}</math>; 在此, <math>B_{k+1}</math>於某些[[範數]]與<math>B_k</math>盡量接近. 即對於某些[[正定矩陣]]<math>V</math>, 以以下方式更新<math>B</math>:
:<math>B_{k+1} = \arg \min_B \| B - B_k \|_V. </math>
近似[[Hessian矩陣]]一般以[[單位矩陣]]等作為初期值<ref>{{Cite book|author=William H. Press|year=2007|title=Numerical Recepes|publisher=Cambridge Press|page=521-526|isbn=978-0-521-88068-8}}</ref>. 最優化問題的解<math>x_k</math>由根據近似所得的<math>B_k</math>計算出的Newton步長更新得出.

以下為該算法的總結:
* <math>\Delta x_k = -\alpha B_k^{-1} \nabla f(x_k) </math>
* <math>x_{k+1} = x_k + \Delta x_k</math>
* 計算新一個疊代點下的[[梯度]]<math>\nabla f(x_{k+1})</math>
* 令<math>y_k = \nabla f(x_{k+1}) - \nabla f(x_k)</math>
* 利用<math>y_k</math>, 直接近似[[Hessian矩陣]]的[[逆矩陣]]<math>B_{k+1}^{-1}</math>. 近似的方法如下表: 

{| class="wikitable"

|-
! Method
! <math>\displaystyle B_{k+1}=</math>
! <math>H_{k+1}=B_{k+1}^{-1}=</math>
|-

| {{Link-en|DFP法|DFP updating formula}}

| <math>\left (I-\frac {y_k \, \Delta x_k^T} {y_k^T \, \Delta x_k} \right ) B_k \left (I-\frac {\Delta x_k y_k^T} {y_k^T \, \Delta x_k} \right )+\frac{y_k y_k^T} {y_k^T \, \Delta x_k}</math>

| <math> H_k + \frac {\Delta x_k \Delta x_k^T}{y_k^{T} \, \Delta x_k} - \frac {H_k y_k y_k^T H_k^T} {y_k^T H_k y_k}</math>

|-

| {{Link-en|BFGS法|BFGS method}}

| <math> B_k + \frac {y_k y_k^T}{y_k^{T} \Delta x_k} - \frac {B_k \Delta x_k (B_k \Delta x_k)^T} {\Delta x_k^{T} B_k \, \Delta x_k}</math>

| <math> \left (I-\frac {y_k \Delta x_k^T} {y_k^T \Delta x_k} \right )^T H_k \left (I-\frac { y_k \Delta x_k^T} {y_k^T \Delta x_k} \right )+\frac
{\Delta x_k \Delta x_k^T} {y_k^T \, \Delta x_k}</math>

|-
| {{Link-en|Broyden法|Broyden's method}}

| <math> B_k+\frac {y_k-B_k \Delta x_k}{\Delta x_k^T \, \Delta x_k} \, \Delta x_k^T  </math>

|<math>H_{k}+\frac {(\Delta x_k-H_k y_k) \Delta x_k^T H_k}{\Delta x_k^T H_k \, y_k}</math>

|-

| Broyden族

| <math>(1-\varphi_k) B_{k+1}^{BFGS}+ \varphi_k B_{k+1}^{DFP}, \qquad \varphi\in[0,1]</math>

|
|-

| {{Link-en|SR1法|SR1 formula}}

| <math>B_{k}+\frac {(y_k-B_k \, \Delta x_k) (y_k-B_k \, \Delta x_k)^T}{(y_k-B_k \, \Delta x_k)^T \, \Delta x_k}</math>

| <math>H_{k}+\frac {(\Delta x_k-H_k y_k) (\Delta x_k-H_k y_k)^T}{(\Delta x_k-H_k y_k)^T y_k}</math>

|}

== 與逆矩陣的關聯 ==

若<math>f</math>是一個[[凸函數|凸]][[二次函數]]，且[[Hessian矩陣]]<math>B</math>[[正定矩陣|正定]]，總是希望由擬牛頓法生成的矩陣<math>H_k</math>收斂於Hessian矩陣的逆<math>H=B^{-1}</math>。這是基於疊代值更新最小 (least-change update) 的擬牛頓法系列的一個實例。<ref name="Gower and Richtarik">{{ cite arxiv | author1 = Robert Mansel Gower |author2= Peter Richtarik | title = Randomized Quasi-Newton Updates are Linearly Convergent Matrix Inversion Algorithms | date = 2015 |eprint=1602.01768| class = math.NA }}</ref>

== 實現 ==

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

== 參見 ==
* [[牛頓法]]
* [[應用於最優化的牛頓法]]

== 參考文獻 ==
<references />

[[Category:最优化算法]]
[[Category:求根算法]]