牛顿法type
status
date
slug
summary
tags
category
icon
password
Property
在确定搜索方向时，最速下降法只用到了目标函数的一阶导数(梯度)，这种方式并非总是最高效的。在某些情况下，如果能够在迭代方法中引人高阶导数，其效率可能将优于最速下降法。牛顿法同时使用一阶和二阶导数来确定搜索方向，当初始点与目标函数的极小点足够接近时，效率要优于最速下降法。
牛顿法的基本思路：给定一个迭代点之后，首先构造一个二次型函数其与目标函数在该点处的一阶和二阶导数相等，以此可以作为目标函数的近似表达式；接下来求该二次型函数的极小点，以此作为下一次迭代的起始点。重复以上过程，以求得目标函数的极小点。如果目标函数本身就是二次型函数，那么构造的近似函数与目标函数完全一致；如果目标函数不是二次型函数，那么近似函数得到的极小点是目标函数极小点所在的大体位置
当目标函数 二阶连续可微时，将函数在点处进行泰勒展开（忽略三次以上的项），可得到二次型近似函数
令，应用函数的局部极小点的一阶必要条件，得
如果，牛顿迭代公式为
在一次迭代中 (令迭代次数序号为 )，牛顿法可以分为两步:
- 求解，得到
- 确定下一个迭代点 l
例：利用牛顿法求解Powell函数的极小点
初始点为
初始点对应的函数值，梯度为
黑塞矩阵为：
第1次迭代：
故有
第2 次迭代：
有
牛顿法性质分析
在单变量的情况下，如果函数的二阶导数，牛顿法无法收敛到极小点；与此类似，在多变量的情况下，如果目标函数的黑塞矩阵 非正定，牛顿法确定的搜索方向并不一定是目标函数值下降的方向
甚至在某些情况下，即使 ，牛顿法也不具有下降性，即可能出现。当初始点 远离函数极小点时，就有可能出现这种情况。尽管存在一些缺陷，但牛顿法的一大优势在于，如果初始点离极小点比较近，那么将表现出相当好的收敛性。
二次型函数收敛性
如果目标函数为二次型函数，牛顿法只需要一次迭代即可从任意初始点 收敛到函数 的极小点 满足 。 令目标函数为
其梯度和黑塞矩阵分别为
利用牛顿法迭代公式，可得在任意初始点下，有
由此可知，目标函数为二次型函数时，对于任意初始点，牛顿法的收敛阶数为
一般意义下牛顿法的收敛性
函数三阶连续可微，点 满足 ，且 可逆。那么对于所有与 足够接近的, 牛顿法能够正常运行，且至少以阶数为2的收敛率收敛到 。
如果初始点靠近极小(大)点，那么牛顿法将具有非常好的收敛性。但是，如果初始点离极小(大)点较远，牛顿法并不一定收敛（有时候会导致黑塞矩阵为奇异矩阵，方法失效）。特别是在求解最小化问题时，该方法不一定具备下降特性。幸运的是，可以对牛顿法进行一些修正
为利用牛顿法求解目标函数 极小点时得到的迭代点序列，如果 ，且 ，则从点 到点 的搜索方向
是一个下降方向，即存在一个 ，使得对于所有 ，都有
成立。
可对牛顿法进行修正如下：
其中，
也就是说，每次迭代都在方向上开展一次一维搜索，由此确定每次搜索的步长。修正牛顿法具备下降特性，即当 时，有
Levenberg-Marquardt修正
如果黑塞矩阵不正定，那么搜索方向 可能不会是下降 方向。牛顿法的 Levenberg-Marquardt 修正能够解决这一问题，保证每次产生的方向是下降方向，修正后的迭代公式为：
其中，
黑塞矩阵为对称矩阵，并不要求是正定的。特征值为 ，对应的特征向量是 。特征值全部为实数，但不要求是正数。对进行简单修正，修正矩阵 ，其中 。可知修正矩阵 的特征值为 ，且满足
即是修正矩阵 的特征向量，对应的特征值是 。因此只要足够大，总可以保证修正矩阵 的特征值都为正数，即修正矩阵是正定矩阵。
修正后迭代公式为
其中，。
引入搜索步长 ，可得新迭代公式为
令 牛顿法的Levenberg-Marquardt修正可以逐步接近牛顿法；令，Levenberg-Marquardt修正又表现出步长较小时梯度方法的特征。实际应用中，开始可为选择较小的值，然后逐渐缓慢增加，直到出现下降特性，即为止。