擬牛頓算法資料

擬牛頓算法擬牛頓法(Quasi-NewtonMethods)是求解非線性優(yōu)化問題最有效的方法之一，于20世紀50年代由美國Argonne國家實驗室的物理學家W.C.Davidon所提出來。Davidon設計的這種算法在當時看來是非線性優(yōu)化領域最具創(chuàng)造性的發(fā)明之一。不久R.Fletcher和M.J.D.Powell證實了這種新的算法遠比其他方法快速和可靠，使得非線性優(yōu)化這門學科在一夜之間突飛猛進。在之后的20年里，擬牛頓方法得到了蓬勃發(fā)展，出現(xiàn)了大量的變形公式以及數(shù)以百計的相關論文。基本概念擬牛頓法和最速下降法(SteepestDescentMethods)一樣只要求每一步迭代時知道目標函數(shù)的梯度。通過測量梯度的變化，構造一個目標函數(shù)的模型使之足以產(chǎn)生超線性收斂性。這類方法大大優(yōu)于最速下降法，尤其對于困難的問題。另外，因為擬牛頓法不需要二階導數(shù)的信息，所以有時比牛頓法(Newton'sMethod)更為有效。如今，優(yōu)化軟件中包含了大量的擬牛頓算法用來解決無約束，約束，和大規(guī)模的優(yōu)化問題。擬牛頓法是解非線性方程組及最優(yōu)化計算中最有效的方法之一.它是一類使每步迭代計算量少而又保持超線性收斂的牛頓型迭代法。擬牛頓法還有很多具體算法，這類算法最早是由戴維登(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年中，前后發(fā)表了一千多篇文章，提出了很多不同的算法及收斂性證明。中國也有一些學者在這方面做出很好的結果。[1]基本思想擬牛頓法的基本思想如下。首先構造目標函數(shù)在當前迭代的二次模型：這里是一個對稱正定矩陣，于是我們取這個二次模型的最優(yōu)解作為搜索方向，并且得到新的迭代點，其中我們要求步長滿足Wolfe條件。這樣的迭代與牛頓法類似，區(qū)別就在于用近似的Hesse矩陣代替真實的Hesse矩陣。所以擬牛頓法最關鍵的地方就是每一步迭代中矩陣的更新。假設得到一個新的迭代，并得到一個新的二次模型：這個公式被稱為割線方程。下面主要介紹這幾種方法：DFP方法，BFGS方法，SR1方法，Broyden族方法。DFP方法記，，，DFP公式為該公式最初由Davidon于1959年提出，隨后被Fletcher和Powell研究和推廣。DFP方法是秩-2更新的一種，由它產(chǎn)生的矩陣是正定的，而且滿足這樣的極小性：BFGS方法DFP更新公式非常有效，但很快就被BFGS公式取代。BFGS與DFP十分類似，是另一種秩-2更新，以其發(fā)明者Broyden,Fletcher,Goldfarb和Shanno的姓氏首字母命名。BFGS公式為由他產(chǎn)生的矩陣同樣保持正定性，而且也滿足一個極小性：BFGS和DFP公式在形式上是對稱的：與對稱，與對稱。但是BFGS比DFP更加有效。對稱秩1（SR1）方法有別于DFP和BFG方法，SR1是一種秩-1更新。它的公式是：。SR1公式不要求矩陣B_k保持正定性，從而更逼近真實的Hesse矩陣，所以適用于信賴域方法(TrustRegionMethods)。Broyden族Boyden族是更廣泛的一類更新公式，其形式為：。當時，Br