Weak duality
ProvedLinearOptimization.lp_weak_dualitydualitylinear-programmingweak-duality
(Theorem 4.3, weak duality) If is a feasible solution to the primal problem and is a feasible solution to the dual problem, then
Preamble
import Definitions.Def_LinearOptimization_DualLP open Matrix /-- **Bertsimas & Tsitsiklis, Theorem 4.3 (p. 146).** Weak duality for the general-form primal/dual pair: any primal-feasible `x` and dual-feasible `p` satisfy `p'b ≤ c'x`. -/
Formal statement
theorem LinearOptimization.lp_weak_duality {m n : ℕ} (P : GeneralFormLP m n)
(x : Fin n → ℝ) (hx : x ∈ generalFeasibleSet P)
(p : Fin m → ℝ) (hp : p ∈ generalFeasibleSet (dualLP P)) :
p ⬝ᵥ P.b ≤ P.c ⬝ᵥ x := by
sorry
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 4.3, p. 146