Strong duality
ProvedLinearOptimization.lp_strong_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.
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`. -/
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
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 , every general-form LP , and every that is primal-optimal (feasible with for all feasible — so the hypothesis presupposes that the primal minimum is attained at ), there exists that is dual-optimal and satisfies . In particular the conclusion entails that the dual feasible set is nonempty and the dual maximum is attained. Nothing is asserted for programs whose primal optimum is not attained (e.g. infeasible or unbounded primal): the statement is then vacuous.
Confirmed by the mission captain (proposal self-audit).