TOPICS
Search

Farkas's Lemma


Let A be a matrix and x and b vectors. Then the system

 Ax=b,  x>=0

has no solution iff the system

 A^(T)y>=0,  b^(T)y<0

has a solution, where y is a vector (Fang and Puthenpura 1993, p. 60). This lemma is used in the proof of the Kuhn-Tucker theorem.


See also

Kuhn-Tucker Theorem, Lagrange Multiplier

Explore with Wolfram|Alpha

References

Fang, S.-C. and Puthenpura, S. Linear Optimization and Extensions: Theory and Algorithms. Englewood Cliffs, NJ: Prentice-Hall, p. 60, 1993.

Referenced on Wolfram|Alpha

Farkas's Lemma

Cite this as:

Weisstein, Eric W. "Farkas's Lemma." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/FarkassLemma.html

Subject classifications