优化算法——牛顿法(Newton Method)

? ? 除了前面说的梯度下降法，牛顿法也是机器学习中用的比较多的一种优化算法。牛顿法的基本思想是利用迭代点

处的一阶导数(梯度)和二阶导数(Hessen矩阵)对目标函数进行二次函数近似，然后把二次模型的极小点作为新的迭代点，并不断重复这一过程，直至求得满足精度的近似极小值。牛顿法的速度相当快，而且能高度逼近最优值。牛顿法分为基本的牛顿法和全局牛顿法。

? ? 基本牛顿法是一种是用导数的算法，它每一步的迭代方向都是沿着当前点函数值下降的方向。

? ? 我们主要集中讨论在一维的情形，对于一个需要求解的优化函数

，求函数的极值的问题可以转化为求导函数

。对函数

进行泰勒展开到二阶，得到

对上式求导并令其为0，则为

即得到

这就是牛顿法的更新公式。

1. 给定终止误差值

，初始点

，令

；

1. 计算

，若

，则停止，输出

；

1. 计算

，并求解线性方程组得解

：

；

1. 令

，

，并转2。

? ? 牛顿法最突出的优点是收敛速度快，具有局部二阶收敛性，但是，基本牛顿法初始点需要足够“靠近”极小点，否则，有可能导致算法不收敛。这样就引入了全局牛顿法。

1. 给定终止误差值

，

，

，初始点

，令

；

1. 计算

，若

，则停止，输出

；

1. 计算

，并求解线性方程组得解

：

；

1. 记

是不满足下列不等式的最小非负整数

：

；

1. 令

，

，

，并转2。

? ? 全局牛顿法是基于Armijo的搜索，满足Armijo准则：

给定

，

，令步长因子

，其中

是满足下列不等式的最小非负整数:

? ? 实验部分使用Java实现，需要优化的函数

，最小值为

。