拉格朗日乘子法（1）：从无约束到等式约束

小象实战讲义 · 机器学习算法精讲

接下来这两节，讲的是通往 SVM 最大间隔的数学准备——拉格朗日乘子法和里面的 KKT 条件。原计划是先讲 SVM 的最大 margin、再讲里边的优化，但讲师在开场特意换了顺序：先把优化讲完，之后再学 SVM 就可能更容易些。理由也说得很直白：今天学机器学习的人，多多少少都看过 SVM、看过 maximum margin，但一到里边的数学推导就有些不清楚——也许最重要的部分，恰恰就是怎么去做这个拉格朗日乘子和优化。不止一位同学说过：关键的就在这个部分。

💡 核心导读

• 优化的两种形态：无约束（$\mathbf{x}$ 随便取，求导置零 / 梯度下降）与有约束（加 s.t. 限制条件，分等式 $h_i(\mathbf{x})=0$ 与不等式 $g_j(\mathbf{x})\le 0$）。
• 几何路线：本节全程用几何的方式、不用代数的方式——等高线（iso-contour）+ 可行域（feasible region）。
• 两个移动条件：在约束曲面上每走一小步 $\mu\Delta\mathbf{x}$，既要仍然在曲面上，又要让目标函数变小。
• 点积判方向：$\Delta\mathbf{x}$ 与负梯度的点积大于零（锐角）⟺ 这一步让 $f$ 下降——本节一路推到的核心条件。

优化：我们已经在做什么

先回顾已经会的东西。学过的线性算法里，很重要的一个部分就是构造一个 cost function $J(\theta)$，$\theta$ 是需要调整的参数，然后在这个大的空间里面去做优化。我们已经知道的做法是梯度下降：从某个起点出发，一步一步走到最好的那个点 $\theta^*$。优化对整个机器学习非常重要。

今天要讲的优化稍微复杂一些：有约束条件的优化。

先看一般的形式。整个问题叫 optimization——构造一个函数之后，找到里面的最优解，尤其当它是高维空间的函数时，这件事显得尤其重要。比如我们想求 $f(x)$ 的最小值：如果 $x$ 属于 $\mathbb{R}$（或者 $\mathbb{R}^N$），没有任何附加限制，这叫无约束优化（unconstrained optimization）；如果加了限制条件，一般写成 subject to，缩写 s.t.——比如要求 $h(x)=0$，合起来就是”在保证 $h(x)=0$ 的条件下优化 $f(x)$“，这叫有约束优化。

约束条件往往不止一个。等式可以有多个：$h_1(x)=0$、$h_2(x)=0$，比如 $x_1 + x_2 - 3 = 0$ 是一个，$x_1^2 + x_2^2 - 18 = 0$ 又是一个。还有一种不等式约束 $g(x) \le 0$，比如 $x_1 + x_2 - 3 \le 0$。有同学问：为什么没有大于等于 0 的写法？——因为总可以通过加负号变换出来：想让它 $\ge 0$，两边乘 $-1$ 不就变成 $\le 0$ 了。习惯上统一写成 $\le 0$。一般地，等式约束编号 $i = 1 \ldots l$，不等式约束编号 $j = 1 \ldots m$。

本节的路线就是讲师说的那句话：从无条件的优化，到等式的优化，再到不等式的优化，一步步详细讲。

无约束优化：一分钟回顾

想求 $\min f(x)$，$x$ 没有任何约束条件、$x \in \mathbb{R}$。比如 $f(x) = x^2$，怎么做？大家都记得：求导，令 $f'(x) = 2x = 0$，推出 $x = 0$——这一点就是最优值，我们叫它 $x^*$。高维也一样，只是此时 $x$ 是向量，要求它的每一个分量的偏导都等于 0（$\partial f / \partial x_j = 0$，$j = 1 \ldots n$）。这是已经会的东西，不再多说。

等式约束：先把它画出来

现在看最简单的有约束情况——等式约束 $h(x) = 0$。讲师给了一个经典例子：

$$\min f(x_1, x_2) = x_1 + x_2 \quad \text{s.t.} \quad h(x_1, x_2) = x_1^2 + x_2^2 - 2 = 0$$

给了这个限制条件之后怎么求？用几何的方式，不用代数的方式。

先画目标函数 $f$。 在 $x_1$、$x_2$ 两个坐标轴构成的平面上，$x_1 + x_2 = 0$ 是一条过原点的直线；往上、往右平移，$x_1 + x_2 = 1$、$x_1 + x_2 = 2$ 是一组平行的直线；往下、往左，$x_1 + x_2 = -1$、$= -2$……当然不止这几条——$x_1 + x_2$ 等于几都行，等于 1.5、等于 3.6 也各有一条直线，任何一个点上都有一条直线穿过，我们只是取了几条关键的。这族直线叫 iso-contour：iso 是”等高”，contour 是”等高线”——它们是 $f$ 的等高线。

再画约束 $h$。 $x_1^2 + x_2^2 = 2$ 是一个圆：圆心在原点 $(0,0)$，半径 $\sqrt{2}$。圆周上的任何一点都满足 $x_1^2 + x_2^2 - 2 = 0$，也就是 $h(x) = 0$——整个圆都是合理的取值范围。这就叫约束条件：$h(x)$ 必须等于 0，满足条件的所有 $x$ 都落在这条（红色的）圆上，这个圆往后有个名字叫 feasible region（可行域）——feasible 就是”可行的”，region 是”区域”：任何落在这里边的点都是可行的；一旦离开这个圆，约束就被破坏了。

于是优化问题变成了一个纯几何问题：在这条红圆上找一个最合适的点，使它的横、纵坐标相加（也就是 $f$）最小。把圆上的 $f$ 值实际扫一遍：

# ---- 在约束圆 x1^2 + x2^2 = 2 上扫描 f = x1 + x2 的取值 ----
import math

r = math.sqrt(2)

def h(x1, x2):
    return x1 * x1 + x2 * x2 - 2

def f(x1, x2):
    return x1 + x2

print("约束圆: x1^2 + x2^2 = 2 (半径 sqrt(2)), 目标 f = x1 + x2")
print("圆上 8 个关键点 (每 45 度) 的 f 值与约束检查:")
for deg in (0, 45, 90, 135, 180, 225, 270, 315):
    t = math.radians(deg)
    x1, x2 = r * math.cos(t), r * math.sin(t)
    print(f"  {deg:3d} 度: ({x1:+.4f}, {x2:+.4f})  f = {f(x1, x2):+.4f}  h = {h(x1, x2):+.1e}")

print("\n细扫 (1 度步长, 360 个点):")
fmin = fmax = None
cnt_min = cnt_max = 0
for deg in range(360):
    t = math.radians(deg)
    x1, x2 = r * math.cos(t), r * math.sin(t)
    v = f(x1, x2)
    if fmin is None or v < fmin - 1e-12:
        fmin, pmin, cnt_min = v, (x1, x2), 1
    elif abs(v - fmin) < 1e-9:
        cnt_min += 1
    if fmax is None or v > fmax + 1e-12:
        fmax, pmax, cnt_max = v, (x1, x2), 1
    elif abs(v - fmax) < 1e-9:
        cnt_max += 1
print(f"  f 最小 = {fmin:.4f}, 只出现在 ({pmin[0]:+.4f}, {pmin[1]:+.4f}), 共 {cnt_min} 个点")
print(f"  f 最大 = {fmax:.4f}, 只出现在 ({pmax[0]:+.4f}, {pmax[1]:+.4f}), 共 {cnt_max} 个点")
print(f"  检算: 该点 h = {h(pmin[0], pmin[1]):+.1e}, 1^2 + 1^2 = 2  <- 在圆上")

约束圆: x1^2 + x2^2 = 2 (半径 sqrt(2)), 目标 f = x1 + x2
圆上 8 个关键点 (每 45 度) 的 f 值与约束检查:
    0 度: (+1.4142, +0.0000)  f = +1.4142  h = +4.4e-16
   45 度: (+1.0000, +1.0000)  f = +2.0000  h = +8.9e-16
   90 度: (+0.0000, +1.4142)  f = +1.4142  h = +4.4e-16
  135 度: (-1.0000, +1.0000)  f = +0.0000  h = +4.4e-16
  180 度: (-1.4142, +0.0000)  f = -1.4142  h = +4.4e-16
  225 度: (-1.0000, -1.0000)  f = -2.0000  h = +4.4e-16
  270 度: (-0.0000, -1.4142)  f = -1.4142  h = +4.4e-16
  315 度: (+1.0000, -1.0000)  f = -0.0000  h = +0.0e+00

细扫 (1 度步长, 360 个点):
  f 最小 = -2.0000, 只出现在 (-1.0000, -1.0000), 共 1 个点
  f 最大 = 2.0000, 只出现在 (+1.0000, +1.0000), 共 1 个点
  检算: 该点 h = +4.4e-16, 1^2 + 1^2 = 2  <- 在圆上

读这张表。圆上全是可行点：每一点的 $h$ 都是 $10^{-16}$ 量级的浮点毛边（数学上精确为 0）。两个特殊点：$(1, 1)$ 处 $f = +2$ 是圆上最大，$(-1, -1)$ 处 $f = -2$ 是圆上最小——检算 $1^2 + 1^2 = 2$，这两点确实在圆上。“相切”的数值含义：细扫 360 个点，$f = -2$ 在整个圆上只出现一次——也就是说等高线 $x_1 + x_2 = -2$ 与圆只碰 $(−1,−1)$ 这一个点、碰一下就分开，这正是”相切”：想再往左下挪一点点等高线，它就与圆无交点了（约束不允许 $f$ 更小）；往右上挪，与圆交成两个点（还有更小的取值）。上侧的 $(1,1)$ 同理，是等高线 $x_1 + x_2 = +2$ 与圆的切点。问题从”带约束的优化”变成了”在圆上找相切的那条等高线”——纯几何。

在圆上走：每一步要满足什么

图画完了，接下来要构造稍微复杂一点的数学。设想我们站在圆上的某一点（记作 $x$），想沿圆移动一小步。这一步写成 $\mu \cdot \Delta x$：

• $\Delta x$ 是一个无穷小的移动单位——比如 $0.000001$ 这种量级，趋于无穷小；
• $\mu$ 是一个缩放常数，代表每次移动多少个 $\Delta x$——跟以前学的梯度下降里的步长一个角色。

这一步移动要满足两个条件。

条件一（可行性）：移动完了之后，这个点仍然在圆上——$h(x + \mu\Delta x) = 0$。一旦离开圆，约束条件就被破坏了，后面的讨论全部作废。

条件二（优化性）：移动完了之后，目标函数要比出发点更小——$f(x + \mu\Delta x) < f(x)$。我们求的是最小值，所以每一次移动都应该让 $f$ 变小，这才是我们期望的移动方向。

于是整个过程可以想象成：在圆上从一个点出发，沿着某一个方向不断地移动，每次移动都比上一次的 $f$ 值小，一路移动到再也找不到这样的方向为止——那当然就是最好的结果了。

要判断”哪个方向能让 $f$ 变小”，就需要 $f$ 的梯度。$f(x_1, x_2) = x_1 + x_2$ 有两个维度，分别求偏导：对 $x_1$ 求偏导等于 1，对 $x_2$ 求偏导也等于 1，写成列向量

$$\nabla f = \begin{bmatrix}\partial f / \partial x_1\\ \partial f / \partial x_2\end{bmatrix} = \begin{bmatrix}1\\ 1\end{bmatrix}$$

而我们更关心的是它的负梯度 $-\nabla f = (-1, -1)$。原因大家记得：梯度下降的更新式 $\theta := \theta - \alpha\nabla J$，前面是一个减号——我们沿着负梯度方向走，函数值才下降。

点积定符号：锐角、直角、钝角

那么移动方向 $\Delta x$ 与负梯度方向应该有什么样的关系？这是一个特别重要的点。先看两个任意向量 $a$、$b$ 的点积与夹角的关系（点积等于模长乘夹角的余弦——讲师现场两次口误说成 sin，此处按正确口径写）：

• 夹角小于 90 度（锐角）：$a \cdot b > 0$——两向量大致往一个方向走，一个在另一个上的投影是正的；
• 夹角等于 90 度（垂直）：$a \cdot b = 0$——两个方向没有任何关系、没有 correlation（第 5.2 节余弦相似度里的老结论）；
• 夹角大于 90 度（钝角）：$a \cdot b < 0$——方向相反。

把它落到我们的问题上：$\Delta x$ 乘上负梯度大于 0，就是核心条件——

$$\Delta x \cdot (-\nabla f) > 0 \quad\Longleftrightarrow\quad \Delta x \text{ 与负梯度成锐角} \quad\Longleftrightarrow\quad \text{这一步让 } f \text{ 变小}$$

从圆上一点实际试三个方向：

# ---- 点积三分支: Delta x 与负梯度的夹角如何决定 f 的升降 ----
import math

grad_f = (1, 1)
neg_grad = (-1, -1)

def dot(a, b):
    return a[0] * b[0] + a[1] * b[1]

def cos_angle(a, b):
    return dot(a, b) / math.sqrt(dot(a, a) * dot(b, b))

x0 = (0.0, math.sqrt(2))          # 圆上 90 度处的点
f0 = x0[0] + x0[1]
eps = 0.001

print(f"梯度 grad f = (1, 1), 负梯度 = (-1, -1)  (梯度下降: theta := theta - alpha*grad)")
print(f"从圆上一点 ({x0[0]:.4f}, {x0[1]:.4f}) 出发, 试探三个方向 (e = {eps}):")
print()
moves = [
    ("锐角方向 (-1, -1)", (-1, -1)),
    ("垂直方向 (-1,  1)", (-1, 1)),
    ("钝角方向 ( 1,  1)", (1, 1)),
]
for name, d in moves:
    p = dot(d, neg_grad)
    x_new = (x0[0] + eps * d[0], x0[1] + eps * d[1])
    f_new = x_new[0] + x_new[1]
    print(f"{name}: delta_x · (-grad) = {p:+.0f}  (cos 夹角 = {cos_angle(d, neg_grad):+.1f})")
    print(f"    f: {f0:.4f} -> {f_new:.4f}  (变化 {f_new - f0:+.4f})")

梯度 grad f = (1, 1), 负梯度 = (-1, -1)  (梯度下降: theta := theta - alpha*grad)
从圆上一点 (0.0000, 1.4142) 出发, 试探三个方向 (e = 0.001):

锐角方向 (-1, -1): delta_x · (-grad) = +2  (cos 夹角 = +1.0)
    f: 1.4142 -> 1.4122  (变化 -0.0020)
垂直方向 (-1,  1): delta_x · (-grad) = +0  (cos 夹角 = +0.0)
    f: 1.4142 -> 1.4142  (变化 +0.0000)
钝角方向 ( 1,  1): delta_x · (-grad) = -2  (cos 夹角 = -1.0)
    f: 1.4142 -> 1.4162  (变化 +0.0020)

三个方向、三种命运：点积 $+2$（锐角）的那一步让 $f$ 从 1.4142 降到 1.4122；点积 $0$（垂直）的一步 $f$ 纹丝不动；点积 $-2$（钝角）的一步反而升到 1.4162。这就是”沿哪个方向走才不断优化”的判据：每一步的 $\Delta x$ 与负梯度的点积要大于零。

一句诚实的注：这三个试探方向只用来演示点积符号与 $f$ 升降的对应关系；真正在圆上走的时候，$\Delta x$ 还必须同时满足条件一（走出这一步还在圆上）——既要在圆上、又要让 $f$ 降，两个条件拧在一起才是完整的题目。另外，约束函数 $h$ 自己也是一个函数，它也有梯度——$h$ 的梯度长什么样、指向哪里，跟我们这张图怎么接上，正是下一节开场要做的事。（本节视频就在这里收尾。）

📝 动手练一练

1. 两个条件：在约束曲面上寻找最优解时，每一步移动 $\mu\Delta x$ 必须满足哪两个条件？分别保证什么？如果只满足其中一个会发生什么？

2. 点积手算：仍取圆上 90 度处的点 $x_0 = (0, \sqrt{2})$。写出 $\nabla f$ 与 $-\nabla f$；对三个试探方向 $(1, 0)$、$(-1, 0)$、$(0, -1)$，分别计算它们与负梯度的点积符号，判断沿该方向 $f$ 升还是降；最后指出——如果要求不离开圆（条件一），哪个方向是可走的、它让 $f$ 升还是降？

本章小结

• 定位：讲 SVM 最大 margin 之前的数学准备——先学优化（拉格朗日乘子、KKT 条件），再学 SVM 更容易；很多同学卡壳就卡在这部分的数学推导上。
• 形式化：无约束（求导置零 / 梯度下降）vs 有约束（s.t.）；等式约束 $h_i(x)=0$（$i = 1 \ldots l$）与不等式约束 $g_j(x) \le 0$（$j = 1 \ldots m$；$\ge 0$ 乘负号即得）。
• 几何工具：$f = x_1 + x_2$ 的等高线族（iso-contour）+ 约束圆 $x_1^2 + x_2^2 = 2$（可行域 feasible region）；优化变成”在圆上找使 $f$ 最小的点”，答案是等高线与圆的切点（$(-1, -1)$，$f = -2$，细扫确认圆上仅此一点取到）。
• 移动条件：$\mu\Delta x$ 中 $\Delta x$ 无穷小、$\mu$ 是缩放常数；条件一 $h(x + \mu\Delta x) = 0$（不出圆），条件二 $f(x + \mu\Delta x) < f(x)$（要变小）。
• 点积判据：$\nabla f = (1, 1)$、更关心负梯度（梯度下降的减号）；$\Delta x \cdot (-\nabla f) > 0$ ⟺ 锐角 ⟺ $f$ 下降（数值验证 $+2/-2/0$ 三分支与 $f$ 升降严格对应；垂直 = 没有 correlation）。
• 悬念：$h$ 自己的梯度长什么样、两个条件怎么合到一张图上——下一节继续。

📋 行动清单

• 自己画出 $x_1 + x_2 = 0, \pm 1, \pm 2$ 五条等高线与半径 $\sqrt{2}$ 的圆，标出两个切点并检算 $1^2 + 1^2 = 2$
• 跑代码一：把约束换成 $x_1^2 + x_2^2 = 8$（半径 $2\sqrt{2}$），重跑扫描，观察最小值点与对应等高线怎么变
• 在圆上另取一点（如 $(1, -1)$），手算该点处三个试探方向与负梯度的点积符号
• 用一句话说清 feasible region 的含义，以及”离开它一步”意味着什么
• 预习下一节《拉格朗日乘子法（2）》——$h$ 的梯度与法线方向

—— 小象教研组