4. 凸优化与对偶理论初步

要真正理解 L1 稀疏正则化为什么能产生稀疏解、又为什么能通过 KKT 条件刻画“哪些参数被压到零”，需要先补齐凸优化的基础语言。本节围绕四个概念展开：凸集、凸函数、次梯度、KKT 条件，最后落到 L1 正则化问题的对偶形式与最优性条件。它们不是孤立的数学名词，而是一条从“可行域形状”到“最优解判据”的推理链。

凸集与凸函数：为什么 L1 问题“好解”

集合 C 是凸集，指对任意 x, y ∈ C 和 λ ∈ [0,1]，都有 λx + (1−λ)y ∈ C，即集合中任意两点的连线仍完全落在集合内。函数 f 是凸函数，指其定义域为凸集，且对任意 x, y 与 λ ∈ [0,1] 满足 f(λx + (1−λ)y) ≤ λf(x) + (1−λ)f(y)。几何上，函数图像上任意两点之间的弦位于图像上方。若 f 可微，凸性等价于 f(y) ≥ f(x) + ∇f(x)ᵀ(y−x)，即一阶泰勒展开是全局下界。

L1 正则化目标通常写成

minimize  F(w) = L(w) + λ‖w‖₁
其中 L(w) 为光滑的损失函数（如平方损失），λ > 0 为正则强度

L1 范数本身是凸函数，光滑损失若为凸（如最小二乘），则 F(w) 是凸函数。凸性带来两个关键好处：局部最优即全局最优；最优解集合本身是凸集。但 L1 范数在坐标为零处不可微，这正是稀疏性的来源，也是必须引入次梯度的原因。

次梯度：不可微点的“斜率集合”

对凸函数 f，若向量 g 满足对所有 y 都有 f(y) ≥ f(x) + gᵀ(y−x)，则称 g 是 f 在 x 处的次梯度。可微点处次梯度唯一，等于梯度；不可微点处次梯度是一个集合，称为次微分 ∂f(x)。对一维绝对值函数 |w|：

∂|w| = { sign(w) }      w ≠ 0
∂|w| = [−1, +1]          w = 0

这个结论是理解稀疏性的核心：当某个参数 w_j = 0 时，L1 项允许其“斜率”在 [−1, 1] 区间内任意取值，从而能够抵消损失函数在该坐标上的梯度。只要损失梯度落在该区间内，零点就可以成为最优解。反之，若损失梯度绝对值超过 λ，零点不再满足条件，参数被“推离”零。

KKT 条件：最优解的判定清单

考虑带等式与不等式约束的一般问题 min f₀(x)，约束 f_i(x) ≤ 0、h_j(x) = 0。在约束品性（如 Slater 条件）满足时，x* 为最优解当且仅当存在乘子 μ_i ≥ 0、ν_j，使以下条件同时成立：

• 原始可行性：f_i(x*) ≤ 0，h_j(x*) = 0；
• 对偶可行性：μ_i ≥ 0；
• 互补松弛：μ_i f_i(x*) = 0；
• 平稳性：0 ∈ ∂f₀(x*) + Σ μ_i ∂f_i(x*) + Σ ν_j ∂h_j(x*)。

对无约束的 L1 正则问题，KKT 平稳性退化为 0 ∈ ∂L(w*) + λ∂‖w*‖₁，逐坐标展开即：

w*_j ≠ 0 时：  ∂L/∂w_j + λ·sign(w*_j) = 0
w*_j = 0 时：  |∂L/∂w_j| ≤ λ

这就是软阈值结构的来源。以最小二乘 L(w) = ½‖Xw − y‖² 为例，若 X 的列近似正交，可得近似闭式解 w*_j ≈ S_λ(z_j)，其中 z_j = x_jᵀy 为最小二乘相关量，S_λ(z) = sign(z)·max(|z| − λ, 0)。当 |z_j| ≤ λ 时该坐标被精确置零，这正是 L1 相对 L2 产生稀疏解的机制。

对偶形式：从原始问题到约束投影

把 L1 范数写成支撑函数形式 ‖w‖₁ = max_{‖u‖∞ ≤ 1} uᵀw，可将原问题改写为 min_w max_{‖u‖∞≤1} L(w) + λuᵀw。交换 min 与 max（凸且满足约束品性时强对偶成立），得到对偶问题：

max_{‖u‖∞ ≤ 1}  min_w [ L(w) + λuᵀw ]

对平方损失，内层最小化可得 w = Xᵀ(y − λu) 形式的关系，对偶变量 u 被约束在无穷范数球内。对偶视角的实用价值在于：它把“稀疏性”转化为对偶变量落在超立方体边界上的问题，也解释了 L1 正则等价于对偶空间中的箱约束。下图给出从原始问题到 KKT 判据、再到稀疏结果的完整逻辑关系。

一个可手算的示例

设一维问题 L(w) = ½(w − 3)²，λ = 1，目标 F(w) = ½(w − 3)² + |w|。按 KKT 条件分情况讨论：若 w* ≠ 0，则 (w* − 3) + sign(w*) = 0。当 w* > 0 时得 w* = 2，验证 |2 − 3| = 1 ≤ λ 成立；当 w* < 0 时得 w* = 4，与假设矛盾。若 w* = 0，则需 |0 − 3| = 3 ≤ λ = 1，不成立。因此最优解为 w* = 2，未置零。若把 λ 提高到 4，则 w* = 0 时 |−3| = 3 ≤ 4 成立，最优解变为 0。这个例子清楚展示了 λ 如何通过“梯度是否落在 [−λ, λ] 内”决定参数存亡。

工程实现中的检查要点

实际使用坐标下降或近端梯度法求解 L1 问题时，KKT 条件可直接作为收敛判据。以近端梯度为例，每步执行 w ← S_{λη}(w − η∇L(w))，收敛时可检查两点：非零坐标处梯度与 λ·sign(w) 之和是否接近零；零坐标处梯度绝对值是否不超过 λ（允许数值容差，如 1e−6）。若某坐标反复在零与非零之间跳动，通常说明 λ 处于临界值附近，或步长 η 过大导致软阈值震荡，应减小步长或检查特征尺度是否归一化。

此外，特征未标准化时各列梯度量级差异很大，同一个 λ 对不同坐标的“置零门槛”并不公平，实践中应先对特征做标准化再调 λ。对偶视角还提示：λ 的上界可由 max_j |x_jᵀy| 估计，当 λ 超过该值时所有参数归零，这可作为 λ 搜索区间的起点。掌握凸性、次梯度与 KKT 这三件工具后，L1 正则化的稀疏现象就不再是经验观察，而是可推导、可验证的最优性结论。