如何理解farkas引理？

1樓：陳曉

Farkas引理的幾何直觀很多人從分離超平面定理 (separation hyperplane theorem) 講得很好了，但是這個引理本身並不依賴於分離超平面定理，只是分離超平面定理使得類似的結果（theorem of alternative）容易推廣到更一般的凸的情形罷了。

而線性不等式組是很特殊的，從Fourier-Motzkin elimination的角度看更加合適。這種基於純代數方法的證明更容易看出來Farkas引理在有理數域上也對。

另外Farkas引理本身就是代數表述，從代數上看也很直觀。可以先考慮齊次的版本：

當且僅當

. 怎麼理解呢？從第二個表述到第乙個就是顯然的，因為若有個使得每個，那麼直接在前面乘上乙個非負的再加起來當然有 .

而Farkas引理的作用，或者說神奇之處，就是說這個反過來也對。就是若第乙個表述成立，則一定是的非負線性組合 (conic combination)! 這個仔細想想就應該是對的。

（嚴格的證明用到Fourier elimination，也是很自然的東西）.

令 , , 上面的Farkas引理就可以重寫成常見的theorem of alternative的版本：

線性不等式組和其中有且必有乙個成立。

一般的非齊次Farkas引理也可以通過齊次版本證明，可以參考Ben-Tal和Nemirovski的凸錐優化講義.

2樓：

經過教授的逐步暗示，似乎這個東西簡單淺顯的過頭了……用幾何來證明的都是耍流氓！埃默里，杜克，哈佛，康奈爾，mit沒乙個好東西[手動狗頭]

要證明的法卡斯引理如下：

0" eeimg="1"/>或者之中有且僅有乙個是可解的。

證明：構造乙個線性規劃問題如下：

以及它的對偶形式：

按照對偶線性規劃的特點，如果乙個LP有解，那麼另乙個LP也有解，且,其中和分別是讓兩個LP取到最大值時的解。

現在我們讓。

於是第乙個線性規劃的目標函式，而第二個線性規劃的目標函式的最大值為0，即。

現在第乙個線性規劃有解意味著有解，意味著第二個線性規劃也有解，也就是說也有解。

即。於是要證明的法卡斯引理等價於

0" eeimg="1"/>或者之中有且僅有乙個是可解的。

顯而易見，qed。

PS. 知乎的公式編輯器也太tm難用了吧。

以下大學的講義裡使用的都是用幾何來證明的：

艾默爾大學：http://www.

mathcs.emory.edu/~hhuan

30/math346_fall17/strong_duality_lp.pdf

杜克大學：https://

哈佛：https://

people.seas.harvard.edu

/~yaron/AM221-S16/lecture_notes/AM221_lecture4.pdf

康奈爾大學:https://

people.orie.cornell.edu

/dpw/orie6300/fall2008/Lectures/lec07.pdf

3樓：包遵信

關於幾何直觀的回答已經很多了，這東西代數上也是很直觀的，不直觀的原因大概是寫的形式不太對——這不是在開玩笑，代數的直觀有時候真的依賴於寫的形式對，補充這個答案只是想講講形式。

這個答案裡的寫法原來長這樣：

集合非空當且僅當,其中

修改一下

集合非空當且僅當 ,，其中

為什麼要這樣改（把全部出現的地方都改成了）呢，因為說白了就是其實是對偶空間中的東西，表現在具體的座標系裡就是每次出現其實都是乙個行向量 .

改完以後基本上有半邊就很顯然了 —— P 非空 => 存在 x ≥ 0 使得 Ax = b, => 乘在這個 x 上就是 , 顯然大於等於 0.

剩下的半邊只是在說，如果點不在凸集裡，可以用對偶空間中的某個向量來測試（或者說「見證」，witness）：是空集 => 存在使得且，把改寫成就可以看出後面這個條件說的是 .

4樓：王源

Farkas引理其實理解起來還是稍微有點困難的，教科書上基本上是用一堆代數推導就證明出來了，這裡就不列出來了。 @Johnny Richards 已經回答的非常非常棒了，事實上Farkas引理與凸錐和凸集分離定理有關，在他的回答中已經寫得非常清晰了。我這邊就補充幾個圖，用乙個特例來說明Farkas引理吧，也算是乙個補充。

Farkas引理：

設是的矩陣，是維向量

集合非空當且僅當 , 其中

這裡我們採用的是Farkas引理等價的改寫了一下，雖然只是等價改寫其實已經有點味道了，我們只需要搞清楚集合和到底是啥，問題就解決一大半了。

為了我們能夠畫出影象，不妨設為2 3的矩陣，設為矩陣的列向量，所構成的凸錐，不了解凸錐的概念的童鞋不要緊，看下圖就明白了：

那麼集合在影象指的是什麼呢？我們不妨改寫一下集合 , , 內積大於等於表示呈夾角小於等於90度，也就是說集合的元素是與的夾角都要小於等於90度。在圖中畫出來就是這樣的：

,這個條件用幾何話語來說就是，所構成的凸錐裡的任意向量都和夾角為非鈍角。

那麼把結論1和結論2放在一起就可以得到，我們想要說明的事情，即集合非空當且僅當,其中

至此我們對Farkas引理在為2 3的矩陣的特殊情況下有了乙個直觀的認識。從這裡其實不難看出即使是比較抽象的乙個定理或者引理，往往需要從幾何上入手來給出直觀的解釋，當高維情況比較複雜看不清楚的時候，不妨先把問題放到二維平面上來看就清晰了許多。

5樓：艾燁生

這個證明完全不需要用任何抽象定理, 只需要簡單的幾何知識和影象!!!!

我就是很看不慣這麼抽象但是簡潔的引理需要這麼不直觀的證明, 但是網上全是需要別的定理(凸集分離定理)來輔助證明,我就是覺得應該可以用簡單的幾何完全解釋證明這個引理

所以想了這麼個辦法, 證明過程不是很嚴謹, 但是稍微補充說明一些細節即可, 最重要的是從頭到尾我都只在用最簡單的幾何影象在證明, 非常便於理解記憶!!

最後一行有個小筆誤, 不要在意這些細節

6樓：Johnny Richards

Farkas引理算是凸優化中經典和常用的引理了，可以用在很多地方（例如證明KKT條件），最近在看最優運輸問題和Wasserstein距離的一些東西，中間對偶性的證明過程中用到了Farkas引理，順路上來回答一發。

原引理長這樣：

設，，那麼以下兩個論斷有且只有乙個是對的：

（1）存在，使得，且。

（2）存在，使得，且。

乍一看容易懵逼，都是些什麼鬼啊，但是只要了解這個引理得出的來龍去脈，結合一些幾何上面的直觀認識，你會發現，上述引理描述的事實幾乎是顯而易見的。

注意到兩個事實：

事實一和錐有關：

是錐（cone），當任取，，有。

被稱為是凸錐（convex cone），當任取，，有。當然，不難論證它是錐而且是凸集（convex set），且選擇不止兩個向量和對應的正係數上述事實也是滿足的。

有了以上認識，了解乙個概念叫conic hull，乙個集合的conic hull被定義為：

可以看到，這是乙個由中的向量張成的乙個凸錐，長成下圖這樣。

conic hull的視覺化，每一條稜就是S中的乙個向量

事實二是點和凸集的分離定理，它可以認為是兩個凸集可以被超平面分開的推論（Corollary）：

假設是乙個閉凸集，如果，那麼存在乙個超平面能夠把和分開。換句話說就是存在乙個非零向量和，滿足對於所有，有同時。

直觀上面來說，就是總能在空間中找到乙個超平面，平面方程引數是和，使得在平面這邊，閉凸集在平面那邊，如下圖所示（盜圖，侵刪）。

總能找到乙個平面，把凸集和凸集外一點分開

特別的，如果不僅是凸集，還是事實一中所提到的凸錐，我們可以找到乙個過原點的平面，分開凸錐和它外面的乙個點，也就是說如果是乙個凸錐，，存在非零滿足對於所有的，有，且。

根據上面兩個事實，我們就可以很直觀的理解farkas引理在說些什麼了，注意這是直觀的說明，並不是嚴謹的證明。

我們把矩陣的列空間寫出來，其實就是 n個m維的向量：，根據事實一，這些向量前面加權非負係數組合出來的點構成的集合就是乙個凸錐，是集合的conic hull。

對於向量，只可能存在兩種互斥情況：（1）在這個凸錐裡。（2）在這個凸錐外。

如果情況（1）成立，說明屬於的conic hull，所以肯定能夠找到一組非負的使得。這就也是定理中的情況（1），直觀感受如下面左圖。

左為b在凸錐內的情況，右圖為b在凸錐外的情況，總能找到過原點的超平面（二維情況下為直線，法向量為y），把b和凸錐分開。

反之如果情況（2）成立，在凸錐外面，根據事實二，肯定能夠找到乙個過原點的超平面，使得在一邊，凸錐在另外一邊。這個超平面法向量為，因為都在凸錐裡面，所以，，...，，合併寫成矩陣乘向量形式就是。

且此時。如上面右圖所示。

題外話：

證明Farkas引理的話，大致步驟基本是這樣：（1）證明有限向量集合的conic hull是閉凸集。（2）利用超平面分離定理，結合凸錐是包含原點的閉凸集，加上一點反證法的論證，得到存在過原點的超平面分離該凸錐外一點和凸錐。

（3）證明引理本身。

具體證明有時間再補上吧～

如何理解farkas引理？

Riesz引理的直觀理解或者是幾何意義是什麼

怎麼直觀地理解上下文無關語言的幫浦引理

這個一階邏輯中的菱形交換圖引理如何證明？

其他用戶還看了：