Strong duality with a polyhedral constraint set
ProvedLinearOptimization.lp_general_strong_dualitydualitylagrangean-dualitylinear-programmingstrong-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.
Preamble
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*`. -/
Formal statement
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
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 4.18, p. 184
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.