修正牛頓法

修正牛頓法（modified Newton method）是尋求無約束最最佳化問題極小點的方法。

牛頓法最初由艾薩克·牛頓於1736年公開提出的。牛頓法是解非線性運算元方程的最有效的方法之一。而修正牛頓法是基於牛頓法改進的一種最最佳化方法。修正牛頓法有時也簡稱牛頓法。為了區別於不進行一維搜尋的古典牛頓法，這裡加了“修正”二字。

基本介紹

• 中文名：修正牛頓法
• 外文名：modified Newton method
• 類別：數學
• 本質：尋求最小點
• 背景：最最佳化方法
• 提出者：艾薩克·牛頓

研究背景

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

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

牛頓法的發展

牛頓法最初由艾薩克·牛頓於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等人又相繼提出了只需三步疊代，就可達到八階收斂的疊代算法。

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

數學描述

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

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