kkt条件_kkt条件 python - CSDN
精华内容
参与话题
  • 在求取有约束条件的优化问题时,拉格朗日乘子法(Lagrange Multiplier) 和KKT条件是非常重要的两个求取方法,对于等式约束的优化问题,可以应用拉格朗日乘子法去求取最优值;如果含有不等式约束,可以应用KKT条件去...

    在求取有约束条件的优化问题时,拉格朗日乘子法(Lagrange Multiplier) 和KKT条件是非常重要的两个求取方法,对于等式约束的优化问题,可以应用拉格朗日乘子法去求取最优值;如果含有不等式约束,可以应用KKT条件去求取。当然,这两个方法求得的结果只是必要条件,只有当是凸函数的情况下,才能保证是充分必要条件。KKT条件是拉格朗日乘子法的泛化。之前学习的时候,只知道直接应用两个方法,但是却不知道为什么拉格朗日乘子法(Lagrange Multiplier) 和KKT条件能够起作用,为什么要这样去求取最优值呢?

    本文将首先把什么是拉格朗日乘子法(Lagrange Multiplier) 和KKT条件叙述一下;然后开始分别谈谈为什么要这样求最优值。

    一. 拉格朗日乘子法(Lagrange Multiplier) 和KKT条件

    通常我们需要求解的最优化问题有如下几类:

    (i) 无约束优化问题,可以写为:

                                          min f(x);  

    (ii) 有等式约束的优化问题,可以写为:

                                           min f(x), 

                                                s.t. h_i(x) = 0; i =1, ..., n 

    (iii) 有不等式约束的优化问题,可以写为:

                                          min f(x), 

                                                s.t. g_i(x) <= 0; i =1, ..., n

                                                      h_j(x) = 0; j =1, ..., m

    对于第(i)类的优化问题,常常使用的方法就是Fermat定理,即使用求取f(x)的导数,然后令其为零,可以求得候选最优值,再在这些候选值中验证;如果是凸函数,可以保证是最优解。

    对于第(ii)类的优化问题,常常使用的方法就是拉格朗日乘子法(Lagrange Multiplier) ,即把等式约束h_i(x)用一个系数与f(x)写为一个式子,称为拉格朗日函数,而系数称为拉格朗日乘子。通过拉格朗日函数对各个变量求导,令其为零,可以求得候选值集合,然后验证求得最优值。

    对于第(iii)类的优化问题,常常使用的方法就是KKT条件。同样地,我们把所有的等式、不等式约束与f(x)写为一个式子,也叫拉格朗日函数,系数也称拉格朗日乘子,通过一些条件,可以求出最优值的必要条件,这个条件称为KKT条件。

    (a) 拉格朗日乘子法(Lagrange Multiplier)

    对于等式约束,我们可以通过一个拉格朗日系数a 把等式约束和目标函数组合成为一个式子L(a, x) = f(x) + a*h(x), 这里把a和h(x)视为向量形式,a是横向量,h(x)为列向量,之所以这么写,完全是因为csdn很难写数学公式,只能将就了.....。

    然后求取最优值,可以通过对L(a,x)对各个参数求导取零,联立等式进行求取,这个在高等数学里面有讲,但是没有讲为什么这么做就可以,在后面,将简要介绍其思想。

    (b) KKT条件

    对于含有不等式约束的优化问题,如何求取最优值呢?常用的方法是KKT条件,同样地,把所有的不等式约束、等式约束和目标函数全部写为一个式子L(a, b, x)= f(x) + a*g(x)+b*h(x),KKT条件是说最优值必须满足以下条件:

    1. L(a, b, x)对x求导为零;

    2. h(x) =0;

    3. a*g(x) = 0;

    求取这三个等式之后就能得到候选最优值。其中第三个式子非常有趣,因为g(x)<=0,如果要满足这个等式,必须a=0或者g(x)=0. 这是SVM的很多重要性质的来源,如支持向量的概念。

    二. 为什么拉格朗日乘子法(Lagrange Multiplier) 和KKT条件能够得到最优值?

    为什么要这么求能得到最优值?先说拉格朗日乘子法,设想我们的目标函数z = f(x), x是向量, z取不同的值,相当于可以投影在x构成的平面(曲面)上,即成为等高线,如下图,目标函数是f(x, y),这里x是标量,虚线是等高线,现在假设我们的约束g(x)=0,x是向量,在x构成的平面或者曲面上是一条曲线,假设g(x)与等高线相交,交点就是同时满足等式约束条件和目标函数的可行域的值,但肯定不是最优值,因为相交意味着肯定还存在其它的等高线在该条等高线的内部或者外部,使得新的等高线与目标函数的交点的值更大或者更小,只有到等高线与目标函数的曲线相切的时候,可能取得最优值,如下图所示,即等高线和目标函数的曲线在该点的法向量必须有相同方向,所以最优值必须满足:f(x)的梯度 = a* g(x)的梯度,a是常数,表示左右两边同向。这个等式就是L(a,x)对参数求导的结果。(上述描述,我不知道描述清楚没,如果与我物理位置很近的话,直接找我,我当面讲好理解一些,注:下图来自wiki)。


    而KKT条件是满足强对偶条件的优化问题的必要条件,可以这样理解:我们要求min f(x), L(a, b, x) = f(x) + a*g(x) + b*h(x),a>=0,我们可以把f(x)写为:max_{a,b} L(a,b,x),为什么呢?因为h(x)=0, g(x)<=0,现在是取L(a,b,x)的最大值,a*g(x)是<=0,所以L(a,b,x)只有在a*g(x) = 0的情况下才能取得最大值,否则,就不满足约束条件,因此max_{a,b} L(a,b,x)在满足约束条件的情况下就是f(x),因此我们的目标函数可以写为 min_x max_{a,b} L(a,b,x)。如果用对偶表达式: max_{a,b} min_x  L(a,b,x),由于我们的优化是满足强对偶的(强对偶就是说对偶式子的最优值是等于原问题的最优值的),所以在取得最优值x0的条件下,它满足 f(x0) = max_{a,b} min_x  L(a,b,x) = min_x max_{a,b} L(a,b,x) =f(x0),我们来看看中间两个式子发生了什么事情:

     f(x0) = max_{a,b} min_x  L(a,b,x) =  max_{a,b} min_x f(x) + a*g(x) + b*h(x) =  max_{a,b} f(x0)+a*g(x0)+b*h(x0) = f(x0)

    可以看到上述加黑的地方本质上是说 min_x f(x) + a*g(x) + b*h(x) 在x0取得了最小值,用fermat定理,即是说对于函数 f(x) + a*g(x) + b*h(x),求取导数要等于零,即

    f(x)的梯度+a*g(x)的梯度+ b*h(x)的梯度 = 0

    这就是kkt条件中第一个条件:L(a, b, x)对x求导为零。

    而之前说明过,a*g(x) = 0,这时kkt条件的第3个条件,当然已知的条件h(x)=0必须被满足,所有上述说明,满足强对偶条件的优化问题的最优值都必须满足KKT条件,即上述说明的三个条件。可以把KKT条件视为是拉格朗日乘子法的泛化。

    展开全文
  • KKT条件

    千次阅读 2019-07-31 16:19:54
    设目标函数为f(x),有k个等式约束条件h(x),等式约束条件有k个系数为λk,使用拉格朗日函数法求最优解。构造拉格朗日函数: 对变量求偏导,可以得到k+1个方程,方程组的解就是函数极值。 3、不等式约束条件 ...

    最优化问题分为三种情况:

    1、无约束问题

    y = f(x),直接求解即可。

     

    2、等式约束条件

    设目标函数为f(x),有k个等式约束条件h(x),等式约束条件有k个系数为λk,使用拉格朗日函数法求最优解。构造拉格朗日函数:

    对变量求偏导,可以得到k+1个方程,方程组的解就是函数极值。

     

    3、不等式约束条件

    设目标函数为f(x),有j个等式约束条件h(x),等式约束条件有j个系数为λk,有k个不等式约束条件,不等式约束条件有k个系数Uk,使用拉格朗日函数法求最优解。构造拉格朗日函数:

    若要求解此问题,需要满足的条件就是KKT条件:

    KKT条件是使一组解成为最优解的必要条件,凸问题中的KKT条件也是充分条件。

     

     

    展开全文
  • KKT条件介绍

    万次阅读 多人点赞 2016-01-16 15:34:36
    KKT条件入门介绍 最近学习的时候用到了最优化理论,但是作为学渣的我是没有多少这方面的理论基础。于是翻了很多大神的博客把容易理解的内容记载到这篇博客中。因此这是篇汇总博客,不算是全部原创,但是基础理论,...

    KKT条件介绍

           最近学习的时候用到了最优化理论,但是我没有多少这方面的理论基础。于是翻了很多大神的博客把容易理解的内容记载到这篇博客中。因此这是篇汇总博客,不算是全部原创,但是基础理论,应该也都差不多吧。因才疏学浅,有纰漏的地方恳请指出。

          KKT条件是解决最优化问题的时用到的一种方法。我们这里提到的最优化问题通常是指对于给定的某一函数,求其在指定作用域上的全局最小值。提到KKT条件一般会附带的提一下拉格朗日乘子。对学过高等数学的人来说比较拉格朗日乘子应该会有些印象。二者均是求解最优化问题的方法,不同之处在于应用的情形不同。

          一般情况下,最优化问题会碰到一下三种情况:

    (1)无约束条件

        这是最简单的情况,解决方法通常是函数对变量求导,令求导函数等于0的点可能是极值点。将结果带回原函数进行验证即可。

    (2)等式约束条件

         设目标函数为f(x),约束条件为hk(x),形如

         s.t. 表示subject to ,“受限于”的意思,l表示有l个约束条件。

         则解决方法是消元法或者拉格朗日法。消元法比较简单不在赘述,拉格朗日法这里在提一下,因为后面提到的KKT条件是对拉格朗日乘子法的一种泛化。

         定义拉格朗日函数F(x),

         其中λk是各个约束条件的待定系数。                                                           

         然后解变量的偏导方程:

          ......,

         如果有l个约束条件,就应该有l+1个方程。求出的方程组的解就可能是最优化值(高等数学中提到的极值),将结果带回原方程验证就可得到解。

         至于为什么这么做可以求解最优化?维基百科上给出了一个比较好的直观解释。

         举个二维最优化的例子:

         min f(x,y) 

         s.t. g(x,y) = c

         这里画出z=f(x,y)的等高线(函数的等高线定义:二元函数z = f(x,y)在空间表示的是一张曲面,这个曲面与平面z = c的交线在xoy面上的投影曲线f(x,y)=c称为函数z=f(x,y)的一条登高线。):


           绿线标出的是约束g(x,y)=c的点的轨迹。蓝线是f(x,y)的等高线。箭头表示斜率,和等高线的法线平行。从梯度的方向上来看,显然有d1>d2。绿色的线是约束,也就是说,只要正好落在这条绿线上的点才可能是满足要求的点。如果没有这条约束,f(x,y)的最小值应该会落在最小那圈等高线内部的某一点上。而现在加上了约束,最小值点应该在哪里呢?显然应该是在f(x,y)的等高线正好和约束线相切的位置,因为如果只是相交意味着肯定还存在其它的等高线在该条等高线的内部或者外部,使得新的等高线与目标函数的交点的值更大或者更小,只有到等高线与目标函数的曲线相切的时候,可能取得最优值。

    如果我们对约束也求梯度g(x,y),则其梯度如图中绿色箭头所示。很容易看出来,要想让目标函数f(x,y)的等高线和约束相切,则他们切点的梯度一定在一条直线上。

    :∇f(x,y)=λ(∇g(x,y)-C) 
    其中λ可以是任何非0实数。

           一旦求出λ的值,将其套入下式,易求在无约束极值和极值所对应的点。


           这就是拉格朗日函数的由来。

    (3)不等式约束条件

           设目标函数f(x),不等式约束为g(x),有的教程还会添加上等式约束条件h(x)。此时的约束优化问题描述如下:


          则我们定义不等式约束下的拉格朗日函数L,则L表达式为:


          其中f(x)是原目标函数,hj(x)是第j个等式约束条件,λj是对应的约束系数,gk是不等式约束,uk是对应的约束系数。0

          此时若要求解上述优化问题,必须满足下述条件(也是我们的求解条件):


          这些求解条件就是KKT条件。(1)是对拉格朗日函数取极值时候带来的一个必要条件,(2)是拉格朗日系数约束(同等式情况),(3)是不等式约束情况,(4)是互补松弛条件,(5)、(6)是原约束条件。

          对于一般的任意问题而言,KKT条件是使一组解成为最优解的必要条件,当原问题是凸问题的时候,KKT条件也是充分条件。

           关于条件(3),后面一篇博客中给出的解释是:我们构造L(x,λ,u)函数,是希望L(x,λ,u)<=f(x)的(min表示求最小值)。在L(x,λ,u)表达式中第二项为0,若使得第三项小于等于0就必须使得系数u>=0,这也就是条件(3)。

           关于条件(4),直观的解释可以这么看:要求得L(x,λ,u)的最小值一定是三个公式项中取得最小值,此时第三项最小就是等于0值的时候。稍微正式一点的解释,是由松弛变量推导而来。

    为方便表示,举个简单的例子:

    现有如下不等式约束优化问题:


    此时引入松弛变量可以将不等式约束变成等式约束。设a1和b1为两个松弛变量,则上述的不等式约束可写为:


    则该问题的拉格朗日函数为:


    根据拉格朗日乘子法,求解方程组:



    同样 u2b1=0,来分析g2(x)起作用和不起作用约束。

    于是推出条件:



    KKT条件介绍完毕。


    参考文献:

    [1]kkt条件:点击打开链接

    [2]kkt条件:点击打开链接

    [3]拉格朗日乘子法:点击打开链接

    [4]对偶理论:点击打开链接









    展开全文
  • 【数学基础】KKT条件

    万次阅读 多人点赞 2018-08-05 00:04:21
    继前面讲的拉格朗日乘子法。拉格朗日乘子法主要用于求解等式约束的问题,当约束...上图左表达的是,当我们要找的局部最优解(或者全局最优解)刚好就在约束条件的可行区域内部(这个时候最优解对应的是g(x)&lt...

    继前面讲的拉格朗日乘子法。拉格朗日乘子法主要用于求解等式约束的问题,当约束加上不等式之后,情况变得更加复杂,首先来看一个简单的情况,给定如下不等式约束问题:

    对应的 Lagrangian 与图形分别如下所示:

    上面这段话可能描述的不够清楚。我总结一下。上图左表达的是,当我们要找的局部最优解(或者全局最优解)刚好就在约束条件的可行区域内部(这个时候最优解对应的是g(x)<0),此时约束条件就没有任何的作用,故此时我们可以让\lambda=0,因为约束条件没有作用。上图右表达的就是没有约束条件下的局部最优解(或者全局最优解)在加上约束条件之后,就取不到了(不在可行域之中了),这时可行域中的局部最优解(或者全局最优解)一定会在边界g(x)=0处取到。所以无论哪种情况都会得到:

    其实就是在这种情况下,我们考虑上图右约束圆圈的边界,而最优点就落在,约束条件的圆心与目标函数的圆心相连直线与边界相交的那个点上。

    有一点需要注意的是,在无约束的拉格朗日乘子法中等式约束与目标函数的梯度是平行的,在这里其实也是平行的,但多了一个条件不仅要平行还要相反,故\lambda必须>0,在等式约束中就没有这个限制。

    看完这张图你可能会觉得这和我上面讲的不一样,但实际上是一样的。这一段不是在解释为什么\lambda为什么一定要大于0,而是在解释当取到最优解的时候,(用我上面的话来讲就是)最优点就落在,约束条件的圆心与目标函数的圆心相连直线与边界相交的那个点上。它是在解释为什么两者是平行的(线性相关的)。

    其实按照我之前的理解来就好了,图中的梯度只画了一个目标函数的,容易搞混了,在红点处其实还有一个反方向的约束条件的梯度。

    可见对于不等式约束,只要满足一定的条件,依然可以使用拉格朗日乘子法解决,这里的条件便是 KKT 条件。接下来给出形式化的 KKT 条件 首先给出形式化的不等式约束优化问题:

    列出 Lagrangian 得到无约束优化问题:

    经过之前的分析(算上拉格朗日乘子法处理等式约束那一篇文章的),便得知加上不等式约束后可行解 x(局部最优解或全局最优解,可能有多个,要代原式中判断) 需要满足的就是以下的 KKT 条件:

    注意这边L只对x求偏导。

    满足 KKT 条件后极小化 Lagrangian 即可得到在不等式约束条件下的可行解。 KKT 条件看起来很多,其实很好理解:

    (1) :拉格朗日取得可行解的必要条件;

    (2) :这就是以上分析的一个比较有意思的约束,称作松弛互补条件;

    (3) ∼∼ (4) :初始的约束条件;

    (5) :不等式约束的 Lagrange Multiplier 需满足的条件。


    一个简单的例子

    其实这边有个问题,约束函数一般是取到等号的,不然很有可能就无解了。

     

    还有两个约束就是原本的不等式约束g_1(x)<=0,g_2(x)<=0

    用这6个等式联立方程组解出x,\alpha就好了。在例子原文中作者啰嗦了一大堆。但实际上就是这个道理。不过对于这种求解方程组的工作,会有一些更高效的方法去做。如SMO算法。以后有时间会再详细讲解的。

    SVM 中的支持向量便是来自于此,需要注意的是 KKT 条件与对偶问题也有很大的联系,下一篇文章就是拉格朗日对偶。


    从拉格朗日乘子法到KKT条件,讲了这么多,对于拉格朗日乘子\alpha或者\lambda在做什么似乎还没有明了的讲过。

    拉格朗日乘子加入到目标函数中,有两个作用:

    1. 将约束函数引入到目标函数中,转化为无约束问题,不满足约束条件的解会使得目标函数无穷大,故而无解。
    2. 引入拉格朗日乘子另一个最大的作用就是将约束条件与目标函数混在一起,使得我们可以同时计算目标函数的梯度与约束条件的梯度,根据相关的性质从而找到我们想找到的局部最优解或者全局最优解。

    参考文章:

    约束优化方法之拉格朗日乘子法与KKT条件

    解密SVM系列(一):关于拉格朗日乘子法和KKT条件

     

    展开全文
  • 真正理解拉格朗日乘子法和KKT条件

    万次阅读 多人点赞 2018-05-29 11:08:13
     这篇博文中直观上讲解了拉格朗日乘子法和 KKT 条件,对偶问题等内容。 首先从无约束的优化问题讲起,一般就是要使一个表达式取到最小值: minf(x)minf(x) min f(x)  如果问题是 maxf(x)maxf(x)maxf(x) 也可以...
  • KKT条件总结

    千次阅读 2018-08-16 15:34:52
     最近学习的时候用到了最优化理论,但是我没有多少这方面的... KKT条件是解决最优化问题的时用到的一种方法。我们这里提到的最优化问题通常是指对于给定的某一函数,求其在指定作用域上的全局最小值。提到KKT条...
  • 什么是KKT条件

    万次阅读 2019-04-22 19:49:52
    尊重原创:知乎:什么是KKT条件 对于具有等式和不等式约束的一般优化问题 [\begin{array}{l} \min {\rm{ }}f({\bf{x}})\ s.t.{\rm{ }}{g_j}({\bf{x}}) \le 0(j = 1,2, \cdots ,m)\ {\rm{ }}{h_k}({\bf{x}}) = 0(k = ...
  • 拉格朗日乘子法及KKT条件证明

    千次阅读 2018-12-28 14:30:20
    拉格朗日乘子法(Lagrange Multiplier) 和KKT条件
  • 最优化理论与KKT条件

    万次阅读 2014-05-09 09:59:51
    最优化理论是研究函数在给定一组约束条件下的最小值(或者最大值)的数学问题. 一般而言, 一个最优化问题具有如下的基本形式: min.:f(x) s.t.:gi(x)≤0,i=1,2,...,p,hj(x)=0,k=1,2,...,q,x∈...
  • 拉格朗日乘数法和KKT条件的直观解释 标签(空格分隔): 机器学习 linbin 2018-05-10 Abstract 在SVM的推导中,最优化问题是其中的核心,这里我们简单介绍下最优化问题,特别是带有约束的最优化问题,并且...
  • PS:以下来自人工智能头条公众号,支持向量机部分约束问题分为等式约束和不等式约束,对于等式约束问题我们可以直接采用...一、关于拉格朗日乘子法和KKT条件1)关于拉格朗日乘子法首先来了解拉格朗日乘子法,那么为什...
  • 然而我看了一些文章和西瓜书后总结出KKT条件是 对于 x∈D, max L(x, lambda, mu) = f(x)的条件 ![图片说明](https://img-ask.csdn.net/upload/201801/19/1516372126_180896.jpg) 然后这两个问题的解在值上相等的条件...
  • 凸优化、拉格朗日乘子、KKT条件

    千次阅读 2018-05-22 16:16:38
    在学校开的机器学习课上老师讲了拉格朗日乘子和KKT条件,当时百思不得其解啊,为什么约束区域如果不包括可行解,那么最优解一定在边界上?后来在网上查了凸函数的性质:Convex optimization is a subfield of ...
  • 一般地,一个最优化数学模型能够表示成下列标准形式: ... KKT最优化条件是Karush[1939]以及Kuhn和Tucker[1951]先后独立发表出來的。这组最优化条件在Kuhn和Tucker发表之后才逐渐受到重视,因此许多书只记载成「Kuhn
  • SVM中KKT条件介绍

    千次阅读 2017-02-24 15:59:30
    KKT条件介绍  最近学习的时候用到了最优化理论,但是我没有多少这方面的理论基础。于是翻了很多大神的博客把容易理解的内容记载到这篇博客中。因此这是篇汇总博客,不算是全部原创,但是基础理论,应该也都...
  • 拉格朗日乘子法和KKT条件

    万次阅读 2013-12-13 10:28:08
    拉格朗日乘子法(Lagrange Multiplier)和KKT(Karush-Kuhn-Tucker)条件是求解约束优化问题的重要方法,在有等式约束时使用拉格朗日乘子法,在有不等约束时使用KKT条件。前提是:只有当目标函数为凸函数时,使用这两种...
  • KKT条件--约束问题最优化方法

    千次阅读 2019-07-07 23:14:06
    KKT条件: KKT可以概括为以下三个条件: 1)最优点x必须满足所有等式及不等式限制条件, 也就是说最优点必须是一个可行解 2)在最优点x, ∇f 必须是 ∇gi 和 ∇hj 的线性組合(α和β是拉格朗日乘子) 3)该...
  • kkt条件详解

    千次阅读 2017-10-19 11:41:37
    KKT条件介绍  最近学习的时候用到了最优化理论,但是我没有多少这方面的理论基础。于是翻了很多大神的博客把容易理解的内容记载到这篇博客中。因此这是篇汇总博客,不算是全部原创,但是基础理论,应该也都...
  • KKT(Karush-Kuhn-Tucher)条件

    万次阅读 多人点赞 2017-08-02 15:40:41
    KKT(Karush-Kuhn-Tucher)条件在优化理论中,KKT条件是非线性规划(nonlinear programming)最佳解的必要条件[1]。KKT条件将lagrange乘数法(Lagrange multipliers)中的等式约束优化问题推广至不等式约束。本文从La...
  • KKT条件详解

    千次阅读 多人点赞 2019-09-17 13:31:38
    KKT条件详解 主要参考这篇文章和这个知乎回答。 KKT最优化条件是Karush[1939],以及Kuhn和Tucker[1951]先后独立发表出來的。这组最优化条件在Kuhn和Tucker发表之后才逐渐受到重视,因此许多情况下只记载成库恩塔克...
1 2 3 4 5 ... 20
收藏数 6,529
精华内容 2,611
关键字:

kkt条件