PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (200)
Orphanage
Unclass'd
Unproven (490)
Corrections (6)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: High
[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$,

$\displaystyle x^T c^T > \alpha > x^T v^T. $
Since $ 0\in S$, this implies that $ \alpha>0$. Hence for any $ w\ge 0$,
$\displaystyle \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,

$\displaystyle (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)

View style:


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

Cross-references: 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 7364 times total.

Classification:
AMS MSC: 15A39 (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)