一文理解拉格朗日对偶和KKT条件
目标函数: , 引入Lagrange算子:
目标函数:
约束条件:
根据约束条件和目标函数的类型分为3类:
KKT条件指在满足某些规则条件下, 非线性规划 问题能有***解的 充要条件 , 是广义拉格朗日乘数的重要成果
一般优化问题(含等式和不等式约束约束):
引入Lagrange算子 :
KKT条件指上述问题的***点 必须满足:
(1) 约束条件满足:
(2)
即,
***点 处, 必须是 和 的 线性组合
引入拉格朗日算子可以求出极值的原因 :
(3) 且
不等式约束一直是优化问题中的难题，求解对偶问题可以将支持向量机原问题约束中的不等式约束转化为等式约束；
支持向量机中用到了高维映射，但是映射函数的具体形式几乎完全不可确定，而求解对偶问题之后，可以使用核函数来解决这个问题。
并不一定要用拉格朗日对偶。要注意用拉格朗日对偶并没有改变***解，而是改变了算法复杂度：
在原问题下，求解算法的复杂度与样本维度（等于权值w的维度）有关；
而在对偶问题下，求解算法的复杂度与样本数量（等于拉格朗日算子a的数量）有关。
因此，
支持向量机实现非线性的方法的数学本质是升维，升维升到无穷维则无法表达w, 所以还是使用拉格朗日对偶方法更好一点。准确的说，可以用一些优化算法直接求最小间距，但是，升维的时候核要是正定的，且升维可数，而且不是很大的时候可以用。
任意一个带约束的优化均可写成:
将上述带约束的优化问题转化为无约束优化问题, 定义拉格朗日(Lagrangian)函数如下:
***化Lagrangian, 令
z(x)满足原始约束条件的x, 其值等于 :
满足初始约束, 则 , 拉格朗日函数第三项被消去:
又因为 , 所以 的***值在 处取得.
所以原始带约束优化问题等价于以下无约束优化问题:
等价于:
上述问题称为 primal problem
总结:
dual problem 只是将primal proble调换了min和max位置:
注意上式和 并不等价.
令:
上式中 为拉格朗日对偶函数(Lagrange dual function), 是primal function的一个下界.
即, 若将primal proble的最小值记为 , 则对于所有的 , 有:
证明:
对所有满足约束条件的x, 总有:
因此
假设 在 处取得极值, 则
代入上式:
于是
这样, 的上界是 ,于是:
是primal problem的 ***下界 !
记dual problem 的***值为 , 得到:
该性质称为weak duality, 对所有的优化问题都成立.
此外,
称为duality gap.
基于weak duality的重要结论:
当
成立时,称为strong duality.
严格满足约束条件的点x, 指 严格到 , 即存在x满足:
原始问题是convex且满足slater条件,则strong duality成立:
特例: 对某些 非convex optimization,strong duality也成立
条件(2)中若 必有 , 反之, 若 可得 , 此条件在SVM中用来证明非支持向量 对应的系数
complementary slacknes 加上其他约束条件即为KKT条件:
通过dual problem可求primal problem的解:
kkt条件是什么？
库恩塔克条件。
亦称“K-T条件”，库恩塔克条件(Kuhn-Tucker conditions)是非线性规划领域里最重要的理论成果之一，是确定某点为极值点的必要条件。如果所讨论的规划是凸规划，那么库恩-塔克条件也是充分条件。
相关信息：
比较库恩-塔克定理与拉格朗日定理，可以发现主要区别在于库恩-塔克乘子的符号是非负的，而拉格朗日乘子可以是任意一个数，这一增加的信息优势可以是很有用的。
当然，库恩-塔克定理仅是极大值条件的一个必要条件,然而，在一个重要的情形里，它是必要且充分的。
***化问题求解方法
在求解***化问题中，拉格朗日乘子法（Lagrange Multiplier）和KKT（Karush Kuhn Tucker）条件是两种最常用的方法。在有等式约束时使用拉格朗日乘子法，在有不等约束时使用KKT条件。
我们这里提到的***化问题通常是指对于给定的某一函数，求其在指定作用域上的全局最小值(因为最小值与***值可以很容易转化，即***值问题可以转化成最小值问题)。提到KKT条件一般会附带的提一下拉格朗日乘子。对学过高等数学的人来说比较拉格朗日乘子应该会有些印象。二者均是求解***化问题的方法，不同之处在于应用的情形不同。
一般情况下，***化问题会碰到一下三种情况：
这是最简单的情况，解决方法通常是函数对变量求导，令求导函数等于0的点可能是极值点。将结果带回原函数进行验证即可。
设目标函数为f(x)，约束条件为h_k(x)，形如:
s.t. 表示subject to ，“受限于”的意思，l表示有l个约束条件。
则解决方法是消元法或者拉格朗日法。消元法比较简单不在赘述，这里主要讲拉格朗日法，因为后面提到的KKT条件是对拉格朗日乘子法的一种泛化。
作为一种优化算法，拉格朗日乘子法主要用于解决约束优化问题，它的基本思想就是通过引入拉格朗日乘子来将含有n个变量和k个约束条件的约束优化问题转化为含有（n+k）个变量的无约束优化问题。拉格朗日乘子背后的数学意义是其为约束方程梯度线性组合中每个向量的系数。
如何将一个含有n个变量和k个约束条件的约束优化问题转化为含有（n+k）个变量的无约束优化问题？拉格朗日乘数法从数学意义入手，通过引入拉格朗日乘子建立极值条件，对n个变量分别求偏导对应了n个方程，然后加上k个约束条件（对应k个拉格朗日乘子）一起构成包含了（n+k）变量的（n+k）个方程的方程组问题，这样就能根据求方程组的方法对其进行求解。
首先定义拉格朗日函数F(x)：
然后解变量的偏导方程：
我们上述讨论的问题均为等式约束优化问题，但等式约束并不足以描述人们面临的问题，不等式约束比等式约束更为常见，大部分实际问题的约束都是不超过多少时间，不超过多少人力，不超过多少成本等等。所以有几个科学家拓展了拉格朗日乘数法，增加了KKT条件之后便可以用拉格朗日乘数法来求解不等式约束的优化问题了。
设目标函数f(x)，不等式约束为g(x)，有的教程还会添加上等式约束条件h(x)。此时的约束优化问题描述如下：
则我们定义不等式约束下的拉格朗日函数L，则L表达式为：
其中f(x)是原目标函数，hj(x)是第j个等式约束条件，λj是对应的约束系数，gk是不等式约束，uk是对应的约束系数。
常用的方法是KKT条件，同样地，把所有的不等式约束、等式约束和目标函数全部写为一个式子L(a, b, x)= f(x) + a g(x)+b h(x)，
首先，我们先介绍一下什么是KKT条件。
KKT条件是指在满足一些有规则的条件下, 一个非线性规划(Nonlinear Programming)问题能有***化解法的一个必要和充分条件. 这是一个广义化拉格朗日乘数的成果. 一般地, 一个***化数学模型的列标准形式参考开头的式子, 所谓 Karush-Kuhn-Tucker ***化条件，就是指上式的***点x∗必须满足下面的条件:
1). 约束条件满足gi(x∗)≤0,i=1,2,…,p, 以及,hj(x∗)=0,j=1,2,…,q
2). ∇f(x∗)+∑i=1μi∇gi(x∗)+∑j=1λj∇hj(x∗)=0, 其中∇为梯度算子;
3). λj≠0且不等式约束条件满足μi≥0,μigi(x∗)=0,i=1,2,…,p。
SVM系列第七讲--KKT条件
上一讲我们介绍了***化问题的两种形式，无约束的和等式约束条件下的，这一讲，我们主要介绍不等式约束条件下的***化问题，并介绍一下我们的KKT条件。
设目标函数f(x)，不等式约束为g(x)，有的教程还会添加上等式约束条件h(x)。此时的约束优化问题描述如下：
则我们定义不等式约束下的拉格朗日函数L，则L表达式为：
求取这些等式之后就能得到候选***值。其中第三个式子非常有趣，因为g(x)=0，如果要满足这个等式，必须a=0或者g(x)=0. 这是SVM的很多重要性质的来源，如支持向量的概念。
接下来我们介绍一下KKT条件的推导：首先让我们针对针对 λ 和 ν ***化，令：
这里 λ⪰0 理解为向量 λ 的每一个元素都非负即可。这个函数 z(x) 对于满足原始问题约束条件的那些 x 来说，其值等于 f0(x) ，这很容易验证，因为满足约束条件的 x 会使得 hi(x)=0 ，因此最后一项消掉了，而 fi(x)≤0 ，并且我们要求了 λ⪰0 ，因此 λifi(x)≤0 ，所以***值只能在它们都取零的时候得到，这个时候就只剩下 f0(x) 了。因此，对于满足约束条件的那些 x 来说，f0(x)=z(x) 。这样一来，原始的带约束的优化问题其实等价于如下的无约束优化问题：
我们把上面的形式称为原始问题，之前了解过SVM的同学肯定知道，如果我们把min和max对换一下位置，就得到这个问题的对偶问题：
交换之后的对偶问题与原始问题的解并不相等，直观的可以这么理解，别墅中***的房子的价格也要比普通楼房的最贵的价格高。当然这是很不严格的说法，我们需要严格的证明这一点，和刚才的z(x)类似，我们再定一个公式：
g 有一个很好的性质就是它是 primal problem 的一个下界。换句话说，如果 primal problem 的最小值记为 p∗ ，那么对于所有的 λ⪰0 和 ν ，我们有：
证明过程如下图：
在强对偶性成立的情况下，我们就可以通过对原始问题的对偶问题的求解来得到***解（SVM就是这么做的），但并不是所有情况下强对偶性都成立，它会有一定的前提。
如果你不是专门研究规划问题的同学，咱们还是直接看结论吧。首先我们介绍一下Slater 条件，Slater 条件是指存在严格满足约束条件的点 x ，这里的“严格”是指 fi(x)≤0 中的“小于或等于号”要严格取到“小于号”，亦即，存在 x 满足：
我们有：如果原始问题是凸优化问题（很庆幸，SVM的规划问题是一个凸优化问题）的并且满足 Slater 条件的话，那么 strong duality 成立。需要注意的是，这里只是指出了 strong duality 成立的一种情况，而并不是唯一情况，不过研究SVM的话 ，知道这种情况足够了。
让我们回到 duality 的话题。来看看 strong duality 成立的时候的一些性质。
假设 x∗ 和 (λ∗,ν∗) 分别是 primal problem 和 dual problem 的极值点，相应的极值为 p∗ 和 d∗ ，首先 p∗=d∗ ，此时我们可以得到：
因为左右两端其实是相等的，所以上面的小于等于号可以替换为等于号，我们一共替换了两次，这两次替换我们都能得到一个重要的性质：
再将其他一些显而易见的条件写到一起，就是传说中的 KKT (Karush-Kuhn-Tucker) 条件：
任何满足强对偶性（不一定要求是通过 Slater 条件得到，也不一定要求是凸优化问题）的问题都满足 KKT 条件，换句话说，这是 强对偶性 的一个必要条件。不过，当原始问题是凸优化问题的时候（当然还要求一应函数是可微的，否则 KKT 条件的最后一个式子就没有意义了），KKT 就可以升级为充要条件。换句话说，如果 原始问题是一个凸优化问题，且存在 x˜ 和 (λ˜,ν˜) 满足 KKT 条件，那么它们分别是 原始问题 和 对偶问题 的极值点并且强对偶性成立。
kkt条件的推导思路以及八卦
KKT条件是用来判断一个解是否属于一个非线性***化问题的。
这个条件也是推导出来的
我们知道，我们要求解一个***化问题，其实就是求解一个函数在某些变量取值不定情况下的最值。首先要看这个函数是不是凸函数，如果是，就是可以用求导求极值的方法求的几个局部***，然后在局部***中选出***即可
如果要求解的这个函数带有等式约束，可以引入拉格朗日乘子，把这些等式约束巧妙的变化到函数中，等效于在函数中多加了几个变量，这个变量就是拉格朗日乘子，然后用求导求极值的方法求的***值。
如果要求解的这个函数不仅仅带有等式约束，还带有不等式约束，那就可以先想个办法把不等式约束变成等式约束，然后再引入拉格朗日乘子，把这些等式约束变化到函数去，再利用求导数求极值的方法求出***值。
其实就是这么一个过程：
那么这个KKT条件就是用来被判断这种带有不等式约束问题解的。把不等式约束变为等式约束，而后又把等式约束巧妙的变化到函数中后，利用求倒求极值的计算时，就把这个条件推导出来了。
KKT条件是这个过程中必然经过的一个点，所以，推导过程中，也可以直接写到这一步，利用这个条件，简化推导过程。
其实KKT条件从功能上可以叫做： 不等式约束的极值必要条件
KKT来源于一个人名，Karush-kuhn-Tucker ***化条件，由于人名Karush-kuhn-Tucker有时候可以别称为Kuhn-Tucker,所以又叫 Kuhn-Tucker条件，Kuhn-Tucker***化条件，又叫库恩塔克条件
原来这是3个人，karush[1939],kuhn-tucker[1951]先后独立发表出来的，由于这组优化条件再kuhn和tucker发表之后才受到重视，因此许多书只记载成了Kuhn-tucker***化条件，库恩塔克***化条件。
刚开始人们只知道kuhn-tucker的文章，后来发现karush在1939年就发表了相关文章。
1939年，德国闪击波兰，人类历史上最波澜壮阔的二战开始了
karush 全称william karush ,生日1917年3月1日，所以1939年时，他是22岁。卒年1997年2月22日。活了80年。 美国加里弗尼亚大学名誉教授
当年发表的文章为
* Minima of functions of several variables with inequalities as side conditions. (1939), William Karush, Thesis (S.M.)--University of Chicago, Department of Mathematics (UoC).
全名：harold w.Kuhn 1925年生，美国数学家，研究博弈论。与David Gale 和 Albert W.Tucker一起，赢得了诺依曼理论奖。普林斯顿大学数学名誉教授。他发明了有名的库恩扑克，作为分配问题的匈牙利描述方法。
他与John Forbes Nash长期合作过，他们曾经是研究生同事，一生的朋友和同事。是让1994年诺贝尔经济学奖委员会关注到Nash的关键人物。Kuhn和Nash都和Albert W. Tucker长期合作过。Tucker是Nash的导师。普林斯顿再电影 A Be***tiful Mind（美丽心灵）采用了Nash的生活。
《美丽心灵》是由朗·霍华德执导，罗素·克劳、詹妮弗·康纳利等主演的剧情片，该片于2001年12月21日在美国上映。该片讲述了患有精神分裂症的数学家约翰·福布斯·纳什，在博弈论和微分几何学领域潜心研究，最终获得诺贝尔经济学奖的故事。
影评在这里：
写到这里不得不说，我们常用的一个解题条件的作者，竟然有这么大的社会影响力
这些作者真不敢随便八卦，一八卦就是一个大牛。
全名：Albert W.Tucker,加拿大籍美国人。1928年多伦多大学毕业，1932年在普林斯顿大学博士毕业。带了很多有名的博士生，在剑桥，哈弗，芝加哥大学游学多年，1933年到达普林斯顿，一直呆到1970年。他主持了普林斯顿数学系长达20年时间。1905年出生，1995年去世，寿命为90年。他的导师叫Lefschetz,1884年9月3日生于莫斯科，1972年卒于普林斯顿。
这些大牛门在学校一直做学术研究，而中国这边却经历了清朝，中国民国，中国等大历史时代。
拉格朗日乘子法和KKT条件
拉格朗日乘子法要解决的就是有 等式 限制条件的凸优化问题。形式如下：
例如：
令
令 导数为0，得到：
求解出x, y, z即为***解，同时也会求出λ，但是没什么用。
关于拉格朗日乘子法的直观理解网上已经有很多解释了，此处仅简要描述。如下图中的f和g，虚线为f的等高线，g限制条件，可以看出，f一定是在和g相切的地方取到***（小）值，所以两者在此处的梯度方向相同，仅相差一个比例因子（即公式中的λ）。
注意g(x)=0是一条曲线，如果有多个限制条件则有多条曲线，此时将g(x)看做一个函数，则g(x)=0是g的一个等高线，函数与等高线垂直的方向一定是增加最快的方向，即梯度方向。f和g梯度方向一样，所以有：
然后再外加一个所求的点一定在曲线g上的方程（即F(x)对λ的导数为0），以上公式和拉格朗日乘子法得出的公式是等价的。
拉格朗日乘子法仅适用于等式约束条件，那如果约束条件为不等式怎么办呢？
答： 当约束条件为不等式时候，结合KKT条件，依然可以用拉格朗日乘子法求解，实际上KKT条件可以把不等式约束转化为等式约束。即，KKT条件求解的问题的形式为：
待续。。。
关于kkt条件和kkt条件和拉格朗日的关系的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。