二次 Sandwich 技巧：凸优化中的边界估计与收敛速率分析

在数值优化的实践中，一个反复出现的困惑是：为什么某些目标函数用梯度下降几步就能收敛，而另一些却陷入无尽的震荡？答案往往隐藏在函数的几何结构之中 —— 具体来说，是函数被 "夹" 在两个二次曲面之间的紧密程度。

从几何直觉到形式化定义

所谓 quadratic sandwich，是指当一个可微函数 $f: \mathbb {R}^n \to \mathbb {R}$ 同时满足两个关键性质时，它在任意点 $x$ 附近都被上下两个二次函数所约束。

μ- 强凸性 要求函数在任何点都向上弯曲，且曲率不低于 $\mu > 0$：

$$f(y) \geq f(x) + \langle \nabla f(x), y-x \rangle + \frac{\mu}{2}|y-x|^2$$

这意味着函数不能有任何 "平坦" 的方向 —— 即使梯度很小，你也能确定自己离最优解不远。相反，L - 光滑性（或 Lipschitz 连续梯度）则限制了函数弯曲的上限：

$$|\nabla f(x) - \nabla f(y)| \leq L|x-y|$$

由此可导出 descent lemma：$f (y) \leq f (x) + \langle \nabla f (x), y-x \rangle + \frac {L}{2}|y-x|^2$。

当这两个条件同时成立时，函数被 "夹" 在了一对曲率分别为 $\mu$ 和 $L$ 的抛物线之间 —— 这就是 quadratic sandwich 的几何本质。

条件数：问题难度的单一度量

Sandwich 的 "厚度" 由条件数 $\kappa = L/\mu$ 刻画。由于最大曲率不可能小于最小曲率，总有 $\kappa \geq 1$。

这个比值是判断优化问题难易程度的核心指标。当 $\kappa \approx 1$ 时，上下界几乎重合，函数接近于一个完美的二次碗，梯度下降只需一步即可到达最优解。但当 $\kappa$ 很大时，问题呈现出病态特征：某些方向的曲率极高（梯度变化剧烈），而另一些方向几乎平坦（梯度几乎不变）。此时，固定步长无法同时适应这两种极端情况 —— 在陡峭方向可能 overshoot，在平坦方向则进展缓慢。这正是梯度下降产生 zigzag 轨迹的根本原因。

从工程角度看，$\kappa$ 直接决定了收敛速率。对于强凸且光滑的函数，梯度下降的迭代误差以 $O ((1-1/\kappa)^k)$ 的速率衰减。条件数每增加一个数量级，达到相同精度所需的迭代次数可能成倍增长。

谱视角：Hessian 的特征值解读

若 $f$ 二阶可微，sandwich 条件可完全转化为对 Hessian 矩阵 $\nabla^2 f (x)$ 特征值的约束。设其特征值为 $0 \leq \lambda_1 (x) \leq \cdots \leq \lambda_n (x)$，则：

• 强凸性 $\Leftrightarrow$ $\lambda_1 (x) \geq \mu$（最小特征值有正下界）
• L - 光滑性 $\Leftrightarrow$ $\lambda_n (x) \leq L$（最大特征值有上界）

这意味着所有特征值都被限制在区间 $[\mu, L]$ 内。当 $\kappa$ 很大时，这个区间很宽，Hessian 的作用变得高度各向异性：沿某些特征方向向量被大幅拉伸，沿另一些方向则几乎不变。这种差异使得梯度（即 Hessian 作用于位移向量）无法准确指向最优解，导致优化路径的扭曲。

工程实践：无需计算特征值的验证技巧

在实际应用中，显式计算 Hessian 的特征值往往代价高昂。一个优雅的替代方案是将光滑性和强凸性的验证转化为对辅助函数凸性的判断：

• $f$ 是 $L$- 光滑 $\Leftrightarrow$ $g (x) = \frac {L}{2}|x|^2 - f (x)$ 是凸函数
• $f$ 是 $\mu$- 强凸 $\Leftrightarrow$ $h (x) = f (x) - \frac {\mu}{2}|x|^2$ 是凸函数

这一转换的数学基础在于：$\nabla^2 g (x) = LI - \nabla^2 f (x)$ 半正定当且仅当 $f$ 的所有特征值不超过 $L$。类似地，$h$ 的凸性对应着特征值的下界约束。

可落地的检查清单：

1. 问题建模阶段：尝试推导目标函数的 Hessian 或其上下界估计，初步判断 $\mu$ 和 $L$ 的量级
2. 算法选择阶段：若 $\kappa <10^3$，标准梯度下降配合适当步长通常足够；若 $10^3 < \kappa < 10^6$，考虑共轭梯度或预处理技术；若 $\kappa> 10^6$，必须引入二阶方法或自适应步长策略
3. 预处理设计：通过变量缩放或线性变换压缩 Hessian 的特征值分布范围，直接降低有效条件数
4. 收敛监控：跟踪梯度范数与迭代距离的比例关系，若该比例异常波动，可能暗示局部光滑性假设失效

边界缺失时的失效模式

理解 sandwich 的完整性对诊断优化失败至关重要。

失去强凸性（$\mu \to 0$）：条件数爆炸，梯度失去与距离的校准关系。典型例子是 L1 范数 $f (x) = |x|_1$，其梯度在几乎处处为 $\pm 1$，无法指示离最优解多远。此时最小值可能不唯一，或存在平坦的次优区域。

失去光滑性（$L \to \infty$）：Descent lemma 失效，solver 失去对步进后函数值的预测能力。考虑 $f (x) = -\ln (x)$，其二阶导数 $1/x^2$ 在接近原点时无界爆炸。在 $x=10$ 处曲率仅为 $0.01$，但在 $x=0.1$ 处激增至 $100$—— 为前者设计的步长在后者将导致灾难性 overshoot。

结语

Quadratic sandwich 不仅是一个优美的理论框架，更是连接凸分析几何与数值算法设计的桥梁。条件数 $\kappa = L/\mu$ 以单一标量概括了问题的本质难度，而谱分析则揭示了这种难度在方向上的分布特征。在实际工程中，与其盲目尝试不同的优化器，不如首先分析目标函数的 sandwich 结构 —— 这将为你选择步长策略、设计预处理方案乃至判断问题是否适定提供坚实的理论依据。

资料来源

• Federico Magnani, "The Quadratic Sandwich", 2026-04-08

systems