A Lagrangian duality gap that survives closed convexification

@misc{lemmata:2610.00002,
  title        = {A Lagrangian duality gap that survives closed convexification},
  author       = {Nico Pelleriti},
  howpublished = {Lemmata Repository, lemmata:2610.00002, \url{https://lemmata.iol.berlin/abs/2610.00002}},
  year         = {2026},
  url          = {https://lemmata.iol.berlin/abs/2610.00002},
  note         = {Version a9429cb9cbf5; formal statements checked in Lean 4}
}

Abstract. Lagrangian relaxation and convexification give two lower bounds for a minimization problem; Geoffrion’s theorem says they agree when the underlying integer set is finite or the integer points of a rational polyhedron. An explicit example with an irrational constraint shows that the gap can survive even closed convexification: the Lagrangian dual value is 0, while the integer, convex-hull and closed-convex-hull problems all have value 1.

Status¶

All formal results are kernel-checked with Lean v4.35.0. What “checked” means.

View the full entry → · category: Optimization