机器学习数学基础 120 章

约束、可行域与投影优化

层级：B｜按需

1. 为什么模型参数需要受限

概率必须非负且和为 1，协方差要正定，SVM 有间隔约束，稀疏模型可限制范数预算。约束不仅表达数学合法性，也编码业务与归纳偏好。

2. 可行域

C=x:gi(x)≤0,hj(x)=0.\mathcal C={x:g_i(x)\le0, h_j(x)=0}.

可行点满足所有约束，不可行点不允许。优化目标只在可行域比较：

min⁡x∈Cf(x).\min_{x\in\mathcal C}f(x).

若 C=∅\mathcal C=\varnothing，问题不可行；若目标沿可行方向无下界，问题无界；二者要区分。

3. 典型可行域

  • 非负正交象限：xi≥0x_i\ge0；
  • box：li≤xi≤uil_i\le x_i\le u_i；
  • L2 球：∥x∥2≤R\|x\|_2\le R；
  • L1 球：∥x∥1≤R\|x\|_1\le R；
  • 概率单纯形：pi≥0,∑ipi=1p_i\ge0,\sum_ip_i=1；
  • 仿射集：Ax=bAx=b；
  • PSD 锥：X⪰0X\succeq0。

前述集合均为凸集，因此与凸目标组合可形成凸优化。

4. 边界最优的梯度

无约束内部最优需要 ∇f=0\nabla f=0。约束最优位于边界时，梯度可以不为零；只要所有可行下降方向都被边界挡住。

例：

min⁡x(x−3)2s.t. x≤1.\min_x(x-3)^2\quad\text{s.t. }x\le1.

最优 x=1x=1，梯度 2(x−3)=−4≠02(x-3)=-4\ne0。负梯度指向右侧，但右移不可行。

5. Euclidean 投影

点 zz 到闭凸集 C\mathcal C 的投影：

ΠC(z)=arg⁡min⁡x∈C12∥x−z∥22.\Pi_\mathcal C(z) =\arg\min_{x\in\mathcal C}\frac12\|x-z\|_2^2.

闭凸集上投影唯一。常见：

  • 区间/box：逐坐标 clip；
  • 非负集合：max⁡(zi,0)\max(z_i,0)；
  • L2 球：若超出半径，按比例缩到边界；
  • 仿射子空间：正交投影公式；
  • 单纯形：不能只逐坐标 clip，需要排序阈值等算法。

6. 投影梯度下降

xt+1=ΠC(xt−ηt∇f(xt)).x_{t+1} =\Pi_\mathcal C(x_t-\eta_t\nabla f(x_t)).

先做无约束梯度步，再投回可行域。投影可能改变方向，因此不能把最终移动简单理解为负梯度。

若投影计算本身昂贵，可用 Frank–Wolfe、障碍法、增广 Lagrangian 或重新参数化。

7. 最优性条件

闭凸集上可微凸函数的最优 x∗x^* 满足

∇f(x∗)T(x−x∗)≥0∀x∈C.\nabla f(x^*)^T(x-x^*)\ge0 \quad\forall x\in\mathcal C.

这表示从 x∗x^* 指向任何可行点的方向都没有负的一阶变化。无约束时可选任意方向，退化为梯度为零。

也可用法锥写

−∇f(x∗)∈NC(x∗).-\nabla f(x^*)\in N_\mathcal C(x^*).

约束边界的法向力抵消目标下降力，是 KKT 的几何基础。

8. 惩罚法

把违反约束加入目标：

min⁡xf(x)+ρ∑i[gi(x)]+2+ρ∑jhj(x)2.\min_x f(x)+\rho\sum_i[g_i(x)]_+^2 +\rho\sum_jh_j(x)^2.

[u]+=max⁡(u,0)[u]_+=\max(u,0)。ρ\rho 大时强迫可行，但太大会造成病态；有限 ρ\rho 的平方惩罚通常不能保证严格满足约束。

L1 型精确惩罚在适当条件下有限权重即可得到可行最优，但非光滑。

9. 障碍法

对 gi(x)<0g_i(x)<0 使用对数障碍：

f(x)−μ∑ilog⁡(−gi(x)).f(x)-\mu\sum_i\log(-g_i(x)).

接近边界时障碍趋无穷，从可行域内部阻止越界。逐步减小 μ\mu 沿中心路径接近约束最优。要求初始严格可行点，是内点法基础。

10. 重新参数化

可用变换自动满足约束：

  • 正数：x=ezx=e^z 或 softplus；
  • 概率单纯形：p=softmax⁡(z)p=\operatorname{softmax}(z)；
  • 协方差正定：Σ=LLT\Sigma=LL^T，LL 对角正；
  • 单位向量：u=v/∥v∥u=v/\|v\|。

优点是无需显式约束；缺点是改变几何、可能引入冗余或饱和，边界值有时无法精确达到。

11. Frank–Wolfe

对凸紧集，Frank–Wolfe 每步解线性子问题：

st=arg⁡min⁡s∈C∇f(xt)Ts,s_t=\arg\min_{s\in\mathcal C} \nabla f(x_t)^Ts,

再做凸组合

xt+1=(1−γt)xt+γtst.x_{t+1}=(1-\gamma_t)x_t+\gamma_ts_t.

它避免投影，适合投影贵而线性最小化便宜的集合，如核范数球；迭代解常保持稀疏/低秩结构。

易错点

  1. 边界最优梯度不必为零。
  2. 对多个约束逐个投影一般不等于投影到交集。
  3. clip 后概率通常不再和为 1。
  4. 大惩罚系数会导致优化病态，不能无限增大而不处理。
  5. 重新参数化可能改变最优路径和数值稳定性。

常见问答

Q1：权重裁剪是投影优化吗？

对 box 约束逐元素 clip 正是 Euclidean 投影；对其他约束随意裁剪未必是正确投影。

Q2：正则化与约束是否等价？

对许多凸问题，某个惩罚权重与某个范数预算可对应同一解，但映射依数据且不一定一一；非凸或不可行情形更复杂。

Q3：为什么 Softmax 参数有冗余？

所有 logits 同加常数不改变概率，故参数化不是一一映射；可固定一个 logit 或接受冗余。

练习

  1. 求标量 z=3z=3 到区间 [−1,2][-1,2] 的投影。
  2. 求向量 (3,4)(3,4) 到半径 2 的 L2 球投影。
  3. 说明边界最优梯度可非零的例子。
  4. 为什么逐元素把负概率截为 0 后还不够？
  5. 给正定矩阵写一种重新参数化。

答案与提示

  1. 2。
  2. 原范数 5，缩放为 (6/5,8/5)(6/5,8/5)。
  3. 本章 min⁡(x−3)2,s.t.x≤1\min(x-3)^2,s.t.x\le1。
  4. 分量和一般不等于 1，还需投影/归一化且注意最小距离标准。
  5. Σ=LLT\Sigma=LL^T，并令 LL 对角通过指数/softplus 为正。