Farkas' lemma in inequality form
ProvedLinearOptimization.farkas_inequality_formdualityfarkaslinear-programming
(Theorem 4.7) Suppose that the system of linear inequalities has at least one solution, and let be some scalar. Then, the following are equivalent:
- (a) every feasible solution to the system satisfies ;
- (b) there exists some such that and .
Preamble
import Mathlib.Data.Matrix.Mul import Mathlib.Data.Real.Basic open Matrix /-- **Bertsimas & Tsitsiklis, Theorem 4.7 (p. 166).** For a solvable system `Ax ≤ b` and a scalar `d`: every solution of `Ax ≤ b` satisfies `c'x ≤ d` iff some `p ≥ 0` has `p'A = c'` and `p'b ≤ d`. -/
Formal statement
theorem LinearOptimization.farkas_inequality_form {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ)
(b : Fin m → ℝ) (c : Fin n → ℝ) (d : ℝ)
(hfeas : ∃ x : Fin n → ℝ, A.mulVec x ≤ b) :
(∀ x : Fin n → ℝ, A.mulVec x ≤ b → c ⬝ᵥ x ≤ d) ↔
∃ p : Fin m → ℝ, 0 ≤ p ∧ Aᵀ.mulVec p = c ∧ p ⬝ᵥ b ≤ d := by
sorry
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 4.7, p. 166
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.