Farkas' lemma
ProvedLinearOptimization.farkas_lemmadualityfarkaslinear-programming
(Theorem 4.6, Farkas' lemma — GOAL) Let be a matrix of dimensions and let be a vector in . Then, exactly one of the following two alternatives holds:
- (a) there exists some such that ;
- (b) there exists some vector such that and .
Preamble
import Mathlib.Data.Matrix.Mul import Mathlib.Data.Real.Basic open Matrix /-- **Bertsimas & Tsitsiklis, Theorem 4.6 (p. 165).** Farkas' lemma: exactly one of (a) `∃ x ≥ 0, Ax = b` and (b) `∃ p, p'A ≥ 0' ∧ p'b < 0` holds. -/
Formal statement
theorem LinearOptimization.farkas_lemma {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ)
(b : Fin m → ℝ) :
Xor' (∃ x : Fin n → ℝ, 0 ≤ x ∧ A.mulVec x = b)
(∃ p : Fin m → ℝ, 0 ≤ Aᵀ.mulVec p ∧ p ⬝ᵥ b < 0) := by
sorry
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 4.6, p. 165
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Farkas alternative, exclusive form. For all , every real matrix , and every , exactly one of the following two alternatives holds (the statement is an exclusive-or: one alternative is true and the other is false): (I) there exists with componentwise and ; (II) there exists with componentwise (i.e. for every column ) and (strict). Degenerate cases are covered by the same claim: e.g. for alternative (I) reduces to , and for alternative (II) is unsatisfiable since is an empty sum .
Human review
Confirmed by the mission captain (proposal self-audit).