统计机器学习-拟牛顿法

作者: 又双叒叕苟了一天 | 来源:发表于2020-06-16 18:04 被阅读0次

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

在牛顿法的迭代中，需要计算海塞矩阵的逆矩阵 $H^{-1}$ ，这一计算比较复杂，考虑用一个 $n$ 阶矩阵 $G_k=G(x^{(k)})$ 来近似代替 $H_k^{-1}=H^{-1}(x^{(k)})$ 。这就是拟牛顿法的基本想法。

假设在第 $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)})\tag2$
其中 $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}\tag3$
公式(2)两边对 $x$ 求导：
$\nabla f(x)=g_k+H(x^{(k)})(x-x^{(k)})=g_k+H_k(x-x^{(k)})\tag4$
将点 $x^{(k+1)}$ 代入公式(4)得到：
$g_{k+1}=\nabla f(x^{(k+1)})=g_k+H_k(x^{(k+1)}-x^{(k)})\tag5$
所以
$g_{k+1}-g_k=H_k(x^{(k+1)}-x^{(k)})\tag6$
记 $y_k=g_{k+1}-g_k$ ， $\delta_k=x^{(k+1)}-x^{(k)}$ ，则
$y_k=H_k\delta_k\tag7$
或者说
$H_k^{-1}y_k=\delta_k\tag8$
公式(7)或公式(8)叫做拟牛顿条件。

如果 $H_k$ 是正定的（ $H_k^{-1}$ 也是正定的），那么可以保证牛顿法搜索方向 $p_k=-H_k^{-1}g_k$ 是下降方向。对公式(2)只展开到1阶：
$f(x)=f(x^{(k)})+g_k^T(x-x^{(k)})\tag9$
而 $x$ 的更新公式为：
$x=x^{(k)}-\lambda H_k^{-1}g_k\tag{10}$
将(10)中的 $x$ 代入(9)得到：
$f(x)=f(x^{(k)})+g_k^T(x^{(k)}-x^{(k)}-\lambda H_k^{-1}g_k)=f(x^{(k)})-\lambda g_k^TH_k^{-1}g_k\tag{11}$
因为 $H_k^{-1}$ 正定，所以 $g_k^TH_k^{-1}g_k\gt0$ 。当 $\lambda$ 为一个充分小的正数时，总有 $f(x)\lt f(x^{(k)})$ ，也就是说 $p_k$ 是下降方向。

综上所述，拟牛顿法使用 $G_k$ 近似 $H_k^{-1}$ （DFP算法）或者使用 $B_k$ （BFGS算法）近似 $H_k$ ，需要满足满足两个条件：

$G_k$ 或 $B_k$ 正定
满足拟牛顿条件，即 $G_{k+1}y_k=\delta_k$ 或 $y_k=B_{k+1}\delta_k$

$G_k$ 或 $B_k$ 通过迭代的方式进行更新，即 $G_{k+1}=G_k+\Delta G_k$ 或 $B_{k+1}=B_k+\Delta B_k$ 。

DFP算法

DFP算法使用 $G_k$ 近似 $H_k^{-1}$ ，需要满足拟牛顿条件 $G_{k+1}y_k=\delta_k$ ， $G_k$ 通过 $G_{k+1}=G_k+\Delta G_k$ 迭代更新。

使
$\Delta G_k=P_k+Q_k\tag{12}$
即
$G_{k+1}=G_k+P_k+Q_k\tag{13}$
公式(13)两边乘上 $y_k$
$G_{k+1}y_k=G_ky_k+P_ky_k+Q_ky_k\tag{14}$
令
$Q_ky_k=-G_ky_k\tag{15}$

$P_ky_k=\delta_k\tag{16}$

则公式(14)为
$G_{k+1}y_k=\delta_k\tag{17}$
满足拟牛顿条件，也不难找出满足条件(15)和(16)的 $P_k$ 和 $Q_k$ ：
$P_k=\frac{\delta_k\delta_k^T}{\delta_k^Ty_k}\tag{18}$

$Q_k=-\frac{G_ky_ky_k^TG_k}{y_k^TG_ky_k}\tag{19}$

于是得到矩阵 $G_{k+1}$ 的迭代公式：
$G_{k+1}=G_k+\frac{\delta_k\delta_k^T}{\delta_k^Ty_k}-\frac{G_ky_ky_k^TG_k}{y_k^TG_ky_k}\tag{20}$

算法

输入：目标函数 $f(x)$ ，梯度 $g(x)=\nabla f(x)$ ，精度要求 $\varepsilon$ ；

输出： $f(x)$ 的极小点 $x^*$ 。

选定初始点 $x^{(0)}$ ，取 $G_0$ 为正定对称矩阵，置 $k=0$
计算 $g_k=g(x^{(k)})$ 。若 $||g_k||\lt\varepsilon$ ，则停止计算，得近似解 $x^*=x^{(k)}$ ；否则转(3)
置 $p_k=-G_kg_k$
一维搜索，求 $\lambda_k$ 使得

$f(x^{(k)}+\lambda_kp_k)=\min_{\lambda\geq0}f(x^{(k)}+\lambda p_k)$

置 $x^{(k+1)}=x^{(k)}+\lambda_kp_k$
计算 $g_{k+1}=g(x^{(k+1)})$ ，若 $||g_{k+1}||\lt\varepsilon$ ，则停止计算，得近似解 $x^*=x^{(k+1)}$ ；否则按公式(20)算出 $G_{k+1}$
置 $k=k+1$ ，转(3)

BFGS算法

DFP算法使用 $B_k$ 近似 $H_k^{-1}$ ，需要满足拟牛顿条件 $y_k=B_{k+1}\delta_k$ ， $B_k$ 通过 $B_{k+1}=B_k+\Delta B_k$ 迭代更新。

使
$\Delta B_k=P_k+Q_k\tag{21}$
即
$B_{k+1}=B_k+P_k+Q_k\tag{22}$
公式(22)两边乘上 $\delta_k$
$B_{k+1}\delta_k=B_k\delta_k+P_k\delta_k+Q_k\delta_k\tag{23}$
令
$Q_k\delta_k=-B_k\delta_k\tag{24}$

$P_k\delta_k=y_k\tag{25}$

则公式(23)为
$B_{k+1}\delta_k=y_k\tag{26}$
满足拟牛顿条件，也不难找出满足条件(24)和(25)的 $P_k$ 和 $Q_k$ ：
$P_k=\frac{y_ky_k^T}{y_k^T\delta_k}\tag{27}$

$Q_k=-\frac{B_k\delta_k\delta_k^TB_k}{\delta_k^TB_k\delta_k}\tag{28}$

于是得到矩阵 $G_{k+1}$ 的迭代公式：
$G_{k+1}=G_k+\frac{y_ky_k^T}{y_k^T\delta_k}-\frac{B_k\delta_k\delta_k^TB_k}{\delta_k^TB_k\delta_k}\tag{29}$

算法

输入：目标函数 $f(x)$ ，梯度 $g(x)=\nabla f(x)$ ，精度要求 $\varepsilon$ ；

输出： $f(x)$ 的极小点 $x^*$ 。

选定初始点 $x^{(0)}$ ，取 $B_0$ 为正定对称矩阵，置 $k=0$
计算 $g_k=g(x^{(k)})$ 。若 $||g_k||\lt\varepsilon$ ，则停止计算，得近似解 $x^*=x^{(k)}$ ；否则转(3)
置 $p_k=-B_k^{-1}g_k$
一维搜索，求 $\lambda_k$ 使得

$f(x^{(k)}+\lambda_kp_k)=\min_{\lambda\geq0}f(x^{(k)}+\lambda p_k)$

置
1. 计算 $g_{k+1}=g(x^{(k+1)})$ ，若 $||g_{k+1}||\lt\varepsilon$ ，则停止计算，得近似解 $x^*=x^{(k+1)}$ ；否则按公式(29)算出 $B_{k+1}$
置 $k=k+1$ ，转(3)

统计机器学习-拟牛顿法

DFP算法

算法

BFGS算法

算法

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读