In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, Farkas' lemma is a solvability theorem for a finite
system
A system is a group of interacting or interrelated elements that act according to a set of rules to form a unified whole. A system, surrounded and influenced by its open system (systems theory), environment, is described by its boundaries, str ...
of
linear inequalities. It was originally proven by the Hungarian mathematician
Gyula Farkas.
[ ]
Farkas'
lemma is the key result underpinning the
linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements and objective are represented by linear function#As a polynomia ...
duality and has played a central role in the development of
mathematical optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfiel ...
(alternatively,
mathematical programming
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfiel ...
). It is used amongst other things in the proof of the
Karush–Kuhn–Tucker theorem in
nonlinear programming
In mathematics, nonlinear programming (NLP) is the process of solving an optimization problem where some of the constraints are not linear equalities or the objective function is not a linear function. An optimization problem is one of calculation ...
.
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
In the interpretation of quantum mechanics, a local hidden-variable theory is a hidden-variable theory that satisfies the principle of locality. These models attempt to account for the probabilistic features of quantum mechanics via the mechanism ...
, given data from any specific set of measurements.
[ ]
Generalizations of the Farkas' lemma are about the solvability theorem for convex inequalities,
[ ] 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.
Statement of the lemma
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).
Here, the notation
means that all components of the vector
are nonnegative.
Example
Let ,
and
The lemma says that exactly one of the following two statements must be true (depending on and ):
# There exist , such that and , or
# There exist such that , , and .
Here is a proof of the lemma in this special case:
* If and , then option 1 is true, since the solution of the linear equations is
and
Option 2 is false, since
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 , then we can take e.g. and .
** If , then, for some number , , so:
Thus we can take, for example, , .
Geometric interpretation
Consider the
closed convex cone
In linear algebra, a cone—sometimes called a linear cone to distinguish it from other sorts of cones—is a subset of a real vector space that is closed under positive scalar multiplication; that is, C is a cone if x\in C implies sx\in C for e ...
spanned by the columns of ; that is,
:
Observe that
is the set of the vectors for which the first assertion in the statement of Farkas' lemma holds. On the other hand, the vector in the second assertion is orthogonal to a
hyperplane
In geometry, a hyperplane is a generalization of a two-dimensional plane in three-dimensional space to mathematical spaces of arbitrary dimension. Like a plane in space, a hyperplane is a flat hypersurface, a subspace whose dimension is ...
that separates and
The lemma follows from the observation that belongs to
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...
there is no hyperplane that separates it from
More precisely, let
denote the columns of . In terms of these vectors, Farkas' lemma states that exactly one of the following two statements is true:
# There exist non-negative coefficients
such that
# There exists a vector
such that
for
and
The sums
with nonnegative coefficients
form the cone spanned by the columns of . Therefore, the first statement tells that belongs to
The second statement tells that there exists a vector such that the angle of with the vectors is at most 90°, while the angle of with the vector is more than 90°. The hyperplane normal to this vector has the vectors on one side and the vector on the other side. Hence, this hyperplane separates the cone spanned by
from the vector .
For example, let , , and . The convex cone spanned by and can be seen as a wedge-shaped slice of the first quadrant in the plane. Now, suppose . Certainly, is not in the convex cone . Hence, there must be a separating hyperplane. Let . We can see that , , and . Hence, the hyperplane with normal indeed separates the convex cone from .
Logic interpretation
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
is unsolvable then
has a solution.
[.] Note that
is a combination of the left-hand sides,
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:
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.
[ Pages 81–104.]
Implications in complexity theory
Farkas' lemma implies that the
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...
"Given a
system of linear equations
In mathematics, a system of linear equations (or linear system) is a collection of two or more linear equations involving the same variable (math), variables.
For example,
: \begin
3x+2y-z=1\\
2x-2y+4z=-2\\
-x+\fracy-z=0
\end
is a system of th ...
, does it have a non-negative solution?" is in the intersection of
NP and
co-NP
In computational complexity theory, co-NP is a complexity class. A decision problem X is a member of co-NP if and only if its complement is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP if and o ...
. This is because, according to the lemma, both a "yes" answer and a "no" answer have a proof that can be verified in polynomial time. The problems in the intersection
are also called ''well-characterized problems''. It is a long-standing open question whether
is equal to
P. In particular, the question of whether a system of linear equations has a non-negative solution was not known to be in P, until it was proved using the
ellipsoid method
In mathematical optimization, the ellipsoid method is an iterative method for convex optimization, minimizing convex functions over convex sets. The ellipsoid method generates a sequence of ellipsoids whose volume uniformly decreases at every ste ...
.
Variants
The Farkas Lemma has several variants with different sign constraints (the first one is the original version):
* Either
has a solution
or
has a solution
with
* Either
has a solution
or
has a solution
with
* Either
has a solution
or
has a solution
with
.
* Either
has a solution
or
has a solution
with
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.
There are also Farkas-like lemmas for
integer
An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
programs.
For systems of equations, the lemma is simple:
* Assume that A and b have rational coefficients. Then either
has an ''integral'' solution
or there exists
such that
is integral and
is not integral.
For system of inequalities, the lemma is much more complicated. It is based on the following two ''rules of inference'':
# Given inequalities
and coefficients
, infer the inequality
.
# Given an inequality
, infer the inequality
.
The lemma says that:
* Assume that A and b have rational coefficients. Then either
has an ''integral'' solution
, or it is possible to infer from
using finitely many applications of inference rules 1,2 the inequality
.
The variants are summarized in the table below.
Generalizations
Generalized Farkas' lemma can be interpreted geometrically as follows: either a vector is in a given closed
convex cone
In linear algebra, a cone—sometimes called a linear cone to distinguish it from other sorts of cones—is a subset of a real vector space that is closed under positive scalar multiplication; that is, C is a cone if x\in C implies sx\in C for e ...
, or there exists a
hyperplane
In geometry, a hyperplane is a generalization of a two-dimensional plane in three-dimensional space to mathematical spaces of arbitrary dimension. Like a plane in space, a hyperplane is a flat hypersurface, a subspace whose dimension is ...
separating the vector from the cone; there are no other possibilities. The closedness condition is necessary, see Separation theorem I in
Hyperplane separation theorem
In geometry, the hyperplane separation theorem is a theorem about disjoint convex sets in ''n''-dimensional Euclidean space. There are several rather similar versions. In one version of the theorem, if both these sets are closed and at least on ...
. For original Farkas' lemma,
is the nonnegative orthant
hence the closedness condition holds automatically. Indeed, for polyhedral convex cone, i.e., there exists a
such that
the closedness condition holds automatically. In
convex optimization
Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets (or, equivalently, maximizing concave functions over convex sets). Many classes of convex optimization problems ...
, various kinds of constraint qualification, e.g.
Slater's condition
In mathematics, Slater's condition (or Slater condition) is a sufficient condition for strong duality to hold for a convex optimization problem, named after Morton L. Slater. Informally, Slater's condition states that the feasible region must ...
, are responsible for closedness of the underlying convex cone
By setting
and
in generalized Farkas' lemma, we obtain the following corollary about the solvability for a finite system of linear equalities:
Further implications
Farkas' lemma can be varied to many further theorems of alternative by simple modifications,
such as
Gordan's theorem: Either
has a solution , or
has a nonzero solution with .
Common applications of Farkas' lemma include proving the
strong duality theorem associated with linear programming and the
Karush–Kuhn–Tucker conditions
In mathematical optimization, the Karush–Kuhn–Tucker (KKT) conditions, also known as the Kuhn–Tucker conditions, are first derivative tests (sometimes called first-order necessary conditions) for a solution in nonlinear programming to be ...
. 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
In mathematics, the Fredholm alternative, named after Ivar Fredholm, is one of Fredholm's theorems and is a result in Fredholm theory. It may be expressed in several ways, as a theorem of linear algebra, a theorem of integral equations, or as a ...
but for the condition to be necessary, one must apply von Neumann's
minimax theorem
In the mathematical area of game theory and of convex optimization, a minimax theorem is a theorem that claims that
: \max_ \min_ f(x,y) = \min_ \max_f(x,y)
under certain conditions on the sets X and Y and on the function f. It is always true that ...
to show the equations derived by Cauchy are not violated.
This is used for
Dill's Reluplex method for verifying deep neural networks.
See also
*
Dual linear program
The dual of a given linear program (LP) is another LP that is derived from the original (the primal) LP in the following schematic way:
* Each variable in the primal LP becomes a constraint in the dual LP;
* Each constraint in the primal LP becom ...
*
Fourier–Motzkin elimination
Fourier–Motzkin elimination, also known as the FME method, is a mathematical algorithm for eliminating variables from a system of linear inequalities. It can output real solutions.
The algorithm is named after Joseph Fourier who proposed the ...
– can be used to prove Farkas' lemma.
Notes
Further reading
*
* {{citation, first = R. T. , last=Rockafellar, author-link=R. T. Rockafellar, title=Convex Analysis, publisher= Princeton University Press, year=1979 , page=200 , mode=cs1
*
Kutateladze S.S.br>
The Farkas lemma revisited.''Siberian Mathematical Journal'', 2010, Vol. 51, No. 1, 78–87.
Lemmas in linear algebra
Convex analysis
Linear programming