[科普中国]-修正牛顿法

研究背景

最优化方法是运筹学的一个重要组成部分:它来源于经济，管理.工程等许多重要领域，同时和一计算数学中偏微分方程数值解法，非线性方程组数值解法等分支有着密切的联系.在自然科学，社会科学，生产实际，工程设计和现代化管理中具有广泛的应用.很多实际问题都可以归结最优化问题来解决:最优化问题的一个核心是设计有效的算法.最优化问题根据函数的具体性质和复杂程度，可以分为很多不同的种类.根据决策变量的取值是离散的还是连续的可以分为离散最优化和连续最优化.根据模型函数是否连续可微，可以分为光滑最优化和非光滑最优化.根据函数的变量是否为线性函数可以分为线性最优化和非线性最优化.无约束优化问题是最优化问题的基础，通常采用迭代法求它的最优解.求解无约束优化问题的常用算法包括最速下降法，牛顿法，拟牛顿法，共扼梯度法等.最速下降法具有存储量小，结构简单，易于实现的优点，具有良好的全局收敛性，但最速下降法收敛速度很慢，理论上只具有局部收敛速度.牛顿法因其局部收敛速度快等优点而受到广泛关注，并且它具有二阶收敛速度，这使得该算法应用很广泛。

各类数学规划优化问题，如线性规划、非线性规划(约束/无约束)、随机规划、二次规划等，是管理科学与工程、运筹学、决策科学和博弈论等研究中热点和难点在经济管理、交通网络工程、人工智能、机器学习等管理和科学工程领域具有深厚的研究背景.近几十年来，无约束非线性规划作为数学规划的一类问题，己得到一些专家学者及工作人员的广泛研究.作为最基本最重要的求解无约束优化问题的方法，牛顿方法及其各种改进一直受到优化研究工作普遍关注。

牛顿法的发展牛顿法最初由艾萨克·牛顿于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行一维搜索的古典牛顿法，这里加了“修正”二字。