View source for Farkas' lemma

{{short description|Solvability theorem for finite systems of linear inequalities}}
In [[mathematics]], '''Farkas' lemma''' is a solvability theorem for a finite [[System of inequalities|system]] of [[linear inequalities]]. It was originally proven by the Hungarian mathematician [[Gyula Farkas (natural scientist)|Gyula Farkas]].<ref name=Farkas1902> {{citation | first1 = Julius (Gyula) | last1 = Farkas | author1-link = Gyula Farkas (natural scientist) | year = 1902 | title = Theorie der Einfachen Ungleichungen | url = http://gdz.sub.uni-goettingen.de/en/dms/load/img/?PPN=PPN243919689_0124&DMDID=dmdlog4 | journal = [[Journal für die reine und angewandte Mathematik]] | volume = 1902 | pages = 1–27 | doi = 10.1515/crll.1902.124.1 | issue = 124 | s2cid = 115770124 }} </ref>
Farkas' [[Lemma (mathematics)|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|Karush–Kuhn–Tucker theorem]] in [[nonlinear programming]].<ref>{{cite book |first=Akira |last=Takayama |title=Mathematical Economics |location=New York |publisher=Cambridge University Press |edition=2nd |year=1985 |isbn=0-521-31498-4 |page=[https://archive.org/details/mathematicalecon00taka/page/48 48] |url=https://archive.org/details/mathematicalecon00taka |url-access=registration }}</ref>
Remarkably, in the area of the foundations of quantum theory, the lemma also underlies the complete set of [[Bell's theorem|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.<ref name=Garg1984> {{citation | first1 = Anupam | last1 = Garg |author1-link = Anupam Garg | last2 = Mermin | first2 = N. D. | author2-link = N. David Mermin | year = 1984 | title = Farkas's Lemma and the Nature of Reality: Statistical Implications of Quantum Correlations | url = https://link.springer.com/article/10.1007%2FBF00741645 | journal = Foundations of Physics | volume = 14 | pages = 1–39 | doi = 10.1007/BF00741645| s2cid = 123622613 }}</ref>
Generalizations of the Farkas' lemma are about the solvability theorem for convex inequalities,<ref name=Jeyakumar2014> {{Citation| title=Farkas' lemma three decades of generalizations for mathematical optimization | first1=N.|last1=Dinh|author1-link=N. Dinh |first2=V. |last2=Jeyakumar|author2-link=V. Jeyakumar |year=2014 |journal = TOP | volume = 22 | pages = 1–22| doi = 10.1007/s11750-014-0319-y | issue = 1| s2cid=119858980}}</ref> 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.<ref name=":0">{{Cite web|last=Border|first=KC|date=2013|title=Alternative Linear Inequalities|url=https://healy.econ.ohio-state.edu/kcb/Notes/Alternative.pdf|access-date=2021-11-29}}</ref>
== 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).<ref>{{citation|last1=Gale|first1=David|title=Activity Analysis of Production and Allocation|year=1951|editor=Koopmans|chapter=Linear Programming and the Theory of Games - Chapter XII|chapter-url=http://cowles.econ.yale.edu/P/cm/m13/m13-19.pdf|publisher=Wiley|last2=Kuhn|first2=Harold|last3=Tucker|first3=Albert W.|author1-link=David Gale|author2-link=Harold Kuhn|author3-link=Albert W. Tucker}}.  See Lemma 1 on page 318.</ref>
{{math_theorem|name=Farkas' lemma| Let <math>\mathbf{A} \in \R^{m\times n}</math>  and <math>\mathbf{b} \in \R^m.</math> Then exactly one of the following two assertions is true:
# There exists an <math>\mathbf{x} \in \R^n</math> such that <math>\mathbf{Ax} = \mathbf{b}</math> and <math>\mathbf{x} \geq 0.</math>
# There exists a <math>\mathbf{y} \in \R^m</math> such that <math>\mathbf{A}^\top\mathbf{y} \geq 0</math> and <math>\mathbf{b}^\top \mathbf{y}  < 0.</math> }}
Here, the notation <math>\mathbf{x} \geq 0</math> means that all components of the vector <math>\mathbf{x}</math> are nonnegative.
== Example ==
Let {{math|1=''m'', ''n'' = 2}}, <math>\mathbf{A} = \begin{bmatrix}6 & 4 \\3 & 0\end{bmatrix},</math> and <math>\mathbf{b} = \begin{bmatrix}b_1 \\b_2\end{bmatrix}.</math> The lemma says that exactly one of the following two statements must be true (depending on {{math|''b''<sub>1</sub>}} and {{math|''b''<sub>2</sub>}}):
# There exist {{math|''x''<sub>1</sub> ≥ 0}}, {{math|''x''<sub>2</sub> ≥ 0}} such that {{math|1=6''x''<sub>1</sub> + 4''x''<sub>2</sub> = ''b''<sub>1</sub>}} and {{math|1=3''x''<sub>1</sub> = ''b''<sub>2</sub>}},  or
# There exist {{math|''y''<sub>1</sub>, ''y''<sub>2</sub>}} such that {{math|6''y''<sub>1</sub> + 3''y''<sub>2</sub> ≥ 0}}, {{math|4''y''<sub>1</sub> ≥ 0}}, and {{math|''b''<sub>1</sub> ''y''<sub>1</sub> + ''b''<sub>2</sub> ''y''<sub>2</sub> < 0}}.
Here is a proof of the lemma in this special case:
* If {{math|''b''<sub>2</sub> ≥ 0}} and {{math|''b''<sub>1</sub> − 2''b''<sub>2</sub> ≥ 0}}, then option 1 is true, since the solution of the linear equations is <math>x_1 = \tfrac{b_2}{3}</math> and <math>x_2 = \tfrac{b_1 - 2b_2}{4}.</math>  Option 2 is false, since <math display=block>b_1 y_1 + b_2 y_2 \ge b_2 (2y_1 + y_2) = b_2 \frac{6y_1 + 3y_2}{3},</math> 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 {{math|''b''<sub>2</sub> < 0}}, then we can take e.g. {{math|1=''y''<sub>1</sub> = 0}} and {{math|1=''y''<sub>2</sub> = 1}}.
** If {{math|''b''<sub>1</sub> − 2''b''<sub>2</sub> < 0}}, then, for some number {{math|''B'' > 0}}, {{math|1=''b''<sub>1</sub> = 2''b''<sub>2</sub> − ''B''}}, so: <math display=block>b_1 y_1 + b_2 y_2 = 2b_2 y_1 + b_2 y_2 - By_1 = b_2 \frac{6y_1 + 3y_2}{3} - By_1.</math> Thus we can take, for example, {{math|1=''y''<sub>1</sub> = 1}}, {{math|1=''y''<sub>2</sub> = −2}}.
== Geometric interpretation ==
Consider the [[closed set|closed]] [[convex cone]] <math>C(\mathbf{A})</math> spanned by the columns of {{math|'''A'''}}; that is,
: <math>
C(\mathbf{A}) = \{\mathbf{A}\mathbf{x} \mid \mathbf{x} \geq 0 \}.
</math>
Observe that <math>C(\mathbf{A})</math> is the set of the vectors {{math|'''b'''}} for which the first assertion in the statement of Farkas' lemma holds. On the other hand, the vector {{math|'''y'''}} in the second assertion is orthogonal to a [[hyperplane]] that separates {{math|'''b'''}} and <math>C(\mathbf{A}).</math> The lemma follows from the observation that {{math|'''b'''}} belongs to <math>C(\mathbf{A})</math> if and only if there is no hyperplane that separates it from <math>C(\mathbf{A}).</math>
More precisely, let <math>\mathbf{a}_1, \dots, \mathbf{a}_n \in \R^m</math> denote the columns of {{math|'''A'''}}. In terms of these vectors, Farkas' lemma states that exactly one of the following two statements is true:
# There exist non-negative coefficients <math>x_1, \dots, x_n \in \R</math> such that <math>\mathbf{b} =x _1 \mathbf{a}_1 + \dots + x_n \mathbf{a}_n.</math>
# There exists a vector <math>\mathbf{y} \in \R^m</math> such that <math>\mathbf{a}_i^\top \mathbf{y} \geq 0</math> for <math>i = 1, \dots, n,</math> and <math>\mathbf{b}^\top \mathbf{y} < 0.</math>
The sums <math>x_1 \mathbf{a}_1 + \dots + x_n \mathbf{a}_n</math> with nonnegative coefficients <math>x_1, \dots, x_n</math> form the cone spanned by the columns of {{math|'''A'''}}. Therefore, the first statement tells that {{math|'''b'''}} belongs to <math>C(\mathbf{A}).</math>
The second statement tells that there exists a vector {{math|'''y'''}} such that the angle of {{math|'''y'''}} with the vectors {{math|'''a'''{{sub|i}}}} is at most 90°, while the angle of {{math|'''y'''}} with the vector {{math|'''b'''}} is more than 90°. The hyperplane normal to this vector has the vectors {{math|'''a'''{{sub|i}}}} on one side and the vector {{math|'''b'''}} on the other side. Hence, this hyperplane separates the cone spanned by <math>\mathbf{a}_1, \dots, \mathbf{a}_n</math> from the vector {{math|'''b'''}}.
For example, let {{math|1=''n'', ''m'' = 2}}, {{math|1=''a''<sub>1</sub> = (1, 0)<sup>T</sup>}}, and {{math|1=''a''<sub>2</sub> = (1, 1)<sup>T</sup>}}. The convex cone spanned by {{math|''a''<sub>1</sub>}} and {{math|''a''<sub>2</sub>}} can be seen as a wedge-shaped slice of the first quadrant in the {{mvar|xy}} plane. Now, suppose {{math|1=''b'' = (0, 1)}}. Certainly, {{mvar|b}} is not in the convex cone {{math|''a''<sub>1</sub>''x''<sub>1</sub> + ''a''<sub>2</sub>''x''<sub>2</sub>}}. Hence, there must be a separating hyperplane. Let {{math|1=''y'' = (1, −1)<sup>T</sup>}}. We can see that {{math|1=''a''<sub>1</sub> · ''y'' = 1}}, {{math|1=''a''<sub>2</sub> · ''y'' = 0}}, and {{math|1=''b'' · ''y'' = −1}}. Hence, the hyperplane with normal {{mvar|y}} indeed separates the convex cone {{math|''a''<sub>1</sub>''x''<sub>1</sub> + ''a''<sub>2</sub>''x''<sub>2</sub>}} from {{mvar|b}}.
== 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 <math>\mathbf{Ax} \le \mathbf{b}</math> is unsolvable then <math>\mathbf{y}^\top \mathbf{A} = 0,</math> <math>\mathbf{y}^\top \mathbf{b} = -1,</math> <math>\mathbf{y} \ge 0</math> has a solution.<ref>{{Citation |last1=Boyd |first1=Stephen P. |title=Convex Optimization |year=2004 |chapter=Section 5.8.3 |chapter-url=https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf#page=275 |chapter-format=pdf |publisher=Cambridge University Press |isbn=978-0-521-83378-3 |access-date=October 15, 2011 |last2=Vandenberghe |first2=Lieven}}.</ref> Note that <math>\mathbf{y}^\top \mathbf{A}</math> is a combination of the left-hand sides, <math>\mathbf{y}^\top \mathbf{b}</math> 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 [[Completeness (logic)|logical completeness]]: <math>\mathbf{Ax} \le \mathbf{b}</math> 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.<ref name="gm06">{{Cite Gartner Matousek 2006}} Pages 81–104.</ref>{{Rp|92–94}}
== Implications in complexity theory ==
Farkas' lemma implies that the [[decision problem]] "Given a system of linear equations, does it have a non-negative solution?" is in the intersection of [[NP (complexity)|NP]] and [[co-NP]]. 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 <math>NP \cap coNP</math> are also called ''well-characterized problems''. It is a long-standing open question whether <math>NP \cap coNP</math> is equal to [[P (complexity)|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]].<ref name=":1" />{{Rp|page=25|pages=}}
== Variants ==
The Farkas Lemma has several variants with different sign constraints (the first one is the original version):<ref name="gm06" />{{Rp|92}}
* Either <math>\mathbf{Ax} = \mathbf{b}</math> has a solution <math>\mathbf{x} \geq 0,</math> or <math>\mathbf{A}^\top\mathbf{y} \geq 0</math> has a solution '''<math>\mathbf{y} \in \R^m</math>''' with <math>\mathbf{b}^\top \mathbf{y} < 0.</math>
* Either <math>\mathbf{Ax} \leq \mathbf{b}</math> has a solution <math>\mathbf{x} \geq 0,</math>  or <math>\mathbf{A}^\top\mathbf{y} \geq 0</math> has a solution '''<math> \mathbf{y} \geq 0</math>''' with <math>\mathbf{b}^\top \mathbf{y} < 0 </math>
* Either <math>\mathbf{Ax} \leq \mathbf{b}</math> has a solution <math>\mathbf{x} \in \R^n,</math> or <math>\mathbf{A}^\top\mathbf{y} = 0</math> has a solution '''<math> \mathbf{y} \geq 0</math>''' with <math>\mathbf{b}^\top \mathbf{y} < 0</math>.
* Either <math>\mathbf{Ax} = \mathbf{b}</math> has a solution <math>\mathbf{x} \in \R^n,</math> or <math>\mathbf{A}^\top\mathbf{y} = 0</math> has a solution '''<math>\mathbf{y} \in \R^m</math>''' with <math>\mathbf{b}^\top \mathbf{y} \neq 0.</math>
The latter variant is mentioned for completeness; it is not actually a "Farkas lemma" since it contains only equalities. Its proof is an [[Fredholm alternative|exercise in linear algebra]].
There are also Farkas-like lemmas for integer programs.<ref name=":1">{{Cite Geometric Algorithms and Combinatorial Optimization}}</ref>{{Rp|page=|pages=12--14}} For systems of equations, the lemma is simple:
* Assume that '''A''' and '''b''' have rational coefficients. Then either <math>\mathbf{Ax} = \mathbf{b}</math> has an ''integral'' solution <math>\mathbf{x} \in \Z^n,</math>or there exists '''<math>\mathbf{y} \in \R^n</math>'''such that <math>\mathbf{A}^\top\mathbf{y}</math> is integral and <math>\mathbf{b}^\top \mathbf{y}</math> 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 <math>a_1^T x \leq b_1,\ldots , a_m^T x \leq b_m</math> and coefficients <math>w_1,\ldots,w_m</math>, infer the inequality <math>\left(\sum_{i=1}^m w_i a_i^T\right) x \leq \sum_{i=1}^m w_i b_i</math>.
# Given an inequality <math>a_1 x_1  + \cdots + a_m x_m \leq b</math>, infer the inequality  <math>\lfloor a_1\rfloor  x_1  + \cdots + \lfloor a_m \rfloor x_m \leq \lfloor b \rfloor</math>.
The lemma says that:
* Assume that '''A''' and '''b''' have rational coefficients. Then either <math>\mathbf{Ax} \leq \mathbf{b}</math> has an ''integral'' solution <math>\mathbf{x} \in \Z^n, x\geq 0</math>, or it is possible to infer from <math>\mathbf{Ax} \leq \mathbf{b}</math> using finitely many applications of inference rules 1,2 the inequality <math>0^T x \leq -1</math>.
The variants are summarized in the table below.
{| class="wikitable"
|+
!System
!Constraints on x
!
!Alternative system
!Constraints on y
|-
|<math>\mathbf{Ax} = \mathbf{b}</math>
|<math>\mathbf{x} \in \R^n, x\geq 0</math>
|
|<math>\mathbf{A}^\top\mathbf{y} \geq 0</math>,   <math>\mathbf{b}^\top \mathbf{y} < 0</math>
|'''<math>\mathbf{y} \in \R^m</math>'''
|-
|<math>\mathbf{Ax} \leq \mathbf{b}</math>
|<math>\mathbf{x} \in \R^n, x\geq 0</math>
|
|<math>\mathbf{A}^\top\mathbf{y} \geq 0</math>,   <math>\mathbf{b}^\top \mathbf{y} < 0</math>
|'''<math>\mathbf{y} \in \R^m</math>''',  '''<math> \mathbf{y} \geq 0</math>'''
|-
|<math>\mathbf{Ax} \leq \mathbf{b}</math>
|<math>\mathbf{x} \in \R^n</math>
|
|<math>\mathbf{A}^\top\mathbf{y} = 0</math>,   <math>\mathbf{b}^\top \mathbf{y} < 0</math>
|'''<math>\mathbf{y} \in \R^m</math>''',   '''<math> \mathbf{y} \geq 0</math>'''
|-
|<math>\mathbf{Ax} = \mathbf{b}</math>
|<math>\mathbf{x} \in \R^n</math>
|
|<math>\mathbf{A}^\top\mathbf{y} = 0</math>,   <math>\mathbf{b}^\top \mathbf{y} \neq 0</math>
|'''<math>\mathbf{y} \in \R^m</math>'''
|-
|<math>\mathbf{Ax} = \mathbf{b}</math>
|<math>\mathbf{x} \in \Z^n</math>
|
|<math>\mathbf{A}^\top\mathbf{y}</math> integral, <math>\mathbf{b}^\top \mathbf{y}</math> not integral
|'''<math>\mathbf{y} \in \R^n</math>'''
|-
|<math>\mathbf{Ax} \leq \mathbf{b}</math>
|<math>\mathbf{x} \in \Z^n, x\geq 0</math>
|
|<math>0^T x \leq -1</math> can be inferred from <math>\mathbf{Ax} \leq \mathbf{b}</math>
|
|}
== Generalizations ==
{{math_theorem|name=Generalized Farkas' lemma| Let <math>\mathbf{A} \in \R^{m \times n},</math> <math>\mathbf{b} \in \R^m,</math> <math>\mathbf{S}</math> is a closed convex cone in <math>\R^n,</math> and the [[dual cone]] of <math>\mathbf{S}</math> is <math>\mathbf{S}^* = \{ \mathbf{z} \in \R^n \mid \mathbf{z}^\top \mathbf{x} \geq 0, \forall \mathbf{x} \in \mathbf{S} \}.</math> If convex cone <math>C(\mathbf{A}) = \{\mathbf{A}\mathbf{x} \mid \mathbf{x} \in \mathbf{S} \}</math> is closed, then exactly one of the following two statements is true:
# There exists an <math>\mathbf{x} \in \R^n</math> such that <math>\mathbf{Ax} = \mathbf{b}</math> and <math>\mathbf{x} \in \mathbf{S}.</math>
# There exists a <math>\mathbf{y} \in \R^m</math> such that <math>\mathbf{A}^\top \mathbf{y} \in \mathbf{S}^* </math> and <math>\mathbf{b}^\top \mathbf{y} < 0.</math> }}
Generalized Farkas' lemma can be interpreted geometrically as follows: either a vector is in a given closed [[cone (linear algebra)|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, <math>\mathbf{S}</math> is the nonnegative orthant <math>\R_+^n,</math> hence the closedness condition holds automatically. Indeed, for polyhedral convex cone, i.e., there  exists a <math>\mathbf{B} \in \R^{n \times k}</math>  such that <math>\mathbf{S} = \{\mathbf{B}\mathbf{x} \mid \mathbf{x} \in \R_+^k \} ,</math> 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 <math>C(\mathbf{A}).</math>
By setting <math>\mathbf{S} = \R^n</math> and <math>\mathbf{S}^* = \{0\}</math> in generalized Farkas' lemma, we obtain the following corollary about the solvability for a finite system of linear equalities:
{{math_theorem|name=Corollary| Let <math>\mathbf{A} \in \R^{m \times n}</math> and <math>\mathbf{b} \in \R^m.</math> Then exactly one of the following two statements is true:
# There exists an <math>\mathbf{x} \in \R^n</math> such that <math>\mathbf{Ax} = \mathbf{b}.</math>
# There exists a <math>\mathbf{y} \in \R^m</math> such that <math>\mathbf{A}^\top\mathbf{y} = 0</math> and <math>\mathbf{b}^\top\mathbf{y} \neq 0.</math> }}
== Further implications ==
Farkas's lemma can be varied to many further theorems of alternative by simple modifications,<ref name=":0" /> such as [[Gordan's theorem]]: Either <math>\mathbf{Ax} < 0</math> has a solution {{math|'''x'''}}, or <math>\mathbf{A}^\top \mathbf{y} = 0 </math> has a nonzero solution {{math|'''y'''}} with {{math|'''y''' ≥ 0}}.
Common applications of Farkas' lemma include proving the [[Dual linear program|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 ==
* [[Dual linear program]]
* [[Fourier–Motzkin elimination]] – can be used to prove Farkas' lemma.
== Notes ==
{{reflist}}
== Further reading ==
* {{citation |first1=A. J. |last1=Goldman |first2=A. W. |last2=Tucker |title=Linear Inequalities and Related Systems |editor-first=H. W. |editor-last=Kuhn |editor2-first=A. W. |editor2-last=Tucker |location=Princeton |publisher=Princeton University Press |year=1956 |chapter=Polyhedral Convex Cones |pages=19–40 |isbn=0691079994 |chapter-url=https://books.google.com/books?id=zfaUBDY33XkC&pg=PA19 |mode=cs1 }}
* {{citation|first = R. T. |last=Rockafellar|author-link=R. T. Rockafellar|title=Convex Analysis|publisher= Princeton University Press|year=1979 |page=200 |mode=cs1 }}
* [[Semen Samsonovich Kutateladze|Kutateladze S.S.]] [https://link.springer.com/article/10.1007/s11202-010-0010-y The Farkas lemma revisited.] ''Siberian Mathematical Journal'', 2010, Vol.&nbsp;51, No.&nbsp;1, 78–87.
[[Category:Lemmas in linear algebra]]
[[Category:Convex analysis]]
[[Category:Linear programming]]