人工智能中的最优化方法

任何一个最优化问题都可以用三个要素描述，这是本书的统一建模语言（教材第 1 章）：

建模演示——线性回归：

输入样本 $(x_i, y_i), i=1,\dots,N$，要找一个线性模型 $y \approx \mathbf{w}^\top\mathbf{x} + b$。

· 决策变量：$\mathbf{w}, b$（权重和偏置）

· 目标函数：均方误差 $\min \frac{1}{N}\sum_{i=1}^N \|y_i - \mathbf{w}^\top\mathbf{x}_i - b\|^2$

· 约束条件：无约束（普通线性回归没有显式约束）

该有限和形式 $\min \frac{1}{N}\sum f_i(x)$ 正是机器学习经验风险最小化（ERM）的数学表达，它引出了随机优化算法（见模块 5）。

教材第 1 章 §1.2「优化问题的定义」（定义 1.1）、一般模型（式 1.1）· 附件讲义 ERM

教材第 1 章按五个维度给优化问题分类。对 AI 工程师最重要的是下面两项：

按函数形式：

· 线性规划（LP）：$\min \mathbf{c}^\top\mathbf{x}$ s.t. $\mathbf{Ax}=\mathbf{b}, \mathbf{x}\ge 0$

· 二次规划（QP）：$\min \frac12\mathbf{x}^\top\mathbf{Q}\mathbf{x} + \mathbf{c}^\top\mathbf{x}$（SVM 属于此类）

· 非线性规划（NLP）：函数非线性的最一般情形（深度学习就是大规模 NLP）

按参数确定性：

· 确定型：所有参数精确已知

· 随机型：$\min_{\mathbf{x}} f(\mathbf{x}) = \frac{1}{N}\sum_{i=1}^N f_i(\mathbf{x})$ —— 机器学习中的经验风险最小化！

连续 vs 离散：这是教材上、下两篇的分界线——第 2-8 章讲连续优化（梯度类方法），第 10 章起讲组合/离散优化。

教材第 1 章 §1.2「优化问题的分类」（五维分类）· 有限和随机优化

定义（教材第 1 章 §1.3）：

· 全局最优解 $x^*$：所有可行点中目标值最小者。

· 局部最优解 $\bar{x}$：在邻域 $N(\bar{x})$ 内目标值最小（出邻域可能更差）。

基本迭代格式：几乎所有优化算法都可写为

其中 $\mathbf{d}^k$ 是搜索方向（如负梯度）、$t_k$ 是步长。这个统一的格式贯穿全书。

收敛性指标：收敛速度分为线性收敛、超线性收敛、二次收敛（教材 §1.3）。牛顿法达到二次收敛，梯度下降通常线性收敛。

教材第 1 章 §1.3「迭代格式」「收敛性」「收敛速度」· 邻域定义 1.4-1.5

给定 6 种食物（鸡肉、牛肉、生菜、土豆、牛奶、番茄）和 11 种营养成分的最低日需求量，求总花费最小的饮食方案。

建模：

· 决策变量 $x_j$ = 食物 j 的购买量（克）

· 目标：$\min \sum_{j=1}^6 c_j x_j = 0.34x_1 + 0.27x_2 + 0.15x_3 + 0.22x_4 + 0.20x_5 + 0.25x_6$

· 约束：$\sum_j a_{ij}x_j \ge b_i$（第 i 种营养达标），$x_j \ge 0$

这就是规范形线性规划：目标极小化、约束为不等式、变量非负。

教材第 1 章 §1.2 节食问题（例 1.1）· scipy.linprog 示例代码

一般形 → 标准形 三招：

① $\max \rightarrow \min$ 取负：$\max z = \min (-z)$

② 不等式补平：$\le b_i$ 加松弛变量 $+x_{n+i}$；$\ge b_i$ 减剩余变量 $-x_{n+i}$

③ 自由变量拆分：$x_i$ 无限制 → $x_i = x_i^+ - x_i^-$（两非负变量之差）

教材第 2 章 §2.1「标准形」（定义 2.1）、「一般形化标准形」

线性约束 $\mathbf{Ax}=\mathbf{b}, \mathbf{x}\ge 0$ 定义的可行域 $F$ 是一个凸多面体（凸集——任意两点连线仍在集内）。等高线 $\mathbf{c}^\top\mathbf{x}=k$ 是一族平行超平面。

当 $k$ 不断减小（极小化），等高线平行移动，最先"碰到"可行域的某个顶点——这就是最优解。

教材第 2 章 §2.3「线性规划问题的几何性质」· §2.4「极点与基本可行解的对应」

基矩阵（Basis）：从约束矩阵 $\mathbf{A}$（m×n）中取 m 个线性无关的列组成 m×m 满秩方阵 $\mathbf{B}$。其余列构成 $\mathbf{N}$。

基本解：令非基变量 $\mathbf{x}_N = \mathbf{0}$，由 $\mathbf{Bx}_B = \mathbf{b}$ 解得 $\mathbf{x}_B = \mathbf{B}^{-1}\mathbf{b}$，得 $\mathbf{x} = (\mathbf{B}^{-1}\mathbf{b}, \mathbf{0})$。

基本可行解（BFS）：若 $\mathbf{B}^{-1}\mathbf{b} \ge 0$，即基本解落在可行域内。

教材第 2 章 §2.2「基本可行解的定义」· §2.4「极点与基本可行解的对应」

既然最优解必在极点，而极点只有有限个，为什么不全枚举出来比较？因为 $\binom{n}{m}$ 随规模指数增长！

单纯形法的聪明之处：从初始极点开始，每次考察相邻极点，如果目标值更低就跳过去；通过检验数规则判断"所有相邻极点都不更低"→ 停止（因为凸性保证此时已是全局最优）。

教材第 2 章 §2.5「单纯形方法的迭代思想」

检验数（Reduced Cost）：

$\bar{c}_j$ 的含义：让非基变量 $x_j$ 增加 1 个单位，目标值净减小多少。

· $\bar{c}_j < 0$ → 引进 $x_j$ 可降低目标值（继续迭代）

· 所有 $\bar{c}_j \ge 0$ → 已到最优（停止）

最小比值法则（定出基变量）：

当 $\theta = \theta_0$ 时恰有一个基变量降为 0 → 离基；$x_k$ 从 0 升至 $\theta_0$ → 进基。几何上就是从当前极点沿一条棱走到相邻极点。

两种情况：退化（$\theta_0=0$，基变换但极点不变）；无界（所有 $\bar{a}_{ik}\le 0$，问题无有限最优解）。

教材第 2 章 §2.5.4「检验数」· §2.5.2「最小比值」

例题：$\min z = -x_2 + 2x_3$ s.t. $x_1 - 2x_2 + x_3 = 2,\; x_2 - 3x_3 + x_4 = 1,\; x_2 - x_3 + x_5 = 2,\; \mathbf{x}\ge 0$

教材第 2 章 §2.6「单纯形法实例」

from scipy.optimize import linprog
c = [0.34, 0.27, 0.15, 0.22, 0.20, 0.25]  # 6 foods
A_ub = -a_matrix  # scipy uses A_ub x <= b_ub
b_ub = -b_vector  # flip >= to <=
res = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=(0,None), method='highs')
print(f'Min cost: ¥{res.fun:.2f}')  # ¥17.54
print(f'Solution: {res.x}')  # 6 foods in grams

参数说明：`c` 目标系数（最小化）、`A_ub, b_ub` 不等式约束、`A_eq, b_eq` 等式约束、`bounds` 变量范围、`method='highs'` 大规模 LP 推荐。

结果解读：`res.x` 最优解、`res.fun` 最优值、`res.status`（0=最优/1=达到迭代上限/2=不可行/3=无界）、`res.success`。

注意：scipy 的 `A_ub x <= b_ub` 形式与教材 `Ax >= b` 相反——使用时取负号翻转！

教材第 1 章 §1.2 节食问题 Python 代码 · 教材第 2 章 §2.7-2.8

弱对偶性（定理 3.3）：

对偶问题的任意可行值都是原始最优值的下界。"弱"在只要求可行、不要求最优——结论只是一个不等式。

强对偶性（定理 3.4）：

"最低花费 = 最高定价"——这是整个对偶理论最核心的结论。不等式升级成了等式！

教材第 3 章 §3.2「弱对偶性」（定理 3.3）、「强对偶性」（定理 3.4）

定理 3.5（互补松紧性）：一对可行解 $(\mathbf{x}, \boldsymbol{\pi})$ 同为最优的充要条件：

通俗含义：某资源有富余（约束不紧）→ 影子价格必为零（该资源不值钱）；某变量被启用（$x_j>0$）→ 对应对偶约束必须绷紧。

LP 的 KKT 条件：原始可行 + 对偶可行 + 互补松紧 ⟺ 同时最优。这是全书最优雅的充要条件。

教材第 3 章 §3.2「互补松紧性」（定理 3.5）、验证例题（例 3.5）

① SVM 的对偶化：

硬边际 SVM 原问题：

变量维度 = 特征维度 d（可至万维）。通过对偶得到：

变量维度 = 样本数 N！且只需支持向量（$\alpha_i>0$ 的样本）参与计算。当 $d \gg N$（高维特征场景）时对偶大幅简化！

软边际 SVM（松弛变量 $\xi_i$、惩罚 C、Hinge Loss）的对偶只需加约束 $0 \le \alpha_i \le C$。

② L1/L2 正则化的对偶解释：

正则化 $\min f + \lambda\|\mathbf{w}\|$ 等价于约束优化 $\min f$ s.t. $\|\mathbf{w}\| \le t$（约束与惩罚一一对应）。对偶理论解释：正则化项对应于对偶问题中对约束的"容忍度"——λ 越大 = t 越小 = 约束越紧 = 模型越简单 = 过拟合越轻。

教材第 3 章 §3.1-3.2 · 附件讲义 SVM 原问题/对偶/软边际部分

核心公式：$\mathbf{x}^{k+1} = \mathbf{x}^k - t_k \nabla f(\mathbf{x}^k)$

负梯度方向是当前点局部下降最快的方向（Taylor 一阶展开可证），但全局收敛可能很慢。

算法：① 初点 $\mathbf{x}^0$，$\varepsilon > 0$，k=0；② 算梯度 → 若 $\|\nabla f\| \le \varepsilon$ 则停；③ $\mathbf{d}^k = -\nabla f$；④ 精确一维搜索定步长 $t_k$；⑤ 更新 $\mathbf{x}^{k+1}$。

步长策略：精确一维搜索（黄金分割 0.618）、Armijo 非精确搜索、固定学习率（深度学习常用）。

教材第 7 章 §7.3「最速下降法」· 例题 6.8

牛顿法迭代公式：

从二阶 Taylor 展开推导：$\phi(\mathbf{x}) = f(\mathbf{x}^k) + \nabla f^\top(\mathbf{x}-\mathbf{x}^k) + \frac12(\mathbf{x}-\mathbf{x}^k)^\top\nabla^2 f(\mathbf{x}^k)(\mathbf{x}-\mathbf{x}^k)$，令 $\nabla\phi=0$ 即得。

优点：正定二次函数 1 步到达极小、极小点附近二次收敛（每步精确数字位数翻倍）。

缺点：① Hesse 矩阵不正定时牛顿方向可能不下降（需阻尼/信赖域）；② 每步 O(p²) 存储 + O(p³) 求逆，深度学习中 p 可达亿级 → 完全不可行。

拟牛顿法（BFGS / L-BFGS）：用梯度差构造 Hesse 逆的近似，满足割线方程 $\mathbf{H}_{k+1}\mathbf{y}_k = \mathbf{s}_k$ 而不显式计算二阶导。L-BFGS 只存最近 m 对向量，内存 O(mp)。

教材第 7 章 §7.4「牛顿法」· §7.6「拟牛顿法」· 阻尼牛顿法

Mini-batch SGD：全量梯度 O(N) 代价难以承受 → 每次只算一个小批次的梯度估计。

动量（Momentum）：指数加权移动平均平滑梯度，抑制震荡。

Adam（2015）：动量 + 自适应学习率 + 偏差修正。当前大模型训练的事实标准。

AdamW（2017）：将权重衰减（L2 正则）与梯度更新解耦，解决了 Adam 中正则化效果被自适应学习率稀释的问题。 $\theta_t = \theta_{t-1} - \eta(\hat{m}_t/(\sqrt{\hat{v}_t}+\varepsilon) + \lambda\theta_{t-1})$。

教材第 7 章 §7.3-7.6 · AI 社区 Adam/AdamW 论文 (Kingma & Ba 2015, Loshchilov & Hutter 2017)

凸规划标准形式：

其中 $f_0,\dots,f_m$ 是凸函数，等式约束为仿射（线性）函数。

证明思路：设 $\mathbf{x}^*$ 是局部最优，任取另一可行解 $\mathbf{y}$。构造凸组合 $\mathbf{z}=\lambda\mathbf{x}^*+(1-\lambda)\mathbf{y}$，λ 充分大时 $\mathbf{z}$ 落入 $\mathbf{x}^*$ 的邻域 → $f(\mathbf{z})\ge f(\mathbf{x}^*)$；再由凸性 $f(\mathbf{z})\le \lambda f(\mathbf{x}^*)+(1-\lambda)f(\mathbf{y})$ → 代入得 $f(\mathbf{y})\ge f(\mathbf{x}^*)$。

教材第 1 章 §1.5「凸规划」（定理 1.11）

一旦确定问题是凸的，就可以使用任意局部搜索算法并保证收敛到全局最优。以下 AI 模型都是凸问题：

· Lasso 回归 $\min \frac12\|\mathbf{y}-\mathbf{Xw}\|^2 + \lambda\|\mathbf{w}\|_1$（凸但非光滑，须用次梯度或近端方法）

· 岭回归 $\min \frac12\|\mathbf{y}-\mathbf{Xw}\|^2 + \lambda\|\mathbf{w}\|^2$（严格凸，有唯一最优解）

· SVM $\min \frac12\|\mathbf{w}\|^2 + C\sum\xi_i$ s.t. $y_i(\mathbf{w}^\top\mathbf{x}_i+b)\ge 1-\xi_i,\;\xi_i\ge0$（凸 QP）

· 逻辑回归（交叉熵损失是凸函数——不用担心局部最优）

· 最小二乘（无正则时是凸二次函数）

⛔ 非凸对照：深度神经网络——多层非线性激活的复合导致损失面极度非凸，鞍点远多于差的局部极小，需要 SGD 的随机性与动量来逃离。

教材第 1 章 §1.5 凸规划 · 第 7 章 §7.1 凸函数充要条件

有约束时最优点常被"顶"在边界上——负梯度被约束法向量的非负组合平衡。

一般约束问题的 KKT 条件：存在乘子 $\lambda_i \ge 0$ 和 $\mu_j$ 使：

四条含义：① 稳定性条件（上式）；② 原始可行性；③ 对偶可行性（$\lambda_i \ge 0$）；④ 互补松紧（$\lambda_i g_i = 0$）——松约束乘子为 0，紧约束乘子可正。

FJ 条件 vs KKT：FJ 不需要正则点假设，但 $\lambda_0$ 可能为 0 导致信息丢失。KKT 要求约束梯度线性无关，固定 $\lambda_0=1$ 给出真实的平衡关系。

教材第 8 章 §8.2「KKT 条件」（定理 8.3-8.6）· 凸规划 KKT 充分性

核心思想：把 $\min f$ s.t. 约束 → 一系列无约束 $\min f + \sigma P(x)$，$\sigma\to\infty$ 时逼近原问题。

外罚函数法：

$\sigma_k \to \infty$（外罚因子逐次放大），每次求解无约束子问题，解从可行域外部逐渐逼近。

内罚（障碍）函数法：在可行域内部筑墙，$r_k\to 0$ 时墙撤去。要求初始点在内部。

罚因子过大的问题：问题变得"病态"（条件数爆炸），数值不稳定。解决：增广拉格朗日法（罚 + 显式乘子）。

其他方法：Zoutendijk 可行方向法（线路上逐步下降保持可行）、投影梯度法、SQP（序列二次规划）。

教材第 8 章 §8.4「外罚函数法」·「内罚函数法」· §8.3「可行方向法」· §8.5「SQP」

自动驾驶路径规划：总耗时最小 $\min T_{\text{total}}$ s.t. 避障（$d(\mathbf{p}_t, O_k) \ge d_{\min}$ 不等式约束）、限速（$v_{\min} \le v_t \le v_{\max}$ 盒约束）、终点到达（$\mathbf{p}_T = \mathbf{p}_{\text{goal}}$ 等式约束）→ 这是典型约束非线性规划。

联邦学习隐私约束：各客户端本地训练时，梯度加噪声（差分隐私），需要在"隐私预算 ≤ ϵ"的约束下最大化模型精度 → 约束优化。常用罚函数或投影梯度处理。

教材第 8 章 · AI 社区应用实例

深度网络的损失面高度非凸，但实践中 SGD+动量+合适的学习率总能找到不错的解。原因：

· 鞍点远多于局部极小：高维空间中鞍点（Hesse 有正有负特征值）数量指数级多于严格局部极小点。随机梯度噪声帮助逃离鞍点。

· 过参数化现象：当网络宽度 >> 样本量时，所有局部极小点倾向于具有相同（接近全局最优的）损失值。

· SGD 噪声的泛化益处：平坦极小（flat minima）泛化好、尖锐极小（sharp minima）泛化差——SGD 噪声天然偏好平坦极小。

教材第 7 章最优性条件 · AI 社区研究

点击以下分支逐步导航：

全课程综合 · 教材第 1-8 章总览

课程知识地图回顾（8 模块）：

三要素框架（模 1）→ LP 建模与标准形（模 2）→ 顶点最优 + 单纯形 + linprog（模 3）→ 对偶理论 + SVM（模 4）→ GD/SGD/AdamW（模 5）→ 凸优化全局最优（模 6）→ KKT + 罚函数 + 应用（模 7）→ 大模型前沿 + 选型（模 8）

进阶推荐：

· Boyd & Vandenberghe《Convex Optimization》（凸优化圣经）

· Nocedal & Wright《Numerical Optimization》（数值优化权威教材）

· 本教材第 10-26 章（组合优化、图论算法、整数规划、NP 完全性 → 离散优化的完整世界）

全课程综合 · 教材后续章节指引