PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Very high Entry average rating: Medium
[parent] proof of Farkas lemma (Proof)

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\ge 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\le 0$ holds, and so $w(Ax)\le 0$ However, $$ (wA)x=cx>0, $$ a contradiction. This completes the proof.




Anyone with an account can edit this entry. Please help improve it!

"proof of Farkas lemma" is owned by CWoo. [ full author list (2) | owner history (2) ]
(view preamble | get metadata)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: proof, completes, inequality, solvable, solution of system, contradiction, implies, point, hyperplane, scalar, vector, convex, closed, rows, linear combinations, generated by, cone, solution

This is version 10 of proof of Farkas lemma, born on 2004-02-28, modified 2005-09-23.
Object id is 5649, canonical name is ProofOfFarkasLemma.
Accessed 9653 times total.

Classification:
AMS MSC15A39 (Linear and multilinear algebra; matrix theory :: Linear inequalities)

Pending Errata and Addenda
None.
[ View all 4 ]
Discussion
Style: Expand: Order:
forum policy
S is *not* easily seen to be a closed convex set by chimaira on 2005-08-08 08:17:17
At the beginning of step 2 of the proof of Farkas Lemma, set S is defined. In the following it's crucial that S is a closed and convex set. While "S convex" can be shown easily indeed, "S closed" takes some time. A possible reference (though I wasn't able to verify it): Appendix B.3 "Nonlinear Programming" by Dimitri Bertsekas. Please correct me if I'm wrong.
[ reply | up ]

Interact
post | correct | update request | add example | add (any)