Fork me on GitHub
Math for the people, by the people.

User login

Farkas lemma, proof of

Type of Math Object: 
Major Section: 
Groups audience: 

Mathematics Subject Classification

15A39 no label found


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.

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.

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


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.

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?

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.

Subscribe to Comments for "Farkas lemma, proof of"