一挑三 FJ vs KKT

2017-07-24 本文已影响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

西毒 Stephen P. Boyd Stanford University

南帝 Andrzej Ruszczyński Rutgers University

北丐 Stephen J. Wright, University of Wisconsin

郭靖 Mark Schmidt, University of British Columbia

中神通 Werner Fenchel

中顽童 Jean Jacques Moreau

一挑三 FJ vs KKT

猜你喜欢

热点阅读