优化算法中的梯度下降法与"擦玻璃"之间的联想

Tri-StateTraveler / 2024-10-29 / 原文

考虑简单的无约束二次优化问题

\[\min_{x\in\mathbb{R}^{n}} f(x)=\frac{1}{2}x^{T}Ax \]

其中 $A\in\mathbb{R}^{n\times n}$ 是对称的正定矩阵。我们设 $g_{k}:=Ax_{k}$ 是 $f(x)$ 在迭代点 $x_{k}$ 处的梯度。由于这是一个严格凸的优化问题，其极值点就是全局最优点，记为 $x_{*}$。

为了求解上述问题

牛顿法的迭代格式：$$x_{k+1}=x_{k}+(\nabla^2 f(x_{k}))^{-1}(-g_{k})=x_{k}+A ^{-1}(-g_{k}),$$

其中 $\nabla^2 f(x_{k})$ 是 $f(x)$ 在迭代点 $x_{k}$ 处的 Hessian 矩阵。针对上述优化问题，牛顿法可以实现一步寻优。但是一般函数的 Hessian 难以得到。

梯度法的迭代格式：$$x_{k+1}=x_{k}+\frac{1}{\alpha_{k}}(-g_{k}),$$

其中 $\frac{1}{\alpha_{k}}$称为步长，$-g_{k}$ 为下降方向。
观察牛顿法与梯度法的形式，我们知道在一个好的梯度方法中，其标量 $\alpha_{k}$ 应该具备反映(或逼近) $A$ 的能力，也就是说 $\alpha_{k}$ 应该具有拟牛顿的性质。

最速下降方法： $\alpha_{k}^{SD}=\frac{g_{k}^{T}Ag_{k}}{g_{k}^{T}g_{k}},$

反映当前梯度 $g_{k}$ 关于 $A$ 的瑞丽商，$\alpha_{k}^{SD}$ 逼近 $A$ 的某一特征值，具有拟牛顿的性质。但是 $\alpha_{k}^{SD}$ 会使迭代点走"之字"步(zigzag)，($g_{k-1}$ 与 $g_{k}$ 相互正交)，造成最速下降法的收敛速度变慢，尤其受 $A$ 的条件数的影响。为了避免这种 "zigzag" 现象的发生，Barzilai-Borwein (BB) 采用下面的方法。

BB方法：

\[\alpha_{k}^{BB1}=\frac{g_{k-1}^{T}Ag_{k-1}}{g_{k-1}^{T}g_{k-1}}, \quad \alpha_{k}^{BB2}=\frac{g_{k-1}^{T}A^2g_{k-1}}{g_{k-1}^{T}Ag_{k-1}}, \]

这两者分别是下面最小二乘问题的解

\[\min_{\alpha}\|\alpha s_{k-1}-y_{k-1}\|_{2}^{2},\quad \min_{\alpha}\|s_{k-1}-\frac{1}{\alpha}y_{k-1}\|_{2}^{2} \]

其中 $s_{k-1}:=x_{k}-x_{k-1}$, $y_{k-1}:=g_{k}-g_{k-1}$，且有 $y_{k-1}=As_{k-1}$。值得注意的是：最速下降法是单调的，而BB方法是非单调的。我们可以看到在最小二乘意义下，$\alpha_{k}^{BB}$ 也具有拟牛顿的性质。(梯度之差与位置之差的比，这就是在反映二阶信息！) 对比最速下降法与BB方法，BB1步长相当于最速下降步的向后一步延迟。(学长把学妹，一般比较好？) 在实践中，相比最速下降法，BB的数值表现非常卓越。并且由于其简单的操作，其受到了优化界的广泛关注。

下面集中考察 BB 方法。首先观察下面的一系列不等式(由柯西-施瓦茨不等式得到)：

\[\frac{g_{k-1}^{T}Ag_{k-1}}{g_{k-1}^{T}g_{k-1}}\le\frac{g_{k-1}^{T}A^2g_{k-1}}{g_{k-1}^{T}Ag_{k-1}}\le\ldots\le\frac{g_{k-1}^{T}A^ng_{k-1}}{g_{k-1}^{T}A^{n-1}g_{k-1}}. \]

前两个不等式等价于

\[\alpha_{k}^{BB1}\le\alpha_{k}^{BB2}. \]

由此，我们可以看到在众多的拟牛顿(BB类)步长中，$\alpha_{k}^{BB1}$ 是最小的那个。数值实验也验证了这一点，小的 $\alpha_{k}^{BB1}$ 产生大的步长。如果待优化的问题的条件比较良好，这种大步长会使迭代点快速收敛到最优解 $x_{*}$。对应地，$\alpha_{k}^{BB2}$ 的收敛速度可能相对慢些。如果待优化的问题的条件比较差，$\alpha_{k}^{BB1}$ 对应的大步长可能影响算法的收敛速度(在坏条件下，大步长可能会产生更加剧烈的非单调现象)，下面我们进行简单地分析这种现象。

在梯度法中，我们的目标是消去梯度的元素，直到达到最优性条件

\[\|g_{k}\|_{2}^{2}=0\iff g_{k}^{i}=0, \quad \text{for}\quad i=1,2,\dots,n \]

在 BB 方法中，由迭代格式，我们知道

\[\|g_{k+1}\|_{2}^{2}\le\|I-\frac{1}{\alpha_{k}^{BB}}A\|\|g_{k}\|_{2}^{2}\tag{1} \]

从上面的关系可以看到，如果 $\alpha_{k}^{BB}$ 逼近 $A$ 的最大特征值，那么梯度长度就会下降；如果 $\alpha_{k}^{BB}$ 逼近 $A$ 的最小特征值，那么梯度长度可能会上升。

$\alpha_{k}^{BB}$ 的大小与梯度长度下降和上升的关系，重要的前提是梯度的分量都在同一个数量级(*)。

由于 $A$ 是对称正定的，所以一定可以对角化，不妨设 $$A=\text{diag}(\lambda_1,\ldots,\lambda_{n}),$$
其中 $0<\lambda_1<\ldots<\lambda_n$。则 $\alpha_{k}^{BB}\in[\lambda_{1}, \lambda_{n}]$。结合 $(1)$，我们可以知道 $g_{k}^{1}$ 是一直单调下降的，但是 $g_{k}^{j}$, $2<j<n$ 可能在某些时候是非单调的。如果 $\alpha_{k}^{BB}$ 在上一次迭代靠近 $\lambda_n$ ($g_{k}$ 的第 $n$ 个分量以及其附近分量的元素下降)，而在当前迭代一下子远离了 $\lambda_{n}$(向 $\lambda_{1}$ 靠近)，由 $(1)$，我们知道：这种情况极有可能会使得 $g_{k}$ 的第 $n$ 个分量以及其附近分量的元素又重新变大，也就是说如果 $\alpha_{k}^{BB}$ 在连续迭代中的变化幅度很大(从大突然变到一个不合理的小)，就会使得前后的效果相互抵消。由于$\alpha_{k}^{BB1}$ 总是倾向于产生较小的值，所以刚刚描述的现象，在 $\alpha_{k}^{BB1}$ 中极有可能发生。

注意：这里不是不允许 $\alpha_{k}^{BB}$ 靠近 $\lambda_{1}$，而是希望连续的迭代中 $\alpha_{k}^{BB}$ 最好不要跳跃太大。

如何避免这种现象的发生呢？
我的答案是：控制连续迭代中，$\alpha_{k}^{BB}$ 的变化幅度。如果 $\alpha_{k}^{BB}$ 在上一次迭代靠近 $\lambda_n$ ($g_{k}$ 的第 $n$ 个分量以及其附近分量的元素下降)，那么在当前迭代，我们应该尽量控制 $\alpha_{k}^{BB}$ 仍然在 $\lambda_n$ 附近，直到 $g_{k}$ 的第 $n$ 个分量以及其附近分量的元素消失殆尽，可以忽略了，这一局部任务可以认为完成了。(此时，这些分量的元素与 $g_{k}$前面分量元素的数量级就不在同一个数量级)。下一步的局部任务是消去 $g_{k}$ 的剩余分量。仍然采用这种局部打法。(彻底打扫完一处战场，才能转移到下一处战场进行打扫。) 我想这就是 $ABBmin$ 方法显著优于 BB 方法的通俗解释。$ABBmin$ 方法的形式如下：

\[\begin{equation} \alpha_{k}^{ABBmin}=\left\{ \begin{array}{ll} \max_{j_0\le j\le k}\{\alpha_{j}^{BB2}\}, & \alpha_{k}^{BB1}/\alpha_{k}^{BB2}<\gamma, \\ \alpha_{j}^{BB1}, & otherwise, \end{array}\right.\tag{2} \end{equation} \]

其中 $\gamma\in (0,1)$，$j_{0}=\max(k-M,1)$, $M$ 是参数。该策略表示，当阈值条件满足时，在当前代 $k$ 以及其往前数 $M$ 代中，选出最大的 $\alpha_{j}^{BB2}$。
公式 $(2)$ 中的阈值 $\alpha_{k}^{BB1}/\alpha_{k}^{BB2}<\gamma$ 的情形就是表示，要把 $g_{k}$ 的当前分量元素彻底消完(局部任务干完、干好)；当阈值条件不满足了，说明当前分量元素已经消完(局部任务干好了)，可以转移到其他任务--消灭 $g_{k}$ 的剩余分量元素。由于 $\alpha_{k}^{BB1}$ 倾向于逼近 $\lambda_{1}$ (朝 $\lambda_{1}$ 方向跑，这也是转移阵地的动力来源吧！) 当 $\alpha_{k}^{BB1}$ 跑到一个新位置后，局部地消灭对应的 $g_{k}$ 的分量元素，也就是 (2) 中 $ABBmin$ 的策略。直到最后，$g_{k}$ 只剩下 $g_{k}^{1}$ 分量附近的元素还未消失，当 $\alpha_{k}^{BB1}$ 再次逼近 $\lambda_{1}$ 时，采用局部消去策略，很快就把剩余的梯度分量消除了。达到最优性条件。