凸优化
对偶
深入理解 KKT 条件

深入理解 KKT 条件

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

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

等式约束优化问题

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

minf(x,y)s.t.g(x,y)=0 \begin{aligned} \mathrm{min} \quad & f(x, y) \\ \mathrm{s.t.} \quad & g(x, y) = 0 \end{aligned}

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

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

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

{∂L∂x=fx(x,y)+λgx(x,y)=0∂L∂y=fy(x,y)+λgy(x,y)=0∂L∂λ=g(x,y)=0 \left\{ \begin{aligned} \frac{\partial L}{\partial x} &= f_x(x, y) + \lambda g_x(x, y) = 0 \\ \frac{\partial L}{\partial y} &= f_y(x, y) + \lambda g_y(x, y) = 0 \\ \frac{\partial L}{\partial \lambda} &= g(x, y) = 0 \end{aligned} \right.

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

不等式约束优化问题

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

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

minf(x,y)s.t.g(x,y)⩽0 \begin{aligned} \mathrm{min} \quad & f(x, y) \\ \mathrm{s.t.} \quad & g(x, y) \leqslant 0 \end{aligned}

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

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

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

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

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

更一般地，如果有多个不等式约束，对应到上图中就是有若干平面 σ1,⋯ ,σp\sigma_1,\cdots,\sigma_p，并且在最优点处 ∇f(x⋆,y⋆)\nabla f(x^{\star}, y^{\star}) 可由有效约束对应的平面的支撑超平面的法向量的线性表示。即 ∃μ1,⋯ ,μp⩾0\exists \mu_1,\cdots,\mu_p \geqslant 0，使得

∇f(x⋆,y⋆)=−(μ1∇g1(x⋆,y⋆)+⋯+μp∇gp(x⋆,y⋆)) \nabla f(x^{\star}, y^{\star}) = -(\mu_1 \nabla g_1(x^{\star}, y^{\star}) + \cdots + \mu_p \nabla g_p(x^{\star}, y^{\star}))

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

小结

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

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

KKT 条件的本质

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

fi(x⋆)⩽0,i=1,⋯ ,mhi(x⋆)=0,i=1,⋯ ,pλi⋆⩾0,i=1,⋯ ,mλi⋆fi(x⋆)=0,i=1,⋯ ,m∇f0(x⋆)+∑i=1mλi⋆∇fi(x⋆)+∑i=1pνi⋆∇hi(x⋆)=0 \begin{aligned} f_{i}\left(x^{\star}\right) &\leqslant 0, & i &=1, \cdots, m \\ h_{i}\left(x^{\star}\right) &=0, & i &=1, \cdots, p \\ \lambda_{i}^{\star} & \geqslant 0, & i &=1, \cdots, m \\ \lambda_{i}^{\star} f_{i}\left(x^{\star}\right) &=0, & i &=1, \cdots, m \\ \nabla f_{0}\left(x^{\star}\right)+\sum_{i=1}^{m} \lambda_{i}^{\star} \nabla f_{i}\left(x^{\star}\right)+\sum_{i=1}^{p} \nu_{i}^{\star} \nabla h_{i} \left(x^{\star}\right) &=0 & & \end{aligned}

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

  1. Lagrange 函数的定常方程式：上式最后一行 ∇L=0\nabla L = 0。
  2. 原始可行性：即满足等式约束和不等式约束，上式第一行 fi(x⋆)⩽0f_{i}\left(x^{\star}\right) \leqslant 0 和第二行 hi(x⋆)=0h_{i}\left(x^{\star}\right) =0。
  3. 对偶可行性：即上式第三行 λi⋆⩾0\lambda_{i}^{\star} \geqslant 0。
  4. 互补松弛性：即上式第四行 λi⋆fi(x⋆)=0\lambda_{i}^{\star} f_{i}\left(x^{\star}\right) =0。

简单的例子

考虑下面的问题

minx2+y2s.t.x+y=1y⩽α \begin{aligned} \mathrm{min} \quad & x^2 + y^2 \\ \mathrm{s.t.} \quad & x + y = 1 \\ \quad & y \leqslant \alpha \end{aligned}

写出 Lagrange 函数

L(x,y,λ,ν)=x2+y2+λ(1−x−y)+ν(y−α) L(x, y, \lambda, \nu) = x^2 + y^2 + \lambda(1 - x - y) + \nu(y - \alpha)

KKT 条件方程组如下

{2x−λ=0(1)2y−λ+ν=0(2)ν⩾0(3)ν(y−α)=0(4) \left\{\begin{aligned} 2x - \lambda &= 0 & (1) \\ 2y - \lambda + \nu &= 0 & (2) \\ \nu &\geqslant 0 & (3) \\ \nu(y - \alpha) &= 0 & (4) \end{aligned}\right.

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

{x=12λ(5)y=12λ−12ν(6) \left\{\begin{aligned} x &= \frac{1}{2} \lambda & (5) \\ y &= \frac{1}{2} \lambda - \frac{1}{2} \nu & (6) \end{aligned}\right.

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

λ=12ν+1 \lambda = \frac{1}{2} \nu + 1

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

{x=14ν+12(7)y=−14ν+12(8) \left\{\begin{aligned} x &= \frac{1}{4} \nu + \frac{1}{2} & (7) \\ y &= -\frac{1}{4} \nu + \frac{1}{2} & (8) \end{aligned}\right.

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

{ν⩾2−4αν⩾0 \left\{\begin{aligned} \nu & \geqslant 2 - 4 \alpha \\ \nu & \geqslant 0 \end{aligned}\right.

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

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

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

参考

最优性条件扰动和灵敏度分析