Farkas lemma, proof of
We begin by showing that at least one of the systems has a solution.
Suppose that system 2 has no solution. Let be the cone in generated by nonnegative linear combinations of the rows of . The set is closed and convex. Since system 2 is unsolvable, the vector is not in ; therefore, there exist a scalar and -column vector such that the hyperplane separates from in . This hyperplane can be selected so that for any point ,
Since , this implies that . Hence for any ,
Each is nonpositive. Otherwise, by selecting with sufficiently large and all other , we would get a contradiction. We have now shown that satisfies and , which means that is a solution of system 1. Thus at least one of the systems is solvable.
We claim that systems 1 and 2 are not simultaneously solvable. Suppose that is a solution of system 1 and is a solution of system 2. Then for each , the inequality holds, and so . However,
a contradiction. This completes the proof.
|Title||Farkas lemma, proof of|
|Date of creation||2013-03-22 14:12:51|
|Last modified on||2013-03-22 14:12:51|
|Last modified by||CWoo (3771)|