Duality gaps in nonconvex stochastic optimization

• 成果类型: Article
• 署名作者: Dentcheva, D; Römisch, W
• 署名单位: Stevens Institute of Technology; Humboldt University of Berlin
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-003-0496-1
• 发表日期: 2004
• 页码: 515-535
• 关键词: decomposition method; lagrangian-relaxation; unit commitment; bundle methods

摘要

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.