Farkas引理算是凸优化中经典和常用的引理了,可以用在很多地方(例如证明KKT条件),最近在看最优运输问题和Wasserstein距离的一些东西,中间对偶性的证明过程中用到了Farkas引理,顺路上来回答一发。
原引理长这样:
设 , ,那么以下两个论断有且只有一个是对的:
(1)存在 ,使得 ,且 。
(2)存在 ,使得 ,且 。
乍一看容易懵逼,都是些什么鬼啊,但是只要了解这个引理得出的来龙去脉,结合一些几何上面的直观认识,你会发现,上述引理描述的事实几乎是显而易见的。
注意到两个事实:
事实一和锥有关:
是锥(cone),当任取 , ,有 。
被称为是凸锥(convex cone),当任取 , ,有 。当然,不难论证它是锥而且是凸集(convex set),且选择不止两个向量和对应的正系数上述事实也是满足的。
有了以上认识,了解一个概念叫conic hull,一个集合 的conic hull被定义为:
可以看到,这是一个由 中的向量张成的一个凸锥,长成下图这样。
事实二是点和凸集的分离定理,它可以认为是两个凸集可以被超平面分开的推论(Corollary):
假设 是一个闭凸集,如果 ,那么存在一个超平面 能够把 和 分开。换句话说就是存在一个非零向量 和 ,满足对于所有 ,有 同时 。
直观上面来说,就是总能在空间中找到一个超平面,平面方程参数是 和 ,使得 在平面这边,闭凸集 在平面那边,如下图所示(盗图,侵删)。
特别的,如果 不仅是凸集,还是事实一中所提到的凸锥,我们可以找到一个过原点的平面,分开凸锥和它外面的一个点,也就是说如果 是一个凸锥, ,存在非零 满足对于所有的 ,有 ,且 。
根据上面两个事实,我们就可以很直观的理解farkas引理在说些什么了,注意这是直观的说明,并不是严谨的证明。
我们把矩阵 的列空间写出来,其实就是 n个m维的向量: ,根据事实一,这些向量前面加权非负系数组合出来的点构成的集合就是一个凸锥,是集合 的conic hull。
对于向量 ,只可能存在两种互斥情况:(1) 在这个凸锥里。(2) 在这个凸锥外。
如果情况(1)成立,说明 属于的conic hull,所以肯定能够找到一组非负的 使得 。这就也是定理中的情况(1),直观感受如下面左图。
反之如果情况(2)成立, 在凸锥外面,根据事实二,肯定能够找到一个过原点的超平面,使得 在一边,凸锥在另外一边。这个超平面法向量为 ,因为 都在凸锥里面,所以 , ,..., ,合并写成矩阵乘向量形式就是 。且此时 。如上面右图所示。
题外话:
证明Farkas引理的话,大致步骤基本是这样:(1)证明有限向量集合的conic hull是闭凸集。(2)利用超平面分离定理,结合凸锥是包含原点的闭凸集,加上一点反证法的论证,得到存在过原点的超平面分离该凸锥外一点和凸锥。(3)证明引理本身。
具体证明有时间再补上吧~