Lagrangean dual equals the LP over the convex hull of
ProvedLinearOptimization.lagrangean_dual_eq_lp_over_hull(Theorem 11.4, GOAL — Bertsimas & Tsitsiklis, p. 496, the central result of Section 11.4.) In the setting of Section 11.4 (integer program (11.5): minimize subject to , , integer, with , , , , of integer entries; ; for ; ):
the optimal value of the Lagrangean dual is equal to the optimal cost of the following linear programming problem (11.9):
where is the convex hull of the set .
import Mathlib.Analysis.Convex.Hull
import Definitions.Def_LinearOptimization_IntegerProgram
import Definitions.Def_LinearOptimization_LagrangeanDual
open Matrix
/-- **Bertsimas & Tsitsiklis, Theorem 11.4 (p. 496).** The Lagrangean dual equals the linear
program over the convex hull of `X`:
`Z_D = min {c'x | Ax ≥ b, x ∈ CH(X)}` (as `EReal` values), provided
`X = ∅` or the right-hand LP is feasible. -/
theorem LinearOptimization.lagrangean_dual_eq_lp_over_hull {m₁ m₂ n : ℕ}
(A : Matrix (Fin m₁) (Fin n) ℤ) (b : Fin m₁ → ℤ) (c : Fin n → ℤ)
(D : Matrix (Fin m₂) (Fin n) ℤ) (d : Fin m₂ → ℤ)
(hguard :
lagrangeanIntegerSet (D.map ((↑) : ℤ → ℝ)) (fun i => (d i : ℝ)) = ∅ ∨
{x : Fin n → ℝ | (fun i => (b i : ℝ)) ≤ (A.map ((↑) : ℤ → ℝ)).mulVec x ∧
x ∈ convexHull ℝ (lagrangeanIntegerSet (D.map ((↑) : ℤ → ℝ))
(fun i => (d i : ℝ)))}.Nonempty) :
lagrangeanDualValue (A.map ((↑) : ℤ → ℝ)) (fun i => (b i : ℝ))
(fun j => (c j : ℝ))
(lagrangeanIntegerSet (D.map ((↑) : ℤ → ℝ)) (fun i => (d i : ℝ))) =
lpValue (fun j => (c j : ℝ))
{x : Fin n → ℝ |
(fun i => (b i : ℝ)) ≤ (A.map ((↑) : ℤ → ℝ)).mulVec x ∧
x ∈ convexHull ℝ (lagrangeanIntegerSet (D.map ((↑) : ℤ → ℝ))
(fun i => (d i : ℝ)))} := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Fix integer data (), , , (), , cast to . Let and let , the points of the convex hull of that also satisfy the coupling constraints . Guard hypothesis (a disjunction): either , or is nonempty. Conclusion: the extended-real equality
i.e. the Lagrangean dual value (dualizing over the integer set with componentwise-nonnegative multipliers ) equals the value of the linear program minimizing over . Degenerate reading: when , every inner infimum is , so the left side is , and makes the right side as well. The guard excludes only the case " but "; both sides may be . Equality is asserted, not just an inequality.
Confirmed by the mission captain (proposal self-audit).