如何理解 Farkas 引理？ 第1页

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）证明引理本身。

具体证明有时间再补上吧～