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

本章概览#

1947 年，George Dantzig 提出了单纯形法，用于解决线性规划问题，现代优化理论由此诞生。八十年过去了，优化已成为机器学习的核心驱动力——无论是通过一行代码实现的线性回归，还是拥有 700 亿参数的语言模型，每个训练完成的模型本质上都是某个优化问题的答案。

在所有优化问题中，凸优化占据了一个独特的位置。其定义性质强大到让人觉得有些“作弊”——任何局部最优解一定是全局最优解。此外，针对凸优化问题，已发展出一套成熟算法，这些算法不仅理论清晰，还能保证收敛性。因此，“凸”被视为绿灯，而“非凸”则被视为黄灯。

本章从零开始搭建凸优化的工具箱。首先讲解几何基础：凸集、凸函数和 Jensen 不等式；接着补充微积分知识，如次梯度，用于处理不可微的情况；最后推导具体算法：梯度下降、Nesterov 加速、Adam、牛顿法、BFGS、约束问题中的 KKT 条件，以及用于分解结构化问题的 ADMM。

你将学到的内容包括：

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

先修知识： 多元微积分（梯度、Hessian 矩阵、泰勒展开）和线性代数（特征值、半正定矩阵）。本系列的前几篇文章已经涵盖了这些内容。

凸集与凸函数#

凸集#

简单说，凸集中任意两点之间的连线始终在集合内部。没有凹陷、没有缺口、也没有断开的部分。下图直观地说明了这一点：凸集中的弦永远不会跑出边界，而非凸集中的弦可能直接穿过空隙。

以下是一些常见的凸集，你会反复遇到它们：

• 超平面 $\{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$

这个性质看似简单，却是实际建模的核心工具。复杂可行域几乎总是通过多个简单凸约束的交集构造出来的。

凸函数#

从几何上看，函数图像上任意两点连成的弦，始终位于图像之上或与图像相切。下图左边的碗形曲面是凸的，右边的“鸡蛋盒”则不是。这种差异非常重要：凸碗只有一个极小值点，任何下降算法都能找到它；而鸡蛋盒里到处是局部极小值点，下降算法很容易卡住。

以下是两种重要的凸性强化形式：

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

一阶与二阶判别条件#

定义 2 的几何描述很清晰，但实际操作中很难验证。下面两个定理给出了基于导数的等价条件，这才是实践中真正用到的工具。

换句话说，每条切平面都是 $f$ 的全局下界。这是梯度下降法在凸问题上有效的原因：线性近似 $f(x) + \nabla f(x)^T (y - x)$ 永远不会高估 $f$ ，所以沿着负梯度方向走小步确实能让 $f$ 下降——前提是步长足够小。

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

Jensen 不等式#

凸性不等式 (2) 描述的是两点平均的情况。将其推广到任意概率分布，就得到了机器学习中最常用的不等式之一。

如果 $f$ 是严格凸的且 $X$ 不退化，则不等式严格成立。

证明思路（离散情况）
假设 $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}$ 。

次梯度与非光滑优化#

机器学习中很多常用的目标函数并不是处处可微的。比如， Lasso 中用到的 L1 范数 $\|x\|_1$ 在每个坐标轴上都有尖点； SVM 的 hinge 损失 $\max(0, 1 - y \cdot s)$ 在 $s = 1/y$ 处也不平滑。为了在这些函数上做优化，我需要推广梯度的概念。

次梯度#

所有满足条件的 $g$ 构成的集合称为 $f$ 在 $x$ 处的次微分，记作 $\partial f(x)$ 。如果 $f$ 在 $x$ 处可微，那么次微分只包含一个元素，即 $\partial f(x) = \{\nabla f(x)\}$ 。在不可微点上，次微分通常是一个非平凡集合，表示所有在 $x$ 处与 $f$ 相切的有效线性下界。

最优性条件
$x^\star$ 是凸函数 $f$ 的全局最小值点，当且仅当 $0 \in \partial f(x^\star)$ 。这可以看作是光滑优化中 $\nabla f(x^\star) = 0$ 的推广。

次梯度法#

需要注意的是，次梯度不一定是下降方向——单步更新可能会让函数值变大。为了保证收敛，步长必须逐渐减小，比如取 $\alpha_k = 1/\sqrt{k}$ 。非光滑优化的代价是收敛速度变慢，从光滑问题的 $O(1/k)$ 退化到 $O(1/\sqrt{k})$ 。

对于形如 $f(x) + h(x)$ 的复合问题，其中 $f$ 是光滑函数，$h$ 是非光滑函数（比如 Lasso），可以用近端梯度法处理。这种方法通过 $h$ 的近端算子精确求解，能够恢复到光滑优化的 $O(1/k)$ 收敛速度。

一阶优化算法#

梯度下降#

为什么它有效？因为一阶条件 (3) 告诉我们，在凸函数上，负梯度确实是下降方向，线性近似也不会高估 $f$ 。只要步长合适，就不会“冲过头”。下图展示了二维情况下的结果：在凸面上是一条干净单调的路径直达最小值；在非凸面上则会被困在局部最小值。

证明思路
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$

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

学习率：你无法回避的选择#

梯度下降只有一个参数可以调：步长 $\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 矩阵的最大特征值，结论依然成立。这是梯度下降最重要的工程事实：正确的学习率由曲率决定，不能靠猜。

2D 病态二次型的具体走法：取 $f(w_1, w_2) = \tfrac{1}{2}(10 w_1^2 + w_2^2)$ ，最大特征值 $L=10$ ，最小 $\mu=1$ ，条件数 $\kappa=10$ 。从 $w^{(0)} = (1,\ 1)$ 出发：

• $\eta = 0.1 = 1/L$ ：每步 $w_1$ 缩一半（$w_1 \cdot (1-\eta\cdot 10) = 0$ ），但 $w_2$ 只缩到 $0.9$ 倍。10 步后 $w \approx (0,\ 0.349)$ ，$w_1$ 早就到了，$w_2$ 还在慢慢爬；
• $\eta = 0.18$ （接近上限 $2/L=0.2$ ）：$w_1$ 在 $1$ 和 $-0.8$ 之间来回振荡却不发散，$w_2$ 缩得快了点；
• $\eta = 0.22 > 2/L$ ：$w_1$ 直接发散。

无论 $\eta$ 怎么调，“陡方向 $w_1$ 想要小步、缓方向 $w_2$ 想要大步"的矛盾无法被一个标量步长同时满足——这正是动量法、Adam、特征标准化要解决的核心问题。

非凸反例：取 $f(x) = x^4 - 4x^2 + x$ ，有两个局部极小：$x \approx -1.46$ （全局，$f \approx -4.41$ ）和 $x \approx 1.40$ （局部，$f \approx -2.59$ ）。从 $x^{(0)} = 1$ 用 $\eta=0.05$ 做梯度下降，迭代轨迹 $1 \to 1.35 \to 1.39 \to 1.40 \to \dots$ 直奔局部极小被卡住，全局极小再也找不到。如果改从 $x^{(0)}=-0.5$ 出发，则收敛到全局极小。在凸函数上，梯度下降不会因初始点不同而落到不同最优解；非凸函数上，“初值决定一切”——这就是凸性给的保证一旦丢掉，工程上会变得多脆弱。

动量法与 Nesterov 加速#

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

(14) 是可证最优的：任何只依赖 $\nabla f$ 的一阶方法，在最坏情况下都无法比这更快。这是凸优化中的一个惊喜——一个小小的改动（先前瞻、再走步），就让速率从 $O(1/k)$ 提升到 $O(1/k^2)$ ，而且无需额外计算成本。

自适应学习率与 Adam#

朴素梯度下降对所有坐标使用同一个步长。但在实际问题中，不同坐标的曲率可能相差几个数量级。比如在文本模型中，常见词嵌入每步都收到大量梯度，而生僻词嵌入几乎收不到。自适应方法为每个坐标分配独立的学习率，按近期梯度幅度缩放。

其中 $\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 默认优化器的原因之一。

随机梯度下降（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 训练的深度网络泛化性能通常优于用全批量方法训练到更尖锐极小点的同款网络。

二阶优化算法#

牛顿法#

二次收敛和之前见过的所有速率都不同：简单来说，每迭代一次，结果的有效数字位数翻倍。一旦接近最优点，五六步就能达到机器精度。

但牛顿法有三个主要问题：(i) 每次迭代需要对 Hessian 矩阵分解，复杂度是 $O(n^3)$ ，当 $n > 10^4$ 时几乎不可行；(ii) 存储 Hessian 矩阵本身需要 $O(n^2)$ 的空间；(iii) 如果 $\nabla^2 f$ 不是正定矩阵（比如远离凸区域时），牛顿步可能根本不会让 $f$ 下降，这时需要正则化，比如改成 trust-region 步。

拟牛顿法： BFGS 与 L-BFGS#

拟牛顿法的目标是以一阶方法的代价实现接近牛顿法的效果。它不直接计算 Hessian，而是通过已有的梯度信息来近似 Hessian 的逆。

其中 $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$ 。这是中大规模光滑凸问题的标准工具——比梯度下降收敛快得多，又避免了 Hessian 的高昂代价。

约束优化与对偶理论#

问题形式#

这里假设 $f$ 和 $g_i$ 是凸函数，$h_j$ 是仿射函数。

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

对偶函数定义为 $d(\lambda, \nu) = \min_x \mathcal{L}(x, \lambda, \nu)$ 。无论原问题是否是凸的，$d(\lambda, \nu)$ 关于 $(\lambda, \nu)$ 始终是凹函数，因为它是关于 $(\lambda, \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$ ，满足 $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$ 轴上的最高截距。如果图像集是凸的，这两个值相等；如果不是凸的，支撑超平面上方可能会出现“缺口”，导致对偶间隙。

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 的对偶问题中，只有恰好位于间隔边界上的训练点对应的乘子非零，这些点就是所谓的支持向量，其他点都是无关紧要的“陪跑者”。

ADMM：把复杂问题拆成简单问题#

ADMM 在任何单一场景下都不是最快的算法，但它的鲁棒性极强，而且天生适合分布式计算，因此在大规模结构化问题中占据主导地位。

应用： Lasso
Lasso 问题 $\min \tfrac{1}{2}\|y - X\beta\|^2 + \lambda\|\beta\|_1$ 可以通过引入一个副本变量 $z$ 转化为 ADMM 形式：$\min \tfrac{1}{2}\|y - X\beta\|^2 + \lambda\|z\|_1$ ，约束条件是 $\beta = z$ 。具体来说：

• 更新 $\beta$ 是一个岭回归问题，有闭式解；
• 更新 $z$ 使用的是软阈值算子，逐坐标操作：

这两个子问题的计算成本几乎可以忽略不计，迭代后能得到精确的 Lasso 解。同样的方法还可以用于核范数最小化、全变差去噪、跨多机器的共识优化等问题。

代码：优化算法实现#

下面是一个最小但可用的 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

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

np.random.seed(42)

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}")

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}")

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}")

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}")

常见问题#

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$ ，约束条件是 $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：推导梯度下降法（GD）在目标函数 $f(x) = \tfrac{1}{2} x^T A x - b^T x$ （$A \succ 0$ ）下的收敛速率。

解答：误差定义为 $e^{(k)} = x^{(k)} - x^\star$ ，满足递推关系 $e^{(k+1)} = (I - \alpha A)\, e^{(k)}$ 。要保证收敛，谱范数需要满足 $\|I - \alpha A\| < 1$ ，即对矩阵 $A$ 的所有特征值 $\lambda_i$ ，有 $|1 - \alpha \lambda_i| < 1$ 。由此得出步长范围 $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}$ 。两边取相反数后取指数，即可得到算术-几何平均不等式。

总结#

凸优化是本系列后续内容的核心基础。线性回归、逻辑回归、 SVM 以及许多 EM 风格的算法，最终都能归结为凸优化问题。而这些算法正是解决这些问题的最佳选择。

下一步#

四章铺垫到此为止：分析的语言、向量的语言、概率的语言、优化的语言。从下一章起，我开始把这四套语言叠在同一个具体的算法上——线性回归。

线性回归看起来简单，但它是整个监督学习的"显微镜样本”：它的参数是向量（线性代数），它的损失是高斯似然（概率论），它的求解是凸优化（本章），它的泛化能力可以用偏差-方差分解（第一章）刻画。我会反复回到这种"四语言叠加"视角——不是为了炫耀，而是因为只有把每个算法都拆到这四层，你才知道"为什么换一个损失函数（如 Huber）就只动其中一层"“为什么加 L1 正则会同时动概率层（先验）和优化层（次梯度）"。线性回归是这种思维方式的第一次完整演练。

参考文献#

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.