数学——KKT condition

Posted on Edited on In

实际上，之前的文章中已经多次提到了KKT条件，比如机器学习中SVM，以及信息论中信道容量.但是都是具体问题下的kkt条件。这次来概括说明下，纯数学中的kkt条件。

要说KKT条件，是离不开lagrange multiplier，也就是拉格朗日乘数法。这是在求约束极值下一个非常重要的方法，可以参考：lagrange multiplier。

那么什么是KKT条件呢？

对于目标函数$f:\mathbb{R}^n \rightarrow \mathbb{R}$，约束函数$g_i: \mathbb{R}^n \rightarrow \mathbb{R}$,$h_j: \mathbb{R}^n \rightarrow \mathbb{R}$,如果他们在点$x^ *$都是连续可微的，那么$x^ *$是一个局部最优解,那么需要满足下面几个条件：

  • stationary
    • for maximizing $f(x):\nabla f(x^*) = \sum_{i=1}^m\mu_i\nabla g_i(x^*)+ \sum_{j=1}^n\lambda_i\nabla h_j(x^*)$
    • for minimizing $f(x):-\nabla f(x^*) = \sum_{i=1}^m\mu_i\nabla g_i(x^*)+ \sum_{j=1}^n\lambda_i\nabla h_j(x^*)$
  • primal feasibility
    • $g_i(x^ *) \leq 0$, for $i=1,…,m$
    • $h_j(x^ *) = 0$, for $j=1,…,n$
  • Dual feasibility
    • $\mu_i > 0$, for $i=1,…,m$
  • complementary slackness
    • $\mu_ig_i(x^*)=0$, for $i=1,…,m$.

这几个条件就是KKT条件。如果$m=0$，可以看到的就是高数中的条件极值问题，也就是约束为$h_i(x)=0$.

这几个条件是怎么得到的？什么道理？实际上之前的SVM中说明了。假如我们要minimize，那么约束条件可以转化为dual problem：
$$
\min_{\mu_i,\mu_i \ge 0} (\max (f(x)+\sum_{i=1}^m \mu_i g_i(x) + \sum_{j=1}^n \lambda_j h_j(x) ))
$$

为了让上面的式子和有约束的情况下一样，我们需要保证$\mu_i \ge 0$,因为我们需要让上式满足这个约束$g_i(x) \ge 0$。加入有$x_{\theta},g_i(x_{\theta})>0$,那么在$\max$这一步会将它放至无限大，导致$min$的时候它一定不会被选到。所以$\mu_i \ge 0$是dual feasibility，而primal feasibility也很好理解，也就是那些约束。

至于complementary slackness, 也是很好理解的。如果解上式，$g_i(x)<0$最终会得到$u_i=0$，因此得到$\mu_ig_i(x^*)=0$.

而stationary也就是对对偶问题两侧求导并得0得到的条件。

在凸函数上，满足KKT条件是就是最优解，也就是充要条件，否则只是最优解的必要条件。