从拉格朗日乘数法到 KKT 条件

无约束优化中，我们习惯先令导数或梯度为零，再判断得到的点是不是极小值。但有了约束，最优点可能恰好位于边界，目标函数的梯度并不为零：它仍然指向某个下降方向，只是那个方向不允许走。

拉格朗日乘数法处理等式约束；KKT（Karush–Kuhn–Tucker）条件把这一思路推广到同时含有等式与不等式约束的问题。理解它的关键，是弄清楚哪些约束在最优点真正限制了移动，以及这些限制如何与目标函数的梯度平衡。以下默认目标函数和约束函数连续可微，变量为连续变量。优化问题的分类与常见求解方法可先参阅优化理论概览。

从一个等式约束问题开始

考虑在直线 $x+y=1$ 上寻找离原点最近的点。由于距离和距离的平方有相同的最小点，可以写成

$$\min_{x,y}\ f(x,y)=x^2+y^2, \qquad \text{s.t.}\ h(x,y)=x+y-1=0.$$

直接消元，令 $y=1-x$，得到

$$f(x,1-x)=x^2+(1-x)^2 =2\left(x-\frac12\right)^2+\frac12.$$

因此最优点是 $(1/2,1/2)$，最优值为 $1/2$。然而在这个点，

$$\nabla f=(2x,2y)=(1,1)\ne 0.$$

这不矛盾。无约束时沿 $-\nabla f$ 移动可以降低目标值，但这里会离开直线。沿约束直线的切向量 $d=(d_1,d_2)$ 满足 $d_1+d_2=0$，于是

$$\nabla f^{\mathsf T}d=d_1+d_2=0.$$

最优点处消失的是沿可行切向方向的一阶变化，而不一定是整个梯度。

拉格朗日乘数：把切向条件写成梯度平衡

对于一个等式约束 $h(x)=0$，若 $\nabla h(x^*)\ne 0$，它在 $x^*$ 附近定义一个光滑约束曲面。曲面上的切向量满足

$$\nabla h(x^*)^{\mathsf T}d=0.$$

在局部极小点，沿曲面的正、反两个方向都不能一阶下降，所以 $\nabla f(x^*)$ 必须垂直于整个切空间，也就必须与法向量 $\nabla h(x^*)$ 平行。因此存在实数 $\nu$，使

$$\nabla f(x^*)+\nu\nabla h(x^*)=0.$$

这就是引入拉格朗日乘数的理由。定义拉格朗日函数

$$L(x,\nu)=f(x)+\nu h(x),$$

便可把候选点条件写成

$$\nabla_xL(x,\nu)=0,\qquad h(x)=0.$$

其中 $\nabla_x$ 表示只对原变量 $x$ 求梯度，$\nu$ 是额外引入的未知数。等式约束不区分哪一侧允许进入，所以它的乘数没有正负限制。

对于前面的例子，

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

相应方程为

$$2x+\nu=0,\qquad 2y+\nu=0,\qquad x+y-1=0.$$

解得 $x=y=1/2$、$\nu=-1$，与消元结果一致。

多个等式约束 $h_j(x)=0$ 时，则引入多个乘数：

$$L(x,\nu)=f(x)+\sum_{j=1}^{p}\nu_jh_j(x).$$

当这些约束在候选点的梯度线性无关时，局部极小点满足 $\nabla_xL=0$ 和全部等式约束。这里得到的仍是一阶必要条件，通常还需要判断候选点性质。

换成不等式后，多了什么？

现在保留同一个目标函数，把约束改成 $x+y\ge 1$：

$$\min_{x,y}\ x^2+y^2, \qquad \text{s.t.}\ g(x,y)=1-x-y\le 0.$$

此后统一使用“最小化，且不等式写成 $g_i\le 0$”的约定。

可行域从一条直线变成了一个半平面。最优点仍为 $(1/2,1/2)$，但不能因此把所有不等式一开始都当成等式。例如若约束是 $x+y\ge -1$，原点就在可行域内部，最优点便是原点，边界不需要取到。

活跃约束与非活跃约束

在一个可行点 $x^*$，不等式有两种状态：

状态	数学条件	局部含义
活跃约束	$g_i(x^*)=0$	点位于该约束的边界上
非活跃约束	$g_i(x^*)<0$	该约束还有余量，足够小的移动不会违反它

非活跃约束不参与该点的一阶梯度平衡，因此对应乘数应为零。活跃约束才可能提供非零的约束作用。

为什么不等式乘数必须非负？

对于光滑边界 $g(x)=0$，$\nabla g$ 指向 $g$ 增大的方向，也就是可行域 $g\le 0$ 的外侧。在只有这一个约束、且边界梯度非零的局部极小点，$-\nabla f$ 若非零，就应指向无法继续进入的外侧。因此它应是外法向量的非负倍数：

$$-\nabla f(x^*)=\lambda\nabla g(x^*), \qquad \lambda\ge 0.$$

回到例子，$\nabla f=(1,1)$，$\nabla g=(-1,-1)$，所以 $\lambda=1$，恰好满足

$$\nabla f+\lambda\nabla g=0.$$

这个符号取决于约定。如果保留 $\widetilde g\ge 0$ 的写法，就可以使用 $L=f-\lambda\widetilde g$、$\lambda\ge 0$。不能只改变不等号方向，却照搬原来的拉格朗日函数符号。

互补松弛把两种状态合在一起

“约束有余量时乘数为零”可以写成

$$\lambda_i g_i(x^*)=0.$$

这就是互补松弛。在 $g_i\le 0$、$\lambda_i\ge 0$ 的前提下，它表示

$$g_i(x^*)<0\ \Longrightarrow\ \lambda_i=0, \qquad \lambda_i>0\ \Longrightarrow\ g_i(x^*)=0.$$

反过来并不成立：约束活跃时，乘数也可能为零。例如 $\min_x x^2$、约束 $x\ge 0$，最优点 $x^*=0$ 位于边界，但对应乘数就是零，因为目标函数自身的梯度已经为零。

KKT 条件的完整形式

考虑一般问题，其中 $x\in\mathbb R^n$ 是决策变量，$m$ 个不等式与 $p$ 个等式分别写为

$$\begin{aligned} \min_x\quad &f(x)\\ \text{s.t.}\quad &g_i(x)\le 0,\quad i=1,\ldots,m,\\ &h_j(x)=0,\quad j=1,\ldots,p. \end{aligned}$$

定义

$$L(x,\lambda,\nu) =f(x)+\sum_{i=1}^{m}\lambda_i g_i(x) +\sum_{j=1}^{p}\nu_j h_j(x).$$

点与乘数 $(x^*,\lambda^*,\nu^*)$ 满足 KKT 条件，是指同时满足以下四组关系：

条件	表达式	含义
驻点条件	$\nabla_xL(x^*,\lambda^*,\nu^*)=0$	目标梯度与约束梯度平衡
原始可行性	$g_i(x^*)\le 0,\ h_j(x^*)=0$	点满足原问题的约束
对偶可行性	$\lambda_i^*\ge 0$	不等式乘数符合符号约定；$\nu_j^*$ 不限符号
互补松弛	$\lambda_i^*g_i(x^*)=0$	非活跃约束的乘数为零

驻点条件展开后就是

$$\nabla f(x^*) +\sum_{i=1}^{m}\lambda_i^*\nabla g_i(x^*) +\sum_{j=1}^{p}\nu_j^*\nabla h_j(x^*)=0.$$

没有不等式时，它退化为拉格朗日乘数法；没有任何约束时，则退化为 $\nabla f(x^*)=0$。

注意，不能对每个不等式乘数都令 $\partial L/\partial\lambda_i=0$，因为那样会强迫全部 $g_i(x)=0$，错误地排除约束非活跃的情况。

完整例题：通过活跃集求解

为看清约束从“有余量”到“卡住最优点”的变化，考虑带参数 $a\in\mathbb R$ 的问题：

$$\min_{x,y}\ x^2+y^2, \qquad \text{s.t.}\ a-x-y\le 0.$$

这里 $a$ 是给定参数。拉格朗日函数和 KKT 条件为

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

$$\begin{cases} 2x-\lambda=0,\\ 2y-\lambda=0,\\ a-x-y\le 0,\\ \lambda\ge 0,\\ \lambda(a-x-y)=0. \end{cases}$$

互补松弛提示我们分两种情况讨论。

先取 $\lambda=0$。 驻点条件给出 $x=y=0$。代入约束要求 $a\le 0$，所以该分支只在 $a\le 0$ 时可行。

再取约束活跃，即 $x+y=a$。 驻点条件给出 $x=y=\lambda/2$，从而

$$\lambda=a,\qquad x=y=\frac a2.$$

对偶可行性要求 $a\ge 0$。当 $a=0$ 时，两种分支重合，正好对应“约束活跃但乘数为零”。

合并可得

$$x^*=y^*=\frac{\max\{a,0\}}2, \qquad \lambda^*=\max\{a,0\},$$

$$f^*=\frac{\bigl(\max\{a,0\}\bigr)^2}{2}.$$

还可以独立检查这一结果：当 $a\le 0$ 时，原点可行且目标值非负；当 $a>0$ 时，任意可行点都满足

$$x^2+y^2\ge\frac{(x+y)^2}{2}\ge\frac{a^2}{2},$$

而 $x=y=a/2$ 恰好取到等号。因此上述解确实是全局最优解。

多个不等式时，同样可以猜测哪些约束活跃：对猜测活跃的约束令 $g_i=0$，对其余约束令 $\lambda_i=0$，求解后再检查所有不等式和乘子符号。这适合手算小问题；约束多时，枚举所有活跃集并不是高效算法。

满足 KKT，就一定最优吗？

一般非凸问题：还需要约束资格条件

对于一般光滑问题，要从“局部极小点”推出“KKT 条件成立”，通常需要额外的约束资格条件。一种常用条件是线性无关约束资格条件（LICQ）：在该点，全部等式约束梯度与全部活跃不等式约束梯度共同线性无关。非活跃约束不参与这个检查。

它的作用是避免约束的一阶描述退化。例如

$$\min_x\ x,\qquad \text{s.t.}\ x^2\le 0.$$

唯一可行点 $x^*=0$ 自然是全局最优点，但 $g'(0)=0$，驻点条件却要求

$$1+\lambda\cdot 0=0,$$

不可能成立。可行域确实把点固定在零处，但约束梯度没有反映出这一限制。

即使约束资格条件成立，KKT 对非凸问题通常也只是必要条件。比如 $\min_x -x^2$、约束 $-1\le x\le 1$，在 $x=0$ 处两个约束都非活跃，乘数均为零，且目标导数为零，因而满足 KKT；但它是局部极大点，全局最小值在 $x=\pm1$ 处取得。

因此，非凸问题求出 KKT 点后，还要结合可行方向、二阶条件或其他全局分析判断，不能直接宣布求得最优解。

凸问题：KKT 可以成为最优性证书

若 $f$ 与各个 $g_i$ 是定义在 $\mathbb R^n$ 上的可微凸函数，而等式约束 $h_j$ 是仿射函数，那么满足 KKT 的点是全局最优点。若再有 Slater 条件，即存在满足所有等式且使所有不等式严格成立的点，则在最优解存在时，KKT 也是必要条件。这一结论可参阅 Boyd 等人的凸优化讲义，第 5 章。

下面直接看充分性为什么成立。固定满足 KKT 的乘数 $\lambda^*,\nu^*$。由于 $\lambda_i^*\ge0$，函数 $L(x,\lambda^*,\nu^*)$ 关于 $x$ 凸；驻点条件使 $x^*$ 成为它的全局最小点。

对任意原问题的可行点 $z$，有

$$\underbrace{f(x^*)}_{\text{互补松弛与等式可行性}} =L(x^*,\lambda^*,\nu^*) \le L(z,\lambda^*,\nu^*) \le f(z).$$

最后一个不等式来自 $\lambda_i^*g_i(z)\le0$ 和 $h_j(z)=0$。这条不等式链直接证明了全局最优性。

充分性本身不需要 Slater 条件。 Slater 条件用于保证凸问题最优点处存在满足 KKT 的乘数。若函数只定义在某个凸域上，还需要把定义域条件纳入讨论；本文使用全空间定义的情形，避免把边界条件隐藏在符号里。

做题时如何使用

1. 把问题统一成最小化，明确每个不等式的方向；例如 $x_i\ge0$ 应写成 $-x_i\le0$。
2. 写出拉格朗日函数，区分不等式乘数 $\lambda_i\ge0$ 与等式乘数 $\nu_j\in\mathbb R$。
3. 同时列出驻点、原始可行、对偶可行和互补松弛四组条件。
4. 利用互补松弛分支求解，再把候选点和乘数代回全部条件，排除不可行分支。
5. 最后判断能得出多强的结论：凸问题可用 KKT 证明全局最优；一般非凸问题则仍需进一步分析。

拉格朗日乘数法的出发点是“沿等式约束曲面已经没有一阶下降方向”；KKT 再加入不等式边界的单侧性，以及约束是否活跃的区别。乘子非负和互补松弛正是这两层区别的数学表达。

参考资料

• Stephen Boyd、Lieven Vandenberghe、Parth Nobel：Convex Optimization 课程讲义，第 5 章关于 Slater 条件、互补松弛与凸问题 KKT 最优性条件的讨论。本文例题的求解与反例计算在正文中展开。