Farkas' lemma

Farkas' lemma states that exactly one of two alternatives holds: a linear system has a solution, or a nonnegative linear combination of its constraints certifies infeasibility.

Linear inequality system: A finite collection of linear inequalities in shared variables. One standard form asks whether such inequalities admit a common solution.
Linear inequality: An inequality whose expression in the variables is affine or linear. The lemma's constraints and certificates are built from linear inequalities.
Gyula Farkas: A Hungarian mathematician known for work on inequalities and mathematical analysis. The lemma bears his name and grew from his work on linear inequalities.
Simplex algorithm: An iterative method for solving linear programs by moving among vertices of the feasible polyhedron. Dual information produced by simplex methods can reveal infeasibility.
Gordan's theorem: A theorem stating an alternative between a strict positive solution of a homogeneous system and a nonnegative dependence among its rows. It is a close cousin of Farkas' lemma with a different system and alternative.
Infeasibility certificate: A mathematical witness proving that a system of constraints has no solution. The lemma's second alternative supplies one as nonnegative multipliers.
Convex cone: A set closed under addition and multiplication by nonnegative scalars. Nonnegative combinations of constraint vectors form a convex cone.
Linear programming: The optimization of a linear objective over a region defined by linear constraints. The lemma became a central tool for proving results about linear optimization.
Farkas certificate: A finite set of nonnegative multipliers whose weighted constraints prove a linear system infeasible. This is the explicit witness delivered by one alternative in the lemma.
Stiemke's theorem: A theorem giving mutually exclusive alternatives for a matrix equation and a strictly positive vector in its null space. Its strict-positivity conditions distinguish it from the usual Farkas alternatives.

Linked from 4 pages