Farkas' lemma, cone form: membership in the cone generated by
ProvedLinearOptimization.farkas_cone_corollaryconesfarkaslinear-programming
(Corollary 4.3) Let and be given vectors and suppose that any vector that satisfies , , must also satisfy .
Then, can be expressed as a nonnegative linear combination of the vectors .
Preamble
import Mathlib.Data.Matrix.Mul import Mathlib.Data.Real.Basic open Matrix /-- **Bertsimas & Tsitsiklis, Corollary 4.3 (p. 166).** If every `p` with `p'Aᵢ ≥ 0` for all `i` also has `p'b ≥ 0`, then `b` is a nonnegative linear combination of the `Aᵢ`. -/
Formal statement
theorem LinearOptimization.farkas_cone_corollary {m n : ℕ} (A : Fin n → (Fin m → ℝ))
(b : Fin m → ℝ)
(h : ∀ p : Fin m → ℝ, (∀ i, 0 ≤ p ⬝ᵥ A i) → 0 ≤ p ⬝ᵥ b) :
∃ lam : Fin n → ℝ, (∀ i, 0 ≤ lam i) ∧ b = ∑ i, lam i • A i := by
sorry
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Corollary 4.3, p. 166
Read-back
What the Lean code literally says, in plain math · claude-fable-5
For all , a family of vectors (given as a function, not a matrix), and : if every satisfying for all also satisfies , then there exist coefficients with every and . This is a one-way implication only (no converse is asserted). All inequalities are non-strict. Edge case : the hypothesis becomes “every has ” and the conclusion becomes (the empty sum).
Human review
Confirmed by the mission captain (proposal self-audit).