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 S be the cone in n generated by nonnegative linear combinationsMathworldPlanetmath of the rows a1,,am of A. The set S is closed and convex. Since system 2 is unsolvable, the vector c is not in S; therefore, there exist a scalar α and n-column vectorMathworldPlanetmath x such that the hyperplaneMathworldPlanetmathPlanetmath xTv=α separates c from S in n. This hyperplane can be selected so that for any point vS,


Since 0S, this implies that α>0. Hence for any w0,


Each (Ax)i is nonpositive. Otherwise, by selecting w with wi sufficiently large and all other wj=0, we would get a contradictionMathworldPlanetmathPlanetmath. We have now shown that x satisfies Ax0 and cx=(cx)T=xTcT>α>0, which means that x 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 x is a solution of system 1 and w is a solution of system 2. Then for each i, the inequality wi(Ax)i0 holds, and so w(Ax)0. However,


a contradiction. This completesPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath the proof.

Title Farkas lemma, proof of
Canonical name FarkasLemmaProofOf
Date of creation 2013-03-22 14:12:51
Last modified on 2013-03-22 14:12:51
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 13
Author CWoo (3771)
Entry type Proof
Classification msc 15A39