擬牛頓算法資料

擬牛頓算法擬牛頓法(Quasi-NewtonMethods)是求解非線性優(yōu)化問(wèn)題最有效的方法之一，于20世紀(jì)50年代由美國(guó)Argonne國(guó)家實(shí)驗(yàn)室的物理學(xué)家W.C.Davidon所提出來(lái)。Davidon設(shè)計(jì)的這種算法在當(dāng)時(shí)看來(lái)是非線性優(yōu)化領(lǐng)域最具創(chuàng)造性的發(fā)明之一。不久R.Fletcher和M.J.D.Powell證實(shí)了這種新的算法遠(yuǎn)比其他方法快速和可靠，使得非線性優(yōu)化這門學(xué)科在一夜之間突飛猛進(jìn)。在之后的20年里，擬牛頓方法得到了蓬勃發(fā)展，出現(xiàn)了大量的變形公式以及數(shù)以百計(jì)的相關(guān)論文?；靖拍顢M牛頓法和最速下降法(SteepestDescentMethods)一樣只要求每一步迭代時(shí)知道目標(biāo)函數(shù)的梯度。通過(guò)測(cè)量梯度的變化，構(gòu)造一個(gè)目標(biāo)函數(shù)的模型使之足以產(chǎn)生超線性收斂性。這類方法大大優(yōu)于最速下降法，尤其對(duì)于困難的問(wèn)題。另外，因?yàn)閿M牛頓法不需要二階導(dǎo)數(shù)的信息，所以有時(shí)比牛頓法(Newton'sMethod)更為有效。如今，優(yōu)化軟件中包含了大量的擬牛頓算法用來(lái)解決無(wú)約束，約束，和大規(guī)模的優(yōu)化問(wèn)題。擬牛頓法是解非線性方程組及最優(yōu)化計(jì)算中最有效的方法之一.它是一類使每步迭代計(jì)算量少而又保持超線性收斂的牛頓型迭代法。擬牛頓法還有很多具體算法，這類算法最早是由戴維登(Davidon，W.D.)于1959年提出的，弗萊徹(Fletcher，R.)和鮑威爾(Powell，M.J.D.)于1963年給出了后來(lái)稱為DFP的秩2擬牛頓法，布羅依丹(Broyden，C.G.)于1965年給出了秩1擬牛頓法.方法的收斂性是20世紀(jì)60年代末到20世紀(jì)70年代才逐漸被證明的.由于這類方法受到廣泛注意，從20世紀(jì)60年代到20世紀(jì)70年代近20年中，前后發(fā)表了一千多篇文章，提出了很多不同的算法及收斂性證明。中國(guó)也有一些學(xué)者在這方面做出很好的結(jié)果。[1]基本思想擬牛頓法的基本思想如下。首先構(gòu)造目標(biāo)函數(shù)在當(dāng)前迭代的二次模型：這里是一個(gè)對(duì)稱正定矩陣，于是我們?nèi)∵@個(gè)二次模型的最優(yōu)解作為搜索方向，并且得到新的迭代點(diǎn)，其中我們要求步長(zhǎng)滿足Wolfe條件。這樣的迭代與牛頓法類似，區(qū)別就在于用近似的Hesse矩陣代替真實(shí)的Hesse矩陣。所以擬牛頓法最關(guān)鍵的地方就是每一步迭代中矩陣的更新。假設(shè)得到一個(gè)新的迭代，并得到一個(gè)新的二次模型：這個(gè)公式被稱為割線方程。下面主要介紹這幾種方法：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)生的矩陣同樣保持正定性，而且也滿足一個(gè)極小性：BFGS和DFP公式在形式上是對(duì)稱的：與對(duì)稱，與對(duì)稱。但是BFGS比DFP更加有效。對(duì)稱秩1（SR1）方法有別于DFP和BFG方法，SR1是一種秩-1更新。它的公式是：。SR1公式不要求矩陣B_k保持正定性，從而更逼近真實(shí)的Hesse矩陣，所以適用于信賴域方法(TrustRegionMethods)。Broyden族Boyden族是更廣泛的一類更新公式，其形式為：。當(dāng)時(shí)，Br