第6章非线性规划（二）：拉格朗日乘子与 KKT 条件

系统分析：线性规划、非线性规划与排队模型 · 第 6 / 11 篇（展开目录）

从线性规划建模、单纯形法、对偶与灵敏度、运输与指派，到非线性规划、随机过程、马尔可夫链、排队模型和决策分析，每章都配手算例题和自测，最后一章用综合例题把方法串起来。

约 35 分钟 · 需要第5章的梯度、Hessian 与正定性

读完你能： 写出拉格朗日函数并解出驻点；在切空间 $M$ 上检验二阶充分条件；写出 KKT 条件并按“哪些约束起作用”分情况求解；用凸性判断 KKT 点是否为全局最优；用乘子估计约束右端变化 $\Delta$ 后最优值的改变量。

1. 标准形式与符号约定

\min\ f(X)\qquad\text{s.t.}\quad h_i(X)=0\ (i=1,\dots,m),\qquad g_j(X)\le0\ (j=1,\dots,p).

最大化问题改为 $\min\ -f$ ；
$h'(X)=\alpha$ 写成 $h(X)=h'(X)-\alpha=0$ ， $g'(X)\le\beta$ 写成 $g(X)=g'(X)-\beta\le0$ ；
$\ge$ 约束两边乘 $-1$ 变成 $\le$ 。

拉格朗日函数：

L(X,\lambda,\mu)=f(X)+\sum_i\lambda_i h_i(X)+\sum_j\mu_j g_j(X).

本章所有符号结论都基于这个约定（ $f$ 求极小、约束写成 $h=0$ 、 $g\le0$ 、乘子前面是加号）。换约定会改变乘子的符号，做题时先统一形式最稳妥。

2. 等式约束：拉格朗日乘子法

只有等式约束时，令拉格朗日函数对所有变量和乘子的偏导数为零：

\nabla_X L=\nabla f+\sum_i\lambda_i\nabla h_i=0,\qquad \nabla_\lambda L=h(X)=0 .

一共 $n+m$ 个方程、 $n+m$ 个未知数。几何意义是：在最优点， $\nabla f$ 能由约束的梯度线性表示——沿着约束曲面任何允许的方向移动， $f$ 都不会一阶下降。

例1： $\min\ f=x_1^2+x_2^2+x_3^2$ ，s.t. $x_1+2x_2+x_3=6$ ， $x_1-x_2+x_3=0$ 。

L=x_1^2+x_2^2+x_3^2+\lambda_1(x_1+2x_2+x_3-6)+\lambda_2(x_1-x_2+x_3).

\begin{aligned} \partial L/\partial x_1&=2x_1+\lambda_1+\lambda_2=0\\ \partial L/\partial x_2&=2x_2+2\lambda_1-\lambda_2=0\\ \partial L/\partial x_3&=2x_3+\lambda_1+\lambda_2=0 \end{aligned}

第一、三式相减得 $x_1=x_3$ 。代入两条约束： $2x_1+2x_2=6$ ， $2x_1-x_2=0$ ，解得 $x_1=1,\ x_2=2,\ x_3=1$ 。再代回得 $\lambda_1=-2,\ \lambda_2=0$ 。最优值 $f^*=1+4+1=6$ 。

（几何上这是求原点到两平面交线的最近点； $\lambda_2=0$ 说明原点到第一个平面的最近点 $(1,2,1)$ 本身就满足第二条约束。）

3. 二阶充分条件：只在切空间上检验

驻点不一定是极小。判断方法是看 $\nabla_{XX}^2L$ ——但不需要它处处正定，只需要在约束允许移动的方向上正定。这些方向组成切空间

M=\{Y:\ \nabla h_i(X^*)^{T}Y=0,\ i=1,\dots,m\}.

定理： 若 $X^*$ 满足 $h(X^*)=0$ 、 $\nabla_X L(X^*,\lambda^*)=0$ ，并且对所有 $Y\in M,\ Y\ne0$ 都有 $Y^{T}\nabla^2_{XX}L(X^*,\lambda^*)Y>0$ ，则 $X^*$ 是严格局部极小点。

这里要求 $X^*$ 是正则点：各约束梯度 $\nabla h_i(X^*)$ 线性无关（矩阵 $[\nabla h_1,\dots,\nabla h_m]^{T}$ 的秩为 $m$ ）。

例1中 $\nabla^2_{XX}L=2I$ 在整个空间都正定，当然在 $M$ 上也正定， $(1,2,1)$ 是极小点。下面看一个需要真正用到 $M$ 的例子。

例2：容器设计。 设计一个有盖长方体容器，容积 72 cm³，长 $x_1$ 必须是高 $x_3$ 的 2 倍，材料 10 元/cm²。求成本最低的尺寸。

\min\ f=2(x_1x_2+x_1x_3+x_2x_3)\quad\text{s.t.}\quad h_1=x_1x_2x_3-72=0,\quad h_2=x_1-2x_3=0,\quad x_1,x_2,x_3>0

（总成本是 $10f$ ，不影响最优尺寸）。

\begin{aligned} \partial L/\partial x_1&=2(x_2+x_3)+\lambda_1x_2x_3+\lambda_2=0\\ \partial L/\partial x_2&=2(x_1+x_3)+\lambda_1x_1x_3=0\\ \partial L/\partial x_3&=2(x_1+x_2)+\lambda_1x_1x_2-2\lambda_2=0 \end{aligned}

令 $x_1=2t,\ x_3=t$ 。第二式： $6t+2\lambda_1t^2=0\Rightarrow\lambda_1=-3/t$ 。第一式乘 2 加第三式消去 $\lambda_2$ ：

4(x_2+t)+2\lambda_1x_2t+2(2t+x_2)+2\lambda_1tx_2=0\ \Rightarrow\ 6x_2+8t-12x_2=0\ \Rightarrow\ x_2=\tfrac43t .

容积 $2t\cdot\frac43t\cdot t=\frac83t^3=72$ ， $t=3$ 。所以 $x_1=6,\ x_2=4,\ x_3=3$ （cm）， $\lambda_1=-1$ ，由第一式 $\lambda_2=-2(4+3)+12=-2$ 。表面积 $2(24+18+12)=108$ cm²，最低成本 1080 元。

二阶检验。在 $X^*=(6,4,3)$ 、 $\lambda_1=-1$ 处：

\nabla^2_{XX}L=\begin{pmatrix}0&2&2\\2&0&2\\2&2&0\end{pmatrix}+\lambda_1\begin{pmatrix}0&x_3&x_2\\x_3&0&x_1\\x_2&x_1&0\end{pmatrix} =\begin{pmatrix}0&-1&-2\\-1&0&-4\\-2&-4&0\end{pmatrix}.

这个矩阵在整个空间是不定的（对角线全 0）。但在切空间上： $\nabla h_1=(12,18,24)$ ， $\nabla h_2=(1,0,-2)$ ， $Y\in M$ 要求 $y_1=2y_3$ 且 $12y_1+18y_2+24y_3=0$ ，得 $Y=t(2,-\tfrac83,1)$ ，

Y^{T}\nabla^2_{XX}L\,Y=2t^2\Big[(-1)(2)(-\tfrac83)+(-2)(2)(1)+(-4)(-\tfrac83)(1)\Big]=2t^2\cdot12=24t^2>0 .

在 $M$ 上正定， $(6,4,3)$ 是严格局部极小。

求切空间的套路

写出每个约束的梯度，令它们与 $Y=(y_1,\dots,y_n)$ 的内积为 0，解出 $Y$ 的一般形式（含 $n-m$ 个自由参数），代入 $Y^{T}HY$ 化成平方和或单项。只要结果对所有非零参数都为正即可。

4. 不等式约束：KKT 条件

对 $\min f(X)$ ，s.t. $g_j(X)\le0$ ：约束 $g_j$ 在 $X$ 处起作用（active）指 $g_j(X)=0$ ，不起作用指 $g_j(X)<0$ 。

KKT 条件（必要条件）： 在局部最优点满足适当约束资格条件（例如等式约束和起作用不等式约束的梯度线性无关）时，存在乘子使下列条件成立：

驻点： $\nabla_X L=\nabla f+\sum_j\mu_j\nabla g_j=0$ ；
可行： $g_j(X)\le0$ ；
互补松弛： $\mu_jg_j(X)=0$ ；
乘子非负： $\mu_j\ge0$ 。

（有等式约束时再加上 $h_i(X)=0$ ，对应的 $\lambda_i$ 符号不限。）

条件 3 说：每条约束要么起作用（ $g_j=0$ ），要么它的乘子为 0——这和线性规划的互补松弛是同一回事。条件 4 说：起作用的约束“推”着最优点，推力方向必须指向可行域内，不能反过来。

二阶充分条件： 再要求 $Y^{T}\nabla^2_{XX}L\,Y>0$ 对所有 $Y\in M'$ 、 $Y\ne0$ 成立，其中

M'=\{Y:\ \nabla g_j(X^*)^{T}Y=0\ \text{对所有}\ j\in J\},\qquad J=\{j:\ g_j(X^*)=0,\ \mu_j^*>0\}.

注意 $J$ 只包含起作用且乘子为正的约束；起作用但乘子为 0 的约束不进入 $M'$ 。

分情况求解

KKT 是等式和不等式混合的系统，一般按“哪些乘子为 0”分情况： $p$ 条不等式约束有 $2^p$ 种组合。每种情况把假定为正的乘子对应的约束当作等式，解出来后检查两件事：被假定不起作用的约束是否可行，被假定起作用的乘子是否 $\ge0$ 。

例3： $\min\ f=(x_1-3)^2+(x_2-2)^2$ ，s.t. $g_1=x_1+x_2-4\le0$ ， $g_2=x_1-2x_2\le0$ 。

\nabla_XL:\quad 2(x_1-3)+\mu_1+\mu_2=0,\qquad 2(x_2-2)+\mu_1-2\mu_2=0 .

情况	解	检查	结论
$\mu_1=\mu_2=0$	$(3,\ 2)$	$g_1=1>0$ ，不可行	排除
$\mu_1>0,\ \mu_2=0$	$g_1=0$ ： $x_1=x_2+1$ ，得 $(2.5,\ 1.5)$ ， $\mu_1=1$	$g_2=-0.5\le0$ ， $\mu_1=1\ge0$	KKT 点
$\mu_1=0,\ \mu_2>0$	$g_2=0$ ： $(3.2,\ 1.6)$ ， $\mu_2=-0.4$	$\mu_2<0$ ；且 $g_1=0.8>0$	排除
$\mu_1,\mu_2>0$	两条都取等号： $(8/3,\ 4/3)$ ， $\mu_2=-2/9$	$\mu_2<0$	排除

唯一 KKT 点 $X^*=(2.5,\ 1.5)$ ， $f^*=0.25+0.25=0.5$ 。二阶检验： $J=\{1\}$ ， $M'=\{Y:\ y_1+y_2=0\}$ ， $\nabla^2_{XX}L=2I$ ， $Y^{T}(2I)Y=2(y_1^2+y_2^2)>0$ 。是极小点。（几何上： $(3,2)$ 到直线 $x_1+x_2=4$ 的垂足。）

乘子为负说明“推错了方向”

情况三算出 $\mu_2=-0.4$ ，意思是：要让最优点贴在 $g_2=0$ 上，约束得“往外拉”，这不可能——不等式约束只能挡住你，不能吸住你。乘子为负的情况一律排除。

5. 等式与不等式混合

\min f\quad\text{s.t.}\quad h_i=0,\ g_j\le0:\qquad \nabla f+\sum\lambda_i\nabla h_i+\sum\mu_j\nabla g_j=0,\quad h_i=0,\quad g_j\le0,\quad \mu_jg_j=0,\quad\mu_j\ge0 .

$\lambda_i$ 正负都可以， $\mu_j$ 必须非负。二阶条件的切空间 $M''$ 由所有等式约束的梯度和 $J$ 中不等式约束的梯度共同决定。

例4： $\min\ f=x_1^2+x_2^2$ ，s.t. $x_1+x_2=4$ ， $x_1\ge3$ （写成 $g=3-x_1\le0$ ）。

若 $\mu=0$ ： $2x_1+\lambda=0,\ 2x_2+\lambda=0$ ，得 $x_1=x_2=2$ ，但 $g=1>0$ ，不可行。
若 $\mu>0$ ： $x_1=3$ ， $x_2=1$ 。 $2\cdot3+\lambda-\mu=0$ ， $2\cdot1+\lambda=0$ ，得 $\lambda=-2$ ， $\mu=4\ge0$ 。KKT 点 $(3,1)$ ， $f^*=10$ 。

$M''=\{Y:\ y_1+y_2=0,\ -y_1=0\}=\{0\}$ ，切空间只有零向量，二阶条件自动成立——两条约束已经把点完全固定住了。

6. 凸规划：KKT 点就是全局最优

一般情况下 KKT 点只是候选者。但满足下面条件时，任何 KKT 点都是全局最优解：

目标 $f$ 是凸函数；
所有不等式约束 $g_j$ 是凸函数（这样 $\{g_j\le0\}$ 是凸集）；
所有等式约束 $h_i$ 是线性的。

判断凸性用第5章的方法：Hessian 在整个区域上半正定，函数就是凸的。线性函数既凸又凹。

例5： $\min\ f=x_1^2+x_2^2-4x_1-6x_2$ ，s.t. $x_1+x_2\le3$ 。

无约束极小点是 $(2,3)$ ，但 $2+3>3$ ，不可行，所以约束一定起作用。令 $\mu>0$ ： $2x_1-4+\mu=0$ ， $2x_2-6+\mu=0$ ， $x_1+x_2=3$ 。前两式相减得 $x_2=x_1+1$ ，于是 $x_1=1,\ x_2=2,\ \mu=2\ge0$ ， $f^*=1+4-4-12=-11$ 。

$\nabla^2 f=2I$ 正定， $f$ 凸；约束线性。所以 $(1,2)$ 是全局最优，不必再做二阶检验。

7. 乘子的经济含义：灵敏度

已求得最优解 $X^*$ 和乘子 $\lambda^*,\mu^*$ 。把约束右端改一点： $h_i'(X)=\alpha_i\to\alpha_i+\Delta\alpha_i$ ， $g_j'(X)\le\beta_j\to\beta_j+\Delta\beta_j$ 。最优值的变化近似为

\Delta f^*\approx-\sum_i\lambda_i^*\,\Delta\alpha_i-\sum_j\mu_j^*\,\Delta\beta_j .

这和线性规划的影子价格是同一个概念，只是对非线性问题只在小变化时成立（一阶近似）。

例6： $\min\ f=2x_1^2+x_2^2+3x_3^2$ ，s.t. $x_1+x_2+x_3=11$ 。

$4x_1+\lambda=0,\ 2x_2+\lambda=0,\ 6x_3+\lambda=0$ ，所以 $x_1=-\lambda/4,\ x_2=-\lambda/2,\ x_3=-\lambda/6$ 。代入约束： $-\lambda(\frac14+\frac12+\frac16)=-\frac{11}{12}\lambda=11$ ， $\lambda^*=-12$ 。于是 $X^*=(3,6,2)$ ， $f^*=18+36+12=66$ 。

右端改为 $11+\Delta$ ：

\Delta f^*\approx-\lambda^*\Delta=12\Delta,\qquad f^*(\Delta)\approx66+12\Delta .

精确值可以重新求解得到： $f^*(\Delta)=66+12\Delta+\tfrac{6}{11}\Delta^2$ 。 $\Delta=0.5$ 时近似值 72，精确值 72.136，误差就是被忽略的二次项。

乘子的符号怎么读

在“ $\min f$ ， $L=f+\lambda h$ ， $h=h'-\alpha$ ”的约定下， $\lambda^*=-12$ 表示右端每增加 1，最小值约增加 12。不同教材的约定不同，最可靠的检查方法是：直接想“放宽约束目标应该变好还是变坏”，再核对符号。

8. 小结

拉格朗日函数 $L=f+\sum\lambda_ih_i+\sum\mu_jg_j$ ；等式约束： $\nabla_XL=0$ 与 $h=0$ 联立。
二阶充分条件只在切空间 $M=\{Y:\nabla h^{T}Y=0\}$ 上要求正定；不等式约束只计入起作用且乘子为正的那些。
KKT：驻点 + 可行 + 互补松弛 + $\mu\ge0$ ；按哪些约束起作用分情况，逐一检查可行性和乘子符号。
凸目标 + 凸不等式约束 + 线性等式约束 ⇒ KKT 点就是全局最优。
灵敏度： $\Delta f^*\approx-\sum\lambda_i^*\Delta\alpha_i-\sum\mu_j^*\Delta\beta_j$ 。

自测

1. 广告预算问题：电视每分钟 1 千元、广播每分钟 1 千元，共 5 千元；收入 $R=10x_1+8x_2-x_1^2-x_2^2$（千元）。怎样分配收入最大？预算多 1 千元，收入约增加多少？

改为 $\min\ -R$ ， $h=x_1+x_2-5=0$ 。 $-10+2x_1+\lambda=0$ ， $-8+2x_2+\lambda=0$ ，得 $x_1-x_2=1$ ，于是 $x_1=3,\ x_2=2,\ \lambda=4$ ， $R^*=30+16-9-4=33$ 千元。 $\nabla^2(-R)=2I$ 正定，所以它使 $-R$ 极小，也就是使 $R$ 极大。

预算 $5\to6$ ： $\Delta(-R)^*\approx-\lambda\Delta=-4$ ，即收入约增加 4 千元。（精确值： $x_1=3.5,\ x_2=2.5$ ， $R=36.5$ ，增加 3.5；差额来自二次项。）

2. 例3中如果把第二条约束改成 $x_1-2x_2\le-1$，最优解会变吗？

原最优点 $(2.5,1.5)$ 处 $x_1-2x_2=-0.5>-1$ ，违反新约束，所以会变。两条约束都可能起作用： $x_1+x_2=4$ 与 $x_1-2x_2=-1$ 交于 $(7/3,\ 5/3)$ ，此时 $\mu_1=10/9$ 、 $\mu_2=2/9$ ，均为正，满足 KKT；目标和约束都是凸的，所以这就是新的全局最优， $f^*=(2/3)^2+(1/3)^2=5/9$ 。

3. 为什么例2中 $\nabla^2_{XX}L$ 在全空间不定，却仍能判定为极小？

可行点只能沿着约束曲面移动，不能往任意方向走。二阶条件只关心可行的移动方向，也就是切空间 $M$ 上的方向。在 $M$ 之外让 $L$ 变小的方向，会破坏约束，所以不算。例2的 $M$ 是一条直线，沿这条直线 $Y^{T}HY=24t^2>0$ ，足以保证局部极小。