A geometric study of duality gaps, with applications

Citation
C. Lemarechal et A. Renaud, A geometric study of duality gaps, with applications, MATH PROGR, 90(3), 2001, pp. 399-427
Citations number
37
Categorie Soggetti
Mathematics
Journal title
MATHEMATICAL PROGRAMMING
ISSN journal
00255610 → ACNP
Volume
90
Issue
3
Year of publication
2001
Pages
399 - 427
Database
ISI
SICI code
0025-5610(200105)90:3<399:AGSODG>2.0.ZU;2-C
Abstract
Lagrangian relaxation is often an efficient tool to solve (large-scale) opt imization problems, even nonconvex. However it introduces a duality gap, wh ich should be small for the method to be really efficient. Here we make a g eometric study of the duality gap. Given a nonconvex problem, we formulate in a first part a convex problem having the same dual. This formulation inv olves a convexification in the product of the three spaces containing respe ctively the variables, the objective and the constraints. We apply our resu lts to several relaxation schemes, especially one called "Lagrangean decomp osition" in the combinatorial-optimization community, or "operator splittin g" elsewhere. We also study a specific application, highly nonlinear: the u nit-commitment problem.