# Farkas lemma, proof of

## Primary tabs

Type of Math Object:
Proof
Major Section:
Reference
Parent:
Groups audience:

## Mathematics Subject Classification

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