Zero duality gap certifies optimality
ProvedLinearOptimization.lp_optimal_certificatecertificatedualitylinear-programmingoptimality
(Corollary 4.2) Let and be feasible solutions to the primal and the dual, respectively, and suppose that
Then, and are optimal solutions to the primal and the dual, respectively.
Preamble
import Definitions.Def_LinearOptimization_DualLP open Matrix /-- **Bertsimas & Tsitsiklis, Corollary 4.2 (p. 148).** Feasible `x` and `p` with `p'b = c'x` are automatically optimal for the primal and the dual, respectively. -/
Formal statement
theorem LinearOptimization.lp_optimal_certificate {m n : ℕ} (P : GeneralFormLP m n)
(x : Fin n → ℝ) (hx : x ∈ generalFeasibleSet P)
(p : Fin m → ℝ) (hp : p ∈ generalFeasibleSet (dualLP P))
(heq : p ⬝ᵥ P.b = P.c ⬝ᵥ x) :
IsLpOptimal P.c (generalFeasibleSet P) x ∧
IsLpDualOptimal P.b (generalFeasibleSet (dualLP P)) p := by
sorry
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Corollary 4.2, p. 148