机器学习数学基础 120 章

拉格朗日乘子法

层级：B｜按需

1. 等式约束如何改变最优条件

无约束最优要求梯度为零；在等式约束曲面上，只需沿可行切向没有下降方向。目标梯度可以非零，但必须与约束曲面的法向组合对齐。拉格朗日乘子把这个几何条件写成方程。

2. 单个等式约束

问题：

min⁡xf(x)s.t.h(x)=0.\min_x f(x) \quad\text{s.t.}\quad h(x)=0.

Lagrangian：

L(x,λ)=f(x)+λh(x).\mathcal L(x,\lambda)=f(x)+\lambda h(x).

在满足正则条件的局部最优点：

∇xL=∇f(x)+λ∇h(x)=0,\nabla_x\mathcal L =\nabla f(x)+\lambda\nabla h(x)=0, h(x)=0.h(x)=0.

λ\lambda 是乘子。符号也可定义为 f−λhf-\lambda h，会改变乘子符号但不改变 xx 解。

3. 几何解释

约束曲面 h(x)=0h(x)=0 的法向是 ∇h\nabla h。可行切向 vv 满足

∇hTv=0.\nabla h^Tv=0.

若 ∇f\nabla f 有切向分量，就能沿约束面下降；最优时该分量必须为零，所以

∇f=−λ∇h.\nabla f=-\lambda\nabla h.

目标等高线与约束曲线在最优点相切。

4. 例：固定长度最大化线性函数

max⁡xaTxs.t. xTx=1.\max_x a^Tx \quad\text{s.t. }x^Tx=1.

等价最小化 −aTx-a^Tx：

L=−aTx+λ(xTx−1).\mathcal L=-a^Tx+\lambda(x^Tx-1).

一阶条件：

−a+2λx=0⇒x=a2λ.-a+2\lambda x=0 \Rightarrow x=\frac{a}{2\lambda}.

单位约束给 x=±a/∥a∥x=\pm a/\|a\|，最大值取同方向

x∗=a∥a∥,x^*=\frac a{\|a\|},

与 Cauchy–Schwarz 结论一致。

5. 例：PCA 的特征值问题

最大化单位方向投影方差：

max⁡uuTSus.t. uTu=1.\max_u u^TSu \quad\text{s.t. }u^Tu=1.

Lagrangian：

L=uTSu−λ(uTu−1).\mathcal L=u^TSu-\lambda(u^Tu-1).

对 uu 求梯度：

2Su−2λu=0⇒Su=λu.2Su-2\lambda u=0 \Rightarrow Su=\lambda u.

所以驻点是协方差特征向量，目标值

uTSu=λ.u^TSu=\lambda.

最大值对应最大特征值。

6. 多个等式约束

hj(x)=0,quadj=1,…,q.h_j(x)=0,quad j=1,\ldots,q. L(x,λ)=f(x)+∑j=1qλjhj(x).\mathcal L(x,\lambda) =f(x)+\sum_{j=1}^{q}\lambda_jh_j(x).

一阶条件：

∇f(x)+∑jλj∇hj(x)=0,\nabla f(x)+\sum_j\lambda_j\nabla h_j(x)=0,

加上所有可行条件。约束梯度需要满足线性独立等资格条件，才能保证普通乘子存在。

7. 乘子的敏感性解释

将约束改为 h(x)=ch(x)=c，最优值记 p(c)p(c)。在适当光滑条件与符号约定下，Lagrange 乘子与最优值对约束右端的边际变化有关：

dpdc≈−λ∗.\frac{dp}{dc}\approx-\lambda^*.

因此 λ\lambda 又称影子价格：放宽一单位资源约束能改善多少目标。具体正负取决于约束写法。

8. Lagrangian 不是普通惩罚项

λ\lambda 不是预先固定的正则化超参数，而是与 xx 一起求解，使约束成立。等式约束乘子可正可负。把 λh(x)\lambda h(x) 加入目标后随意最小化 xx、固定 λ\lambda，一般不能保证满足约束。

9. 一阶条件不是充分条件

解 Lagrange 方程得到候选点，还需：

  • 检查所有候选和边界/奇异点；
  • 比较目标值；
  • 使用二阶约束条件；
  • 若问题凸（凸目标、仿射等式），一阶/KKT 条件可成为充分条件。

例：单位圆上最大/最小都满足同一类乘子方程。

10. 约束资格条件

若约束梯度在候选点为零或彼此相关，普通 Lagrange 条件可能无法正确刻画。例如 h(x)=x2=0h(x)=x^2=0 的可行点 x=0x=0 上 ∇h=0\nabla h=0。更一般理论使用 LICQ、MFCQ 等条件或 Fritz John 条件。

读机器学习推导时通常假设正则情形，但应知道条件不是无中生有。

11. 从等式到不等式

不等式 gi(x)≤0g_i(x)\le0 需要乘子 αi≥0\alpha_i\ge0 和互补松弛

αigi(x)=0.\alpha_i g_i(x)=0.

它们连同驻点与可行性形成 KKT 条件，将在下一章详细展开。SVM 推导的核心就在此。

易错点

  1. 乘子符号取决于 Lagrangian 定义，参数解不受影响。
  2. 乘子是待求变量，不是普通手调正则系数。
  3. Lagrange 一阶条件通常只是必要条件。
  4. 必须同时满足原始约束。
  5. 约束梯度退化时需检查资格条件。

常见问答

Q1：为什么不直接把等式约束代入消元？

能方便消元时当然可以；拉格朗日法更对称、可扩展到多维与对偶，并保留敏感性信息。

Q2：PCA 为什么最大化方差会得到特征向量？

单位长度约束的 Lagrange 一阶条件正是 Su=λuSu=\lambda u。

Q3：Lagrange 乘子和正则化 lambda 是一回事吗？

符号常相同但角色不同。乘子由约束最优性决定；正则化系数通常由用户/验证过程选择。

练习

  1. 在约束 x+y=1x+y=1 下最小化 x2+y2x^2+y^2。
  2. 写出其 Lagrangian 与一阶条件。
  3. 固定 xTx=1x^Tx=1 最大化 xTAxx^TAx 会得到什么方程？
  4. 为什么目标梯度在约束最优点不必为零？
  5. 乘子的“影子价格”如何解释？

答案与提示

  1. 对称性或求解得 x=y=1/2x=y=1/2。
  2. x2+y2+λ(x+y−1)x^2+y^2+\lambda(x+y-1)；2x+λ=0,2y+λ=0,x+y=12x+\lambda=0,2y+\lambda=0,x+y=1。
  3. Ax=λxAx=\lambda x（若 AA 对称，常数因子吸收进乘子）。
  4. 只需沿可行切向的一阶变化为零，梯度可由约束法向抵消。
  5. 约束右端小幅放宽时最优值的边际变化率，符号依写法。