Duality gaps in nonconvex stochastic optimization

Preprint series: Institut für Mathematik, Humboldt-Universität zu Berlin (ISSN 0863-0976), Humboldt-Universitt zu Berlin (ISSN 0863-0976), 02-05

MSC 2000

90C15 Stochastic programming

90C11 Mixed integer programming

Abstract
We consider multistage stochastic optimization models. Logical or integrality constraints, frequently present in optimization models, limit the application of powerful convex analysis tools. Different Lagrangian relaxation schemes and the resulting decomposition approaches provide estimates of the optimal value. We formulate convex optimization models equivalent to the dual problems of the Lagrangian relaxations. Our main results compare the resulting duality gap for these decomposition schemes. Attention is paid also to programs that model large systems with loosely coupled components.