一挑三 FJ vs KKT

作者: 史春奇 | 来源:发表于2017-07-24 10:15 被阅读741次

在解决最优化问题时候， Fermat 在1629年就解决了无限制最小问题，但是一直过了靠近160年，才有Lagrange解决等式约束的最值问题，然后再过了160左右，出现了四个人， Karush, John, Kuhn, 和Tucker，他们解决了不等式约束最值问题，这里讲的就是Fritz John, FJ是如何单挑其他三人,Karush, Kuhn, Tucker, KKT的。

FJ是什么？

FJ是1个人的姓名的首字母，是Fritz John, FJ，出生德国的数据家，把偏微分方程 partial differential equations, PDE玩的出神入化的一个人。大家可能都没有听说过他，但是他的黯然销魂掌练出了FJ条件（conditions），这掌不输于武林绝学KKT条件。一般来说，玩偏微分方程出生的都是牛银，譬如，某种意义上，算是我的校友的，Leslie Lamport, LL, 就是搞偏微分方程出身的。不认识LL的，我就说几个关键词吧，Latex的La，拜占庭将军问题Byzantine Generals Problem， 2013年图灵奖。好吧，说PDE说的激动了。

KKT是什么？

KKT是3个人的姓的首字母，分别是Karush, Kuhn和Tucker，最早是有Kuhn和Tucker在1951年总结发表的，但是后来人们发现Karush在1939年硕士论文中就发现了这个必要条件（necessary conditions）。硕士就能做出这样的成就也是非常不容易！但是由于参与了美国的曼哈顿计划（Manhattan Project），使得Karush本人对名利追求并不热衷，而追求和平，他对Karush和Tucker的定理的命名权并不放在心上。以至于KT条件在10年后才重命名为KKT条件。

KKT条件（Condition）是什么？

KKT条件是有不等式条件(inequality constrained problem)最值的必要条件（necessary conditions）。这是对Stationary Point最值理论和Lagrange Muliplier最值理论的进一步泛化（Generalization）。

无条件(unconstraind problem)

我们先回顾一下，无条件(unconstraind problem)最值的充要条件。

要注意的就是，就是鞍点saddle point需要被排除。

等式限制条件（equality constrained condition）

其次，等式限制条件（equality constrained condition）最值的充要条件。

可以看到只是把限制条件改变成了对拉格朗日量（lagrangian）梯度为零的情况。

等价于目标函数的梯度（或者导数）Gradient和限制条件的梯度（Jacobian）在同一直线上（或者成缩放关系）

这里面有两个概念一个是雅克比矩阵Jacobian Matrix，另外一个是零空间Null Space。雅克比矩阵是一个点附近利用梯度替代曲线的本地线性化（local linearization）。

零空间，是对矩阵Ax=0的解空间，零空间的更多细节参考“矩有四子”.

进一步理解雅克比矩阵的含义如下：

不等式限制条件（inequality constrained condition）

然后，不等式限制条件（inequality constrained condition）最值的充要条件。

我们可以看到对比等式情况，首先增加了对于 λ, lamda 与约束条件之间的关系限制。

等式和不等式并存的限制条件（equality and inequality constrained condition）

如果把上面两个不等式情况结合起来就是，我们讨论的KKT条件情况下的充要关系。

KKT要注意约束规格（constraintqualification）！

从上面可以看到， KKT条件是必要条件，并非充分条件，如果要变成充分条件还要加上约束规格(constraint qualification)的成立。

这个特别要注意的，这在美国空军B-2高空轰炸机（B-2 Stealth bomber）的设计上曾经出现过设计事故。在1980年左右，处于里根时代，在设计的时候对，空间在机翼机身分布，燃油，速度，推进器（thrust）都有很大的要求。

并且存在一个最值目标：满油箱状态要飞得最远。 B-2发明之前，其实已经有B-29和B-52机型的存在了。很幸运， B-2找到一个KKT解，这个解导致飞机机身极度压缩，使得飞机几乎由两个机翼组成。飞机设计完成后，实际测试的时候，发现这个机型和B-29，B-52相比，满油箱状态却飞得很短。然后就花费了上亿经费验证设计，没有找到设计模型上的问题。设计模型是对的，那为啥飞行距离很短呢？又花费了很多经费，最终发现，这个模型是一个非凸非线性模型（nonconvex nonlinear programming, nonconvex NLP），最后发现，最优解其实要求机翼很小，好比客机那样。所以KKT解是一个在空气动力学（aerodynamically）上几乎是最差劲的选择。但是最后B-2还是投入实用了，为啥，因为发现B-2有个极好的特性，雷达很难捕捉到，隐身功能。

什么是全局最优解的约束规格(constraint qualification)？

虽然前面给出了代数上的表达式来给定KKT的充要条件（局部最优，local optimum），但是如果直接按约束规格来描述的话，就需要了解凸函数的特性。凸函数，可以有凸函数和严格凸函数，它们之间的差异是有没有等式。伪凸函数（pseduoconvex），就是只要满足通过导数能求最值的函数，并不一样要求凸函数。还有半凸函数（quasiconvex），如下图所示：

基于不同的凸函数的性质，满足KKT条件，是不是全局最优（global optimum）有如下的约束规格（constraint qualification， CO）：

几何理解

为什么要有 dual feasibility （λ） >= 0？

首先，要注意λ的符号，根据Lagrange Stationarity限制，可以知道是有-∇f与∇h方向一致不一致性来定义的。λ>0意味中-∇f与∇h方向一致。

另外，因为要求最小值，那么根据梯度下降（gradient descent）的含义，我们就是要沿着梯度的负方向（-∇f）上走到底。

其次，我们看一下等式限制（equality constraint）的情况，这时候因为限制是在那条线上，所以λ的符号（-∇f与∇h方向一致不一致性）并不重要。因为只要所在直线定了，再加上h(x)=0线的固定，那么对应极值点就定了。

但是在不等式限制（inequality contraint）下，λ的符号（-∇f与∇h一致性）就很重要啦。当g(x)<0，那么根据梯度下降，在-∇f方向走到底，但是必须在g(x)的可行域（feasible region）里，这样要在边界取到最值，那只能如图所示-∇f方向指向区域外面，这样-∇f就固定了，那么在根据∇g的方向（指向g(x)大的一边），来判断λ的符号（-∇f与∇g一致性）。

所以只要g(x)<=0那么，就要求λ>=0。但是为什么前面总结的c(x)>=0,还要求λ>=0呢？那是因为他们的拉格朗日量（lagrangian）写的不一致。

所以相当于-c(x)<=0。这下理解为什么dual feasibility的几何意义了吧。

如何理解Complementary Slackness？

首先我们要比较一下对偶问题 duality，有如下结论：maxi-min <= mini-max。

矮子里面选高个<= 高个里面选矮子。矮子再怎么选都是矮子，高个再怎么挑也是高个，矮子不能高于高个。

根据对偶问题，很容易就知道弱对偶weak duality始终成立，但是如果强对偶strong duality成立的话，就会带来complementary slackness性质，反之，也是成立的。

所以Complementary slackness其实是保证强对偶成立的条件。

假设图示，我们有两个关系g(x)<=0 和 h(x)=0，我们很容易找到primal问题的最优点，就是z左边部分的最低点。

这时候我们再来看对偶问题maxi-min，我们先看求解最小的部分，我们看到如果在线上表示，过可行域里面的任意点，然后L=z+uy，其中y=0的时候， z=f(x)，那么最优解就是直线与z轴的交点。如果要最小化, 就要把先移到切线边上，这样截距最下最小。

然后我们看要使得这个切线的截距最大，就必须调整斜率u，使得它刚好是最低点的切线，这样我们发现求到的maxi-min点和之前primal问题里面的mini-max点一样。根据我们前面的定义，这是强对偶strong duality的情况。

那我们就要比较，当什么时候不一样了，我们发现当不是凸的区域的时候，这时候maxi-min的解要比mini-max的解小。所以这时候对应的weak duality。

这样我们进一步理解了，什么时候complementary slackness满足的话，实现了强对偶，而一个凸的问题，能使得complementary slackness成立。

FJ 和 KKT 的证明

一般情况下， FJ和KKT的证明比较类似，主流的证明，需要利用到一下Farkas Lemma，或者Gordan Theorem，本身这些定理也需要证明。

但是，奥尔迦.布列内娃 Olga, Brezhneva，这位来自俄罗斯的美女博士，她非常希望能够利用很简单的知识来证明Lagrange 和 KKT 定理，最终她发现，如果把KKT的适用范围稍微缩小一点（排除了， KKT对于不可导，但是次可导subdifferential的函数的适用性），可以有很简单的证明，她最终做到了，是不是看上去很美！！！

她的这个工作，得到了最优化工作的四大天王之一的北丐（Stephen Wright）的赏识。以后有时间希望把她的工作也囊括进来。

FJ条件（Condition）是什么？

FJ条件是也是针对等式和不等式同时约束的最优问题的条件。并且，FJ条件也是必要条件（necessary conditions），和KKT类似保护了3种条件， primal feasibility， dual feasibility和complementary slackness。

FJ vs KKT

前面，我们大概了解了FJ和KKT的工作性质，那么对比一下FJ和KKT工作的差异呢？

最大的差异就是FJ不如KKT严格，根据前面说过的，我们知道在线性规划（Linear Programming）中，满足KKT条件，那么一定是最优解（Optimum），但是LP中满足FJ条件，却不一定是最优解。

也正是因为FJ要比KKT稍微宽松一点，所以导致人们选择了KKT条件，以至于有些人都没有听过FJ条件。

但是并不是说FJ条件就可以不要了。因为KKT条件更严格就导致它的适用范围不如FJ条件广泛，举个例子如下，很明显这个情况中，FJ适用，但是KKT就不适用了。

主要原因就是KKT是FJ的约束规格（constraint qualification）下的例子，这个约束规格就是要求限制条件（constraint conditions）在最值点optimum的偏导数之间是线性独立的（linearly independent），如前图所示。而上面的例子可以看到在最优点的导数向量之间成反比，负相关的，不独立。所以FJ适用，但是KKT不适用了。

小结，这里简单总结了下， KKT条件中dual feasibility, complementary slackness的含义，同时简单对比了FJ 条件和KKT条件的差异。让我们看到一个牛掰的， 1挑3的FJ，但同时也感叹，FJ如果进一步细化，或许今天广泛应用的就是FJ系统（System）了！

附录：

最优化之东邪西毒南帝北丐

东邪 Dimitri Bertsekas MIT