Farkas’ lemma is a simple (and very useful) statement in convex analysis.

**Theorem (Farkas’ lemma)**

For any matrix and vector ,* exactly one* of the following holds:

(1) linear system has a solution in the first orthant;

(2)** **there exists such that and

It has an elementary analogue known from a course of linear algebra:

**Theorem (Fredholm’s alternative)**

Exactly one of the following holds:

(1′) linear system has a solution;

(2′)** **there exists such that and

Rather than giving a detailed self-contained proof, I’ll just provide a geometric intuition behind it. Note that (2) implies the negation of (1). To see it,** **transpose and then multiply by from (2). Now it remains to prove that the negation of (1)** **implies (2).

Let us start with a notion of a cone. A *cone* is any set which is closed under multiplication by positive scalars. In other words, implies for any Note that this definition aligns with the geometric notion of a (non-truncated) cone with apex in the origin. Cones are convex sets, i.e.they can contain two points only with the entire segment between these points.

Further, for any set of vectors its *conic hull* is defined as a minimal cone containing them. It is easy to make sure that it is given (parametrized) by for If we rewrite as the columns of a matrix then their conic hull will be the set

Now we can see that geometrically (1) simply says that is in the conic hull of columns of . Indeed, there exist a coefficient vector such that

So, the opposite of (1)** **means that is separated from the cone Then, as cones are convex sets, we can appeal to the separation theorem to draw a hyperplane separating and and obtain (2).

**Remark. **Farkas’ lemma has an interesting consequence. It occurs that the LP feasibility problem (“determine if (2) is feasible”) is essentially as difficult as the separation problem for a cone and a point (given a cone and a point, output the separation hyperplane if the point does not belong to the cone and the negative answer if it does).

### Like this:

Like Loading...

## About Dmitry Ostrovsky

PhD student with interests in learning theory, statistics, and optimization, working with Anatoli Juditsky and Zaid Harchaoui.