转自:http://xuehy.github.io/%E4%BC%98%E5%8C%96/2014/04/13/KKT/
从对偶问题到KKT条件
Apr 13, 2014
对偶问题（Duality）
======
对偶性是优化问题中一个非常重要的性质，它能够神奇地将许多非凸的优化问题转化成凸的问题，关于这一理论，恐怕又是一个博大精深的横向领域，这里我们一切从简，就从线性规划（LP）问题的对偶问题讲起。
说到对偶，我总是会不自禁地想起射影几何的东西，不过这里的对偶和射影几何无关，我们先来看一个非常simple的线性规划问题：
这个问题非常简单，相信初等数学里面这样的问题也是很常见的，最直接的做法就是画图，不等式表示平面的某个区域，然后目标函数是斜率给定的直线，通 过移动直线来获得最大的截距，求得问题的解。不过，不知道人们是否会发现，这些可行解似乎都是某几个不等式变成等式以后的方程组的解。可是，这个规律真的 通行无阻吗？
如果不能画图，比如不给草稿纸，不给笔（什么，你说要在大脑里画？），或者变量的个数非常多(Rn)，这会你还能画吗？
看来光靠作图是行不通了，我们得另寻出路。于是想象一下这样，
于是2成为了x+3y的一个下界，不过这里看起来也是下确界，于是问题解决！
再来看，
s.t.
我们令
于是，px+qy=a(x+y)+bx+cy≥2a,a≥0,b≥0,c≥0，2a为原问题的下界，于是我们可以求下面这个问题
直觉告诉我们（你也可以证明），后一个问题的解正是前一个问题的解，这后面那个问题就叫做原问题的对偶问题。
等等，如果你的数学足够好，你一定在嘀咕这是不是纯粹的毫无意义的奇技淫巧呢？一定在怀疑这样的方法能否推广呢？换句话说，每一个求最小的LP问题都能找到这样的求最大值的对偶问题吗？
我告诉你，答案是肯定的。
看下面这个一般性的LP问题，
假如，c∈Rn,A∈Rm×n,b∈Rm,G∈Rr×n,h∈Rr,
原问题（primal）为，
其对偶问题（dual）可以写为，
写了那么多像变戏法一样的公式，我们来看看有没有更好的方式来理解它呢？
对于每个可行解x,cTx≥cTx+uT(Ax−b)+vT(Gx−h):=L(x,u,v),这个式子显然是成立的,
令C表示原问题可行解的集合，f∗表示原问题的最优解，则f∗≥minx∈CL(x,u,v)≥minx∈RnL(x,u,v)=g(u,v)成立。
于是g(u,v)就是f∗的下界，再注意到，g(u,v)有一些很好的性质，
为了估计更“紧”的下界，我们要求g(u,v)的最大值，并且希望这个最大值正是原问题的最小值。
这个过程有点像很多生活中的事情，比如你去商店替公司买电脑，因为预算有限，上司提醒过你尽量买国产的便宜货，但是又要保证质量。你看了看，发现国 产的全部不超出预算，于是国产的电脑就成为了你本次购买花销的宽泛的下界，当然，你不希望电脑买回去三天就坏了，于是你在国产电脑中寻找比较贵的那种，希 望贵的质量好一些，就这样你顺利地完成了采购电脑的任务。
好了回到正题，我们知道，在线性规划（LP）问题中，对偶问题的解正是原问题的解。而且对偶问题里面几乎全是等式约束，看起来应该很好解决。
于是我们是不是可以洗洗睡了呢？慢！线性规划只是一个很naive的问题罢了，真正现实中的优化往往没那么简单，我们总会有各种麻烦，什么非线性 了，什么非凸了，甚至什么非连续不光滑了，总之现实世界总是和我们理想的数学世界差距太大，好比广告里的康师傅和现实中的康师傅（别忘了，“图片仅供参 考，以实物为准”。）。数学世界总是很简单，就像理想中的世界一样，一切秩序井然，但是工程的世界就好比真实的世界，各种社会问题，各种混乱层出不穷，要 是有机会，我真愿意在数学世界里呆上永远。
又说多了，下面我们忘掉LP问题，来看看更一般的约束优化问题。
我们定义一个在初等微积分中便已经听过的函数，拉格朗日函数
同样我们容易发现f(x)≥L(x,u,v)。
令C为原问题可行解的集合，f∗为原问题的最优解，则
我们称g(u,v)为Lagrange对偶函数，它给出了f∗的下界。
于是我们有了Lagrange对偶问题，
这一次我们没法保证对偶问题的解就是原问题的解。我们只能胸有成竹地说f∗≥g∗成立。
这个性质被称作弱对偶性（weak duality）。
理所当然，强对偶性（strong duality）是指f∗=g∗的情形了。
有个叫做Slater’s condition的东西，它告诉我们什么时候强对偶性成立，不过我们暂时不关心它，因为在实际中，即便是只有弱对偶性，往往对偶问题的解也已经满足要求了。 还有一个重要的性质，那就是对偶问题总是凸的，这可是解决优化问题的研究者们最大的福音了，因为对于凸的问题，军火库里有着一堆不同规格的武器，而对于非凸的，人们往往绞尽脑汁试图将其转化为凸优化问题。
好了回到原路，我们的目标是说明什么是KKT条件，到目前为止，我们已经知道了从LP到一般约束优化问题，对偶性怎样导致了Lagrange对偶问题的出现，
那么KKT在哪里呢？
不远了。
KKT
======
在开始将这个KKT条件之前，我们先回顾一下Lagrange对偶问题。
理解数学的东西，例子是必不可少的。那么我们就来看一下一个例子。
考虑二次规划（QP），Q≻0
这个问题的Lagrange函数为
令∂xL=0,我们得到x∗=−Q−1(c−u+ATv),
于是 g(u,v)=L(x∗,u,v)=−12(c−u+ATv)TQ−TQQ−1(c−u+ATv)−bTv=−12(c−u+ATv)TQ−1(c−u+ATv)−bTv,u≥0
好了，接下来我们来看KKT。
令x表示原问题可行域中的解，u,v是对偶问题可行解，我们定义duality gap（不知道怎么翻译，对偶差异？）为，
显然，我们有
上面这个式子，在算法的角度可是相当重要的，不过那是后话了。
对于一般性的约束优化问题
KKT 条件是
- 0∈∂f(x)+∑i=1mui∂h(x)+∑j=1rvi∂li(x)
- ui⋅hi(x)=0,∀i
- hi(x)≤0,lj(x)=0,∀i,j
- ui≥0,∀i
这四个条件分别被称作stationarity,complementary slackness,primal feasibility,dual feasibility。
可以证明KKT条件是原问题解和对偶问题解存在且gap为0的充分条件，在强对偶性下，也是必要条件。
好了，现在我们看到了KKT条件的面目，但是仔细琢磨，就会发现这些条件，不过是前面推导Lagrange对偶问题过程中，理所当然的一些东西罢了。
首先stationarity（平稳性）不过是Lagrange函数求极值得到Lagrange对偶函数的过程中，所需的步骤罢了。
第二个条件需要稍微推导一下（利用gap为0），不过也是很simple的，窃以为这个条件才是最关键的东西。后两个条件则更trivial。
有了前一部分的东西，KKT条件的出现也应该是理所当然的。然而数学总是这样，一些很简单的东西，往往出现之前就是巨大的困难。
KKT是Karush-Kuhn-Tucker的缩写，虽然Karush更早提出了这个东西，不过一直不被人注意（数学上很多东西都是这样），不过 他也算幸运的，至少没有被从这个条件的名字中除去，相比而言，很多其他人则倒霉多了。不过指不定他心里根本不在乎这个空虚的名衔呢！
想必到此为止，你定然对Lagrange对偶和KKT条件的来龙去脉有了简单的认识了，你至少知道对偶问题是怎么来的，为什么以及什么时候能够等价于原问题，然后KKT条件不过是更加抽象的总结罢了。
接下来我们看一下KKT条件的各种出场。KKT条件使得我们能够直接分析一个优化问题，不必再劳神地写出Lagrange函数，求出对偶问题。它使 得我们能够依据原问题直接写出解的充要条件，得到一个新的问题，而这个新问题的求解往往有一些固定的套路和算法，但是口说无凭，到底方便在哪，我们到以后 再说。 同样，我们继续看二次规划问题，不过这次的约束条件都是等式约束。
对于Q⪰0，
利用KKT条件，我们可以得到原问题解x的充要条件，
对于某个u
将 [xu]视作整体，则原二次规划问题等价于上面的线性系统求解问题。
再看一个简单的例子，求f(x,y)=3x2+4y2+x−5y在x,y≥0时候的最小值。
由KKT条件，我们可以写出
简单分情况分析一下，我们就可以得到正确的解x=0,y=58。
最后，让我们来看一个复杂一些的问题，这个问题涉及到矩阵分解，
已知矩阵X,L,我们要找到矩阵U,V,满足
其中U,V都是非负矩阵。
于是令Ψ,Φ分别为uik≥0和vjk≥0的Lagrange乘子,则
Lagrange函数可以写为
KKT条件告诉我
因此我们可以得到如下方程：
基于这个方程可以得到一个迭代求解上面该问题的算法。
具体么，我懒得写了。总之，KKT条件无所不在，只要你要处理优化问题，那就休想逃避它了。当然如果你只想永远做一个不求甚解的实践者，那么也不用操心它，不过有谁能丢下这么奇妙的数学，而不觉得可惜呢？