[omscs-ml] 拉格朗日乘子法：从直觉到 SVM 的完整入门

核心目标：理解“为什么要引入拉格朗日乘子”、怎么算、以及它为什么会出现在 SVM 里。

---

1. 问题背景：什么是“有约束优化”？

普通优化问题长这样：

$$\min_{x,y} f(x,y)$$

比如：

$$\min_{x,y} x^2+y^2$$

这个问题的最优解很明显：

$$x=0,\quad y=0$$

因为 $x^2+y^2$ 表示点 $(x,y)$ 到原点的距离平方，离原点最近当然是在原点。

但是如果加一个限制：

$$x+y=1$$

问题就变成：

$$\min_{x,y} x^2+y^2$$

subject to:

$$x+y=1$$

这时你不能随便取 $x,y$，必须在直线 $x+y=1$ 上找最优点。

这类问题就叫 有约束优化问题。

---

2. 拉格朗日乘子法的核心想法

假设我们想优化：

$$\min f(x,y)$$

并且满足约束：

$$g(x,y)=0$$

拉格朗日方法会构造一个新的函数：

$$\mathcal L(x,y,\lambda)=f(x,y)+\lambda g(x,y)$$

这里：

• $\mathcal L$ 叫 Lagrangian，也就是拉格朗日函数

• $\lambda$ 叫 Lagrange multiplier，也就是拉格朗日乘子

• $g(x,y)=0$ 是约束条件

然后我们对所有变量求偏导，并令它们等于 0：

$$\frac{\partial \mathcal L}{\partial x}=0$$ $$\frac{\partial \mathcal L}{\partial y}=0$$ $$\frac{\partial \mathcal L}{\partial \lambda}=0$$

注意：

$$\frac{\partial \mathcal L}{\partial \lambda}=g(x,y)$$

所以对 $\lambda$ 求导等于 0，其实就是把原来的约束条件带回来了。

---

3. 例子 1：在直线 $x+y=1$ 上找离原点最近的点

问题：

$$\min_{x,y} x^2+y^2$$

subject to:

$$x+y=1$$

先把约束写成标准形式：

$$g(x,y)=x+y-1=0$$

构造 Lagrangian：

$$\mathcal L(x,y,\lambda)=x^2+y^2+\lambda(x+y-1)$$

分别求偏导：

$$\frac{\partial \mathcal L}{\partial x}=2x+\lambda=0$$ $$\frac{\partial \mathcal L}{\partial y}=2y+\lambda=0$$ $$\frac{\partial \mathcal L}{\partial \lambda}=x+y-1=0$$

由前两个式子：

$$2x+\lambda=0$$ $$2y+\lambda=0$$

所以：

$$2x=2y$$

因此：

$$x=y$$

代入约束：

$$x+y=1$$

得到：

$$2x=1$$

所以：

$$x=\frac12,\quad y=\frac12$$

答案是：

$$\boxed{x=\frac12,\quad y=\frac12}$$

也就是说，直线 $x+y=1$ 上离原点最近的点是：

$$\left(\frac12,\frac12\right)$$

---

4. 几何直觉：为什么 $\nabla f$ 和 $\nabla g$ 要平行？

拉格朗日乘子法背后的关键几何直觉是：

在最优点，目标函数的等高线和约束曲线刚好相切。

对于目标函数：

$$f(x,y)=x^2+y^2$$

它的等高线是很多圆：

$$x^2+y^2=c$$

约束：

$$x+y=1$$

是一条直线。

我们要做的事情是：

找一个尽可能小的圆，让它刚好碰到直线 $x+y=1$。

当圆刚好碰到直线时，它们是相切的。
相切意味着两条曲线在那个点的切线方向相同。

而梯度方向永远垂直于等高线。

所以在最优点：

$$\nabla f$$

和

$$\nabla g$$

方向平行。

数学上写成：

$$\nabla f = -\lambda \nabla g$$

或者：

$$\nabla f = \lambda \nabla g$$

符号正负取决于你怎么定义 Lagrangian，比如写成 $f+\lambda g$ 还是 $f-\lambda g$。
核心是不变的：两个梯度平行。

---

5. 例子 2：固定周长，最大化长方形面积

假设一个长方形的长是 $x$，宽是 $y$。

面积是：

$$A=xy$$

周长固定为 20：

$$2x+2y=20$$

也就是：

$$x+y=10$$

问题是：

$$\max_{x,y} xy$$

subject to:

$$x+y=10$$

构造 Lagrangian：

$$\mathcal L(x,y,\lambda)=xy+\lambda(x+y-10)$$

求偏导：

$$\frac{\partial \mathcal L}{\partial x}=y+\lambda=0$$ $$\frac{\partial \mathcal L}{\partial y}=x+\lambda=0$$ $$\frac{\partial \mathcal L}{\partial \lambda}=x+y-10=0$$

前两个式子说明：

$$y=-\lambda$$ $$x=-\lambda$$

所以：

$$x=y$$

代入约束：

$$x+y=10$$

得到：

$$x=5,\quad y=5$$

所以固定周长时，面积最大的长方形是正方形。

最大面积是：

$$A=5\times 5=25$$

---

6. $\lambda$ 到底是什么？

$\lambda$ 不是原问题中的变量，而是为了处理约束引入的辅助变量。

可以直观理解成：

$\lambda$ 衡量约束对最优值的影响强度。

如果一个约束很“卡住”最优解，它对应的乘子往往不为 0。
如果一个约束对最优解没有影响，它对应的乘子可能是 0。

在机器学习里，尤其是 SVM 里面，这个理解非常重要。

---

7. 等式约束 vs 不等式约束

前面的例子都是等式约束：

$$g(x)=0$$

比如：

$$x+y=1$$

但是机器学习里更常见的是不等式约束：

$$g(x)\le 0$$

比如 SVM 的 hard-margin 约束：

$$y_i(w^T x_i+b)\ge 1$$

可以改写为：

$$1-y_i(w^T x_i+b)\le 0$$

这种不等式约束需要用 KKT 条件。

---

8. 不等式约束例子：最小化 $x^2$，但要求 $x\ge 1$

问题：

$$\min_x x^2$$

subject to:

$$x\ge 1$$

直觉上，$x^2$ 最小想去 $x=0$，但是约束要求 $x\ge 1$。
所以最优解显然是：

$$x=1$$

现在用拉格朗日方法看一遍。

先把约束写成：

$$1-x\le 0$$

构造 Lagrangian：

$$\mathcal L(x,\lambda)=x^2+\lambda(1-x)$$

不等式约束下要求：

$$\lambda\ge 0$$

对 $x$ 求导：

$$\frac{d\mathcal L}{dx}=2x-\lambda=0$$

所以：

$$\lambda=2x$$

KKT 条件还要求：

$$\lambda(1-x)=0$$

这个叫 complementary slackness，中文常翻译成 互补松弛条件。

它的意思是：

一个不等式约束要么刚好卡住最优解，要么它对应的乘子为 0。

在这个例子里，最优解是：

$$x=1$$

所以：

$$\lambda=2$$

这里约束 $x\ge 1$ 是 active 的，也就是它真的限制住了最优解。

---

9. 什么是 active constraint？

考虑约束：

$$x\ge 1$$

如果最优解是：

$$x=1$$

说明这个约束刚好卡住了最优解，这叫 active constraint。

如果最优解是：

$$x=5$$

那么约束 $x\ge 1$ 没有真正限制最优解，这叫 inactive constraint。

在 KKT 条件中：

$$\lambda g(x)=0$$

表示：

• 如果约束 inactive，那么 $\lambda=0$

• 如果 $\lambda>0$，那么约束必须 active

---

10. KKT 条件快速总结

对于问题：

$$\min_x f(x)$$

subject to:

$$g_i(x)\le 0$$

Lagrangian 是：

$$\mathcal L(x,\lambda)=f(x)+\sum_i \lambda_i g_i(x)$$

KKT 条件包括：

1. Stationarity

$$\nabla_x \mathcal L(x,\lambda)=0$$

意思是对原变量求导为 0。

2. Primal feasibility

$$g_i(x)\le 0$$

意思是原约束必须满足。

3. Dual feasibility

$$\lambda_i\ge 0$$

意思是不等式约束对应的乘子必须非负。

4. Complementary slackness

$$\lambda_i g_i(x)=0$$

意思是每个约束要么 active，要么对应乘子为 0。

---

11. 拉格朗日和 SVM 的关系

Hard-margin SVM 的 primal problem 是：

$$\min_{w,b} \frac12 \|w\|^2$$

subject to:

$$y_i(w^T x_i+b)\ge 1$$

这里：

• $w$ 是超平面的法向量

• $b$ 是偏置

• $x_i$ 是第 $i$ 个样本

• $y_i\in\{-1,+1\}$ 是标签

目标函数：

$$\frac12 \|w\|^2$$

的作用是让 margin 尽可能大。

约束：

$$y_i(w^T x_i+b)\ge 1$$

表示每个点不仅要分类正确，而且要离分界线有一定距离。

把约束改成标准形式：

$$1-y_i(w^T x_i+b)\le 0$$

于是每个样本都有一个拉格朗日乘子：

$$\alpha_i\ge 0$$

SVM 的 Lagrangian 是：

$$\mathcal L(w,b,\alpha) = \frac12\|w\|^2 + \sum_i \alpha_i[1-y_i(w^T x_i+b)]$$

---

12. SVM 里的 $\alpha_i$ 是什么？

在 SVM 里，每个样本点都有一个约束：

$$y_i(w^T x_i+b)\ge 1$$

所以每个样本点都有一个对应的拉格朗日乘子：

$$\alpha_i$$

如果某个点离分界线很远，它的约束并不关键，那么：

$$\alpha_i=0$$

如果某个点刚好在 margin 上，它的约束很关键，那么：

$$\alpha_i>0$$

这些 $\alpha_i>0$ 的点就是：

$$\text{support vectors}$$

也就是支持向量。

所以 SVM 的一个重要结论是：

最终分类边界主要由 support vectors 决定，而不是由所有训练点平均决定。

---

13. 为什么 SVM 里面最后会出现点积？

从 SVM 的 Lagrangian 出发，对 $w$ 求导：

$$\frac{\partial \mathcal L}{\partial w} = w-\sum_i \alpha_i y_i x_i=0$$

所以：

$$w=\sum_i \alpha_i y_i x_i$$

这说明最终的法向量 $w$ 是由训练样本线性组合出来的。

进一步推导 dual problem 时，会出现：

$$x_i^T x_j$$

也就是样本之间的 dot product。

这就是 kernel trick 的入口：

如果我们把点积替换成 kernel function：

$$K(x_i,x_j)$$

就可以得到非线性的 SVM。

---

14. 一个学习路线

如果你是第一次学，可以按这个顺序理解：

1. 先理解普通无约束优化：求导等于 0
2. 再理解等式约束：引入 $\lambda$
3. 再理解几何图像：等高线和约束曲线相切
4. 再理解不等式约束：KKT 条件
5. 最后看 SVM：每个样本一个 $\alpha_i$
6. 再看 dual problem 和 kernel trick

---

15. 一页总结

等式约束

问题：

$$\min f(x)$$

subject to:

$$g(x)=0$$

Lagrangian：

$$\mathcal L(x,\lambda)=f(x)+\lambda g(x)$$

求解：

$$\nabla_x \mathcal L=0$$ $$\frac{\partial \mathcal L}{\partial \lambda}=0$$

---

不等式约束

问题：

$$\min f(x)$$

subject to:

$$g_i(x)\le 0$$

Lagrangian：

$$\mathcal L(x,\lambda)=f(x)+\sum_i \lambda_i g_i(x)$$

KKT：

$$\nabla_x \mathcal L=0$$ $$g_i(x)\le 0$$ $$\lambda_i\ge 0$$ $$\lambda_i g_i(x)=0$$

---

SVM

Primal problem：

$$\min_{w,b} \frac12\|w\|^2$$

subject to:

$$y_i(w^T x_i+b)\ge 1$$

Lagrangian：

$$\mathcal L(w,b,\alpha) = \frac12\|w\|^2 + \sum_i \alpha_i[1-y_i(w^T x_i+b)]$$

Support vector：

$$\alpha_i>0$$

Non-support vector：

$$\alpha_i=0$$

---

16. 小练习

练习 1

求：

$$\min_{x,y} x^2+y^2$$

subject to:

$$2x+y=4$$

提示：构造

$$\mathcal L=x^2+y^2+\lambda(2x+y-4)$$

---

练习 2

求：

$$\max_{x,y} xy$$

subject to:

$$x+y=12$$

答案应该会告诉你：固定周长时，正方形面积最大。

---

练习 3

求：

$$\min_x (x-2)^2$$

subject to:

$$x\ge 5$$

直觉答案是 $x=5$。
你可以试着用 KKT 条件验证它。

---

17. 最后一句话

拉格朗日方法最重要的不是背公式，而是理解这句话：

当你在约束条件下优化一个目标时，最优点不是“目标函数自己最想去的地方”，而是“目标函数想下降的方向刚好被约束挡住的地方”。

这就是为什么在最优点：

$$\nabla f$$

会和约束的梯度：

$$\nabla g$$

平行。

而在 SVM 里，每个训练样本的约束都有一个乘子 $\alpha_i$。
那些 $\alpha_i>0$ 的点，就是真正决定分类边界的 support vectors。