A geometric study of duality gaps, with applications

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.