机器学习数学推导（四）：凸优化理论

本章概览

1947 年，George Dantzig 提出了线性规划的单纯形法，现代优化理论从此正式登场。八十年过去，优化已经成为机器学习的发动机：你训练过的每一个模型——从一行代码的线性回归，到 700 亿参数的语言模型——本质上都是某个优化问题的解。

而在所有优化问题中，凸优化享有特殊地位：它的定义性质强到让人觉得"作弊"——任何局部最优解必定是全局最优解，并且有一整套理论清晰、收敛性可证的算法可以高效求解。我们之所以把"凸"看作绿灯，把"非凸"看作黄灯，根源就在这一条。

本章自底向上搭建凸优化的工具箱：先讲几何（凸集、凸函数、Jensen 不等式），再补微积分（次梯度，处理不可微情形），最后推导算法——梯度下降、Nesterov 加速、Adam、牛顿法、BFGS，处理约束的 KKT 条件，以及把可分结构问题拆开来解的 ADMM。

你将学到：

1. 凸集与凸函数——几何定义、一阶/二阶判别条件、Jensen 不等式
2. 次梯度——把微积分推广到不可微目标（如 L1 范数）
3. 一阶方法——梯度下降、动量、Nesterov、Adam，以及背后的收敛速率
4. 二阶方法——牛顿法和 BFGS，理解"代价 vs 收敛速度"的权衡
5. 约束优化——拉格朗日函数、弱/强对偶性、KKT 条件
6. ADMM——把一个棘手的联合问题拆成两个易解的交替子问题

先修知识： 多元微积分（梯度、Hessian、泰勒展开）、线性代数（特征值、半正定矩阵）。本系列前三篇覆盖了这些。

1. 凸集与凸函数

1.1 凸集

定义 1（凸集）。集合 $C \subseteq \mathbb{R}^n$ 是凸集，如果对任意 $x, y \in C$ 和任意 $\lambda \in [0, 1]$，

通俗地说：凸集中任意两点连成的线段始终在集合内部。没有凹陷，没有缺口，没有断开。下图把这件事画得很直白——凸集里的弦永远不会越界，非凸集里的弦却可能直接穿过空隙跑出去。

几个会反复出现的凸集：

• 超平面 $\{x : a^T x = b\}$ 与半空间 $\{x : a^T x \leq b\}$——线性约束问题的基本砖块。
• 范数球 $\{x : \|x\| \leq r\}$，对任何范数都成立。L2 球是标准的圆球；L1 球是稀疏性背后那个出名的菱形。
• 椭球 $\{x : (x - x_0)^T A (x - x_0) \leq 1\}$（要求 $A \succ 0$）。
• 多面体——有限个半空间的交集，正是线性规划的可行域。

定理 1（交集仍为凸）。任意一族凸集的交集 $\bigcap_i C_i$ 仍是凸集。

证明：若 $x, y$ 都属于每个 $C_i$，由凸性 $\lambda x + (1-\lambda) y$ 也属于每个 $C_i$，因此属于它们的交集。$\square$

这一条看似平凡，却是凸建模的主力——再复杂的可行域，几乎都是用一堆简单的凸约束相交搭出来的。

1.2 凸函数

定义 2（凸函数）。$f : C \to \mathbb{R}$ 是凸函数，如果定义域 $C$ 是凸集，且对所有 $x, y \in C$、$\lambda \in [0, 1]$，

几何上，函数图像上任意两点连成的弦，始终落在图像之上（或与图像相切）。下图左边那个碗形曲面是凸的，右边的"鸡蛋盒"则不是。这点差别后果非常严重：凸碗只有唯一的极小点，任何下降算法都能找到它；非凸的鸡蛋盒里到处是局部最小点，下降算法极易困死在某个浅坑里。

凸性的两个常用强化版本，值得单独记住：

• 严格凸：当 $x \neq y$ 且 $\lambda \in (0, 1)$ 时，(2) 取严格不等号。这排除了水平台地，并保证（如果有最小点）唯一最小点。
• $\mu$-强凸（$\mu > 0$）：$f(x) - \tfrac{\mu}{2}\|x\|^2$ 仍然是凸函数。等价地说，$f$ 在每个方向上至少有二次曲率。强凸性是后面线性收敛速率的根源。

1.3 一阶与二阶判别条件

定义 2 几何上很干净，但实际操作时难验证。下面两个等价条件用的是导数，是真正在用的判别工具。

定理 2（一阶条件）。若 $f$ 可微，则 $f$ 凸当且仅当对所有 $x, y$，

换句话说，每条切平面都是 $f$ 的全局下界。这条性质是凸问题上梯度下降"能管用"的真正原因：线性近似 $f(x) + \nabla f(x)^T (y - x)$ 永不高估 $f$，所以沿负梯度走小步一定让 $f$ 下降——前提是步长足够小。

定理 3（二阶条件）。若 $f$ 二阶可微，则 $f$ 凸当且仅当 Hessian 处处半正定：

如果 $\nabla^2 f \succ 0$ 处处成立，则 $f$ 严格凸；如果 $\nabla^2 f \succeq \mu I$ 处处成立，则 $f$ 是 $\mu$-强凸的。Hessian 检验是实践中最常用的凸性证明手段——例如线性回归的 Hessian 就是 $X^T X$，自动半正定。

1.4 Jensen 不等式

凸性不等式 (2) 是关于"两点平均"的论断。把它推广到任意概率分布上，就得到了机器学习里使用频率最高的不等式之一。

定理 4（Jensen 不等式）。设 $f$ 是凸函数，$X$ 是可积随机变量，则

若 $f$ 严格凸且 $X$ 不退化，则不等式严格成立。

证明思路（离散）：对取值 $x_1, \ldots, x_n$、概率 $p_1, \ldots, p_n$ 的随机变量，反复套用定义 2 的弦不等式作归纳即可：$f(\sum p_i x_i) \leq \sum p_i f(x_i)$。连续情形通过逼近得证。$\square$

Jensen 撑起了大量后续理论，本系列里至少会再见到它两次：

• KL 散度的非负性：取 $-\log$（凸），有 $D_{KL}(p \| q) = \mathbb{E}_p[-\log(q/p)] \geq -\log \mathbb{E}_p[q/p] = 0$。
• 变分推断中的 ELBO：对数边缘 $\log p(x)$ 由 $\mathbb{E}_q[\log p(x, z) - \log q(z)]$ 从下方界定，正是 Jensen 应用在 $\log$ 上。

值得背下来的常见凸函数：仿射 $a^T x + b$（既凸又凹）；指数 $e^{ax}$；所有范数 $\|x\|$；负熵 $x \log x$（$x > 0$）；平方损失 $\tfrac{1}{2}\|x\|^2$；以及 softmax 背后的 log-sum-exp $\log \sum_i e^{x_i}$。

2. 次梯度与非光滑优化

机器学习里最有用的目标函数中，有不少根本不是处处可微：Lasso 中的 $\|x\|_1$ 在每个坐标轴上有折点；SVM 的 hinge 损失 $\max(0, 1 - y \cdot s)$ 也是分段线性的。要在这些对象上做"微积分"，就得把梯度推广开。

2.1 次梯度

定义 3（次梯度）。向量 $g \in \mathbb{R}^n$ 是 $f$ 在 $x$ 处的次梯度，如果对所有 $y$，

所有这样的 $g$ 组成的集合叫次微分，记作 $\partial f(x)$。当 $f$ 在 $x$ 处可微时，$\partial f(x) = \{\nabla f(x)\}$，只有一个元素。在不可微点上，次微分通常是一个非平凡集合，包含了"所有在该点与 $f$ 相切的合法线性下界"。

例（绝对值）。对 $f(x) = |x|$，

最优性：凸函数 $f$ 的全局最小点 $x^\star$ 当且仅当 $0 \in \partial f(x^\star)$。这是 $\nabla f(x^\star) = 0$ 在不可微情形下的对应。

2.2 次梯度法

把梯度替换成任一次梯度，就得到次梯度法：

一个微妙但要紧的点：次梯度不一定是下降方向——单步可能让函数值上升。为了保证收敛，步长必须递减，例如 $\alpha_k = 1/\sqrt{k}$。代价就是收敛速率从光滑情形的 $O(1/k)$ 退到 $O(1/\sqrt{k})$。

对于"光滑+非光滑"形式的复合问题 $f(x) + h(x)$（Lasso 正是如此），近端梯度法通过对 $h$ 调用其近端算子精确处理，可以把速率拉回光滑情形的 $O(1/k)$。

3. 一阶优化算法

3.1 梯度下降

梯度下降是连续优化里最基础的算法：每一步沿着局部最陡下降方向走。

它为什么管用？根源就是一阶条件 (3)：在凸函数上，负梯度真的是下降方向，而且线性近似从不高估 $f$，所以只要步长不太离谱，就不会"冲过头"。下图把这点在二维上画了出来——凸面上是一条干净单调的下降轨迹，非凸面上则被钉死在了一个局部最小点上。

定理 5（凸+光滑情形）。设 $f$ 凸且其梯度 $L$-Lipschitz 连续（即 $\|\nabla f(x) - \nabla f(y)\| \leq L \|x - y\|$），取固定步长 $\alpha = 1/L$，则

证明思路：Lipschitz 梯度等价于"下降不等式" $f(y) \leq f(x) + \nabla f(x)^T(y - x) + \tfrac{L}{2}\|y - x\|^2$。代入 $y = x - \tfrac{1}{L}\nabla f(x)$，再结合一阶凸性 (3)，对 $k$ 步望远求和即得 (10)。$\square$

定理 6（强凸情形）。若 $f$ 还满足 $\mu$-强凸性，则

这是线性收敛：每步误差按固定比例缩小。比例由条件数 $\kappa = L / \mu$ 决定。条件数接近 1 时几步就收敛，条件数到 $10^6$ 量级就要算上百万步。改善条件数——通过预条件化、归一化或正则化——是优化里最实用的工程技巧之一。

3.2 学习率：你必须做的一个选择

梯度下降只有一个旋钮：步长 $\alpha$。在同一个凸二次函数上，三种典型选择会讲出三个完全不同的故事。

对一维二次 $f(x) = \tfrac{L}{2} x^2$ 算下来，更新公式是 $x^{(k+1)} = (1 - \alpha L) x^{(k)}$，画面瞬间清晰：

• $0 < \alpha < 1/L$：单调收敛，但步子太小，要走很多步。
• $\alpha = 1/L$：一维上单步就能跳到最优点。
• $1/L < \alpha < 2/L$：仍然收敛，但跨过最优点来回振荡。
• $\alpha > 2/L$：$|1 - \alpha L| > 1$，迭代被放大，发散。

到了高维，把 $L$ 换成最大 Hessian 特征值，结论一样。这是关于梯度下降最该铭记的一条工程事实：正确的学习率由曲率决定，不能凭感觉。

3.3 动量法与 Nesterov 加速

在又长又窄的"峡谷"地形上，梯度下降会左右撞墙，而不是沿着谷底前进。动量法通过累积历史梯度，抑制这种横向摇摆，并在一致方向上积攒速度。

Heavy ball（Polyak, 1964）：

Nesterov 加速梯度（NAG）：在"动量将带你去到的"前瞻点处计算梯度，

定理 7（Nesterov 加速收敛）。对 $L$-光滑凸函数，

(14) 可证最优：在最坏情况下，任何只查询 $\nabla f$ 的一阶方法都不可能渐近地比这更快。这是凸优化里少有的几条"惊喜"之一——一个看起来微小的改动（先前瞻、再走步），就把速率从 $O(1/k)$ 提到 $O(1/k^2)$，而且不需要付出额外计算成本。

3.4 自适应学习率与 Adam

朴素梯度下降对所有坐标用同一个步长。但实际中，不同坐标的有效曲率可能差好几个数量级——例如文本模型里，常见词嵌入每步都收到大量梯度，而生僻词嵌入几乎没有。自适应方法给每个坐标自己的学习率，按其近期梯度幅度缩放。

Adam 把两个想法揉到一起：动量风格的一阶矩，以及 RMSProp 风格的自适应二阶矩。

其中 $\hat m^{(k+1)} = m^{(k+1)} / (1 - \beta_1^{k+1})$，$\hat v^{(k+1)} = v^{(k+1)} / (1 - \beta_2^{k+1})$ 是偏差修正后的估计。标准超参 $(\beta_1, \beta_2, \alpha, \varepsilon) = (0.9, 0.999, 10^{-3}, 10^{-8})$ 在深度学习的各种任务上都意外地好用，这正是 Adam 成为 Transformer 默认优化器的原因之一。

3.5 随机梯度下降（SGD）

大规模机器学习里，全梯度 $\nabla f(x) = \tfrac{1}{N}\sum_{i=1}^N \nabla f_i(x)$ 在百万级样本上算一遍是不可承受的。**随机梯度下降（SGD）**用一个随机小批量代替这个全和，用一步噪声换一步便宜。

下图直观展示了这种差异：确定性 GD 路径平滑笔直，SGD 路径则是围绕同一轨迹的噪声游走，平均上靠近 GD，但每步都在抖。

凸目标上，SGD 用固定步长达到 $O(1/\sqrt{k})$、用衰减步长达到 $O(1/k)$——单步比 GD 慢，但单步成本只有 GD 的 $1/N$，总耗时反而快很多。在非凸场景里噪声还有一个意外的好处：能帮 SGD 跳出浅鞍点和窄局部极小点，这部分解释了为什么用 SGD 训练的深度网络泛化通常优于用全批量方法训练到更尖锐极小点的同款网络。

4. 二阶优化算法

4.1 牛顿法

如果说一阶方法把 $f$ 局部近似成切平面，那么牛顿法就是把它近似成抛物面，然后直接跳到抛物面的最低点。在 $x^{(k)}$ 处的二阶泰勒展开是

对右边关于 $x$ 求梯度并置零，得到牛顿步：

定理 8（二次收敛）。在强凸最小点附近、Hessian Lipschitz 的条件下，

二次收敛和我们之前见过的速率有质的不同：粗略地说，每一步把正确数字的位数翻倍。一旦靠近最优点，五六步就能到机器精度。

代价分布在三处：(i) 每步要对 Hessian 做 $O(n^3)$ 的分解，$n > 10^4$ 几乎做不到；(ii) 存 Hessian 本身就是 $O(n^2)$；(iii) 远离凸区域时 Hessian 不一定半正定，牛顿步连下降方向都未必是，需要正则化为 trust-region 步。

4.2 拟牛顿法：BFGS 与 L-BFGS

拟牛顿法的目标是用一阶代价近似拿到牛顿的好处。它不真去算 Hessian，而是只用已经看到的梯度去近似 Hessian 的逆。

BFGS 对逆 Hessian 近似 $H^{(k)}$ 的更新是

其中 $s_k = x^{(k+1)} - x^{(k)}$，$y_k = \nabla f^{(k+1)} - \nabla f^{(k)}$，$\rho_k = 1/(y_k^T s_k)$。这个公式是被精心构造的：$H^{(k+1)}$ 满足割线方程 $H^{(k+1)} y_k = s_k$（这是真实逆 Hessian 与梯度差/步长差关系的对应），并保持对称正定。

$n$ 大到连 $H$ 都存不下时就用 L-BFGS：只保留最近 $m \approx 5$–$20$ 对 $(s_i, y_i)$，通过递归的二循环公式隐式地算 $H g$。这是中大规模光滑凸问题的标准主力——比 GD 收敛快得多，又不用付 Hessian 的代价。

5. 约束优化与对偶理论

5.1 问题形式

通用的约束凸优化问题是

我们假设 $f$ 与 $g_i$ 凸，$h_j$ 仿射。

5.2 拉格朗日函数与对偶问题

拉格朗日函数把约束用乘子 $\lambda_i \geq 0$（不等式）和 $\nu_j \in \mathbb{R}$（等式）卷进目标函数：

对偶函数 $d(\lambda, \nu) = \min_x \mathcal{L}(x, \lambda, \nu)$ 关于 $(\lambda, \nu)$ 始终是凹函数——无论原问题是否凸（它是关于 $(\lambda, \nu)$ 的一族仿射函数的逐点最小）。

定理 9（弱对偶性）。对任何可行的 $\lambda \geq 0$ 与 $\nu$，

证明：对任意可行 $x$，因 $\lambda_i \geq 0$ 且 $g_i(x) \leq 0$ 有 $\sum_i \lambda_i g_i(x) \leq 0$，又 $\sum_j \nu_j h_j(x) = 0$，故 $\mathcal{L}(x, \lambda, \nu) \leq f(x)$。对 $x$ 取下确界得 $d(\lambda, \nu) \leq f(x)$，对所有可行 $x$ 成立，所以 $d(\lambda, \nu) \leq f(x^\star)$。$\square$

对偶问题 $\max_{\lambda \geq 0, \nu}\, d(\lambda, \nu)$ 的最优值为 $d^\star \leq f^\star$。差 $f^\star - d^\star \geq 0$ 称为对偶间隙。当 $f^\star = d^\star$ 时称强对偶性成立。

Slater 条件：对凸问题，只要存在严格可行点（某个 $\tilde x$ 使所有不等式约束都严格成立 $g_i(\tilde x) < 0$，等式约束方面的几条温和技术条件略），就有强对偶性。强对偶性才是对偶问题真正有用的关键：解对偶得到的最优值与原问题相同，而对偶往往结构更简单。

几何画面就在下图。像集 $\{(g(x), f(x)) : x \in \mathbb{R}^n\}$ 把一切信息都装进去了：$f^\star$ 是在 $g \leq 0$ 区域内 $f$ 的最小值，$d^\star$ 则是从下方支撑像集的非垂直超平面在 $f$ 轴上的最高截距。当像集本身凸时，这两个值重合；当不凸时，可能在支撑超平面上方"凹进去一块"，于是出现对偶间隙。

5.3 KKT 条件

强对偶性成立时，最优的原始变量与对偶变量共同满足一组小巧的方程与不等式——Karush-Kuhn-Tucker (KKT) 条件。

定理 10（KKT）。设强对偶性成立、所有函数可微。$(x^\star, \lambda^\star, \nu^\star)$ 是原始-对偶最优解当且仅当：

1. 原始可行：$g_i(x^\star) \leq 0$，$h_j(x^\star) = 0$。
2. 对偶可行：$\lambda_i^\star \geq 0$。
3. 互补松弛：$\lambda_i^\star\, g_i(x^\star) = 0$，对所有 $i$ 成立。
4. 稳定性：$\nabla f(x^\star) + \sum_i \lambda_i^\star \nabla g_i(x^\star) + \sum_j \nu_j^\star \nabla h_j(x^\star) = 0$。

对满足 Slater 条件的凸问题，KKT 既是必要条件也是充分条件——解 KKT 方程组就等同于解原优化问题。

稳定性条件的几何含义非常震撼：在最优点，$-\nabla f(x^\star)$（目标想要的方向）必须落在活跃约束法向所张成的锥里。否则就能找到一个可行的下降方向，矛盾。下图把这点放在二维例子里讲明白了：在半平面约束下的最优点处，负目标梯度和约束梯度方向严格相反，由乘子精确平衡。

互补松弛是 KKT 里直觉最强的一条：对每个不等式，要么约束活跃（$g_i(x^\star) = 0$），要么乘子为零（$\lambda_i^\star = 0$）。失活的约束对最优解毫无贡献——把它们删了答案不变。这条观察直接给了支持向量机 (SVM) 它的名字：在 SVM 的对偶里，只有恰好处于间隔边界上的训练点乘子非零，这些就是所谓的支持向量，其他训练点全是"陪跑"。

6. ADMM：把难题拆成两个易题

有些问题里，对 $(x, z)$ 联合优化很难，但给定 $z$ 单优化 $x$、以及给定 $x$ 单优化 $z$ 都很容易。ADMM——交替方向乘子法——正好利用这种结构：

增广拉格朗日在普通拉格朗日上再加一个二次罚项：$\mathcal{L}_\rho(x, z, u) = f(x) + g(z) + u^T(Ax + Bz - c) + \tfrac{\rho}{2}\|Ax + Bz - c\|^2$。ADMM 交替对 $x$、$z$ 取最小，再对对偶变量 $u$ 做一步梯度上升：

ADMM 在任何单一场景下都不是最快的，但鲁棒且天然适合分布式，所以在大规模结构化问题里独霸一方。

应用：Lasso。Lasso 问题 $\min \tfrac{1}{2}\|y - X\beta\|^2 + \lambda\|\beta\|_1$ 通过引入副本写成 ADMM 形式：$\min \tfrac{1}{2}\|y - X\beta\|^2 + \lambda\|z\|_1$ s.t. $\beta = z$。然后

• $\beta$-更新是岭回归，有闭式解；
• $z$-更新是软阈值算子，按坐标作用：

两个子问题几乎免费，迭代下来恰好得到精确的 Lasso 解。同样的套路适用于核范数最小化、全变差去噪、跨多机器的共识优化等等。

7. 代码：优化算法实现

下面是 GD、Newton、BFGS 与 ADMM-Lasso 的最小可运行实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

import numpy as np
from scipy.linalg import cho_factor, cho_solve

np.random.seed(42)

# ---- 凸二次：f(x) = 0.5 x^T Q x - b^T x ----
n = 10
A = np.random.randn(n, n)
Q = A.T @ A + np.eye(n)        # 正定
b = np.random.randn(n)
x_true = np.linalg.solve(Q, b)
f      = lambda x: 0.5 * x @ Q @ x - b @ x
grad_f = lambda x: Q @ x - b

# ---- 梯度下降 ----
x = np.zeros(n)
alpha = 1.0 / np.linalg.eigvalsh(Q).max()    # alpha = 1/L
for _ in range(200):
    x = x - alpha * grad_f(x)
print(f"GD:     ||x - x*|| = {np.linalg.norm(x - x_true):.2e}")

# ---- 牛顿法（Hessian = Q 为常量，单步即精确） ----
x = np.zeros(n)
for _ in range(5):
    x = x - np.linalg.solve(Q, grad_f(x))
print(f"Newton: ||x - x*|| = {np.linalg.norm(x - x_true):.2e}")

# ---- BFGS（带 Armijo 回溯线搜索） ----
x, H, g = np.zeros(n), np.eye(n), grad_f(np.zeros(n))
for _ in range(200):
    d = -H @ g
    t = 1.0
    while f(x + t * d) > f(x) + 0.1 * t * (g @ d):
        t *= 0.5
    x_new = x + t * d
    g_new = grad_f(x_new)
    s, y = x_new - x, g_new - g
    rho = 1.0 / (y @ s) if y @ s > 0 else 0.0
    if rho > 0:
        I = np.eye(n)
        H = (I - rho * np.outer(s, y)) @ H @ (I - rho * np.outer(y, s)) \
          + rho * np.outer(s, s)
    x, g = x_new, g_new
print(f"BFGS:   ||x - x*|| = {np.linalg.norm(x - x_true):.2e}")

# ---- ADMM 求解 Lasso ----
ns, nf = 100, 50
X = np.random.randn(ns, nf)
beta_true = np.zeros(nf); beta_true[:10] = np.random.randn(10)
y = X @ beta_true + 0.1 * np.random.randn(ns)
lam, rho = 0.1, 1.0
L = cho_factor(X.T @ X + rho * np.eye(nf))
beta = z = u = np.zeros(nf)
for _ in range(500):
    beta = cho_solve(L, X.T @ y + rho * (z - u))            # 岭回归式更新
    z    = np.sign(beta + u) * np.maximum(np.abs(beta + u) - lam / rho, 0.0)  # 软阈值
    u    = u + beta - z                                     # 对偶上升
print(f"ADMM:   非零数 = {int(np.sum(np.abs(z) > 1e-4))}/10, "
      f"误差 = {np.linalg.norm(z - beta_true):.4f}")

8. 深度问答

Q1：深度学习是非凸的，为什么还要学凸优化？

三个理由叠加。第一，机器学习里很多"主力"模型本身就是凸的——线性/岭回归、逻辑回归、SVM、大多数经典统计估计。第二，在任何足够光滑的损失函数的局部最小点附近，曲面看上去都像二次函数，所以凸优化的收敛速率局部成立。第三，Adam、带动量的 SGD、AdaGrad 这些现代优化器，都是先在凸场景里设计、分析，再"移植"到深度学习里的；理解它们的凸根源，就能预判它们在哪种非凸情形下会失灵。

Q2：条件数 $\kappa$ 到底是什么意思？

$\kappa = L / \mu$ 衡量的是等高线被拉伸的程度。$\kappa = 1$ 表示等高线是正圆，梯度下降一步到位。$\kappa = 100$ 表示一个方向比另一个方向长 100 倍，梯度下降左右撞墙。$\kappa \sim 10^6$ 时迭代几乎垂直于真正的下降方向，进度爬行。岭回归的"杀手锏"就是改善条件数：在 $X^T X$ 上加 $\lambda I$，把最小特征值从接近零提升到至少 $\lambda$，把 $\kappa = \lambda_{\max}/\lambda_{\min}$ 换成 $\kappa = (\lambda_{\max}+\lambda)/(\lambda_{\min}+\lambda)$，可能小好几个量级。

Q3：面对一个新问题，怎么挑算法？

跟着问题结构走。

实在不知道选什么：光滑问题先试 L-BFGS，非光滑结构化问题先试 ADMM，神经网络相关问题先试 Adam。

练习题

练习 1：证明 $f(x_1, x_2) = x_1^2 - x_1 x_2 + x_2^2$ 严格凸。

解答：Hessian 为 $\begin{pmatrix} 2 & -1 \\ -1 & 2\end{pmatrix}$，特征值为 $1$ 与 $3$，均为正，所以 Hessian 正定，$f$ 严格凸。

练习 2：用 KKT 条件求解 $\min x_1^2 + x_2^2$ s.t. $x_1 + x_2 \geq 1$。

解答：约束写为 $g(x) = 1 - x_1 - x_2 \leq 0$。稳定性：$2x_i - \lambda = 0$，故 $x_1 = x_2 = \lambda/2$。若约束不活跃则 $\lambda = 0$、$x = 0$，但这违反约束；所以约束活跃，$x_1 + x_2 = 1$，得 $x_1 = x_2 = 1/2$、$\lambda = 1$。

练习 3：对 $f(x) = \tfrac{1}{2} x^T A x - b^T x$（$A \succ 0$），推导 GD 的收敛速率。

解答：误差 $e^{(k)} = x^{(k)} - x^\star$ 满足 $e^{(k+1)} = (I - \alpha A)\, e^{(k)}$。收敛要求谱范数 $\|I - \alpha A\| < 1$，即 $|1 - \alpha \lambda_i| < 1$ 对 $A$ 的所有特征值 $\lambda_i$ 成立，给出 $0 < \alpha < 2/\lambda_{\max}$。最优步长 $\alpha^\star = 2/(\lambda_{\min} + \lambda_{\max})$，对应收敛比率 $(\kappa - 1)/(\kappa + 1)$。

练习 4：用 Jensen 证明算术-几何平均不等式 $\tfrac{1}{n}\sum x_i \geq (\prod x_i)^{1/n}$（$x_i > 0$）。

解答：$-\log$ 在 $(0, \infty)$ 上凸。Jensen 给 $-\log\!\big(\tfrac{1}{n}\sum x_i\big) \leq \tfrac{1}{n}\sum (-\log x_i) = -\log(\prod x_i)^{1/n}$。两侧取相反数再指数即得 AM-GM 不等式。

总结

凸优化是后续章节真正会反复用到的内核：线性回归、逻辑回归、SVM 以及不少 EM 类算法，最终都归约为某个凸优化问题，用本章的算法即是正解。

参考文献

1. Boyd, S. & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
2. Nocedal, J. & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
3. Nesterov, Y. (2004). Introductory Lectures on Convex Optimization. Springer.
4. Kingma, D. P. & Ba, J. (2015). Adam: A Method for Stochastic Optimization. ICLR.
5. Boyd, S., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011). Distributed Optimization and Statistical Learning via ADMM. Foundations and Trends in ML.
6. Bubeck, S. (2015). Convex Optimization: Algorithms and Complexity. Foundations and Trends in ML.
7. Bottou, L., Curtis, F. E., & Nocedal, J. (2018). Optimization Methods for Large-Scale Machine Learning. SIAM Review.

系列导航