擬牛頓法
擬牛頓法
擬牛頓法(Quasi-Newton Methods)是求解非線性優化問題最有效的方法之一，於20世紀50年代由美國Argonne國家實驗室的物理學家W. C. Davidon所提出來。Davidon設計的這種演演算法在當時看來是非線性優化領域最具創造性的發明之一。不久R. Fletcher和M. J. D. Powell證實了這種新的演演算法遠比其他方法快速和可靠，使得非線性優化這門學科在一夜之間突飛猛進。在之後的20年裡，擬牛頓方法得到了蓬勃發展，出現了大量的變形公式以及數以百計的相關論文。
擬牛頓法和最速下降法(Steepest Descent Methods)一樣只要求每一步迭代時知道目標函數的梯度。通過測量梯度的變化，構造一個目標函數的模型使之足以產生超線性收斂性。這類方法大大優於最速下降法，尤其對於困難的問題。另外，因為擬牛頓法不需要二階導數的信息，所以有時比牛頓法(Newton's Method)更為有效。如今，優化軟體中包含了大量的擬牛頓演演算法用來解決無約束，約束，和大規模的優化問題。
擬牛頓法的基本思想如下。首先構造目標函數在當前迭代的二次模型：
這裡是一個對稱正定矩陣，於是我們取這個二次模型的最優解作為搜索方向，並且得到新的迭代點，其中我們要求步長滿足Wolfe條件。這樣的迭代與牛頓法類似，區別就在於用近似的Hesse矩陣代替真實的Hesse矩陣。所以擬牛頓法最關鍵的地方就是每一步迭代中矩陣的更新。現在假設得到一個新的迭代，並得到一個新的二次模型：
我們儘可能地利用上一步的信息來選取。具體地，我們要求,
從而得到這個公式被稱為割線方程。下面主要介紹這幾種方法：DFP方法，BFGS方法，SR1方法，Broyden族方法。
記,,,DFP公式為
該公式最初由Davidon於1959年提出，隨後被Fletcher和Powell研究和推廣。DFP方法是秩-2更新的一種，由它產生的矩陣是正定的，而且滿足這樣的極小性：
有別於DFP和BFG方法，SR1是一種秩-1更新。它的 公式是：SR1 公式不要求矩陣保持正定性，從而更逼近真實的Hesse矩陣，所以適用於信賴域方法(Trust Region Methods)。
Boyden族是更廣泛的一類更新 公式，其形式為：。當時，Broyden族 公式就變成了BFGS公式；當時，Broyden族公式就變成了DFP公式。因此BFGS和DFP均可看成Broyden族的特殊形式或者其中一員。