Duality gaps in nonconvex stochastic optimization

Darinka Dentcheva, Werner Römisch

Research output: Contribution to journalArticlepeer-review

25 Scopus citations

Abstract

We consider multistage stochastic optimization models containing nonconvex constraints, e.g., due to logical or integrality requirements. We study three variants of Lagrangian relaxations and of the corresponding decomposition schemes, namely, scenario, nodal and geographical decomposition. Based on convex equivalents for the Lagrangian duals, we compare the duality gaps for these decomposition schemes. The first main result states that scenario decomposition provides a smaller or equal duality gap than nodal decomposition. The second group of results concerns large stochastic optimization models with loosely coupled components. The results provide conditions implying relations between the duality gaps of geographical decomposition and the duality gaps for scenario and nodal decomposition, respectively.

Original languageEnglish
Pages (from-to)515-535
Number of pages21
JournalMathematical Programming
Volume101
Issue number3
DOIs
StatePublished - 2004

Keywords

  • Decomposition
  • Duality gap
  • Integer programming
  • Lagrangian relaxation
  • Nonconvex optimization
  • Stochastic programming

Fingerprint

Dive into the research topics of 'Duality gaps in nonconvex stochastic optimization'. Together they form a unique fingerprint.

Cite this