KKT条件_KKT在什么情况下使用

KKT（Karush-Kuhn-Tucker）条件有时也称KT条件，最初发现此定理的是Kuhn，Tucker两人，后来发现Karush在1939年的一篇文章中已经有过这个定理表述，所以常以取三人名字命名为KKT条件。不带约束的非线性规划问题可以用梯度法、模式搜索法获得最优解，带约束的线性规划可以通过单纯形法解决，KKT条件解决的是带有约束、非线性规划最优解问题，根据约束形式可分为等式和不等式或两种情况混合的情形，针对这三种情形，KKT条件给出了通用的公式化解决方案，满足KKT条件的点称为K-T点，K-T点同时也是非线性规划的最优解。KKT在非线性规划、神经网络、对偶定理中都有重要的应用，KKT是机器学习中必须掌握的知识点。

一、约束条件为等式

    约束条件是等式情形在介绍函数梯度与隐函数说明过，利用拉格朗日乘法可获得此时的最值，具体推导过程可看本站历史文章。简单回顾一下，满足多个等式的图像是空间的一条’曲线’，或者说满足所有等式约束条件的可行区是空间的一条’曲线’。’曲线’上任意一点的切线正交于所有约束函数在该点的梯度，当目标函数在这条’曲线’有最优解时，目标函数的在最值点处的梯度，也正交于曲线在最值点的切线（可由最值点处目标函数偏导数都为0推导出），因此可以得到一个结论：约束函数和目标函数的梯度都正交于’曲线’最值点的切线，所以目标函数在最值点的梯度可用约束函数梯度线性表示。如下图，目标函数f的梯度▽f与等式约束g1、g2的梯度▽g1、▽g2在一个平面上，这个平面的法平面是该点的切线。

约束为等式时,KKT条件表述如下：

这里需要注意两点：

1、上面的表述中正交两个字打了黑体加粗，正交与垂直两者有区别，两个向量垂直代表相互夹角是90度，而正交含义是内积为0，比如任何向量和零向量的内积都是0，这是正交的情形但并不垂直。

2、曲线两个字都打了引号，代表这里的曲线是一个抽象的空间几何概念，要与平常认知的曲线区别开。比如两个平面h1(x,y)=x-y-2和h2(x,y)=-5x-y+1是三维空间平面，而当h1(x,y)=0和h2(x,y)=0时，x-y-2=0和-5x-y+1=0是二维空间两条直线，如下图：

这两条直线在二维空间相交于点P，点P就是上面表述’曲线’的一种，点P的切线是一个零向量，h1(x,y)和h2(x,y)梯度▽h1、▽h2是二维空间两个向量，而▽h1、▽h2与零向量内积必定为0，代表梯度正交于切线。

二、约束条件为不等式

2.1 几何角度

    带有不等式的非线性规划问题可以用下面形式表达：

不等式方程组gi(x)>=0所围成区域为目标函数的可行区，由于gi(x)有可能是非线性函数，此时可行区不能确保是凸集，即使是凸集，该凸集有可能有无数个极点，此时不能像单纯形法那样迭代每个极点获得最值，可行区与目标函数的定义域位置关系可以分为两种情形。

情形一：目标函数的全局最小点在可行区内，如下图：

红色圆点代表目标函数的等值线，点状空间代表了不等式约束设定的可行区，这种情形直接用梯度法求解目标函数即可获得最值，约束条件不起到任何作用，KKT条件不是专门针对这种情形。

情形二：目标函数的全局最值点在可行区外，此时只能求得目标函数在约束条件下的局部最值点，如下图所示：

观察图像可以发现，目标函数等值线与约束边界相切时得到最值点，边界函数为gi(x)=0，与等式约束条件一样，此处目标函数的梯度与边界函数gi(x)梯度有如下关系：

f函数梯度指向函数增大方向，即指向可行区内；而在可行区内约束函数gi(x)<=0,gi(x)的梯度应指向可行区域外，所以f函数梯度与约束函数gi(x)梯度方向正好是相反的；如果不等式约束是x+y>=-2,则两个梯度是同一个方向。这里演示的是等值线与众多约束中一个条件边界相切情形，有时目标函数与可行区相交于一点，该点是多个约束边界的交点，如下图所示：

上图红色点代表最值点，它是g1(x)≦0、g2(x)≦0两个约束条件边界的交点，由于最值必定出现在边界上，所以不等式约束情形可以转化为等式约束的情形，有拉格朗日乘数法表达式：

     ②

从之前约束条件为等式分析可以知道，上面公式代表了n个等式（x ∈ Rn），而我们目标是求出n+m个变量，即变量x1,x2,x3..xn;μ1,μ2,..μm，目前方程组的方程只有n个，这显然是解不出来的。看一下最值点所在的位置，将红色最值点标记为x*，我们把约束分为两类，一类不等式约束其边界不是最值点所在曲线，如上图的边界g3(x)，将最值点x*带入后恒有g3(x*)>0，最终的最值点相对于g3(x)>=0这个约束，可以自由移动一段距离都不会违反这个约束，换言之g3(x)>=0这个不等式相对于最值点没有起到任何约束作用,这时g3(x*)对应的梯度系数μ3可设为0；另一类不等式边界是最值点所在曲线，如上面的g1(x),g2(x),这类约束对应的梯度系数大于0，但本身是边界函数，函数本身值为0。综上所述，对于所有的不等式,无论最终是否起到约束作用，都有以下等式：

μigi(x)=0       ③

公式3也称为互补松弛条件，得到这m个等式松弛条件后联合公式（2）即可解出所有的变量，从而得到最值。不等式约束非线性规划问题中，具体到每一个不等式是否起到约束作用，是根据最值点位置来确定的，通过引入互补松弛条件本质是一种待定系数法。

2.2  代数角度

    上面从几何角度说明了约束为不等式的情形，几何方法形象生动，带来弊端是不严谨，接下来通过代数方法归纳KKT条件，首先引入Gordan定理：

Gordan定理：设A是m*n矩阵，则Ax<0有解的充要条件是ATy=0,y>=0无解。

Gordan定理的充分性和必要性都可以通过反证法证明，这里不详细介绍证明过程,Gordan定理是充要性的描述，所以也可以反过来描述:

设A是m*n矩阵，则Ax<0无解的充要条件是ATy=0,y>=0有解。

    针对开始非线性规划问题：

设有最值点x*,则点x*沿着方向d延伸一端距离后，如果要求仍然还在可行区内，对方向d是有要求的，从之前分析可知，最值点一定出现在边界上，而边界函数值等于0，利用微分知识可以写出这个条件:,即必须确保最值点沿d方向是递增的，这样才能确保gi(x)>0从而满足约束条件，为了和Gordan定理形式相同，把这个条件改写为：

       ④

余下文章请转至链接：KKT条件

今天的文章KKT条件_KKT在什么情况下使用分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。