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 ''m'', ''n'' = 2, , and . The lemma says that exactly one of the following two statements must be true (depending on ''b''1 and ''b''2): # There exist ''x''1 ≥ 0, ''x''2 ≥ 0 such that 6 ''x''1 + 4 ''x''2 = ''b''1 and 3 ''x''1 = ''b''2, or # There exist ''y''1, ''y''2 such that 6 ''y''1 + 3 ''y''2 ≥ 0, 4 ''y''1 ≥ 0, and ''b''1 ''y''1 + ''b''2 ''y''2 < 0. Here is a proof of the lemma in this special case: * If ''b''2 ≥ 0 and ''b''1 − 2''b''2 ≥ 0, then option 1 is true, since the solution of the linear equations is ''x''1 = ''b''2/3 and ''x''2 = (''b''1-2''b''2) / 4. Option 2 is false, since ''b''1 ''y''1 + ''b''2 ''y''2 ≥ ''b''2 (2 ''y''1 + ''y''2) = ''b''2 (6 ''y''1 + 3 ''y''2) / 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''2 < 0, then we can take e.g. ''y''1 = 0 and ''y''2 = 1. ** If ''b''1 − 2''b''2 < 0, then, for some number ''B'' > 0, ''b''1 = 2''b''2 − B, so: ''b''1 ''y''1 + ''b''2 ''y''2 = 2 ''b''2 ''y''1 + ''b''2 ''y''2 − ''B'' ''y''1 = ''b''2 (6 ''y''1 + 3 ''y''2) / 3 − ''B'' ''y''1. Thus we can take, for example, ''y''1 = 1, ''y''2 = −2.Geometric interpretation
Consider the closed convex cone 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 that separates and . The lemma follows from the observation that belongs to if and only if 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 ''n'', ''m'' = 2, ''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 ''xy'' 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''.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.Variants
The Farkas Lemma has several variants with different sign constraints (the first one is the original version): * Either the system has a solution with , or the system has a solution with . * Either the system has a solution with , or the system has a solution with and . * Either the system has a solution with , or the system has a solution with and . * Either the system has a solution with , or the system 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.Generalizations
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 inFurther implications
Farkas's lemma can be varied to many further theorems of alternative by simple modifications, such as Gordan's theorem: Either has a solution ''x'', or 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'sSee also
*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.