统计机器学习-牛顿法

2020-06-16 本文已影响0人又双叒叕苟了一天

假设 $f(x)$ 是 $\textbf R^n$ 上具有二阶连续偏导数的函数，要求解的无约束最优化问题是
$\min_{x\in\textbf R^n}f(x)\tag1$
$x^*$ 表示目标函数 $f(x)$ 的极小点。

函数 $f(x)$ 有极值的必要条件是在极值点的一阶导数为0，特别是当海塞矩阵是正定矩阵时，函数 $f(x)$ 的极值为极小值。（因为当海塞矩阵是正定矩阵时函数为凸函数）

所以牛顿法的目标是通过迭代的方式找到一个 $x$ 的点使得
$\nabla f(x)=0\tag2$
假设在第 $k$ 次迭代时，找到的点是 $x^{(k)}$ ，让 $f(x)$ 在点 $x^{(k)}$ 附近进行二阶泰勒展开：
$f(x)=f(x^{(k)})+g_k^T(x-x^{(k)})+\frac12(x-x^{(k)})^TH(x^{(k)})(x-x^{(k)})\tag3$
其中 $g_k=g(x^{(k)})=\nabla f(x^{(k)})$ 是 $f(x)$ 在点 $x^{(k)}$ 的梯度， $H(x^{(k)})$ 是 $f(x)$ 的海塞矩阵（类似于二阶导数）在点 $x^{(k)}$ 的值：
$H(x)=\bigg[\frac{\partial^2f}{\partial x_i\partial x_j}\bigg]_{n\times n}\tag4$
假设在第 $k+1$ 次迭代时，找到的点是 $x^{(k+1)}$ ，满足(2)的要求，即：
$\nabla f(x^{(k+1)})=0\tag5$
公式(3)两边对 $x$ 求导：
$\nabla f(x)=g_k+H(x^{(k)})(x-x^{(k)})=g_k+H_k(x-x^{(k)})\tag6$
然后将点 $x^{(k+1)}$ 代入公式(6)并通过公式(5)得到：
$\nabla f(x^{(k+1)})=g_k+H(x^{(k)})(x^{(k+1)}-x^{(k)})=0\tag7$
所以
$x^{(k+1)}=x^{(k)}-H_k^{-1}g_k\tag8$
记
$H_kp_k=-g_k\tag9$
则公式(7)为
$x^{(k+1)}=x^{(k)}+p_k\tag{10}$
其中
$p_k=-H_k^{-1}g_k\tag{11}$
这样就得到了牛顿法的迭代方式，即公式(8)或公式(10)。