百科问答小站 logo
百科问答小站 font logo



如何理解 Farkas 引理? 第1页

  

user avatar   johnny-richards 网友的相关建议: 
      

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

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




  

相关话题

  请问能给出一个例子,使一个向量空间的子集只满足包含0且对加法封闭但不对标量乘法封闭吗? 
  光刻机,计算机半导体硬件研发和制造,需要那些学科? 
  国内本科运筹学课程的教育都存在哪些问题? 
  有没有比图灵机能力更强的计算模型? 
  当下的工程学对经验公式依赖程度几何? 
  2022 年最适合写业务代码的编程语言是哪个? 
  CPU 的摩尔定律是不是因为 10 纳米的限制已经失效了?10 纳米之后怎么办? 
  为什么好多人说大牛都玩Unix/Linux? 
  有哪些「上帝算法」? 
  人类大脑的聪慧程度以 IQ 为标准,那么人工智能的水平用什么指标来衡量呢? 

前一个讨论
如何看待人教版教材疑似出现低级错误,用爱因斯坦相对论证明勾股定理?
下一个讨论
线性空间的对偶空间和优化里的拉格朗日对偶有什么关系?





© 2024-11-08 - tinynew.org. All Rights Reserved.
© 2024-11-08 - tinynew.org. 保留所有权利