深入理解 KKT 条件

INFO

本节将对上一小节最优性条件中提出的 KKT 条件进行深入的理解和分析。

KKT 条件究其本质，是优化问题取得最优解的必要条件。下面我们首先从我们最熟悉的知识开始。

等式约束优化问题

我们在《高等数学》课程中学习过多元函数的极值问题，其中提到了 Lagrange 乘子法。其本质就是运用《凸优化》课程当中讲的 Lagrange 函数，求解等式优化问题。只不过《高等数学》课程中不涉及不等式约束，仅仅只有等式约束。为了更贴近也更容易回忆起《高等数学》所学内容，我们在这里仅考虑二元函数，并且只有一个等式约束。此时，这个约束优化问题记为

$$\begin{array}{rl}\min & f(x,y)\\ \mathrm{s}.\mathrm{t}.& g(x,y)=0\end{array}$$

这里只有一个等式约束，因此只需要引入一个 Lagrange 乘子 $\lambda$ 即可

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

计算 $L$ 对 $x$、$y$ 和 $\lambda$ 的偏导数，并令它们都等于零，就可以得到最优解的必要条件

$$\{\begin{array}{rl}{\displaystyle \frac{\partial L}{\partial x}}& =f_x(x,y)+\lambda g_x(x,y)=0\\ {\displaystyle \frac{\partial L}{\partial y}}& =f_y(x,y)+\lambda g_y(x,y)=0\\ {\displaystyle \frac{\partial L}{\partial \lambda }}& =g(x,y)=0\end{array}$$

解上面的方程组就可以得到最优解 $(x^{\star },y^{\star })$。

不等式约束优化问题

我们注意到，在刚才在求解的过程中，我们其实一点也不关心 $\lambda$ 的取值，因为那是我们引入的新变量，我们只关心原问题当中 $(x,y)$ 的取值。实际上，按照《高等数学》当中的方法求解出的 $\lambda$ 是无法判断其符号的。对于只含有等式约束的问题，这个问题并不重要。但是，对于含有不等式约束的问题来说，不等号的方向和引入的 Lagrange 乘子之间则是具有一定联系的。

我们先考虑仅含有一个不等式的约束的二元函数优化问题

$$\begin{array}{rl}\min & f(x,y)\\ \mathrm{s}.\mathrm{t}.& g(x,y)⩽0\end{array}$$

我们先来讨论最优解 $(x^{\star },y^{\star })$ 的情况，它应该有且仅有如下两种：

1. $g(x^{\star },y^{\star })<0$，说明最优解位于可行域的内部，称为内部解。此时约束条件是无效的。
2. $g(x^{\star },y^{\star })=0$，说明最优解位于可行域的边界，称为边界解。此时约束条件是有效的。

这两种情况的最优解具有不同的必要条件：

1. 内部解：原问题退化为无约束优化问题，只要驻点 $(x^{\star },y^{\star })$ 满足 $\mathrm{\nabla }f=0$ 且 $\lambda =0$。
2. 边界解：原问题转变为等式约束优化问题，这与之前讨论的情况相同。可以证明的一点是，最优解处的 $f$ 和 $g$ 的梯度方向是反向，即 $\mathrm{\exists }\lambda$ 使得 $\mathrm{\nabla }f=-\lambda \mathrm{\nabla }g$。这里 $\lambda$ 的正负性是有意义的。由于我们希望最小化 $f$，梯度 $\mathrm{\nabla }f$ 的值表示函数值上升最快的方向，因而负梯度方向 $-\mathrm{\nabla }f$ 应该指向可行域的内部。$\mathrm{\nabla }g$ 指向可行域的外部，即 $g(x,y)>0$ 的区域，因为约束 $g(x,y)⩽0$。因此这里的 $\lambda ⩾0$，这就是之前几节讲的对偶可行性。

边界解的情况可以通过上图加深理解。图中表示的是二元函数 $f(x,y)$ 在不等式约束 $g(x,y)⩽0$ 下的优化问题，并且最优解在边界的情况。如图所示，最优点即为平面 $\pi$（方程 $z=f(x,y)$）和平面 $\sigma$（方程 $g(x,y)=0$）的交点。约束 $g(x,y)⩽0$ 说明了可行域在平面 $\sigma$ 的下侧。梯度 $\mathrm{\nabla }f$ 指向上方，负梯度 $-\mathrm{\nabla }f$ 指向下方可行域内部。在最优解 $(x^{\star },y^{\star })$ 处，$\mathrm{\nabla }f$ 和 $\mathrm{\nabla }g$ 共线。

更一般地，如果有多个不等式约束，对应到上图中就是有若干平面 ${\sigma }_1,\cdots ,{\sigma }_p$，并且在最优点处 $\mathrm{\nabla }f(x^{\star },y^{\star })$ 可由有效约束对应的平面的支撑超平面的法向量的线性表示。即 $\mathrm{\exists }{\mu }_1,\cdots ,{\mu }_p⩾0$，使得

$$\mathrm{\nabla }f(x^{\star },y^{\star })=-({\mu }_1\mathrm{\nabla }{g}_1(x^{\star },y^{\star })+\cdots +{\mu }_p\mathrm{\nabla }{g}_p(x^{\star },y^{\star }))$$

而不论是内部解还是边界解，$\lambda g(x,y)=0$ 恒成立，这就是互补松弛性。

小结

回顾了等式约束优化和不等式约束优化之后，我们可以从中提炼出一种转化的思想：

1. 无约束优化问题：令梯度向量为零即可。
2. 等式约束优化问题：引入 Lagrange 乘子，将原目标函数转化为 Lagrange 函数，将原问题转化为无约束优化问题。
3. 不等式约束优化问题：引入松弛变量，将原不等式约束函数转化为等式约束函数，将原问题转化为等式约束优化问题。

KKT 条件的本质

综合上面的讨论与分析，我们再来看看 KKT 条件：

$$\begin{array}{rlrl}{f}_i\left(x^{\star }\right)& ⩽0,& i& =1,\cdots ,m\\ h_i\left(x^{\star }\right)& =0,& i& =1,\cdots ,p\\ {\lambda }_i^{\star }& ⩾0,& i& =1,\cdots ,m\\ {\lambda }_i^{\star }{f}_i\left(x^{\star }\right)& =0,& i& =1,\cdots ,m\\ \mathrm{\nabla }{f}_0\left(x^{\star }\right)+\sum _{i=1}^m{\lambda }_i^{\star }\mathrm{\nabla }{f}_i\left(x^{\star }\right)+\sum _{i=1}^p{\nu }_i^{\star }\mathrm{\nabla }{h}_i\left(x^{\star }\right)& =0& & \end{array}$$

其中一个包含了四个条件，它们分别是：

1. Lagrange 函数的定常方程式：上式最后一行 $\mathrm{\nabla }L=0$。
2. 原始可行性：即满足等式约束和不等式约束，上式第一行 $f_i\left(x^{\star }\right)⩽0$ 和第二行 $h_i\left(x^{\star }\right)=0$。
3. 对偶可行性：即上式第三行 ${\lambda }_i^{\star }⩾0$。
4. 互补松弛性：即上式第四行 ${\lambda }_i^{\star }{f}_i\left(x^{\star }\right)=0$。

简单的例子

考虑下面的问题

$$\begin{array}{rl}\min & x^2+y^2\\ \mathrm{s}.\mathrm{t}.& x+y=1\\ & y⩽\alpha \end{array}$$

写出 Lagrange 函数

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

KKT 条件方程组如下

$$\{\begin{array}{rlr}2x-\lambda & =0& (1)\\ 2y-\lambda +\nu & =0& (2)\\ \nu & ⩾0& (3)\\ \nu (y-\alpha )& =0& (4)\end{array}$$

分别由 (1) 式和 (2) 式求出

$$\{\begin{array}{rlr}x& ={\displaystyle \frac{1}{2}}\lambda & (5)\\ y& ={\displaystyle \frac{1}{2}}\lambda -{\displaystyle \frac{1}{2}}\nu & (6)\end{array}$$

代入等式约束 $x+y=1$，得到 $\lambda$ 和 $\nu$ 的函数关系

$$\lambda ={\displaystyle \frac{1}{2}}\nu +1$$

再代入式 (5) 和 (6) 中，消去 $\lambda$

$$\{\begin{array}{rlr}x& ={\displaystyle \frac{1}{4}}\nu +{\displaystyle \frac{1}{2}}& (7)\\ y& =-{\displaystyle \frac{1}{4}}\nu +{\displaystyle \frac{1}{2}}& (8)\end{array}$$

最后再加入不等式约束，得到

$$\{\begin{array}{rl}\nu & ⩾2-4\alpha \\ \nu & ⩾0\end{array}$$

下面对参数 $\alpha$ 进行分类讨论：

1. 若 $\alpha >{\displaystyle \frac{1}{2}}$，不难验证 $\nu =0>2-4\alpha$。此时满足所有的 KKT 条件，约束不等式是无效的。$x^{\star }=y^{\star }={\displaystyle \frac{1}{2}}$ 是内部解。
2. 若 $\alpha ={\displaystyle \frac{1}{2}}$，$\nu =0=2-4\alpha$。此时满足所有的 KKT 条件，约束不等式是有效的。$x^{\star }=y^{\star }={\displaystyle \frac{1}{2}}$ 是边界解。
3. 若 $\alpha <{\displaystyle \frac{1}{2}}$，$\nu =2-4\alpha >0$。此时约束不等式是有效的。$x^{\star }=1-\alpha$，$y^{\star }=\alpha$。

本题的几何意义如图所示。目标函数对应的曲面 $\mathrm{\Gamma }$ 是（椭）圆抛物面，等式约束对应平面 $\pi$，不等式约束对应以平面 $\sigma$ 为边界的左半空间。曲面 $\mathrm{\Gamma }$ 和平面 $\pi$ 的交线为图中的红色曲线（该曲线实际上是一个抛物线）。不考虑不等式约束，该优化问题的最优解为 $(x^{\star },y^{\star })=({\displaystyle \frac{1}{2}},{\displaystyle \frac{1}{2}})$，最优值为 $f(x^{\star },y^{\star })={\displaystyle \frac{1}{2}}$，对应图中红点的坐标 $({\displaystyle \frac{1}{2}},{\displaystyle \frac{1}{2}},{\displaystyle \frac{1}{2}})$。不等式约束实际上是让平面 $\alpha$ 沿 $y$ 轴方向平移，以 $\alpha ={\displaystyle \frac{1}{2}}$ 为界，可以分三种情况讨论。

参考

• Karush-Kuhn-Tucker (KKT) 条件
• 浅谈最优化问题的KKT条件