KKT条件（Karush–Kuhn–Tucker conditions）

对于一般地约束优化问题

$$\begin{array}{ll} {\min } & {f(\boldsymbol x)} \\ {\text {s.t.}} & {g_{i}(\boldsymbol x) \leq 0 \quad(i=1, \ldots, m)} \\ {} & {h_{j}(\boldsymbol x)=0 \quad(j=1, \ldots, n)} \end{array}$$

其中，自变量$\boldsymbol x\in \mathbb{R}^n$。设$f(\boldsymbol x),g_i(\boldsymbol x),h_j(\boldsymbol x)$具有连续的一阶偏导数，$\boldsymbol x^*$是优化问题的局部可行解。若在$\boldsymbol x^*$处约束限制条件（constraint qualifications or regularity conditions）^[1][2]成立，则一定存在$\boldsymbol \mu^*=(\mu_1^*,\mu_2^*,…,\mu_m^*)^T,\boldsymbol \lambda^*=(\lambda_1^*,\lambda_2^*,…,\lambda_n^*)^T,$使得

$$\left\{ \begin{aligned} & \nabla_{\boldsymbol x} L(\boldsymbol x^* ,\boldsymbol \mu^* ,\boldsymbol \lambda^* )=\nabla f(\boldsymbol x^* )+\sum_{i=1}^{m}\mu_i^* \nabla g_i(\boldsymbol x^* )+\sum_{j=1}^{n}\lambda_j^* \nabla h_j(\boldsymbol x^*)=0 &(1) \\ & h_j(\boldsymbol x^*)=0 &(2) \\ & g_i(\boldsymbol x^*) \leq 0 &(3) \\ & \mu_i^* \geq 0 &(4)\\ & \mu_i^* g_i(\boldsymbol x^*)=0 &(5) \end{aligned} \right.$$

其中$L(\boldsymbol x,\boldsymbol \mu,\boldsymbol \lambda)$为拉格朗日函数

$$L(\boldsymbol x,\boldsymbol \mu,\boldsymbol \lambda)=f(\boldsymbol x)+\sum_{i=1}^{m}\mu_i g_i(\boldsymbol x)+\sum_{j=1}^{n}\lambda_j h_j(\boldsymbol x)$$

以上5条即为KKT条件，其中条件(2)和(3)为约束条件显然成立，条件(1)、(4)、(5)成立的简单证明（严格数学证明参见[1] § 4.2.1）如下：

由约束条件：$g_i(\boldsymbol x) \leq 0$可知，$\boldsymbol x^*$一定满足$g_i(\boldsymbol x^*) \lt 0$或者$g_i(\boldsymbol x^*) = 0$，下面对这两种情形分别进行讨论：

• 当$g_i(\boldsymbol x^*) \lt 0$时：
  此时极小值点在$g_i(\boldsymbol x) \lt 0$这个区域内（如上图左部所示），所以$g_i(\boldsymbol x) \leq 0$这个约束可以忽略，那么此时的优化问题等价于仅含等式约束的优化问题，所以$\mu_i^* = 0$。
• 当$g_i(\boldsymbol x^*) = 0$时：
  此时极小值点在$g_i(\boldsymbol x) = 0$这个边界上，所以约束$g_i(\boldsymbol x) \leq 0$等价于约束$g_i(\boldsymbol x) = 0$，那么此时的优化问题同样等价于仅含等式约束的最优化问题。根据拉格朗日乘子法的原理可知，此时$f(\boldsymbol x)$和$ g_i(\boldsymbol x)=0$在极小值点处相切（如上图右部所示），梯度（正梯度）平行，即$\nabla f(\boldsymbol x^*)+\mu_i^* \nabla g_i(\boldsymbol x^*)=0 \quad (\mu_i^*\in \mathbb{R})$。易知$g_i(\boldsymbol x)=0$这个边界上的梯度都是向外的，而$\nabla f(\boldsymbol x^*)$一定和$\nabla g_i(\boldsymbol x^*)$的方向相反（如果不相反的话极小值点就不会在边界上取到而是在$g_i(\boldsymbol x) \lt 0$内取），所以$\nabla f(\boldsymbol x^*)$和$\nabla g_i(\boldsymbol x^*)$异号，那么$\mu_i^*$一定大于0。

综上，当$g_i(\boldsymbol x^*) \lt 0$时$\mu_i^* = 0$， $g_i(\boldsymbol x^*) = 0$时$\mu_i^* \gt 0$，所以条件(4)、(5)恒成立；由于对$\lambda_j$取值无要求，所以总存在$\lambda_j^*$使得条件(1)恒成立。
【注】：

• 若在$\boldsymbol x^*$处约束限制条件成立，则KKT条件是局部可行解$\boldsymbol x^*$的必要条件；
• 若在$\boldsymbol x^*$处约束限制条件不成立，则局部解$\boldsymbol x^*$不一定满足KKT条件（证明参见[1] § 4.2.1）;
• 满足KKT条件的点$\boldsymbol x^*$不一定是局部可行解（证明参见[1] § 4.2.1）；
• 若上述优化问题是凸优化问题，也即目标函数$f(\boldsymbol x)$是凸函数，不等式约束$g_i(\boldsymbol x)$是凸函数，等式约束$h_j(\boldsymbol x)$是仿射函数，那么此时KKT条件为局部可行解$\boldsymbol x^*$的充分条件，同时局部可行解$\boldsymbol x^*$也为全局可行解（证明参见[1] § 4.4），特别地，此时若在$\boldsymbol x^*$处约束限制条件也成立，那么KKT条件即升级为充要条件=充分条件+必要条件；

参考文献：

[1] 王燕军. 《最优化基础理论与方法》
[2] Karush–Kuhn–Tucker conditions