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