KKT条件(Karush–Kuhn–Tucker conditions)

对于一般地约束优化问题

其中,自变量$\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,$使得

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

以上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