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