如何理解farkas引理?-而線性不等式組是很特殊的

Farkas引理的幾何直觀很多人從分離超平面定理(separationhyperplanetheorem)講得很好了,但是這個引理本身并不依賴于分離超平面定理,只是分離超平面定理使得類似的結果(theoremofalternative)容易推廣到更一般的凸的情形罷了。

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

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

當且僅當

.

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

而Farkas引理的作用,或者說神奇之處,就是說這個反過來也對。就是若第一個表述成立,則一定是的非負線性組合(coniccombination)!這個仔細想想就應該是對的。(嚴格的證明用到Fourierelimination,也是很自然的東西).

令,,上面的Farkas引理就可以重寫成常見的theoremofalternative的版本:

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

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

0 条回复 A文章作者 M管理員
    暫無討論,說說你的看法吧