Farkas’ lemma – Wikipedia

Farkas’ lemma is a solvability theorem for a finite system of linear inequalities in mathematics. It was originally proven by the Hungarian mathematician Gyula Farkas.^[1]
Farkas’ lemma is the key result underpinning the linear programming duality and has played a central role in the development of mathematical optimization (alternatively, mathematical programming). It is used amongst other things in the proof of the Karush–Kuhn–Tucker theorem in nonlinear programming.^[2]
Remarkably, in the area of the foundations of quantum theory, the lemma also underlies the complete set of Bell inequalities in the form of necessary and sufficient conditions for the existence of a local hidden-variable theory, given data from any specific set of measurements.^[3]

Generalizations of the Farkas’ lemma are about the solvability theorem for convex inequalities,^[4] i.e., infinite system of linear inequalities. Farkas’ lemma belongs to a class of statements called “theorems of the alternative”: a theorem stating that exactly one of two systems has a solution.^[5]

Statement of the lemma[edit]

There are a number of slightly different (but equivalent) formulations of the lemma in the literature. The one given here is due to Gale, Kuhn and Tucker (1951).^[6]

Here, the notation

x≥0{displaystyle mathbf {x} geq 0}

means that all components of the vector

x{displaystyle mathbf {x} }

are nonnegative.

Example[edit]

Let m, n = 2,

A=[6430]{displaystyle mathbf {A} ={begin{bmatrix}6&4\3&0end{bmatrix}}}

, and

b=[b1b2]{displaystyle mathbf {b} ={begin{bmatrix}b_{1}\b_{2}end{bmatrix}}}

. The lemma says that exactly one of the following two statements must be true (depending on b₁ and b₂):

1. There exist x₁ ≥ 0, x₂ ≥ 0 such that 6 x₁ + 4 x₂ = b₁ and 3 x₁ = b₂, or
2. There exist y₁, y₂ such that 6 y₁ + 3 y₂ ≥ 0, 4 y₁ ≥ 0, and b₁y₁ + b₂y₂ < 0.

Here is a proof of the lemma in this special case:

• If b₂ ≥ 0 and b₁ − 2b₂ ≥ 0, then option 1 is true, since the solution of the linear equations is x₁ = b₂/3 and x₂ = (b₁-2b₂) / 4. Option 2 is false, since b₁y₁ + b₂y₂ ≥ b₂ (2 y₁ + y₂) = b₂ (6 y₁ + 3 y₂) / 3, so if the right-hand side is positive, the left-hand side must be positive too.
• Otherwise, option 1 is false, since the unique solution of the linear equations is not weakly positive. But in this case, option 2 is true:
  • If b₂ < 0, then we can take e.g. y₁ = 0 and y₂ = 1.
  • If b₁ − 2b₂ < 0, then, for some number B > 0, b₁ = 2b₂ − B, so: b₁y₁ + b₂y₂ = 2 b₂y₁ + b₂y₂ − B y₁ = b₂ (6 y₁ + 3 y₂) / 3 − B y₁. Thus we can take, for example, y₁ = 1, y₂ = −2.

Geometric interpretation[edit]

Consider the closed convex cone

C(A){displaystyle C(mathbf {A} )}

spanned by the columns of

A{displaystyle mathbf {A} }

; that is,

C(A)={Ax∣x≥0}.{displaystyle C(mathbf {A} )={mathbf {A} mathbf {x} mid mathbf {x} geq 0}.}

Observe that

C(A){displaystyle C(mathbf {A} )}

is the set of the vectors

b{displaystyle mathbf {b} }

for which the first assertion in the statement of Farkas’ lemma holds. On the other hand, the vector

y{displaystyle mathbf {y} }

in the second assertion is orthogonal to a hyperplane that separates

b{displaystyle mathbf {b} }

and

C(A){displaystyle C(mathbf {A} )}

. The lemma follows from the observation that

b{displaystyle mathbf {b} }

belongs to

C(A){displaystyle C(mathbf {A} )}

if and only if there is no hyperplane that separates it from

C(A){displaystyle C(mathbf {A} )}

.

More precisely, let

a1,…,an∈Rm{displaystyle mathbf {a} _{1},dots ,mathbf {a} _{n}in mathbb {R} ^{m}}

denote the columns of

A{displaystyle mathbf {A} }

. In terms of these vectors, Farkas’ lemma states that exactly one of the following two statements is true:

1. There exist non-negative coefficients
   x1,…,xn∈R{displaystyle x_{1},dots ,x_{n}in mathbb {R} }
   such that b=x1a1+⋯+xnan{displaystyle mathbf {b} =x_{1}mathbf {a} _{1}+dots +x_{n}mathbf {a} _{n}}
   .
2. There exists a vector
   y∈Rm{displaystyle mathbf {y} in mathbb {R} ^{m}}
   such that aiTy≥0{displaystyle mathbf {a} _{i}^{mathsf {T}}mathbf {y} geq 0}
   for i=1,…,n{displaystyle i=1,dots ,n}
   , and bTy<0{displaystyle mathbf {b} ^{mathsf {T}}mathbf {y} <0}
   .

The sums

x1a1+⋯+xnan{displaystyle x_{1}mathbf {a} _{1}+dots +x_{n}mathbf {a} _{n}}

with nonnegative coefficients

x1,…,xn{displaystyle x_{1},dots ,x_{n}}

form the cone spanned by the columns of

A{displaystyle mathbf {A} }

. Therefore, the first statement tells that

b{displaystyle mathbf {b} }

belongs to

C(A){displaystyle C(mathbf {A} )}

.

The second statement tells that there exists a vector

y{displaystyle mathbf {y} }

such that the angle of

y{displaystyle mathbf {y} }

with the vectors

ai{displaystyle mathbf {a} _{i}}

is at most 90°, while the angle of

y{displaystyle mathbf {y} }

with the vector

b{displaystyle mathbf {b} }

is more than 90°. The hyperplane normal to this vector has the vectors

ai{displaystyle mathbf {a} _{i}}

on one side and the vector

b{displaystyle mathbf {b} }

on the other side. Hence, this hyperplane separates the cone spanned by

a1,…,an{displaystyle mathbf {a} _{1},dots ,mathbf {a} _{n}}

from the vector

b{displaystyle mathbf {b} }

.

For example, let n, m = 2, 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 xy 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.

Logic interpretation[edit]

A particularly suggestive and easy-to-remember version is the following: if a set of linear inequalities has no solution, then a contradiction can be produced from it by linear combination with nonnegative coefficients. In formulas: if

Ax{displaystyle Ax}

≤

b{displaystyle b}

is unsolvable then

yTA=0{displaystyle y^{mathsf {T}}A=0}

,

yTb=−1{displaystyle y^{mathsf {T}}b=-1}

,

y{displaystyle y}

≥

0{displaystyle 0}

has a solution.^[7] Note that

yTA{displaystyle y^{mathsf {T}}A}

is a combination of the left-hand sides,

yTb{displaystyle y^{mathsf {T}}b}

a combination of the right-hand side of the inequalities. Since the positive combination produces a zero vector on the left and a −1 on the right, the contradiction is apparent.

Thus, Farkas’ lemma can be viewed as a theorem of logical completeness:

Ax{displaystyle Ax}

≤

b{displaystyle b}

is a set of “axioms”, the linear combinations are the “derivation rules”, and the lemma says that, if the set of axioms is inconsistent, then it can be refuted using the derivation rules.^{[8]: 92–94}

Variants[edit]

The Farkas Lemma has several variants with different sign constraints (the first one is the original version):^[8]: 92

The latter variant is mentioned for completeness; it is not actually a “Farkas lemma” since it contains only equalities. Its proof is an exercise in linear algebra.

Generalizations[edit]

Generalized Farkas’ lemma can be interpreted geometrically as follows: either a vector is in a given closed convex cone, or there exists a hyperplane separating the vector from the cone; there are no other possibilities. The closedness condition is necessary, see Separation theorem I in Hyperplane separation theorem. For original Farkas’ lemma,

S{displaystyle mathbf {S} }

is the nonnegative orthant

R+n{displaystyle mathbb {R} _{+}^{n}}

, hence the closedness condition holds automatically. Indeed, for polyhedral convex cone, i.e., there exists a

B∈Rn×k{displaystyle mathbf {B} in mathbb {R} ^{ntimes k}}

such that

S={Bx∣x∈R+k}{displaystyle mathbf {S} ={mathbf {B} mathbf {x} mid mathbf {x} in mathbb {R} _{+}^{k}}}

, the closedness condition holds automatically. In convex optimization, various kinds of constraint qualification, e.g. Slater’s condition, are responsible for closedness of the underlying convex cone

C(A){displaystyle C(mathbf {A} )}

.

By setting

S=Rn{displaystyle mathbf {S} =mathbb {R} ^{n}}

and

S∗={0}{displaystyle mathbf {S} ^{*}={0}}

in generalized Farkas’ lemma, we obtain the following corollary about the solvability for a finite system of linear equalities:

Further implications[edit]

Farkas’s lemma can be varied to many further theorems of alternative by simple modifications,^[5] such as Gordan’s theorem: Either

Ax<0{displaystyle Ax<0}

has a solution x, or

ATy=0{displaystyle A^{mathsf {T}}y=0}

has a nonzero solution y with y ≥ 0.

Common applications of Farkas’ lemma include proving the strong duality theorem associated with linear programming and the Karush–Kuhn–Tucker conditions. An extension of Farkas’ lemma can be used to analyze the strong duality conditions for and construct the dual of a semidefinite program. It is sufficient to prove the existence of the Karush–Kuhn–Tucker conditions using the Fredholm alternative but for the condition to be necessary, one must apply von Neumann’s minimax theorem to show the equations derived by Cauchy are not violated.

See also[edit]

Further reading[edit]