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 $\mathbb{R}^{n}$ generated by nonnegative linear combinations of the rows $a_{1},\dots,a_{m}$ 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 $\alpha$ and $n$ -column vector $x$ such that the hyperplane $x^{T}v=\alpha$ separates $c$ from $S$ in $\mathbb{R}^{n}$ . This hyperplane can be selected so that for any point $v\in S$ ,

x^{T}c^{T}>\alpha>x^{T}v^{T}.

Since $0\in S$ , this implies that $\alpha>0$ . Hence for any $w\geq 0$ ,

\alpha>x^{T}(wA)^{T}=wAx=\sum_{i=0}^{m}w_{i}(Ax)_{i}.

Each $(Ax)_{i}$ is nonpositive. Otherwise, by selecting $w$ with $w_{i}$ sufficiently large and all other $w_{j}=0$ , we would get a contradiction. We have now shown that $x$ satisfies $Ax\leq 0$ and $cx=(cx)^{T}=x^{T}c^{T}>\alpha>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 $w_{i}(Ax)_{i}\leq 0$ holds, and so $w(Ax)\leq 0$ . However,

(wA)x=cx>0,

a contradiction. This completes 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