路径： 本科数学/ 进阶数学/ 矩阵分析与谱图论/凸优化与对偶理论：从梯度下降到 KKT
31

凸优化与对偶理论：从梯度下降到 KKT

Convex Optimization & Duality · 机器学习训练的引擎

【章首引子】训练神经网络 = 最小化损失 L(θ)。为什么梯度下降有时收敛、有时震荡？答案藏在凸优化里：凸问题没有局部极小陷阱，KKT 条件给出最优解的完整刻画，对偶理论把"难的原问题"变成"好解的对偶问题"。这一章是一切机器学习训练的数学发动机。

卡必背公式 / 记忆口诀
凸函数：f(λx+(1−λ)y)≤λf(x)+(1−λ)f(y)
拉格朗日 L=f+Σλᵢgᵢ+Σμⱼhⱼ
KKT：平稳+可行+λ≥0+互补松弛
弱对偶 d*≤p*；强对偶 Slater
口诀：凸问题没局部坑，KKT 四条件定最优

① 是什么：凸集、凸函数与对偶

啥凸优化在解什么

① 凸集：集合 C 内任意两点连线段都在 C 内：x,y∈C ⇒ λx+(1−λ)y∈C（0≤λ≤1）。凸函数 f：f(λx+(1−λ)y)≤λf(x)+(1−λ)f(y)——函数图像在弦下方。二阶可微时 f″⪰0（Hessian 半正定）即可判定。

② 凸优化问题：minimize f(x) s.t. gᵢ(x)≤0, hⱼ(x)=0，其中 f、−gᵢ 凸，hⱼ 仿射。核心好处：任何局部极小都是全局极小——没有"卡住出不来"的坑。

③ 梯度下降：x_{k+1}=x_k−η∇f(x_k)。对凸强凸函数（f″⪰mI, m>0），指数收敛 f(x_k)−f*≤O((1−ηm)^k)；一般凸函数次线性 O(1/k)。

④ 拉格朗日函数：L(x,λ,μ)=f(x)+Σᵢ λᵢ gᵢ(x)+Σⱼ μⱼ hⱼ(x)，λᵢ≥0。把约束揉进目标。

图 31.1：可行域（阴影）+ 目标等高线 + 最优点（在约束边界上）
可行域（凸） 无约束最优（不可行） x*（在约束 g=0 上） ∇f(x*) = −λ∇g(x*)

② KKT 条件与对偶

证KKT 与弱/强对偶

KKT 条件（x* 最优的必要条件，强对偶下充分）：① 平稳性：∇f(x*)+Σλᵢ∇gᵢ(x*)+Σμⱼ∇hⱼ(x*)=0；② 原始可行：gᵢ(x*)≤0, hⱼ(x*)=0；③ 对偶可行：λᵢ≥0；④ 互补松弛：λᵢ gᵢ(x*)=0。对偶函数：d(λ,μ)=infₓ L(x,λ,μ)，对偶问题 max_{λ≥0,μ} d(λ,μ)，最优值 d*。弱对偶：d*≤p*（恒成立，对偶间隙非负）；强对偶：d*=p*（Slater 条件：凸问题且存在严格可行点时成立）。

推导思路（为什么互补松弛）：若 gᵢ(x*)<0（约束未卡边），对应乘子 λᵢ=0，因为最优点不在这个约束的边界上，它不"发力"；若 gᵢ(x*)=0（约束卡边），λᵢ>0 把目标往可行域内推。这就是 λᵢgᵢ=0。

推导思路（弱对偶）：对任意 λ≥0，d(λ,μ)=infₓ L(x,λ,μ)≤L(x*,λ,μ)=f(x*)+Σλᵢgᵢ(x*)≤f(x*)=p*（用了 gᵢ(x*)≤0 和 λᵢ≥0）。所以对偶函数恒是原问题最优值的下界，max 它仍 ≤ p*。强对偶时上下界重合。

次梯度：凸函数不可微时（如 f(x)=|x| 在 0 点），用次梯度 ∂f(x)：v∈∂f(x) 当且仅当 f(y)≥f(x)+vᵀ(y−x) 对所有 y。次梯度下降 x_{k+1}=x_k−η g_k（g_k∈∂f(x_k)）是 Lasso、SVM 等不可微问题的算法基础。

③ 例题

例1：min x² s.t. x≥1（带约束）
【审题】无约束最优 x=0 不可行，最优点必在边界 x=1。
思路：写 g(x)=1−x≤0，套 KKT。
逐步：L=x²+λ(1−x)。平稳：2x−λ=0；互补：λ(1−x)=0。若 λ=0 则 x=0（不满足 x≥1）；故 λ>0 ⇒ 1−x=0 ⇒ x=1，λ=2。最优 x*=1，p*=1。
例2：共轭先验直觉——LASSO 的稀疏
【审题】min ‖y−Xβ‖² + λ‖β‖₁。
思路：L1 惩罚在 0 不可微，用次梯度。
逐步：在 βⱼ=0，次梯度含 [−λ,λ]，若 −2Xⱼᵀ(y−Xβ) 落在该区间内，则 βⱼ=0 最优——这就是 Lasso 产生稀疏解的原因。对偶视角：Lasso 对偶是有界约束的二次规划，强对偶成立。
例3：强对偶与 Slater
【审题】min x² s.t. x≥1（凸），存在严格可行点（如 x=2）。
思路：Slater 满足 ⇒ 强对偶。
逐步：对偶函数 d(λ)=infₓ [x²+λ(1−x)]。对 x 求导 2x−λ=0 ⇒ x=λ/2，代入 d(λ)=λ²/4+λ(1−λ/2)=λ−λ²/4。max_{λ≥0} d(λ)：d′=1−λ/2=0 ⇒ λ=2，d*=2−1=1=p*。强对偶成立，对偶值=原值。
凸优化核心公式 凸函数：f(λx+(1−λ)y)≤λf(x)+(1−λ)f(y)；f″⪰0
L(x,λ,μ)=f(x)+Σλᵢgᵢ(x)+Σμⱼhⱼ(x)，λᵢ≥0
KKT：∇f+Σλᵢ∇gᵢ+Σμⱼ∇hⱼ=0；g≤0；λ≥0；λg=0
弱对偶 d*≤p*；强对偶 d*=p*（Slater：凸+严格可行）

④ AI 落点

优化
AI 落点 1：训练损失即凸/非凸优化

线性回归、SVM、Logistic 回归是凸问题，梯度下降必收敛到全局最优；深度网络非凸，但凸优化提供了收敛分析的基准语言。

优化
AI 落点 2：正则化与 KKT

L1（Lasso）稀疏、L2（权重衰减）、Early Stopping 都能写成约束优化，KKT 解释了为什么 L1 把权重压到 0。

算法
AI 落点 3：对偶与 SVM

硬间隔 SVM 原问题难，但对偶问题变成只涉及核函数 K(xᵢ,xⱼ) 的二次规划——核技巧由此而来。

优化
AI 落点 4：ADMM 与分布式

ADMM 把原问题拆成局部子问题 + 对偶变量协调，是分布式训练、联邦学习、Lasso 求解的通用框架，本质是对偶分解。

⑤ 延展

展知识衔接地图

往本科走：多元微积分（梯度、Hessian）是 KKT 的语言基础。

往算法走：对偶 → SVM/核方法；次梯度 → Lasso；强对偶 → 变分推断的 ELBO（下一章贝叶斯与后续 VI）。

思维陷阱

以为凸优化一定易解。凸性保证全局最优，但维度爆炸（内点法 O(n³)）仍可能慢；大规模凸问题靠一阶方法（SGD/ADMM）。

忽略 Slater 条件乱用强对偶。非凸问题强对偶一般不成立，对偶间隙 d*<p* 可能很大——不能把对偶下界当真实最优。

忘记互补松弛。KKT 四条件缺一不可；只写平稳性不写 λg=0 会把不可行点当最优。

练习

【基础】f(x)=x² 是不是凸函数？f(x)=−x² 呢？

查看解答f″=2≥0 凸；f″=−2≤0 凹（不是凸）。
【自评反馈】对 → 下一题。

【进阶】min x² s.t. x≥1，写出对偶函数并求 d*。

查看解答见例3：d(λ)=λ−λ²/4，max 在 λ=2 处 d*=1=p*。
【自评反馈】对 → 下一题。

【挑战】解释为什么 L1 正则产生稀疏解而 L2 不产生。

查看解答L1 |β| 在 0 不可微，次梯度区间 [−1,1] 允许梯度为 0 停在 0；L2 β² 在 0 梯度为 0 但 0 不卡边，解是"缩小但不归零"的 soft-threshold 与 ridge 收缩。
记
小结卡

① 凸函数 f(λx+(1−λ)y)≤λf(x)+(1−λ)f(y)；凸问题局部最优=全局最优。

② KKT 四条件：平稳性、原始可行、对偶可行 λ≥0、互补松弛 λg=0。

③ 弱对偶 d*≤p* 恒成立；Slater 条件下强对偶 d*=p*。次梯度处理不可微凸函数。

← 上一节 研究生数学总览