修正牛頓法

最優化方法是運籌學的一個重要組成部分:它來源於經濟，管理.工程等許多重要領域，同時和一計算數學中偏微分方程數值解法，非線性方程組數值解法等分支有着密切的聯繫.在自然科學，社會科學，生產實際，工程設計和現代化管理中具有廣泛的應用.很多實際問題都可以歸結最優化問題來解決:最優化問題的一個核心是設計有效的算法.最優化問題根據函數的具體性質和複雜程度，可以分為很多不同的種類.根據決策變量的取值是離散的還是連續的可以分為離散最優化和連續最優化.根據模型函數是否連續可微，可以分為光滑最優化和非光滑最優化.根據函數的變量是否為線性函數可以分為線性最優化和非線性最優化.無約束優化問題是最優化問題的基礎，通常採用迭代法求它的最優解.求解無約束優化問題的常用算法包括最速下降法，牛頓法，擬牛頓法，共扼梯度法等.最速下降法具有存儲量小，結構簡單，易於實現的優點，具有良好的全局收斂性，但最速下降法收斂速度很慢，理論上只具有局部收斂速度.牛頓法因其局部收斂速度快等優點而受到廣泛關注，並且它具有二階收斂速度，這使得該算法應用很廣泛。

各類數學規劃優化問題，如線性規劃、非線性規劃(約束/無約束)、隨機規劃、二次規劃等，是管理科學與工程、運籌學、決策科學和博弈論等研究中熱點和難點在經濟管理、交通網絡工程、人工智能、機器學習等管理和科學工程領域具有深厚的研究背景.近幾十年來，無約束非線性規劃作為數學規劃的一類問題，己得到一些專家學者及工作人員的廣泛研究.作為最基本最重要的求解無約束優化問題的方法，牛頓方法及其各種改進一直受到優化研究工作普遍關注。

牛頓法最初由艾薩克·牛頓於1736年公開提出的。牛頓法是解非線性算子方程的最有效的方法之一。儘管牛頓法的提出己經有兩百多年的歷史了，但是其收斂速度快，適用範圍廣等優點仍然受到眾多學者的廣泛關注，對牛頓法的改進、優化等研究仍在進行。除了修正牛頓法、阻尼牛頓法等等早期的改進算法之外，人們對於非線性算子方程解法的改進也都圍繞着牛頓法。

2000年，美國的L. O. Jay對R. S. Dembo等人於1982年提出的不精確牛頓法進行簡化，得到一種簡化的不精確牛頓法，並在一定條件下建立了相應的局部收斂性定理。到了2008年，中國的M. Wu在假設導數滿足弱Lipschitz條件的情況下，證明了不精確牛頓法的半局部收斂性定理。

2003年，何吉歡提出將非線性算子方程改寫成禍合方程系統，應該能得到一種新的求解非線性算子方程的方法。於是，韓國的C. Chun在2005年時，應用禍合方程系統的思想，對非線性算子方程應用Adomian級數法，提出了一系列建立在Adomian級數下的，求非線性算子方程的高階收斂方法。在之後的幾年中，C. B. Chun等人將牛頓法與其他高階收斂方法相結合，提出多種具體的高階收斂方法，並將收斂階由三階提升到了六階。

2007年，巴基斯坦的K. I. Noor和M. A. Noor延用禍合方程系統的思想，提出了兩步哈雷方法。同時指出兩步哈雷方法屬於預測效正法，即以牛頓法做為預測函數，以哈雷方法做為效正函數。己經證明兩步哈雷方法是六階收斂的，並且是有效的。若將效正函數定義為其他高階收斂的迭代法，又將產生多種高階收斂的兩步預測效正函數。

2008年，中國的W H. Bi和H. M. Ren等人應用四階收斂的方法提出了一類七階收斂的新算法，並且在每步迭代中避免了二階導數的計算，相對減少了計算量。

2009年，W H. Bi和H. M. Ren等人又相繼提出了只需三步迭代，就可達到八階收斂的迭代算法。

可以發現，近幾年圍繞着牛頓法做出算法的改進，主要集中在提高迭代法的收斂階上。但是，提高收斂階的代價卻是計算量的增大。兼顧收斂階與計算量的算法仍是今後工作的重點內容。 ^[1] 

修正牛頓法是尋求無約束最優化問題極小點的方法。按目標函數在迭代點處的牛頓方向，進行一維搜索迭代，設f是目標函數，xk是當前迭代點，其迭代公式為

修正牛頓法的收斂速度很快，當f的二階導數及其黑塞矩陣的逆陣便於計算時，使用這種方法非常有效。修正牛頓法有時也簡稱牛頓法。為了區別於不進 ^[2]  行一維搜索的古典牛頓法，這裏加了“修正”二字。