Self-concordance and decomposition-based interior point methods for the two-stage stochastic convex optimization problem

Michael Chen*, Sanjay Mehrotra

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

We study the two-stage stochastic convex optimization problem whose first- and second-stage feasible regions admit a self-concordant barrier. We show that the barrier recourse functions and the composite barrier functions for this problem form self-concordant families. These results are used to develop prototype primal interior point decomposition algorithms that are more suitable for a heterogeneous distributed computing environment. We show that the worst case iteration complexity of the proposed algorithms is the same as that for the short- and long-step primal interior algorithms applied to the extensive formulation of this problem. The generality of our results allows the possibility of using barriers other than the standard log-barrier in an algorithmic framework.

Original languageEnglish (US)
Pages (from-to)1667-1687
Number of pages21
JournalSIAM Journal on Optimization
Volume21
Issue number4
DOIs
StatePublished - Dec 1 2011

Keywords

  • Benders' decomposition
  • Conic programming
  • Convex programming
  • Interior point methods
  • Stochastic programming

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'Self-concordance and decomposition-based interior point methods for the two-stage stochastic convex optimization problem'. Together they form a unique fingerprint.

Cite this