无约束优化

梯度下降、牛顿法和拟牛顿法

Posted by Xiaosheng on March 29, 2018

许多机器学习模型的训练过程就是在求解无约束最优化问题,梯度下降法 (gradient descent)、牛顿法 (Newton method) 和拟牛顿法 (quasi Newton method) 都是求解这类问题的常用方法。其中梯度下降法实现简单,而牛顿法和拟牛顿法收敛速度快。

1. 梯度下降法

假设 $f(\boldsymbol{x})$ 是 $\mathbb{R}^{n}$ 上具有一阶连续偏导数的函数。要求解的无约束最优化问题是

$\boldsymbol{x}^*$ 表示目标函数 $f(\boldsymbol{x})$ 的极小点。

梯度下降法是一种迭代算法,选取适当的初值 $\boldsymbol{x}^{(0)}$,不断迭代,更新 $\boldsymbol{x}$ 的值,进行目标函数的极小化,直至收敛。由于负梯度方向是使函数值下降最快的方向,在迭代的每一步,以负梯度方向更新 $\boldsymbol{x}$ 的值,从而达到减少函数值的目的。

由于 $f(\boldsymbol{x})$ 具有一阶连续偏导数,若第 $k$ 次迭代值为 $\boldsymbol{x}^{(k)}$,则可将 $f(\boldsymbol{x})$ 在 $\boldsymbol{x}^{(k)}$ 附近进行一阶泰勒展开:

为了满足 $f(\boldsymbol{x})<f(\boldsymbol{x}^{(k)})$,我们可以选择

即 $k+1$ 次迭代值 $\boldsymbol{x}^{(k+1)}$ 可以这样计算:

其中 $\lambda_k$ 是步长,可以设置为固定常数,也可以由一维搜索确定,即 $\lambda_k$ 使得

这就是梯度下降法。当目标函数为凸函数时,局部极小点就对应着函数的全局最小点,此时梯度下降法可确保收敛到全局最优解。

当目标函数 $f(\boldsymbol{x})$ 二阶连续可微时,可将 $(1.2)$ 替换为更精确的二阶泰勒展开式,这样就得到了牛顿法。但牛顿法使用了二阶导数 $\nabla^2f(\boldsymbol{x})$,其每轮迭代中涉及到海森矩阵的求逆,计算复杂度相当高,尤其在高维问题中几乎不可行,因此通过拟牛顿法以较低的计算代价寻找海森矩阵的近似逆矩阵。

2. 牛顿法

考虑无约束最优化问题

其中 $\boldsymbol{x}^*$ 为目标函数的极小点。

牛顿法的基本思想是:在现在极小点估计值附近对 $f(\boldsymbol{x})$ 做二阶泰勒展开,进而找到极小点的下一个估计值。假设 $f(\boldsymbol{x})$ 具有二阶连续偏导数,若第 $k$ 次迭代值为 $\boldsymbol{x}^{(k)}$,则可将 $f(\boldsymbol{x})$ 在 $\boldsymbol{x}^{(k)}$ 附近进行二阶泰勒展开:

这里,$g_k = \nabla f(\boldsymbol{x}^{(k)})$ 是 $f(\boldsymbol{x})$ 的梯度向量在点 $\boldsymbol{x}^{(k)}$ 的值,$H(\boldsymbol{x}^{(k)})$ 是 $f(\boldsymbol{x})$ 的海森矩阵 (Hesse matrix)

在点 $\boldsymbol{x}^{(k)}$ 的值。函数 $f(\boldsymbol{x})$ 有极值的必要条件是在极值点处一阶导数为 0,即梯度向量为 0。特别是当 $H(\boldsymbol{x}^{(k)})$ 是正定矩阵时,函数 $f(\boldsymbol{x})$ 的极值为极小值。

牛顿法利用极小点的必要条件

每次迭代中从点 $\boldsymbol{x}^{(k)}$ 开始,求目标函数的极小点,作为第 $k+1$ 次迭代值 $\boldsymbol{x}^{(k+1)}$。具体地,假设 $\boldsymbol{x}^{(k+1)}$ 满足:

由 $(2.2)$ 有

其中 $H_k = H(\boldsymbol{x}^{(k)})$。这样 $(2.5)$ 可以化为

因此

使用 $(2.8)$ 作为迭代公式的算法就是牛顿法。

3. 拟牛顿法

3.1 思路

但是在牛顿法的迭代中,需要计算海森矩阵的逆矩阵 $H^{-1}$,这一计算比较复杂,考虑用一个 $n$ 阶矩阵 $G$ 来近似代替 $H^{-1}$。这就是拟牛顿法的基本想法。

先看牛顿法迭代中海森矩阵 $H_k$ 满足的条件。类似于牛顿法,设经过 $K+1$ 次迭代后得到 $\boldsymbol{x}^{(k+1)}$,我们将 $f(\boldsymbol{x})$ 在 $\boldsymbol{x}^{(k+1)}$ 进行二阶泰勒展开:

于是可得

在 $(3.2)$ 中取 $\boldsymbol{x} = \boldsymbol{x}^{(k)}$,即得

记 $y_k = g_{k+1}-g_{k}$,$\delta_k = \boldsymbol{x}^{(k+1)} - \boldsymbol{x}^{(k)}$,则

式 $(3.4)$ 或 $(3.5)$ 称为拟牛顿条件。

拟牛顿法将 $G_{k+1}$ 作为 $H^{-1}_{k+1}$ 的近似,或者将 $B_{k+1}$ 作为 $H_{k+1}$,要求矩阵 $G_{k}$ 满足同样的条件。首先,每次迭代矩阵 $G_{k}$ 或者 $B_{k}$ 是正定的。同时类似 $(3.4)$ 和 $(3.5)$,$G_{k+1}$ 和 $B_{k+1}$ 满足下面的拟牛顿条件:

3.2 DFP 算法

DFP 是最早的拟牛顿法,该算法的核心是通过迭代的方法,对 $H^{-1}_{k+1}$ 做近似。迭代格式为:

其中 $P_{k},Q_{k}$ 是待定矩阵。这时,

为了使 $G_{k+1}$ 满足拟牛顿条件 $(3.6)$,可使 $P_{k}$ 和 $Q_{k}$ 满足:

事实上,不难找出这样的 $P_{k}$ 和 $Q_{k}$,例如取

这样就可得到矩阵 $G_{k+1}$ 的迭代公式:

称为 DFP 算法。可以证明,如果初始矩阵 $G_0$ 是正定的,则迭代过程中的每个矩阵 $G_k$ 都是正定的。

DFP 算法

输入:目标函数 $f(\boldsymbol{x})$,梯度 $g(\boldsymbol{x}) = \nabla f(\boldsymbol{x})$,精度要求 $\varepsilon$:

输出:$f(\boldsymbol{x})$ 的极小点 $\boldsymbol{x}^*$

(1) 选定初始点 $\boldsymbol{x}^{(0)}$,取 $G_0$ 为正定对称矩阵,置 $k=0$

(2) 计算 $g_k = g(\boldsymbol{x}^{(k)}$。若 $\Vert g_k \Vert < \varepsilon$,则停止计算,得近似解 $\boldsymbol{x}^*=\boldsymbol{x}^{(k)}$;否则转 (3)

(3) 置 $\boldsymbol{x}^{(k+1)} = \boldsymbol{x}^{(k)}-G_kg_k$

(4) 计算 $g_{k+1} = g(\boldsymbol{x}^{(k+1)})$,若 $\Vert g_{k+1}\Vert < \varepsilon$,则停止计算,得近似解 $\boldsymbol{x}^* = \boldsymbol{x}^{(k+1)}$;否则,按 $(3.14)$ 计算 $G_{k+1}$

(5) 置 $k=k+1$,转 $(3)$

3.3 BFGS 算法

BFGS 算法是最流行的拟牛顿算法。

可以考虑用 $G$ 逼近海森矩阵的逆矩阵 $H^{-1}$,也可以考虑用 $B$ 逼近海森矩阵 $H$。这时,相应的拟牛顿条件是 $(3.7)$。我们可以用同样地方法得到另一迭代公式。首先令

为了使 $B_{k+1}$ 满足拟牛顿条件 $(3.7)$,可使 $P_{k}$ 和 $Q_{k}$ 满足:

找出适合条件的 $P_k$ 和 $Q_k$,得到 BFGS 算法矩阵 $B_{k+1}$ 的迭代公式:

可以证明,如果初始矩阵 $B_0$ 是正定的,则迭代过程中的每个矩阵 $B_k$ 都是正定的。

BFGS 算法

输入:目标函数 $f(\boldsymbol{x})$,梯度 $g(\boldsymbol{x}) = \nabla f(\boldsymbol{x})$,精度要求 $\varepsilon$:

输出:$f(\boldsymbol{x})$ 的极小点 $\boldsymbol{x}^*$

(1) 选定初始点 $\boldsymbol{x}^{(0)}$,取 $B_0$ 为正定对称矩阵,置 $k=0$

(2) 计算 $g_k = g(\boldsymbol{x}^{(k)}$。若 $\Vert g_k \Vert < \varepsilon$,则停止计算,得近似解 $\boldsymbol{x}^*=\boldsymbol{x}^{(k)}$;否则转 (3)

(3) 置 $\boldsymbol{x}^{(k+1)} = \boldsymbol{x}^{(k)}-B^{-1}_kg_k$

(4) 计算 $g_{k+1} = g(\boldsymbol{x}^{(k+1)})$,若 $\Vert g_{k+1}\Vert < \varepsilon$,则停止计算,得近似解 $\boldsymbol{x}^* = \boldsymbol{x}^{(k+1)}$;否则,按 $(3.19)$ 计算 $B_{k+1}$

(5) 置 $k=k+1$,转 $(3)$

参考

peghoty《牛顿法与拟牛顿法学习笔记》
李航《统计学习方法》