Zero duality gap certifies optimality
ProvedLinearOptimization.lp_optimal_certificate(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.
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. -/
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
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Here a general-form linear program with rows and variables ( arbitrary natural numbers) is a data record consisting of an real matrix , vectors and , a relation symbol from attached to each row , and a sign restriction from {nonnegative, nonpositive, free} attached to each variable . A point is feasible for iff for every row the number (dot product of row with ) stands in that row's relation to (, , or ), and every coordinate obeys its sign restriction (, , or unrestricted). The dual of is again a general-form LP: matrix ( rows, variables), right-hand side , cost vector ; its row carries relation / / according as variable of is nonnegative / nonpositive / free, and its variable is nonnegative / nonpositive / free according as row of has relation / / . Unwinding, is dual-feasible iff for every : when variable of is nonnegative, when nonpositive, when free (the row constraint of the dual literally reads ); and for every : when row of is a -row, when a -row, unrestricted when an -row. Here “ is primal-optimal” means: is feasible for and for every feasible (a global minimizer of the primal objective), and “ is dual-optimal” means: is dual-feasible and for every dual-feasible (a global maximizer of ). The theorem asserts: for every general-form LP , every primal-feasible , and every dual-feasible , if (exact equality of objective values) then is primal-optimal and is dual-optimal. This is a one-way implication from the equality certificate to the pair of optimality claims; no converse is asserted.
Confirmed by the mission captain (proposal self-audit).