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
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.