This article was accepted into the corpus but its outbound wikilinks were never NER-processed — typical at the deepest BFS hop or when the run's entity cap was reached. No expansion funnel to show.
| Farkas lemma | |
|---|---|
| Name | Farkas lemma |
| Field | Linear programming, Convex analysis, Optimization (mathematics) |
| Author | Gyula Farkas |
| Year | 1902 |
| Related | Gordan's theorem, Farkas' lemma generalizations, Motzkin's transposition theorem, Hahn–Banach theorem, Separation theorem (convex analysis) |
Farkas lemma
Farkas lemma is a fundamental result in Linear algebra and Convex analysis that provides an alternative between solvability of a linear system with nonnegativity constraints and existence of a linear functional certifying infeasibility. It underpins duality in Linear programming, informs results in Combinatorial optimization, and connects to separation theorems used throughout Functional analysis, Game theory, and Control theory. The lemma appears in many formulations across literature influenced by work in Hungarian mathematics and subsequent developments in German and British schools of optimization.
One common form of the lemma states: for a matrix A with entries in the real numbers and a vector b in R^n, exactly one of the following holds: there exists x >= 0 with A x = b, or there exists y with y^T A >= 0 and y^T b < 0. This dichotomy is equivalent to alternatives such as Gordan's theorem and Motzkin's transposition theorem and is closely related to the duality statement in Linear programming via the Simplex algorithm and interior-point methods developed by researchers associated with Dantzig, Karmarkar, and others. Alternative algebraic statements appear in texts on Matrix theory and Numerical linear algebra where connections to Singular value decomposition and rank are emphasized.
Geometrically, the lemma describes whether b lies in the cone generated by the columns of A; if not, there exists a hyperplane separating b from that cone. This view employs concepts from Convex geometry such as convex cones, supporting hyperplanes, and faces, and relates to separation results like the Hahn–Banach theorem. Visual intuitions draw on classical geometry studied by figures associated with Euclid, Descartes, and later developments by Carathéodory, Helly, and Radon. Applications to polyhedral theory relate to Polytope, simplex geometry and to combinatorial structures analyzed by researchers linked to Erdős, Kőnig, and Tutte.
Proofs of the lemma appear in algebraic, geometric, and analytic flavors. Algebraic proofs exploit elimination theory related to methods from Gauss–Jordan elimination and rely on linear independence notions developed in Cayley and Sylvester work. Geometric proofs use separating hyperplane arguments reminiscent of proofs of the Hahn–Banach theorem by functional analysts connected to Banach, Fréchet, and Riesz. Analytic proofs derive from convex optimization duality that echoes advances by Von Neumann in Game theory and John von Neumann's minimax theorem, and from variational analysis traditions influenced by Moreau, Fenchel, and Rockafellar. Constructive algorithmic proofs are given via the Simplex algorithm history in the work of Dantzig and through modern Interior-point method frameworks associated with Karmarkar.
Multiple variants extend the lemma to infinite-dimensional settings and structured cones. Infinite-dimensional extensions relate to the Hahn–Banach theorem and to separation in Topological vector space contexts studied by Schwartz and Dieudonné. Cone-generalizations involve Lorentz cone, Positive semidefinite cone, and Cone programming frameworks that connect to Semidefinite programming developments by researchers around Nesterov, Nemirovski, and Vandenberghe. Closely related statements include Gordan's theorem, generalized Farkas-type results, Motzkin transposition, and algebraic formulations used in Integer programming and Combinatorial optimization influenced by Cook, Karp, and Gröbner basis methods from Buchberger.
Farkas lemma is central to proofs of strong duality in Linear programming and is used in deriving optimality conditions such as the Karush–Kuhn–Tucker conditions in nonlinear programming with roots in work by Karush, Kuhn, and Tucker. It features in certificates of infeasibility in Integer programming and cutting-plane methods associated with Gomory and Lenstra. In Control theory and Robust optimization it helps derive linear matrix inequality formulations studied by authors in IEEE, SIAM, and INFORMS communities. The lemma informs economic equilibrium analyses tracing to Walras and Arrow–Debreu model ideas and appears in algorithmic complexity contexts tied to Karmarkar and Khachiyan.
The lemma originated in 1902 in work by Gyula Farkas within the Austro-Hungarian Empire mathematical tradition and was later integrated into the modern theory of linear inequalities and linear programming developed mid-20th century. Its consolidation into optimization theory tracks through contributions by Gordan, Motzkin, Dantzig, and the functional analysis school formed by Banach and Hahn. Subsequent expansions were driven by research communities in United States, France, and Soviet Union producing links to Game theory and Convex analysis that remain standard in contemporary treatments by authors associated with SIAM and major texts in Operations research taught at institutions like Princeton University, Massachusetts Institute of Technology, and University of Cambridge.
Category:Theorems in convex analysis