Convergence of a weighted barrier decomposition algorithm for two-stage stochastic programming with discrete support

Sanjay Mehrotra*, M. Gokhan Özevin

*Corresponding author for this work

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

Mehrotra and Özevin [SIAM J. Optim., 19 (2009), pp. 1846-1880] computationally found that a weighted primal barrier decomposition algorithm significantly outperforms the equally weighted barrier decomposition proposed and analyzed in [G. Zhao, Math. Program., 90 (2001), pp. 507-536; S. Mehrotra and M. G. Özevin, Oper. Res., 57 (2009), pp. 964-974; S. Mehrotra and M. G. Özevin, SIAM J. Optim., 18 (2007), pp. 206-222]. Here we consider a weighted barrier that allows us to analyze iteration complexity of algorithms in all of the aforementioned publications in a unified framework. In particular, we prove self-concordance parameter values for the weighted barrier and using these values give a worst-case iteration complexity bound for the weighted decomposition algorithm.

Original languageEnglish (US)
Pages (from-to)2474-2486
Number of pages13
JournalSIAM Journal on Optimization
Volume20
Issue number5
DOIs
StatePublished - Sep 2 2010

Keywords

  • Benders decomposition
  • Large scale optimization
  • Linear-quadratic programming
  • Nondifferentiable convex optimization
  • Two stage stochastic programming

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'Convergence of a weighted barrier decomposition algorithm for two-stage stochastic programming with discrete support'. Together they form a unique fingerprint.

  • Cite this