|
|
|
|
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)
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 MSC: | 15A39 (Linear and multilinear algebra; matrix theory :: Linear inequalities) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|