优化-7-高阶优化

高阶优化

在本章中，我们介绍一些利用高阶信息的优化方法。

牛顿法 Newton’s Method

在一阶优化的语境下，迭代式

$$x_{k+1} = x_k - \frac{1}{L} \nabla f(x_k)$$

实质上是最小化 Lipschitz 光滑性的上界，即

$$x_{k+1} = \arg \min_{x} f(x_k) + \nabla f(x_k)^T (x - x_k) + \frac{L}{2} \|x - x_k\|^2$$

其中二次项是一个在函数上处处相等的估计，这导致学习率是一个定值。但事实上目标函数光滑程度往往不是处处相等的，如果能用泰勒展开代替光滑性上界，就能得到一个更好的估计，这样我们就得到了牛顿法：

$$x_{k+1} = \arg \min_{x} f(x_k) + \nabla f(x_k)^T (x - x_k) + \frac{1}{2} (x - x_k)^T \nabla^2f(x_k) (x - x_k)$$

当 时，牛顿法的迭代式为

$$x_{k+1} = x_k - \left[\nabla^2f(x_k)\right]^{-1} \nabla f(x_k)$$

且有收敛性质如下：若 强凸且 可逆，则

$$\| x_{k+1} - x^* \|^2 \leq \frac{1}{2} \|x_k - x^*\|^2$$

共轭梯度法 Conjugate Gradient Method

在牛顿法中，为了计算 ，我们需要计算 的逆矩阵，求逆一个很昂贵的操作。共轭梯度法是另一种利用高阶信息的优化方法，相较于牛顿法，共轭梯度法无需计算矩阵的逆。

线搜法

要说明白共轭梯度法，我们首先要从其最基本的形式线搜法出发。线搜法是一类迭代方法，其迭代式为

$$x_{k+1} = x_k + \gamma_k p_k$$

其中向量 是搜索方向，标量 是步长。从一个初始位置 出发，每一步选择一个搜索方向，然后沿该方向走一步，不同的方法在 和 的选择上各有不同。不难看出，梯度下降法也是一种线搜法，其搜索方向为 ，步长为 。

共轭方向法

考虑一个极端的例子

$$f(x) = \frac{1}{2}x^T\begin{bmatrix}100 & 0 \\ 0 & 1\end{bmatrix}x$$

在第五章随机优化中，我们已经使用过了这个例子，在初始化不好的情况下，梯度下降法收敛将非常困难，可以使用 AdaGrad 算法可以对特征进行约束。

但对于这样不同特征间解耦非常好的目标，使用坐标下降法显然更为高效，在 和 方向上各下降一步即可。需要说明的是，坐标下降法同样也是一种线搜法。

对于上述的例子，其二次项系数为对角矩阵，因此有着天然的解耦性质，可以使用坐标下降法。但是对于更一般的情形，当二次项系数并非对角阵时，原先的正交基就不再适用，如下图所示（图源锦恢）：

考虑这样一个二次优化问题

$$f(x) = \frac{1}{2}x^T Q x$$

对于正定矩阵 ，如果有一对非 向量 满足

$$x_i^T Q x_j = 0$$

则称 为共轭方向。如果我们能找到这样一组 个互相共轭的共轭基 ，并在这组基上执行线搜法，我们就得到了共轭方向法。

二次型

考虑二次型目标函数

$$f(x) = \frac{1}{2}x^T Q x$$

对于正定矩阵 ，存在平方根 ，即 。对 进行特征分解，有

$$A = P^{-1} \Lambda P$$

由于 为正交矩阵，于是 存在逆矩阵

$$A^{-1} = P \Lambda^{-1} P^{-1}$$

将 代入 ，得到

$$f(A^{-1}) = \frac{1}{2} {A^{-1}}^T QA^{-1} = \frac{1}{2} A^{-1} QA^{-1} = \frac{1}{2} I$$

因此 的平方根 的逆 的各列之间关于 共轭，因此我们得到了 的共轭基为目标二次型的Hessian矩阵的平方根逆矩阵的列向量组。

一般情形

若目标函数为二次型，则其 Hessian 处处相等，因此可以直接得到这一组共轭基。但是对于更复杂的目标，使用函数某处的 Hessian 来近似整个函数的共轭基未免过于理想。因此，一般使用迭代的方法来获取下一个与当前搜索方向共轭的方向，而不是一次性获取完整的共轭基。

共轭梯度法是共轭方向法的一种良好实现，其主要特征在于使用梯度信息来获取共轭方向。其搜索方向的构造要求如下：

• 所有的搜索方向共轭
• 搜索方向 仅为梯度 和 的线性组合，即 $$d_k = -g_k + \alpha_{k-1}d_{k-1}$$

两边同乘 ，由共轭性质，有

$$d_{k-1}^T\nabla^2f(x_{k-1}) d_k = 0$$

即

$$-d_{k-1}^T\nabla^2f(x_{k-1})g_k + \alpha_{k-1}d_{k-1}^T\nabla^2f(x_{k-1})d_{k-1} = 0$$

整理得

$$\alpha_{k-1} = \frac{d_{k-1}^T\nabla^2f(x_{k-1})g_k}{d_{k-1}^T\nabla^2f(x_{k-1})d_{k-1}}$$

由于二阶导是梯度的变化率，因此

$$g_{k+1} - g_k = \nabla^2f(x_{k-1})(x_{k+1}-x_k) = \alpha_k \nabla^2f(x_{k-1})d_k$$

经整理可得

$$\alpha_{k-1} = \frac{g_{k-1}^Tg_{k-1}}{d_{k-1}^T\nabla^2f(x_{k-1})d_{k-1}}$$

因此可得共轭梯度法迭代式

$$\begin{cases} \alpha_{k} = \frac{g_{k}^Tg_{k}}{d_{k}^T\nabla^2f(x_k)d_{k}} \\ d_k = -g_k + \alpha_{k-1}d_{k-1} \\ x_{k+1} = x_k + \alpha_k d_k \end{cases}$$

拟牛顿法 Quasi-Newton Methods

Motivation

可以看到，在共轭梯度法中，虽然避免了计算 Hessian 矩阵的逆，但是仍然需要计算 Hessian 矩阵本身，这一操作依然非常耗时。拟牛顿法就是一种通过估计来近似计算 Hessian 矩阵（的逆）的方法，从而更高效的进行牛顿法。

一个直观的想法是，正如可以通过对函数值差分来获得梯度的近似，在方向 上的梯度值的近似为

$$\nabla f(x)^Tv \approx f(x+v)-f(x)$$

我们也可以通过对梯度差分来获得 Hessian 的近似，即

$$\nabla^2 f(x)s \approx \nabla f(x+v)-\nabla f(x)$$

拟牛顿条件

由牛顿法迭代式，有

$$g_{k+1} - g_k = \nabla^2f(x_k)(x_{k+1}-x_k)$$

记

$$y_k = g_{k+1} - g_k \\ s_k = x_{k+1} - x_k$$

对于近似 Hessian 矩阵 ，有

$$y_k = H_k s_k$$

DFP 算法

DFP 算法是一种求解这个近似矩阵的方法，其迭代式为

$$H_{k+1}^{-1} = H_k^{-1} + \frac{s_k s_k^T}{y_k^Ts_k} - \frac{G_k y_k y_k^T G_k}{y_k^T G_k y_k}$$

可以证明，若初始矩阵 为正定矩阵，则迭代过程中的每个 均为正定矩阵，一般初始值取 。

BFGS 算法

BFGS 迭代式为

$$H_{k+1} = H_k + \frac{y_k y_k^T}{y_k^Ts_k} - \frac{G_k s_k s_k^T G_k}{s_k^T G_k s_k}$$

可以证明，若初始矩阵 为正定矩阵，则迭代过程中的每个 均为正定矩阵，一般初始值取 。

Limited Memory BFGS

L-BFGS 算法是 BFGS 算法的一种改进，其主要思想是仅仅保存最近的 个 和 ，并且使用这些信息来近似 ，从而解决内存开销。Hessian 矩阵的存储开销会达到参数数量的平方级别，而 L-BFGS 算法的存储开销只有参数数量的线性级别，当参数数量很大时，Hessian 无法参数，只能在每轮迭代时使用历史信息重构 Hessian 矩阵。