## You are here

HomeFarkas lemma, proof of

## Primary tabs

# 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.

## Mathematics Subject Classification

15A39*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## S is *not* easily seen to be a closed convex set

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.

## Re: S is *not* easily seen to be a closed convex set

The following argument that S is closed seems to me to work. Please let me know if I have made some obvious or nonobvious mistake.

The set S = { wA : w >= 0 } is the cone generated by nonnegative linear combinations of rows of A. Let { v_i : 0 <= i <= k } be a basis for the rowspace of A. Then

S = { \sum_i c_i v_i : c_i >= 0 for all i } .

Suppose x is in the complement of S. Since the rowspace of A is closed in R^n, we may assume that

x = \sum_i c_i v_i ,

where at least one of the c_i is negative. Choose a positive h smaller than the absolute value of any such c_i. Then the open parallelotope

P = { x + \sum_i d_i v_i : |d_i| < h for all i }

contains x and is contained in the complement of S. Hence S is closed.

I deleted the word ``easily'' from the argument since it contributed no content.

## Re: S is *not* easily seen to be a closed convex set

You are right, but what you say about the proof of closedness by mps? Do you think it is correct? I have some perplexities.

Giorgio Giorgi

facilty of Economics

University of Pavia - Italy

ggiorgi@eco.unipv.it

## Re: S is *not* easily seen to be a closed convex set

Hi,

there's a problem in the second paragraph. The convex cone generated by a set A of vectors is *not* the same as the convex cone generated by a basis of the linear subspace generated by A.

For example, in the three dimensional case, the basis will obviously have at most three vectors. But the cone will look like an n-sided "pyramid", and you need to keep at least one vector in every extremal direction/edge.

## Re: S is *not* easily seen to be a closed convex set

May I ask what is meant here by "convex cone" generated by a set of vectors? Is this supposed to be the smallest convex set containing the set of vectors?

## Re: S is *not* easily seen to be a closed convex set

Like mps said, it's given by the nonnegative linear combinations of the original vectors. It's the smallest set closed under convex combination (or altenatively just addition), and under mult. with nonnegative scalars.