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的梯度g1g2在一个平面上,这个平面的法平面是该点的切线。

有条件极值.jpg

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

拉格朗日条件.png

这里需要注意两点:

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是二维空间两条直线,如下图:

等式约束.png

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

二、约束条件为不等式

2.1 几何角度

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

不等式约束.png

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

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

全局一.jpg

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

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

拉格朗日乘法.jpg

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

222.jpg

不等式2.gif

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

图二jpg.jpg

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

不等式3.gif     

从之前约束条件为等式分析可以知道,上面公式代表了n个等式(x ∈ Rn),而我们目标是求出n+m个变量,即变量x1,x2,x3..xn1,μ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有解。

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

不等式约束.png

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

1222.gif       ④

-请登陆后阅读余下文章-
登录|注册
上一篇  一维搜索 下一篇 惩罚函数
评论区