Decomposition-based interior point methods for two-stage stochastic semidefinite programming

Sanjay Mehrotra*, M. Gökhan Özevin

*Corresponding author for this work

Research output: Contribution to journalArticle

21 Scopus citations

Abstract

We introduce two-stage stochastic semidefinite programs with recourse and present an interior point algorithm for solving these problems using Bender's decomposition. This decomposition algorithm and its analysis extend Zhao's results [Math. Program., 90 (2001), pp. 507-536] for stochastic linear programs. The convergence results are proved by showing that the logarithmic barrier associated with the recourse function of two-stage stochastic semidefinite programs with recourse is a strongly self-concordant barrier on the first stage solutions. The short-step variant of the algorithm requires O(√p + Kr ln μ0/ε) Newton iterations to follow the first stage central path from a starting value of the barrier parameter μ0 to a terminating value ε. The long-step variant requires O((p + Kr) ln μ0/ε) damped Newton iterations. The calculation of the gradient and Hessian of the recourse function and the first stage Newton direction decomposes across the second stage scenarios.

Original languageEnglish (US)
Pages (from-to)206-222
Number of pages17
JournalSIAM Journal on Optimization
Volume18
Issue number1
DOIs
StatePublished - Dec 1 2007

Keywords

  • Benders decomposition
  • Interior point methods
  • Primal methods
  • Semidefinite programming
  • Stochastic programming

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science

Fingerprint Dive into the research topics of 'Decomposition-based interior point methods for two-stage stochastic semidefinite programming'. Together they form a unique fingerprint.

  • Cite this