44.02.04 · optimization-control / 02-convex-duality-kkt

Farkas' Lemma and the Theorems of the Alternative

shipped3 tiersLean: none

Anchor (Master): Rockafellar 1970 Convex Analysis (Princeton) §22 (Helly, Farkas, the theorems of the alternative); Schrijver 1986 Theory of Linear and Integer Programming (Wiley) §7; Ben-Tal & Nemirovski 2001 Lectures on Modern Convex Optimization (SIAM) §1

Intuition Beginner

You have a pile of arrows, all sticking out from the same point. By stacking them with non-negative amounts — you may scale an arrow up, leave it out, but never flip it backwards — you can reach a whole fan-shaped region of the plane. That reachable region is the cone of your arrows. Now someone hands you a target arrow and asks a yes-or-no question: can I build this target by stacking my arrows with non-negative amounts?

Farkas' lemma says there are exactly two possibilities, and never both at once. Either the target sits inside the fan, so you can build it. Or the target sits outside the fan, and then there is a clean, decisive reason it cannot be built: a flat dividing wall passes through the starting point with every one of your arrows on one side and the target strictly on the other side.

So a "no" answer is never a vague failure. A "no" always comes with a certificate — the dividing wall — that anyone can check in a moment. Either you exhibit the recipe that builds the target, or you exhibit the wall that proves no recipe exists. There is no murky middle ground where you simply could not find a recipe but also have no proof one is impossible.

This is the everyday face of a deep fact. Questions of the form "does a solution exist?" get replaced by a sharper pair: "here is a solution" versus "here is a proof that none exists." That swap is the engine behind why linear programs always have a matching price problem, and why constrained-optimization problems always come with multipliers.

Visual Beginner

Picture two arrows pinned at the origin, opening up a wedge between them. Every arrow you can build with non-negative amounts lands somewhere inside that wedge (the shaded fan). A target arrow either lands inside the fan — built — or outside it. When it lands outside, a single straight wall slides through the origin so the whole wedge is on one side and the target is on the other.

        target (outside)            target (inside)
            ^                            \
             \   wall                     \   . . . . .
              \  |                          \ .  fan  .
   arrow a2    \ |                  arrow a2 \. shaded .
       \        \|                      \     X. . . . .
        \        X-------- arrow a1      \   /        arrow a1
         \      /|                        \ /
          \    / |   <- everything         X------------>
           \  /  |      buildable lies       origin
   --------- X---+----  on one side of
           origin       the wall;
                        target on the other

Worked example Beginner

Work in the plane with the two building arrows $a_{1} = (1, 0)$ and $a_{2} = (0, 1)$ . Non-negative combinations are $x_{1} a_{1} + x_{2} a_{2} = (x_{1}, x_{2})$ with $x_{1} \geq 0$ and $x_{2} \geq 0$ — exactly the upper-right quarter-plane.

Target one: $b = (2, 3)$ . Can we build it with non-negative amounts? Take $x_{1} = 2$ and $x_{2} = 3$ . Both amounts are at least $0$ , and $2 \cdot (1, 0) + 3 \cdot (0, 1) = (2, 3) = b$ . Built. The target was inside the fan, so a recipe exists and we just wrote it down.

Target two: $b = (2, - 3)$ . Try to build it: we would need $x_{1} = 2$ and $x_{2} = - 3$ , but $- 3$ is a backwards amount, which is not allowed. So no non-negative recipe exists. Farkas promises a dividing wall. Use the direction $y = (0, - 1)$ . Check each arrow against it: $y$ paired with $a_{1}$ gives $0$ , and $y$ paired with $a_{2}$ gives $- 1$ . Both are at most $0$ , so every buildable arrow lands on the " $\leq 0$ " side. Now pair $y$ with the target: $y$ paired with $b = (2, - 3)$ gives $0 \cdot 2 + (- 1) (- 3) = 3$ , which is greater than $0$ . The target is strictly on the other side.

What this tells us. The wall direction $y$ is a one-line proof that $(2, - 3)$ cannot be built: every building arrow scores $\leq 0$ against $y$ , while the target scores $+ 3$ . A non-negative recipe would have to score $\leq 0$ too, so none can exist.

Check your understanding Beginner

Exercise (easy, multiple choice).

Farkas' lemma says that for a fixed set of building arrows and a target, exactly one of these always holds:

A. The target can be built with non-negative amounts. B. There is a dividing wall with every arrow on one side and the target strictly on the other. C. Exactly one of A or B holds — never both, never neither. D. Both A and B always hold at the same time.

Hint

Re-read the very first promise: there are two possibilities and never both at once.

Answer

C. Exactly one of A or B holds.

Feedback-correct: correct — this "exactly one of two" structure is what the word alternative means. Feedback-wrong: A and B cannot both hold, because a wall separating the target from every buildable arrow would also separate it from any recipe built out of those arrows; and they cannot both fail, which is the content of the lemma.

Formal definition Intermediate+

Fix $A \in R^{m \times n}$ with columns $a_{1}, \dots, a_{n} \in R^{m}$ , and $b \in R^{m}$ . The finitely generated cone generated by the columns is

cone (A) = {A x : x \in R^{n}, x \geq 0} = {\sum_{j = 1}^{n} x_{j} a_{j} : x_{j} \geq 0},

where $x \geq 0$ means $x_{j} \geq 0$ for every coordinate. This is a convex cone: closed under addition and under multiplication by non-negative scalars. The pairing $⟨ y, v ⟩ = \sum_{i = 1}^{m} y_{i} v_{i}$ is the standard inner product on $R^{m}$ .

A theorem of the alternative asserts that for a pair of systems $(S_{1})$ and $(S_{2})$ , exactly one is solvable: $(S_{1})$ has a solution if and only if $(S_{2})$ has none. The solution of the unsolvable system's dual is a certificate of infeasibility.

Definition (Farkas alternative). The two systems

(F_{1}) : A x = b, x \geq 0 and (F_{2}) : A^{T} y \leq 0, ⟨ b, y ⟩ > 0

are called the Farkas pair. System $(F_{1})$ asks whether $b \in cone (A)$ ; system $(F_{2})$ asks for a separating direction $y$ that scores $\leq 0$ against every column yet strictly positive against $b$ .

A polyhedral cone is a set of the form ${v : C v \leq 0}$ for some matrix $C$ (a finite intersection of homogeneous half-spaces). The Minkowski-Weyl theorem identifies polyhedral cones with finitely generated cones; the half of that identity used below is that $cone (A)$ is closed in $R^{m}$ — the new content of this unit, since separation of a point from a convex set requires the set to be closed.

Counterexamples to common slips

The cone must be closed for separation to certify infeasibility. Convex sets that are not closed can fail to be separated from a boundary point by a strict inequality. Example: the set ${(x_{1}, x_{2}) : x_{1} > 0} \cup {(0, 0)}$ is convex but not closed, and the origin cannot be strictly separated from it. Finitely generated cones avoid this pathology precisely because they are always closed — this is what makes Farkas a clean dichotomy rather than an approximate one.
Not every closed convex cone is finitely generated. The ice-cream (second-order) cone ${(x, t) : ∥ x ∥ \leq t}$ is closed and convex but is not the conic hull of finitely many vectors; Farkas as stated applies to finitely generated (equivalently polyhedral) cones. The conic generalisation needs the closed-cone separation argument but loses the rational/finite certificate.
Equality vs inequality form changes the dual sign pattern. The system $A x \leq b$ (inequality form) has Farkas dual $A^{T} y = 0, y \geq 0, ⟨ b, y ⟩ < 0$ . Mixing up which side carries the sign constraint is the most common error; track which primal variable is sign-constrained and which primal row is an inequality.

Key theorem with proof Intermediate+

We prove Farkas' lemma. The geometric separating-hyperplane theorem of 02.11.02 is the engine; the finite-dimensional closedness of $cone (A)$ is the content that makes separation applicable.

Theorem (Farkas' lemma). Let $A \in R^{m \times n}$ and $b \in R^{m}$ . Exactly one of the following holds:

$(F_{1})$ there exists $x \in R^{n}$ with $A x = b$ and $x \geq 0$ ;

$(F_{2})$ there exists $y \in R^{m}$ with $A^{T} y \leq 0$ and $⟨ b, y ⟩ > 0$ .

Proof that both cannot hold. Suppose $(F_{1})$ and $(F_{2})$ held simultaneously. Then $⟨ b, y ⟩ = ⟨ A x, y ⟩ = ⟨ x, A^{T} y ⟩ = \sum_{j} x_{j} (A^{T} y)_{j} \leq 0$ , because each $x_{j} \geq 0$ and each $(A^{T} y)_{j} \leq 0$ . This contradicts $⟨ b, y ⟩ > 0$ . So at most one of the systems is solvable.

Lemma (finitely generated cones are closed). $cone (A) = {A x : x \geq 0}$ is a closed subset of $R^{m}$ .

Proof of the lemma. Argue by induction on the number of generators $n$ . For $n = 0$ the cone is ${0}$ , closed. Carathéodory's theorem for cones states that every point of $cone (A)$ is a non-negative combination of a linearly independent subset of the columns: if $v = \sum_{j} x_{j} a_{j}$ with $x_{j} \geq 0$ and the active columns ${a_{j} : x_{j} > 0}$ are dependent, a dependency $\sum_{j} λ_{j} a_{j} = 0$ lets one decrease some $x_{j}$ to zero while keeping $v$ fixed and all coefficients non-negative, reducing the support. Hence

cone (A) = S ⋃ cone (A_{S}),

a finite union over the subsets $S \subseteq {1, \dots, n}$ whose columns $A_{S}$ are linearly independent. For each such $S$ , the map $x_{S} \mapsto A_{S} x_{S}$ is a linear isomorphism onto its image, so it is a closed map on the closed set ${x_{S} \geq 0}$ , and $cone (A_{S})$ is closed. A finite union of closed sets is closed. $□$

Proof of the dichotomy. Assume $(F_{1})$ fails, that is $b \in / cone (A)$ . The cone $K := cone (A)$ is non-empty (it contains $0$ ), convex, and closed by the lemma. The singleton ${b}$ is compact and convex and disjoint from $K$ . The second geometric Hahn-Banach theorem 02.11.02 strictly separates them: there exist $y \in R^{m} ∖ {0}$ and scalars $α_{1} < α_{2}$ with

⟨ y, v ⟩ \leq α_{1} < α_{2} \leq ⟨ y, b ⟩ for all v \in K .

Because $0 \in K$ , taking $v = 0$ gives $α_{1} \geq 0$ , hence $⟨ y, b ⟩ \geq α_{2} > α_{1} \geq 0$ , so $⟨ b, y ⟩ > 0$ . It remains to show $A^{T} y \leq 0$ , i.e. $⟨ y, a_{j} ⟩ \leq 0$ for each column. Fix a column $a_{j}$ and a scalar $t > 0$ ; then $t a_{j} \in K$ , so $t ⟨ y, a_{j} ⟩ = ⟨ y, t a_{j} ⟩ \leq α_{1}$ . Letting $t \to \infty$ forces $⟨ y, a_{j} ⟩ \leq 0$ (otherwise the left side diverges to $+ \infty$ , exceeding the fixed bound $α_{1}$ ). Thus $A^{T} y \leq 0$ and $⟨ b, y ⟩ > 0$ , which is exactly $(F_{2})$ . So whenever $(F_{1})$ fails, $(F_{2})$ holds, completing the dichotomy. $□$

Bridge. This dichotomy builds toward the whole of linear-programming duality and appears again in the constraint-qualification analysis of nonlinear optimization. This is exactly the statement that a vector either lies in a finitely generated cone or is strictly separated from it, and the foundational reason the alternative is clean — never both, never neither — is the closedness lemma: separation of a point from a convex set certifies non-membership only when the set is closed, and finite generation forces closedness. The geometric step is dual to the membership question — the supporting functional $y$ produced by Hahn-Banach is precisely the dual variable that prices infeasibility. Putting these together, the columns $a_{j}$ become constraint gradients and $b$ becomes an objective gradient, so that Farkas reads "either the objective gradient is a non-negative combination of active constraint gradients (a KKT multiplier vector exists) or there is a feasible improving direction"; that reading generalises to the Karush-Kuhn-Tucker conditions under a linear constraint qualification.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Prove Gordan's theorem: exactly one of (a) $A x = 0, x \geq 0, x \neq = 0$ is solvable, or (b) $A^{T} y > 0$ (strictly, every coordinate positive) is solvable. Reduce to Farkas.

Hint

System (b) says $\sum_{j} a_{j}$ -pairings are all positive; relate it to a Farkas system with $b = 1$ and an auxiliary scalar.

Answer

System (b), $A^{T} y > 0$ , is equivalent to: there exist $y$ and $t > 0$ with $A^{T} y \geq t 1$ , i.e. $A^{T} y - t 1 \geq 0, t > 0$ . Negate $y \mapsto - y$ and apply the inequality Farkas form (Exercise 1) to the system $[- A^{T} ∣ 1] (t y) \leq 0$ with the extra strict requirement on $t$ : the alternative to (b) is the existence of $x \geq 0, x \neq = 0$ with $A x = 0$ (the $1^{T} x = 1$ normalisation forces $x \neq = 0$ ). The two cannot coexist: if $A x = 0, x \geq 0, x \neq = 0$ and $A^{T} y > 0$ , then $0 = ⟨ A x, y ⟩ = ⟨ x, A^{T} y ⟩ > 0$ since some $x_{j} > 0$ multiplies a positive entry. Contradiction.

Exercise 4 (medium, symbolic).

Prove Stiemke's theorem: exactly one of (a) $A x = 0, x > 0$ (strictly positive) is solvable, or (b) $A^{T} y \geq 0, A^{T} y \neq = 0$ is solvable.

Hint

Stiemke is the "transpose-dual" of Gordan: swap the roles of the strict and non-strict cones. Apply Gordan to $A^{T}$ .

Answer

Apply Gordan's theorem (Exercise 3) to the matrix $A^{T}$ in place of $A$ : exactly one of $A^{T} y = 0, y \geq 0, y \neq = 0$ or $A z > 0$ holds — that is not yet Stiemke. Instead use the homogeneous Farkas duality directly: the cone ${A x : x > 0}$ has closure $cone (A)$ , and $0$ lies in the relative interior of $cone (A)$ iff $A x = 0$ has a strictly positive solution. The negation is that $0$ is on the boundary, which by supporting-hyperplane gives $y$ with $⟨ y, a_{j} ⟩ \geq 0$ for all $j$ and strict for at least one, i.e. $A^{T} y \geq 0, A^{T} y \neq = 0$ . Incompatibility: $A x = 0, x > 0$ and $A^{T} y \geq 0, \neq = 0$ give $0 = ⟨ x, A^{T} y ⟩ > 0$ , contradiction.

Exercise 6 (hard, symbolic).

Prove Motzkin's transposition theorem: given matrices $B, C, D$ , exactly one of (a) $B x > 0, C x \geq 0, D x = 0$ is solvable, or (b) $B^{T} u + C^{T} v + D^{T} w = 0$ with $u \geq 0, v \geq 0, u \neq = 0$ is solvable. (Assume $B$ has at least one row.)

Hint

Introduce a scalar $t$ and rewrite $B x > 0$ as $B x \geq t 1, t > 0$ ; then the whole system is a single Farkas/Gordan-type homogeneous system in $(x, t)$ .

Answer

Replace $B x > 0$ by $B x - t 1 \geq 0$ with the requirement $t > 0$ . System (a) is then solvable iff the homogeneous system $B x - t 1 \geq 0, C x \geq 0, D x = 0, t \geq 0$ has a solution with $t > 0$ . Maximising $t$ subject to those linear inequalities is a linear program whose value is positive iff (a) holds; by the inequality Farkas alternative the value is non-positive iff there is a dual certificate $u \geq 0, v \geq 0, w$ free with $B^{T} u + C^{T} v + D^{T} w = 0$ and $1^{T} u = 1$ (so $u \neq = 0$ ), which is (b). Incompatibility: pairing (a) and (b), $0 = ⟨ x, B^{T} u + C^{T} v + D^{T} w ⟩ = ⟨ B x, u ⟩ + ⟨ C x, v ⟩ + ⟨ D x, w ⟩ > 0$ since $⟨ B x, u ⟩ > 0$ (as $B x > 0, u \geq 0, u \neq = 0$ ) and the other two terms are $\geq 0$ . Contradiction. Gordan, Stiemke, and the inequality Farkas form are all special cases.

Exercise 7 (hard, symbolic).

Use Farkas' lemma to prove weak and strong LP duality for the primal $min ⟨ c, x ⟩$ subject to $A x = b, x \geq 0$ and dual $max ⟨ b, y ⟩$ subject to $A^{T} y \leq c$ .

Hint

Weak duality is the same one-line pairing as in the theorem. For strong duality, apply Farkas to the augmented system asserting "primal value $< γ$ " for $γ$ just below the optimum.

Answer

Weak: if $A x = b, x \geq 0$ and $A^{T} y \leq c$ , then $⟨ c, x ⟩ \geq ⟨ A^{T} y, x ⟩ = ⟨ y, A x ⟩ = ⟨ b, y ⟩$ . Strong: let $p^{⋆}$ be the (finite, attained) primal optimum. For any $γ < p^{⋆}$ , the system $A x = b, x \geq 0, ⟨ c, x ⟩ \leq γ$ is infeasible. Writing this as a single standard-form feasibility and applying Farkas yields multipliers $(y, λ)$ with $λ \geq 0$ , $A^{T} y - λ c \leq 0$ , and $⟨ b, y ⟩ - λγ > 0$ . A normalisation argument (the case $λ = 0$ is excluded by primal feasibility of some point) lets one set $λ = 1$ , giving $A^{T} y \leq c$ with $⟨ b, y ⟩ > γ$ . Letting $γ ↑ p^{⋆}$ produces a dual-feasible $y$ with $⟨ b, y ⟩ \geq p^{⋆}$ ; weak duality gives the reverse, so the dual optimum equals $p^{⋆}$ .

Exercise 8 (hard, symbolic).

Give a closed convex cone in $R^{3}$ that is not finitely generated, exhibit a boundary direction that is a non-strict but not strict separator, and explain which step of the Farkas proof breaks for it.

Hint

The second-order (Lorentz) cone is the standard example; recall the closedness lemma relied on a finite union over independent subsets.

Answer

Take the Lorentz cone $L = {(x_{1}, x_{2}, t) : x_{1}^{2} + x_{2}^{2} \leq t}$ , closed and convex but not the conic hull of finitely many vectors. The boundary ray through $(1, 0, 1)$ has supporting functional $y = (1, 0, - 1)$ : $⟨ y, v ⟩ \leq 0$ for all $v \in L$ , with equality along the whole boundary ray, so $y$ separates but not strictly. The Farkas dichotomy as stated still has a separation theorem available (the closed-cone case), but the closedness lemma's proof breaks: there is no finite family of independent generating subsets whose conic hulls union to $L$ , so the "finite union of closed images" argument does not apply. Closedness of $L$ holds for analytic reasons instead, and the resulting alternative (conic duality) only guarantees a non-strict certificate unless a Slater interior-point condition is imposed.

Advanced results Master

The fundamental theorem of linear inequalities and Carathéodory bounds

For $a_{1}, \dots, a_{n}, b \in R^{m}$ , exactly one holds: either $b = \sum_{j} x_{j} a_{j}$ with $x_{j} \geq 0$ , or there is a hyperplane ${v : ⟨ y, v ⟩ = 0}$ containing $m - 1$ linearly independent vectors from ${a_{1}, \dots, a_{n}}$ , with $⟨ y, a_{j} ⟩ \leq 0$ for all $j$ and $⟨ y, b ⟩ > 0$ . This sharpened Farkas — due to the column-geometry analysis systematised by Schrijver ^{[Schrijver §7]} — produces a combinatorial certificate: the separating hyperplane may be taken to pass through a basis of columns. The conic Carathéodory bound is its quantitative shadow: any $b \in cone (A) \subseteq R^{m}$ is a non-negative combination of at most $m$ linearly independent columns. Both refinements come from the same independent-subset decomposition used to prove closedness; the certificate is rational whenever the data are rational, which is why Farkas underwrites exact infeasibility proofs for rational linear programs.

The Minkowski-Weyl equivalence

A convex cone $K \subseteq R^{m}$ is finitely generated ( $K = cone (A)$ for some $A$ ) if and only if it is polyhedral ( $K = {v : C v \leq 0}$ for some $C$ ). One direction: $cone (A)^{\circ} = {y : A^{T} y \leq 0}$ is polyhedral by inspection, and Exercise 5 gives $K = K^{\circ\circ}$ , so $K = (cone (A)^{\circ})^{\circ}$ is the dual of a polyhedral cone — which is again finitely generated by applying the first computation to a generating matrix of the polyhedral cone. The equivalence is the cone-level statement of LP duality: representing a cone by generators versus by constraints are dual descriptions, interchanged by polarity, and Farkas is the membership-test bridge between them ^{[Rockafellar §19]}.

Helly's theorem and the alternative

Farkas sits inside a family of dichotomies governed by Helly's theorem: in $R^{m}$ , if every $m + 1$ members of a finite family of convex sets have a common point, then all of them do. Rockafellar ^{[Rockafellar §22]} derives the theorems of the alternative and Helly from the same separation core. The Helly number $m + 1$ matches the Carathéodory bound and the basis size in the fundamental theorem; all three count the same intrinsic dimension. Infeasibility of a system of linear inequalities is thereby locally certifiable: a system $A x \leq b$ is infeasible iff some sub-system of at most $m + 1$ inequalities already is, the LP analogue of compactness reducing global to finite.

Conic and semi-infinite generalisations

Replacing the non-negative orthant by a general closed convex cone $K$ with dual $K^{*}$ gives the conic Farkas lemma: provided a Slater interior-point condition holds (or the image cone is closed), exactly one of $A x = b, x \in K$ or $A^{T} y \in K^{*}, ⟨ b, y ⟩ < 0$ is solvable. Without closedness — the generic situation for the semidefinite cone — the alternative degrades to an approximate form and strong duality can fail, exactly the gap repaired by constraint qualifications. The polyhedral case is the one place the dichotomy is unconditional, because finite generation forces closedness for free; every richer cone pays for separation with a regularity hypothesis.

Synthesis. Farkas' lemma is exactly the assertion that a vector either lies in a finitely generated cone or is strictly separated from it, and the central insight organising this unit is that the clean two-way alternative rests on one structural fact — finitely generated cones are closed — which is dual to the membership question through the bipolar identity $K = K^{\circ\circ}$ . The foundational reason the polyhedral case needs no constraint qualification, while the conic case does, is that finite generation supplies closedness automatically whereas the second-order and semidefinite cones do not, so putting these together the Minkowski-Weyl equivalence, the Carathéodory and Helly bounds, and LP strong duality are all the same separation theorem read through different descriptions of the same cone. The result generalises the smooth Lagrange-multiplier picture to the non-smooth polyhedral setting and appears again in the Karush-Kuhn-Tucker conditions, where the columns are active constraint gradients and the separating functional is the multiplier vector. The bridge is polarity: generators and constraints are conjugate descriptions of a cone, Farkas is the test that passes between them, and duality theory is what that test becomes once an objective is attached.

Full proof set Master

Proposition 1 (homogeneous Farkas / closed-cone separation). Let $K = cone (A) \subseteq R^{m}$ and $b \in R^{m}$ . Then $b \in K$ , or there exists $y$ with $⟨ y, a_{j} ⟩ \leq 0$ for all $j$ and $⟨ y, b ⟩ > 0$ , and not both.

Proof. This is the Key theorem restated; the proof there established closedness of $K$ via the finite union over linearly independent column subsets (Carathéodory reduction), then strictly separated the compact set ${b}$ from the closed convex $K$ by the second geometric Hahn-Banach theorem 02.11.02, and used the cone scaling $t a_{j} \in K$ for all $t > 0$ to push the separating functional to satisfy $⟨ y, a_{j} ⟩ \leq 0$ . Mutual exclusivity is the pairing $⟨ b, y ⟩ = ⟨ x, A^{T} y ⟩ \leq 0$ when $x \geq 0$ . $□$

Proposition 2 (affine / inequality Farkas). Exactly one of $A x \leq b$ (in $x$ ) and ${y \geq 0, A^{T} y = 0, ⟨ b, y ⟩ < 0}$ is solvable.

Proof. Feasibility of $A x \leq b$ is equivalent to $b \in cone ([A ∣ I]) + (free x -part)$ after introducing slacks $A x + s = b, s \geq 0$ and splitting $x = x^{+} - x^{-}$ with $x^{\pm} \geq 0$ . Concretely, $A x \leq b$ has a solution iff the standard-form system $[A ∣ - A ∣ I] (x^{+}; x^{-}; s) = b$ with $(x^{+}; x^{-}; s) \geq 0$ has a solution. Apply Proposition 1 to the augmented matrix $M = [A ∣ - A ∣ I]$ . The dual condition $M^{T} y \leq 0$ unpacks to $A^{T} y \leq 0, - A^{T} y \leq 0, y \leq 0$ , i.e. $A^{T} y = 0$ and $y \leq 0$ ; together with $⟨ b, y ⟩ > 0$ and the sign flip $y \mapsto - y$ this is precisely $y \geq 0, A^{T} y = 0, ⟨ b, y ⟩ < 0$ . $□$

Proposition 3 (Gordan). Exactly one of $A x = 0, x \geq 0, x \neq = 0$ and $A^{T} y > 0$ is solvable.

Proof. $A^{T} y > 0$ is solvable iff there are $y, t$ with $A^{T} y \geq t 1$ and $t > 0$ . The system ${A^{T} y - t 1 \geq 0}$ in variables $(y, t)$ with the objective of maximising $t$ is a linear program; its optimal value exceeds $0$ iff $A^{T} y > 0$ has a solution. By Proposition 2 applied to the constraints, the value is $\leq 0$ iff there is a dual multiplier $x \geq 0$ on the rows of $A^{T}$ with $A x = 0$ and the normalisation row giving $1^{T} x = 1$ , hence $x \neq = 0$ . Exclusivity: $A x = 0, x \geq 0, x \neq = 0$ and $A^{T} y > 0$ force $0 = ⟨ x, A^{T} y ⟩ > 0$ . $□$

Proposition 4 (Stiemke). Exactly one of $A x = 0, x > 0$ and $A^{T} y \geq 0, A^{T} y \neq = 0$ is solvable.

Proof. The existence of $x > 0$ with $A x = 0$ is equivalent to $0$ lying in the relative interior of $cone (A)$ together with $cone (A)$ being a linear subspace along the support — equivalently, no supporting hyperplane of $cone (A)$ at $0$ is proper. Its negation produces, by the supporting-hyperplane corollary of 02.11.02, a functional $y$ with $⟨ y, a_{j} ⟩ \geq 0$ for all $j$ and strict inequality for at least one $j$ (else the hyperplane would be improper), i.e. $A^{T} y \geq 0, A^{T} y \neq = 0$ . Exclusivity: $A x = 0, x > 0$ and $A^{T} y \geq 0, \neq = 0$ give $0 = ⟨ x, A^{T} y ⟩ > 0$ since every $x_{j} > 0$ and some $(A^{T} y)_{j} > 0$ . $□$

Proposition 5 (Carathéodory bound for cones). Every $b \in cone (A) \subseteq R^{m}$ is a non-negative combination of at most $m$ linearly independent columns of $A$ .

Proof. Among all representations $b = \sum_{j \in S} x_{j} a_{j}$ with $x_{j} > 0$ , choose one with $∣ S ∣$ minimal. If the columns ${a_{j} : j \in S}$ were linearly dependent, there is $λ \neq = 0$ with $\sum_{j \in S} λ_{j} a_{j} = 0$ ; assume some $λ_{j} > 0$ (else negate $λ$ ). For $τ \geq 0$ , $b = \sum_{j \in S} (x_{j} - τ λ_{j}) a_{j}$ , and increasing $τ$ to $τ^{⋆} = min_{λ_{j} > 0} x_{j} / λ_{j}$ drives one coefficient to $0$ while keeping all coefficients $\geq 0$ , contradicting minimality of $∣ S ∣$ . So the active columns are independent, hence $∣ S ∣ \leq m$ . $□$

Connections Master

The separating-hyperplane engine is the geometric Hahn-Banach theorem of 02.11.02: the closed convex cone $cone (A)$ and the external point $b$ are strictly separated by exactly the second geometric form, and the supporting functional it returns is the Farkas certificate $y$ . Where that unit works in a general normed space and needs Zorn's lemma, the finite-dimensional specialisation here trades the choice principle for the explicit closedness lemma proved by Carathéodory reduction.
The membership question $b \in cone (A)$ is a non-negative solvability question for the linear system $A x = b$ , sharpening the unrestricted solvability theory of 01.01.06: Kronecker-Capelli tests solvability with $x$ free via rank equality, while Farkas tests solvability under the sign constraint $x \geq 0$ via cone membership, and the column-space geometry both rest on is the rank-nullity picture of 01.01.05.
The separating object is an affine hyperplane in the sense of 01.01.18: the wall ${v : ⟨ y, v ⟩ = α}$ that isolates $b$ from the cone is precisely a hyperplane, and the homogeneous cone case places it through the origin, making Farkas the constrained-feasibility incarnation of the affine-subspace separation studied there.
Linear-programming strong duality and the Karush-Kuhn-Tucker multiplier theorem are the two headline consumers: LP duality is Farkas applied to the augmented "value $< γ$ " system (Exercise 7), and KKT existence under a linear constraint qualification is Farkas applied to the objective gradient against the active-constraint gradients, identifying the cone-membership coefficients as the multipliers.

Historical & philosophical context Master

Gyula Farkas published the lemma in its definitive form in Theorie der einfachen Ungleichungen ^{[Farkas 1902]} (Journal für die reine und angewandte Mathematik 124, 1-27), having developed it through the 1890s in connection with the mechanical principle of virtual work and Fourier's earlier study of systems of linear inequalities; Farkas sought to characterise exactly when a force can be expressed as a non-negative combination of constraint reaction forces. The strict-inequality alternative now bearing Gordan's name appeared earlier, in Paul Gordan's Über die Auflösung linearer Gleichungen mit reellen Coefficienten ^{[Gordan 1873]} (Mathematische Annalen 6, 23-28), in the context of invariant theory. Erich Stiemke gave the complementary strictly-positive-solution alternative in 1915, and Theodore Motzkin's 1936 Basel dissertation ^{[Motzkin 1936]} unified the family into the transposition theorem that contains Farkas, Gordan, and Stiemke as special cases.

The results were absorbed into convex analysis through the systematic separation-theorem treatments of Fenchel and, definitively, Rockafellar's Convex Analysis (1970), which placed Farkas, Helly, and the theorems of the alternative on the common foundation of separating hyperplanes for polyhedral convex sets. The practical reach widened with the rise of linear programming: Dantzig's simplex method (1947), the von Neumann duality theory of zero-sum games, and Kuhn and Tucker's 1951 nonlinear-programming paper all rest on the Farkas dichotomy, which supplies the constraint qualification under which multipliers provably exist. Schrijver's Theory of Linear and Integer Programming (1986) records the combinatorial and complexity-theoretic refinements, including the rational-certificate property that places linear-inequality infeasibility in the complexity class $NP \cap co - NP$ .

Bibliography Master

@article{farkas1902einfachen,
  author  = {Farkas, Gyula},
  title   = {Theorie der einfachen Ungleichungen},
  journal = {Journal f\"ur die reine und angewandte Mathematik},
  volume  = {124},
  pages   = {1--27},
  year    = {1902}
}

@article{gordan1873aufloesung,
  author  = {Gordan, Paul},
  title   = {\"Uber die Aufl\"osung linearer Gleichungen mit reellen Coefficienten},
  journal = {Mathematische Annalen},
  volume  = {6},
  pages   = {23--28},
  year    = {1873}
}

@phdthesis{motzkin1936beitraege,
  author  = {Motzkin, Theodore Samuel},
  title   = {Beitr\"age zur Theorie der linearen Ungleichungen},
  school  = {University of Basel},
  year    = {1936}
}

@book{rockafellar1970convex,
  author    = {Rockafellar, R. Tyrrell},
  title     = {Convex Analysis},
  series    = {Princeton Mathematical Series},
  number    = {28},
  publisher = {Princeton University Press},
  year      = {1970}
}

@book{boyd2004convex,
  author    = {Boyd, Stephen and Vandenberghe, Lieven},
  title     = {Convex Optimization},
  publisher = {Cambridge University Press},
  year      = {2004}
}

@book{schrijver1986theory,
  author    = {Schrijver, Alexander},
  title     = {Theory of Linear and Integer Programming},
  series    = {Wiley-Interscience Series in Discrete Mathematics},
  publisher = {John Wiley \& Sons},
  year      = {1986}
}

@book{bental2001lectures,
  author    = {Ben-Tal, Aharon and Nemirovski, Arkadi},
  title     = {Lectures on Modern Convex Optimization},
  series    = {MPS-SIAM Series on Optimization},
  publisher = {SIAM},
  year      = {2001}
}

Prerequisites

02.11.02
01.01.03
01.01.05
01.01.06
01.01.18

Tier anchors

beginner: Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §2.5, §5.8 — separating hyperplanes and the geometry of alternatives
intermediate: Rockafellar 1970 Convex Analysis (Princeton) §19, §22; Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §5.8
master: Rockafellar 1970 Convex Analysis (Princeton) §22 (Helly, Farkas, the theorems of the alternative); Schrijver 1986 Theory of Linear and Integer Programming (Wiley) §7; Ben-Tal & Nemirovski 2001 Lectures on Modern Convex Optimization (SIAM) §1

References

Rockafellar, R. T. — Convex Analysis (Princeton University Press, 1970) · §19 (polyhedral convex sets); §22 (Helly's theorem, Farkas' lemma, the theorems of the alternative)
Boyd, S. & Vandenberghe, L. — Convex Optimization (Cambridge University Press, 2004) · §2.5 (separating and supporting hyperplanes); §5.8 (theorems of alternatives)
Schrijver, A. — Theory of Linear and Integer Programming (Wiley, 1986) · §7 (Fundamental theorem of linear inequalities; Farkas, Gordan, Stiemke, Motzkin)
Farkas, J. — Theorie der einfachen Ungleichungen · Journal für die reine und angewandte Mathematik 124 (1902), 1-27
Gordan, P. — Über die Auflösung linearer Gleichungen mit reellen Coefficienten · Mathematische Annalen 6 (1873), 23-28
Motzkin, T. S. — Beiträge zur Theorie der linearen Ungleichungen · Doctoral dissertation, Basel (1936)

Estimated time

beginner: 16m
intermediate: 42m
master: 72m