擬牛頓法

擬牛頓法和最速下降法(Steepest Descent Methods)一樣只要求每一步迭代時知道目標函數的梯度。通過測量梯度的變化，構造一個目標函數的模型使之足以產生超線性收斂性。這類方法大大優於最速下降法，尤其對於困難的問題。另外，因為擬牛頓法不需要二階導數的信息，所以有時比牛頓法(Newton's Method)更為有效。如今，優化軟件中包含了大量的擬牛頓算法用來解決無約束，約束，和大規模的優化問題。

擬牛頓法是解非線性方程組及最優化計算中最有效的方法之一.它是一類使每步迭代計算量少而又保持超線性收斂的牛頓型迭代法。

擬牛頓法還有很多具體算法，這類算法最早是由戴維登(Davidon，W.D.)於1959年提出的，弗萊徹(Fletcher，R.)和鮑威爾(Powell，M.J.D.)於1963年給出了後來稱為DFP的秩2擬牛頓法，布羅依丹(Broyden，C.G.)於1965年給出了秩1擬牛頓法.方法的收斂性是20世紀60年代末到20世紀70年代才逐漸被證明的.由於這類方法受到廣泛注意，從20世紀60年代到20世紀70年代近20年中，前後發表了一千多篇文章，提出了很多不同的算法及收斂性證明。中國也有一些學者在這方面做出很好的結果。 ^[1] 

擬牛頓法的基本思想如下。首先構造目標函數在當前迭代

的二次模型：

這裏

是一個對稱正定矩陣，於是我們取這個二次模型的最優解作為搜索方向，並且得到新的迭代點

，其中我們要求步長

滿足Wolfe條件。這樣的迭代與牛頓法類似，區別就在於用近似的Hesse矩陣

代替真實的Hesse矩陣。所以擬牛頓法最關鍵的地方就是每一步迭代中矩陣

的更新。假設得到一個新的迭代

，並得到一個新的二次模型：

我們儘可能地利用上一步的信息來選取

。具體地，我們要求

，從而得到

這個公式被稱為割線方程。下面主要介紹這幾種方法：DFP方法，BFGS方法，SR1方法，Broyden族方法。

記

，

，

，DFP公式為

該公式最初由Davidon於1959年提出，隨後被Fletcher和Powell研究和推廣。DFP方法是秩-2更新的一種，由它產生的矩陣

是正定的，而且滿足這樣的極小性：

DFP更新公式非常有效，但很快就被BFGS公式取代。BFGS與DFP十分類似，是另一種秩-2更新，以其發明者Broyden, Fletcher, Goldfarb和Shanno的姓氏首字母命名。BFGS公式為

由他產生的矩陣

同樣保持正定性，而且也滿足一個極小性：

BFGS和DFP公式在形式上是對稱的：

與

對稱，

與

對稱。但是BFGS比DFP更加有效。

有別於DFP和BFG方法，SR1是一種秩-1更新。它的公式是：

。SR1公式不要求矩陣B_k保持正定性，從而更逼近真實的Hesse矩陣，所以適用於信賴域方法(Trust Region Methods)。

Boyden族是更廣泛的一類更新公式，其形式為：

。當

時，Broyden族公式就變成了BFGS公式；當

時，Broyden族公式就變成了DFP公式。因此BFGS和DFP均可看成Broyden族的特殊形式或者其中一員。