Farkas' Lemma - Geometric Interpretation

Geometric Interpretation

Let a₁, …, a_n ∈ Rm denote the columns of A. In terms of these vectors, Farkas's lemma states that exactly one of the following two statements is true:

1. There exist coefficients x₁, …, x_n ∈ R, x₁, …, x_n ≥ 0, such that b = x₁a₁ + ··· + x_na_n.
2. There exists a vector y ∈ Rm such that a_i · y ≥ 0 for i = 1, …, n and b · y < 0.

The vectors x₁a₁ + ··· + x_na_n with nonnegative coefficients constitute the convex cone of the set {a₁, …, a_n} so the first statement says that b is in this cone.

The second statement says that there exists a vector y such that the angle of y with the vectors a_i is at most 90° while the angle of y with the vector b is more than 90°. The hyperplane normal to this vector has the vectors a_i on one side and the vector b on the other side. Hence, this hyperplane separates the vectors in the cone of {a₁, …, a_n} and the vector b.

For example, let n,m=2 and a₁ = (1,0)T and a₂ = (1,1)T. The convex cone spanned by a₁ and a₂ can be seen as a wedge-shaped slice of the first quadrant in the x-y plane. Now, suppose b = (0,1). Certainly, b is not in the convex cone a₁x₁+a₂x₂. Hence, there must be a separating hyperplane. Let y = (1,−1)T. We can see that a₁ · y = 1, a₂ · y = 0, and b · y = −1. Hence, the hyperplane with normal y indeed separates the convex cone a₁x₁+a₂x₂ from b.

Farkas's lemma can thus be interpreted geometrically as follows: Given a convex cone and a vector, either the vector is in the cone or there is a hyperplane separating the vector from the cone, but not both.