深入理解 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$，这就是之前几节讲的对偶可行性。

TikZ 代码

\begin{tikzpicture}[line cap=round,line join=round,scale=1.05,
  xq/.style={orange!45}, yq/.style={cyan!45}]
  % KKT geometry: surface pi (objective) and sigma (constraint), gradients at (x*,y*)
  % projection: X = 0.9x + 0.6y, Y = 0.55z - 0.35x + 0.3y
  \foreach \xx in {-1.7,-1.275,...,1.7}
    \draw[xq] plot[domain=-1.7:1.7,samples=9]
      ({0.9*\xx + 0.6*\x}, {0.55*(1.05 + 0.08*\xx - 0.06*\x) - 0.35*\xx + 0.3*\x});
  \foreach \yy in {-1.7,-1.275,...,1.7}
    \draw[xq] plot[domain=-1.7:1.7,samples=9]
      ({0.9*\x + 0.6*\yy}, {0.55*(1.05 + 0.08*\x - 0.06*\yy) - 0.35*\x + 0.3*\yy});
  \node at (-2.5,0.9) {$\pi$};
  \foreach \xx in {-1.7,-1.275,...,1.7}
    \draw[yq] plot[domain=-1.7:1.7,samples=13]
      ({0.9*\xx + 0.6*\x}, {0.55*(-0.45 + 0.3*\xx*\xx + 0.3*\x*\x) - 0.35*\xx + 0.3*\x});
  \foreach \yy in {-1.7,-1.275,...,1.7}
    \draw[yq] plot[domain=-1.7:1.7,samples=13]
      ({0.9*\x + 0.6*\yy}, {0.55*(-0.45 + 0.3*\x*\x + 0.3*\yy*\yy) - 0.35*\x + 0.3*\yy});
  \node at (-2.5,-1.0) {$\sigma$};
  % point (x*, y*) on pi and gradient arrows
  \fill (0.315,0.54) circle (2.2pt) node[below right] {$(x^{\star}, y^{\star})$};
  \draw[->,very thick,blue!60!black] (0.315,0.54) -- (0.315,1.145)
    node[right] {$\nabla f(x^{\star}, y^{\star})$};
  \draw[->,very thick,brown!70!black,dashed] (0.315,0.5) -- (0.315,-0.3725)
    node[right] {$-\lambda \nabla g(x^{\star}, y^{\star})$};
\end{tikzpicture}

边界解的情况可以通过上图加深理解。图中表示的是二元函数 $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$。

TikZ 代码

\begin{tikzpicture}[line cap=round,line join=round,scale=1.05,
  grid/.style={gray!50}]
  % paraboloid Gamma: z = x^2 + y^2 with planes pi: x+y=1 and sigma: y=alpha
  % projection: X = 0.9x + 0.6y, Y = 0.55z - 0.35x + 0.3y
  % plane pi: x + y = 1 (horizontal + vertical grid lines)
  \foreach \z in {0.1,0.6,1.1,1.6,2.1}
    \draw[blue!55] plot[domain=-0.35:1.45,samples=8]
      ({0.9*\x + 0.6*(1-\x)}, {0.55*\z - 0.35*\x + 0.3*(1-\x)});
  \foreach \xx in {-0.2,0.25,0.7,1.15,1.4}
    \draw[blue!55] ({0.9*\xx + 0.6*(1-\xx)}, {-0.35*\xx + 0.3*(1-\xx)})
      -- ({0.9*\xx + 0.6*(1-\xx)}, {1.155 - 0.35*\xx + 0.3*(1-\xx)});
  \node[blue!60!black] at (-2.7,-1.7) {$\pi: x + y = 1$};
  % paraboloid rings and profiles
  \foreach \h in {0.3,0.75,1.3,1.9}
    \draw[grid] plot[variable=\t,domain=0:360,samples=49]
      ({0.9*sqrt(\h)*cos(\t) + 0.6*sqrt(\h)*sin(\t)},
       {0.55*\h - 0.35*sqrt(\h)*cos(\t) + 0.3*sqrt(\h)*sin(\t)});
  \foreach \a in {0,45,90,135,180,225,270,315}
    \draw[grid] plot[domain=0:1.4,samples=9]
      ({0.9*\x*cos(\a) + 0.6*\x*sin(\a)},
       {0.55*\x*\x - 0.35*\x*cos(\a) + 0.3*\x*sin(\a)});
  % plane sigma: y = alpha (alpha = 0.5)
  \foreach \z in {0.1,0.6,1.1,1.6,2.1}
    \draw[orange!40] plot[domain=-1.3:1.3,samples=8]
      ({0.9*\x + 0.3}, {0.55*\z - 0.35*\x + 0.15});
  \foreach \xx in {-1.2,-0.6,0,0.6,1.2}
    \draw[orange!40] ({0.9*\xx + 0.3}, {-0.35*\xx + 0.15})
      -- ({0.9*\xx + 0.3}, {1.155 - 0.35*\xx + 0.15});
  \node[orange!70!black] at (2.9,2.2) {$\sigma: y = \alpha$};
  % intersection curve of Gamma and pi (red parabola)
  \draw[very thick,red] plot[domain=-0.25:1.25,samples=25]
    ({0.9*\x + 0.6*(1-\x)}, {0.55*(\x*\x + (1-\x)*(1-\x)) - 0.35*\x + 0.3*(1-\x)});
  % axes and labels
  \draw[->,dashed,blue!60!black] (0,0) -- (0,1.35);
  \node at (-1.6,2.4) {$\Gamma: z = x^2 + y^2$};
  \fill[red] ({0.9*0.5 + 0.6*0.5}, {0.55*0.5 - 0.35*0.5 + 0.3*0.5}) circle (2.0pt)
    node[below right] {$(x^{\star}, y^{\star})$};
\end{tikzpicture}

本题的几何意义如图所示。目标函数对应的曲面 $\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条件