Strong duality with a polyhedral constraint set
ProvedLinearOptimization.lp_general_strong_duality(Theorem 4.18, Strong duality — Bertsimas & Tsitsiklis, p. 184.) With the same setup as Theorem 4.17 (primal: minimize subject to , with ; dual: maximize subject to ):
if the primal problem has an optimal solution, so does the dual, and the respective optimal costs are equal.
import Definitions.Def_Polyhedron
import Definitions.Def_LinearOptimization_LagrangeanDual
open Matrix
/-- **Bertsimas & Tsitsiklis, Theorem 4.18 (p. 184).** Strong duality for the general dual,
attainment form: if `x*` is optimal for `min c'x` over
`{y | Ay ≥ b, y ∈ P}` (`P = {y | Dy ≥ d}`), then some `p ≥ 0` maximizes
`g` over the nonnegative orthant and `g(p) = c'x*`. -/
theorem LinearOptimization.lp_general_strong_duality {m₁ m₂ n : ℕ}
(A : Matrix (Fin m₁) (Fin n) ℝ) (b : Fin m₁ → ℝ) (c : Fin n → ℝ)
(D : Matrix (Fin m₂) (Fin n) ℝ) (d : Fin m₂ → ℝ)
(xstar : Fin n → ℝ)
(hopt : IsLpOptimal c {y | b ≤ A.mulVec y ∧ y ∈ polyhedron D d} xstar) :
∃ p : Fin m₁ → ℝ, 0 ≤ p ∧
(∀ q : Fin m₁ → ℝ, 0 ≤ q →
lagrangeanObjective A b c (polyhedron D d) q ≤
lagrangeanObjective A b c (polyhedron D d) p) ∧
lagrangeanObjective A b c (polyhedron D d) p =
((c ⬝ᵥ xstar : ℝ) : EReal) := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Fix real matrices (), () and vectors . Assume is optimal for the primal problem: belongs to and for every in that set. The conclusion asserts the existence of a multiplier such that three things hold: (i) componentwise; (ii) maximizes the Lagrangean objective among nonnegative multipliers — for every , where in the extended reals (the constraint set of the inner infimum is the full continuous polyhedron , with no integrality); (iii) equals as an extended real (so in particular is finite). This packages strong duality plus dual attainment: existence of an optimal multiplier with zero duality gap, conditional on primal optimality being attained at . No rank, boundedness, or interiority hypotheses appear.
Confirmed by the mission captain (proposal self-audit).