同梯度下降法一样,牛顿法和拟牛顿法也是求解无约束最优化问题的常用方法。牛顿法本身属于迭代算法,每一步需要求解目标函数的海赛矩阵的逆矩阵,计算比较复杂。拟牛顿法通过正定矩阵近似海赛矩阵的逆矩阵或海赛矩阵,简化了这一计算过程。
当
在
处具有
阶连续导数,我们可以用
的
次多项式逼近函数
公式:
其中
表示泰勒余项,它是
的高阶无穷小。
Hessian Matrix
,是一个多元函数的二阶偏导数构成的方阵,描述了函数的局部曲率
以二元函数
为例,它在
点处的泰勒展开式为: $$ f(x_1,x_2) = f(x_1{(0)},x_2{(0)})
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 + ... $$ 其中
即二元函数
在
点处的海森矩阵,即二阶偏导数组成的方阵;
是函数在该点处的梯度。
考虑无约束最优化问题:
假设
具有二阶连续导数,运用迭代的思想,我们假设第
次迭代值为
, 将
进行二阶泰勒展开:
其中
是
的高阶无穷小,也叫做泰勒余项。
由于二阶可导,函数
有极值的必要条件是极值点处一阶导数为0,令
为0解出
:
至此,当数列满足收敛条件时我们可以构造一个初始值
和上述递推公式得到一个数列
不停地逼近极小值点
按照前面海森矩阵的介绍,在多自变量情况下,二阶泰勒展开式可写为:
函数
极值必要条件要求它必须是
的驻点,即:
由于
和
分别表示函数
的梯度和海森矩阵取值为
的实值向量和实值矩阵,我们分别将其记为
和
,根据驻点解出
:
同样我们可以构造一个迭代数列不停地去逼近函数的最小值点。
在牛顿法的迭代过程中,需要计算海森矩阵
,一方面有计算量大的问题,另一方面当海森矩阵非正定时牛顿法也会失效,因此我们考虑用一个
阶矩阵
来近似替代
`。
根据前面的迭代式子:
取
, 我们可以得到:
记
,
,那么可以得到:
或
上述两个式子就是拟牛顿条件。
根据拟牛顿条件,我们可以构造不同的
,这里仅列出常用的几种拟牛顿法,可根据需要再学习具体实现。
[1] 统计学习方法