Portal:Gravitation/Where to start

2010-08-02T10:46:25Z

203.219.15.37:

{{more footnotes|date=October 2011}}

'''Farkas's lemma''' is a result in [[mathematics]] stating that a vector is either in a given [[cone (linear algebra)|convex cone]] or that there exists a [[hyperplane|(hyper)plane]] separating the vector from the cone - there are no other possibilities. It was originally proved by the Hungarian mathematician [[Gyula Farkas (natural scientist)|Gyula Farkas]] {{harvs|txt|year=1894|year2=1902}}. It is used amongst other things in the proof of the [[Karush–Kuhn–Tucker|Karush–Kuhn–Tucker theorem]] in [[nonlinear programming]].

Farkas's lemma is an example of a [[theorem of the alternative]]; a theorem stating that of two systems, one or the other has a solution, but not both nor none.

== Statement of the lemma ==
Let ''A'' be a real ''m'' × ''n'' [[matrix (mathematics)|matrix]] and ''b'' an ''m''-dimensional real [[vector space|vector]]. Then, exactly one of the following two statements is true:
# There exists an ''x'' ∈ '''R'''''n'' such that ''Ax'' = ''b'' and ''x'' ≥ 0.
# There exists a ''y'' ∈ '''R'''''m'' such that ''ATy'' ≥ 0 and ''bTy'' < 0.
Here, the notation ''x'' ≥ 0 means that all components of the vector ''x'' are nonnegative.

There are a number of slightly different (but equivalent) formulations of the Lemma in the literature. The one given here is due to [[David Gale|Gale]], [[Harold Kuhn|Kuhn]] and [[Albert W. Tucker|Tucker]] in 1951.

== Geometric interpretation ==
Let ''a''1, …, ''a''''n'' ∈ '''R'''''m'' denote the columns of ''A''. In terms of these vectors, Farkas's lemma states that exactly one of the following two statements is true:
# There exist coefficients ''x''1, …, ''x''''n'' ∈ '''R''', ''x''1, …, ''x''''n'' ≥ 0, such that ''b'' = ''x''1''a''1 + ··· + ''x''''n''''a''''n''.
# There exists a vector ''y'' ∈ '''R'''''m'' such that ''a''''i'' · ''y'' ≥ 0 for ''i'' = 1, …, ''n'' and ''b'' · ''y'' < 0.

The vectors ''x''1''a''1 + ··· + ''x''''n''''a''''n'' with nonnegative coefficients constitute the [[convex cone]] of the set {''a''1, …, ''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''1, …, ''a''''n''} and the vector ''b''.

For example, let ''n,m''=2 and ''a''1 = (1,0)T and ''a''2 = (1,1)T. The convex cone spanned by ''a''1 and ''a''2 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''1''x''1+''a''2''x''2. Hence, there must be a separating hyperplane. Let ''y'' = (1,−1)T. We can see that ''a''1 · ''y'' = 1, ''a''2 · ''y'' = 0, and ''b'' · ''y'' = −1. Hence, the hyperplane with normal ''y'' indeed separates the convex cone ''a''1''x''1+''a''2''x''2 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.

== Further implications ==
Farkas's lemma can be varied to many further theorems of alternative by simple modifications, such as [[Gordan's theorem]]: Either <math>Ax < 0</math> has a solution ''x'', or <math>A^T y = 0 </math> has a nonzero solution ''y'' with ''y'' ≥ 0.

Common applications of Farkas' lemma include proving the strong and weak duality theorem associated with linear programming, game theory at a basic level and the [[Kuhn-Tucker conditions|Kuhn-Tucker]] constraints. 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 Kuhn-Tucker constraints using the Fredholm alternative but for the condition to be necessary, one must apply the Von Neumann equilibrium theorem to show the equations derived by Cauchy are not violated.

A particularly suggestive and easy-to-remember version is the following: if a set of inequalities has no solution, then a contradiction can be produced from it by linear combination with nonnegative coefficients. In formulas: if <math>Ax</math> ≤ <math>b</math> is unsolvable then <math>y^T A = 0</math>, <math>y^T b = -1</math>,
<math>y</math> ≥ <math>0</math> has a solution.<ref>{{Citation|title=Convex Optimization|first1=Stephen P.|last1=Boyd|first2=Lieven|last2=Vandenberghe|year=2004|publisher=Cambridge University Press|isbn=978-0-521-83378-3|url=http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf|format=pdf|accessdate=October 15, 2011|chapter=Section 5.8.3}}</ref> (Note that <math>y^T A</math> is a combination of the left hand sides, <math>y^T 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.)

==Notes==
{{reflist}}

== References ==
* {{Citation | last1=Berkovitz | first1=Leonard D. | title=Convexity and Optimization in <math>\mathbb{R}^n</math> | publisher=[[John Wiley & Sons]] | location=New York | isbn=978-0-471-35281-5 | year=2001}}.
* {{citation | first1 = Gyula | last1 = Farkas | author1-link = Gyula Farkas (natural scientist) | year = 1894 | title = A Fourier-féle mechanikai elv alkamazásai | journal = Mathematikai és Természettudományi Értesítő | volume = 12 | pages = 457–472 }}. reference from Schrijver's Combinatorial Optimization textbook
* {{citation | first1 = Julius (Gyula) | last1 = Farkas | author1-link = Gyula Farkas (natural scientist) | year = 1902 | title = Über die 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 = 124 | pages = 1–27 | doi = 10.1515/crll.1902.124.1 | issue = 124 }}.
* {{citation|first = R. T. |last=Rockafellar|author-link=R. T. Rockafellar|title=Convex Analysis|publisher= Princeton University Press|year=1979 |page=See Page 200}}
* {{citation|author=Gale, Kuhn and Tucker|chapter= Linear Programming and the Theory of Games - Chapter XII|title= Activity Analysis of Production and Allocation|editor =Koopmans|publisher= Wiley |year=1951|url = http://cowles.econ.yale.edu/P/cm/m13/m13-19.pdf }}. See Lemma 1 on page 318.
* {{Citation|doi=10.1007/s11202-010-0010-y|last=Kutateladze |first=S.|title=The Farkas Lemma Revisited |url=http://www.math.nsc.ru/LBRT/g2/english/ssk/preprint229.pdf|year=2010|journal=Siberian Mathematical Journal|volume=51|pages=78–87|issue=1|postscript=.}}



[[Category:Mathematical optimization]]
[[Category:Lemmas]]
[[Category:Convex analysis]]
[[Category:Linear programming]]
[[Category:Oriented matroids]]

formulasearchengine - User contributions [en]

Portal:Gravitation/Where to start