第 25 章 线性代数在优化中的应用¶
前置：线性方程组 (Ch01) · 正定矩阵 (Ch16) · 矩阵流形 (Ch24) · 凸集基础 (Ch64A)
本章脉络：优化问题的线性代数本质 \(\to\) 线性规划 (LP) 的标准型与矩阵表示 \(\to\) 单纯形法 (Simplex Method) 的代数步骤 \(\to\) 强对偶性 (Strong Duality) 与 Farkas 引理 \(\to\) 二次规划 (QP) 与 KKT 条件 \(\to\) 核心进阶：半正定规划 (SDP) \(\to\) 内点法 (Interior Point Methods) 的代数逻辑 \(\to\) 应用：投资组合优化、机器学习中的支持向量机 (SVM)、压缩感知理论、稀疏编码
延伸：最优化是线性代数的“行动指南”；它将方程组从“求相等”提升到“求最优”，证明了矩阵的不等式约束定义了高维空间的凸几何边界，是所有 AI 算法自动更新参数的数学引擎
在前面的章节中，我们关注的是求解 \(Ax = b\)。但在现实世界中，资源是有限的，我们的目标往往是在满足一组线性约束的同时，最大化收益或最小化成本。这就是最优化理论。线性代数为优化提供了核心语言：线性规划中的单纯形旋转本质上是基变换，而半正定规划则是特征值理论在约束空间的终极应用。本章将展示线性代数如何成为从有限资源中榨取最大价值的数学利器。
25.1 线性规划与单纯形代数¶
定义 25.1 (线性规划 LP 标准型)
$\(\min \mathbf{c}^T \mathbf{x} \quad \text{s.t. } A\mathbf{x} = \mathbf{b}, \mathbf{x} \ge 0\)$ 单纯形法逻辑：从增广矩阵的一个基可行解（顶点）开始，通过初等行变换（转轴操作）移动到另一个使目标函数减小的邻接顶点。
25.2 对偶理论与 Farkas 引理¶
定理 25.1 (强对偶定理)
若原始问题有最优解，则其对偶问题 \(\max \mathbf{b}^T \mathbf{y}\) 也有最优解，且两者的最优值相等。 代数本质：这是 Farkas 引理的直接结果，揭示了“可行性”与“超平面分离”之间的深层对称性。
25.3 半正定规划 (SDP)¶
定义 25.2 (半正定规划)
$\(\min \operatorname{tr}(CX) \quad \text{s.t. } \operatorname{tr}(A_i X) = b_i, X \succeq 0\)$ 地位：SDP 是凸优化的顶峰，它将线性规划的变量从向量扩展到了矩阵，能够精确处理复杂的矩阵特征值约束。
练习题¶
1. [基础] 将 \(\min x_1 - x_2\) 约束于 \(x_1+x_2 \le 4, x_1, x_2 \ge 0\) 化为标准型。
参考答案
转换步骤： 1. 引入松弛变量 \(s_1 \ge 0\)。 2. 将不等式变为等式：\(x_1 + x_2 + s_1 = 4\)。 3. 目标函数保持：\(\mathbf{c} = (1, -1, 0)^T\)。 标准型：\(\min (1, -1, 0) \begin{pmatrix} x_1 \\ x_2 \\ s_1 \end{pmatrix}\) 满足 \((1, 1, 1) \mathbf{x} = 4\) 且 \(\mathbf{x} \ge 0\)。
2. [单纯形] 在单纯形法中，选定一个入基变量的代数依据是什么？
参考答案
理由： 计算检验数（Reduced Cost） \(\bar{c}_j = c_j - \mathbf{c}_B^T B^{-1} A_j\)。 若某非基变量的检验数为负，说明将该变量增加（即进入基）会导致目标函数值下降。这本质上是寻找目标函数在可行域边界上的最速下降方向。
3. [对偶] 写出 \(\min \mathbf{c}^T \mathbf{x}, A\mathbf{x} \ge \mathbf{b}, \mathbf{x} \ge 0\) 的对偶问题。
参考答案
结论： \(\max \mathbf{b}^T \mathbf{y}, A^T \mathbf{y} \le \mathbf{c}, \mathbf{y} \ge 0\)。 物理意义：原始问题是在约束下寻找最低成本，对偶问题则是在资源定价约束下寻找最高收益。
4. [SDP] 判定：线性规划（LP）是否是半正定规划（SDP）的一个特例？
参考答案
是的。 理由：如果将 SDP 中的矩阵变量 \(X\) 限制为对角矩阵，则 \(X \succeq 0\) 约束退化为对角元 \(x_i \ge 0\)。同时迹运算退化为向量点积。因此 LP 只是在对角矩阵子空间上进行的 SDP。
5. [KKT] 在二次规划 \(\min \frac{1}{2}\mathbf{x}^T Q \mathbf{x} + \mathbf{c}^T \mathbf{x}\) 中，Q 的什么性质保证了全局最优？
参考答案
结论：Q 必须是半正定的 (\(Q \succeq 0\))。 理由：半正定性保证了目标函数是凸的。对于凸优化问题，任何局部极小值都是全局最优值。如果 \(Q\) 有负特征值，问题将变得非凸，寻找全局解将极其困难。
6. [计算] 利用对偶性判定：若 \(\mathbf{c}^T \mathbf{x}\) 的某个可行解为 10，而对偶问题的某个可行解为 12，这可能吗？
参考答案
结论：不可能（针对最小化原问题）。 理由：根据弱对偶定理，任何对偶问题的可行值（最大化）始终小于等于原始问题的任何可行值（最小化）。即 \(Objective_{dual} \le Objective_{primal}\)。既然 \(12 > 10\)，这种配置违反了对偶原理。
7. [应用] 支持向量机 (SVM) 中的“核技巧”如何体现线性代数的威力？
参考答案
SVM 的原始问题是在高维空间寻找超平面。 通过对偶化，问题转化为只涉及样本间内积 \(x_i^T x_j\) 的形式。 利用矩阵正定性，我们可以用核函数 \(K(x_i, x_j)\) 替换内积，从而在不显式计算高维映射的情况下实现非线性分类。
8. [内点法] 简述内点法相对于单纯形法的核心优势。
参考答案
对比： - 单纯形法：沿边界（顶点）移动，最坏情况下复杂度是指数级的（Klee-Minty 示例）。 - 内点法：从可行域内部穿过，利用牛顿法沿着中心路径逼近最优解。 结论：内点法具有多项式级复杂度，在处理超大规模或具有矩阵约束（如 SDP）的问题时表现更为优越。
9. [Farkas引理] Farkas 引理在矩阵方程中描述了什么？
参考答案
它描述了一个二择一的选择： 要么存在 \(x \ge 0\) 满足 \(Ax=b\)（目标点在锥内）； 要么存在 \(y\) 使得 \(A^T y \ge 0\) 且 \(b^T y < 0\)（存在一个超平面将目标点与锥分离）。 这是所有线性约束优化存在性证明的代数母版。
10. [应用] 什么是“压缩感知”中的 \(\ell_1\) 最小化？它为何是优化问题？
参考答案
解释： 我们希望在 \(Ax=b\) 的约束下寻找最稀疏的解（\(\ell_0\) 范数最小）。由于 \(\ell_0\) 优化是 NP-难的，线性代数证明了在一定条件下（RIP 性质），可以用线性规划 \(\min \|x\|_1\) 来精确替代。这一向凸优化的转化是现代信号处理的里程碑。
本章小结¶
线性代数是最优化理论的引擎与准绳：
- 几何的视角：它将枯燥的数值约束转化为高维空间中的多面体与锥，确立了搜索最优解的几何路径。
- 对偶的和谐：强对偶定理展示了优化问题背后深刻的代数平衡，证明了成本的下限与价值的上限在最优处必然合一。
- 从向量到算子：从 LP 到 SDP 的跨越标志着线性代数从处理简单的离散分配转向处理复杂的系统稳定性与矩阵结构优化，是通往现代 AI 算法的必经之路。