Karush-Kuhn-Tucker (KKT)条件是非线性规划(nonlinear programming)最佳解的必要条件。KKT条件将Lagrange乘数法(Lagrange multipliers)所处理涉及等式的约束优化问题推广至不等式。在实际应用上，KKT条件(方程组)一般不存在代数解，许多优化算法可供数值计算选用。这篇短文从Lagrange乘数法推导KKT条件并举一个简单的例子说明解法。
1. 等式约束优化问题
给定一个目标函数$f:\mathbb{R}^n \rightarrow \mathbb{R}$ ，我们希望找到$x \in \mathbb{R}$，在满足约束条件$g(x) = 0$的前提下，使得$L(x,\lambda) = f(x) + \lambda g(x)$有最小值。这个约束优化问题记为
\[\begin{align*} min \quad f&(x)\\ s.t. \quad g&(x)=0\end{align*}\]为方便分析，假设$f$与$g$是连续可导函数。我们在高等数学中学过的Lagrange乘数法是等式约束优化问题的典型解法。
定义Lagrangian函数
\[L(x,\lambda) = f(x) + \lambda g(x)\]其中$\lambda$ 称为Lagrange乘数。Lagrange乘数法将原本的约束优化问题转换成等价的无约束优化问题
\[\min\limits_{x,\lambda} \ L(x,\lambda)\]计算$L$对$x$与$\lambda$的偏导数并令其为0，可得最优解的必要条件： \(\nabla_{x}L = \frac{\partial L}{\partial x} = \nabla f + \lambda \nabla g = 0\)
\[\nabla_{\lambda}L = \frac{\partial L}{\partial \lambda} = g(x) = 0\]其中第一式为定常方程式(stationary equation)，第二式为约束条件。解开上面$n+1$个方程式可得$L(x,\lambda)$的stationary point$x^{\star}$以及$\lambda$的值(正负数皆可能)。
2. 不等式约束优化问题
接下来我们将约束等式$g(x)=0$推广为不等式$g(x) \leq 0$ 。考虑这个问题
\[\begin{align*} min \quad f&(x)\\ s.t. \quad g&(x) \leq 0\end{align*}\]假设$x^{\star}$为满足约束条件的最佳解，分开两种情况讨论：
(1) $g(x^{\star}) < 0$, 最佳解位于可行域$K$的内部，称为内部解(interior solution)，这时约束条件是无效的(inactive)；
(2) $g(x^{\star}) = 0$, 最佳解落在可行域$K$的边界，称为边界解(boundary solution)，此时约束条件是有效的(active)。
这两种情况的最佳解具有不同的必要条件。
(1)内部解：在约束条件无效的情形下，$g(x)=0$不起作用，约束优化问题退化为无约束优化问题，因此驻点$x^{\star}$满足$\nabla f=0$且$\lambda=0$。
(2)边界解：在约束条件有效的情形下，约束不等式变成等式$g(x)=0$，这与前述Lagrange乘数法的情况相同。我们可以证明驻点$x^{\star}$发生于$\nabla f \in span \nabla g$，换句话说，存在$\lambda$使得$\nabla f = -\lambda \nabla g$，但这里$\lambda$的正负号是有其意义的。因为我们希望最小化$f$，梯度$\nabla f$ (函数$f$在点$x$的最陡上升方向)应该指向可行域$K$的内部(因为最优解最小值是在边界取得的)，但$\nabla g$指向$K$的外部(即$g(x) > 0$的区域，因为约束是小于等于0)，因此$\lambda \ge 0$，称为对偶可行性(dual feasibility)。
因此，不论是内部解或边界解，$\lambda g(x)=0$恒成立，称为互补松弛性(complementary slackness)。整合上述两种情况，最佳解的必要条件包括Lagrangian函数$L(x,\lambda)$的定常方程式、原始可行性、对偶可行性，以及互补松弛性：
\[\begin{align*}\nabla_{x}L = \nabla f + \lambda \nabla g = 0 \\g(x) \leq 0 \\ \lambda \geq 0 \\ \lambda g(x) = 0 \end{align*}\]这些条件合称为Karush-Kuhn-Tucker (KKT)条件。如果我们要最大化$f(x)$且受限于$g(x) \leq 0$，那么对偶可行性要改成$\lambda \leq 0$
上面结果可推广至多个约束等式与约束不等式的情况。考虑标准约束优化问题(或称非线性规划)：
\[\begin{align*}min \quad f&(x)\\s.t. \quad g_{j}&(x) = 0, j = 1,\cdots,m,\\ \quad h_{k}&(x) \leq 0, k = 1,\cdots,p.\end{align*}\]定义Lagrangian 函数
\[L(x,\{\lambda_{j}\},\{\mu_{k}\}) = f(x) + \sum\limits_{j=1}^m \lambda_{j}g_{j}(x) + \sum\limits_{k=1}^p\mu_{k}h_{k}(x)\]其中$\lambda_{j}$是对应$g_{j}(x)=0$的Lagrange乘数，$\mu_{k}$是对应$h_{k}(x) \leq 0$的Lagrange乘数(或称KKT乘数)。
KKT条件包括
\[\begin{align*}\nabla_{x}L &= 0 \\g_{j}(x)& = 0, j=1,\cdots,m,\\h_{k}(x) &\leq 0,\\ \mu_{k} &\geq 0,\\ \mu_{k}h_{k}(x) &= 0, k=1,\cdots,p.\end{align*}\]3. 一个例子
\[\begin{align*}min \quad x_1^2 + x_2^2,\\s.t. \quad x_1 + x_2 = 1 \\ \quad x_2 \leq \alpha, \end{align*}\]其中$\left(x_{1}, x_{2}\right) \in \mathbb{R}^{2}$，$\alpha$为实数. 写出Lagrangigan函数
\[L\left(x_{1}, x_{2}, \lambda, \mu\right)=x_{1}^{2}+x_{2}^{2}+\lambda\left(1-x_{1}-x_{2}\right)+\mu\left(x_{2}-\alpha\right)\]KKT方程组如下：
\[\begin{aligned} \frac{\partial L}{\partial x_{i}} &=0, \quad i=1,2 \\ x_{1}+x_{2} &=1 \\ x_{2}-\alpha & \leq 0 \\ \mu & \geq 0 \\ \mu\left(x_{2}-\alpha\right) &=0 \end{aligned}\]求偏导可得$\frac{\partial L}{\partial x_1}=2 x_1-\lambda=0$ , $\frac{\partial L}{\partial x_2}=2 x_2-\lambda+\mu=0$ , 分别解出$x_1=\frac{\lambda}{2}$ 且 $x_2=\frac{\lambda}{2}-\frac{\mu}{2}$. 代入约束等式$x_1 + x_2 = 1$, 得$x_1=\frac{\mu}{4}+\frac{1}{2}$, $x_2=-\frac{\mu}{4}+\frac{1}{2}$
最后再加入约束不等式，$-\frac{\mu}{4}+\frac{1}{2} \leq \alpha$，即$\mu \geq 2-4 \alpha$. 下面分三种情况讨论
(1) $\alpha > \frac{1}{2}$ : 不难验证$\mu=0>2-4 \alpha$ 满足所有的KKT条件，约束不等式是无效的，$x_1^{\star}=x_2^{\star}=\frac{1}{2}$是内部解，目标函数的最小值是$\frac{1}{2}$.
(2) $\alpha = \frac{1}{2}$ : 如同1，$\mu=0=2-4 \alpha$，满足所有的KKT条件，$x_1^{\star}=x_2^{\star}=\frac{1}{2}$是边界解
(3) $\alpha < \frac{1}{2}$ : 这时约束不等式是有效的，$\mu=2-4 \alpha>0$，则$x_1^{\star}=1-\alpha$，$x_2^{\star}=\alpha$，目标函数的极小值是$(1-\alpha)^{2}+\alpha^{2}$.
