Strong duality
ProvedLinearOptimization.lp_strong_dualitydualitylinear-programmingstrong-duality
(Theorem 4.4, strong duality, GOAL) If a linear programming problem has an optimal solution, so does its dual, and the respective optimal costs are equal.
Preamble
import Definitions.Def_LinearOptimization_DualLP open Matrix /-- **Bertsimas & Tsitsiklis, Theorem 4.4 (p. 148).** Strong duality, attainment form: if the general-form primal has an optimal solution `x`, then its dual has an optimal solution `p`, and the optimal costs agree: `p'b = c'x`. -/
Formal statement
theorem LinearOptimization.lp_strong_duality {m n : ℕ} (P : GeneralFormLP m n)
(x : Fin n → ℝ) (hx : IsLpOptimal P.c (generalFeasibleSet P) x) :
∃ p : Fin m → ℝ,
IsLpDualOptimal P.b (generalFeasibleSet (dualLP P)) p ∧
p ⬝ᵥ P.b = P.c ⬝ᵥ x := by
sorry
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 4.4, p. 148
Human review
Confirmed by the mission captain (proposal self-audit).