[机器学习必知必会]牛顿法与拟牛顿法

前言

同梯度下降法一样，牛顿法和拟牛顿法也是求解无约束最优化问题的常用方法。牛顿法本身属于迭代算法，每一步需要求解目标函数的海赛矩阵的逆矩阵，计算比较复杂。拟牛顿法通过正定矩阵近似海赛矩阵的逆矩阵或海赛矩阵，简化了这一计算过程。

需要提前了解的知识

1.泰勒展开

当

在

处具有

阶连续导数，我们可以用

的

次多项式逼近函数

公式：

其中

表示泰勒余项，它是

的高阶无穷小。

2.海森矩阵

Hessian Matrix，是一个多元函数的二阶偏导数构成的方阵，描述了函数的局部曲率

以二元函数

为例，它在

点处的泰勒展开式为： $$ f(x_1,x_2) = f(x_1{(0)},x_2{(0)})

• \frac{\partial{f}}{\partial{x_1}}\Big|_{X^{(0)}} \triangle x_1
• \frac{\partial{f}}{\partial{x_2}}\Big|_{X^{(0)}} \triangle x_2
• \frac{1}{2} \bigg[ \frac{\partial 2{f}}{\partial{x_12}}\Big|_{X^{(0)}} \triangle x_1^2
• \frac{\partial 2{f}}{\partial{x_1}\partial{x_2}}\Big|_{X{(0)}} \triangle x_1 \triangle x_2
• \frac{\partial 2{f}}{\partial{x_22}}\Big|_{X^{(0)}} \triangle x_2^2 \bigg]
• ...

f(X) = f(X^{(0)}) + \bigg [ \frac{\partial f}{\partial x_1} + \frac{\partial f}{\partial x_2} \bigg ] \bigg|{X^{(0)}} \begin{pmatrix} \triangle x_1 \ \triangle x_2 \end{pmatrix} + \frac{1}{2} (\triangle x_1 , \triangle x_2) \begin{pmatrix} \frac{\partial ^2f}{\partial x_1^2} & \frac{\partial ^2f}{\partial x_1 \partial x_2} \ \frac{\partial ^2f}{\partial x_2 \partial x_1} & \frac{\partial ^2f}{\partial x_2^2} \end{pmatrix} \bigg |{X^{(0)}} \begin{pmatrix} \triangle x_1 \ \triangle x_2 \end{pmatrix}

• ...

f(X) = f(X^{(0)}) + \triangledown f(X{(0)})T \triangle X + \frac{1}{2} \triangle X^T H(X^{(0)}) \triangle X + ... $$ 其中

即二元函数

在

点处的海森矩阵，即二阶偏导数组成的方阵；

是函数在该点处的梯度。

牛顿法

考虑无约束最优化问题：

1.首先讨论单自变量情况

假设

具有二阶连续导数，运用迭代的思想，我们假设第

次迭代值为

， 将

进行二阶泰勒展开：

其中

是

的高阶无穷小，也叫做泰勒余项。

由于二阶可导，函数

有极值的必要条件是极值点处一阶导数为0，令

为0解出

：

至此，当数列满足收敛条件时我们可以构造一个初始值

和上述递推公式得到一个数列

不停地逼近极小值点

2.多自变量的情况

按照前面海森矩阵的介绍，在多自变量情况下，二阶泰勒展开式可写为：

函数

极值必要条件要求它必须是

的驻点，即：

由于

和

分别表示函数

的梯度和海森矩阵取值为

的实值向量和实值矩阵，我们分别将其记为

和

，根据驻点解出

：

同样我们可以构造一个迭代数列不停地去逼近函数的最小值点。

拟牛顿法

在牛顿法的迭代过程中，需要计算海森矩阵

，一方面有计算量大的问题，另一方面当海森矩阵非正定时牛顿法也会失效，因此我们考虑用一个

阶矩阵

来近似替代

`。

1.拟牛顿条件

根据前面的迭代式子：

取

， 我们可以得到：

记

,

，那么可以得到：

或

上述两个式子就是拟牛顿条件。

2.常见的拟牛顿法

根据拟牛顿条件，我们可以构造不同的

，这里仅列出常用的几种拟牛顿法，可根据需要再学习具体实现。

• DFP算法（Davidon-Fletcher-Powell）
• BFGS算法（Broydeb-Fletcher-Goldfarb-Shanno）
• Broyden类算法

Reference

[1] 统计学习方法