On the implementation of interior point decomposition algorithms for two-stage stochastic conic programs

Sanjay Mehrotra*, M. Gökhan Özevin

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


In this paper we develop a practical primal interior decomposition algorithm for two-stage stochastic programming problems. The framework of this algorithm is similar to the framework in [S. Mehrotra and M. G. Özevin, "Decomposition based interior point methods for twostage stochastic convex quadratic programs with recourse," to appear in Oper. Res.; S. Mehrotra and M. G. Öevin, SIAM J. Optim., 18 (2007), pp. 206-222] and [G. Zhao, Math. Program., 90 (2001), pp. 507-536], however, their algorithm is altered in a simple yet fundamental way to achieve practical performance. In particular, this new algorithm weighs the log-barrier terms in the second stage problems differently from the theoretical algorithms analyzed in [S. Mehrotra and M. G. Özevin, Oper. Res., to appear], [S. Mehrotra and M. G. Özevin, SIAM J. Optim., 18 (2007), pp. 206-222], and [G. Zhao, Math. Program., 90 (2001), pp. 507-536]. We give a method for generating a suitable starting point; a method for selecting a good starting barrier parameter; a heuristic for first stage step-length calculation without performing line searches; and a method for adaptive addition of new scenarios over the course of the algorithm. The decomposition algorithm is implemented to solve two-stage stochastic conic programs with recourse whose underlying cones are Cartesian products of linear, second order, and semidefinite cones. The performance of primal decomposition method is studied on a set of randomly generated test problems as well as a two-stage stochastic programming extension of the Markowitz portfolio selection model. The computational results show that an efficient and stable implementation of the primal decomposition method is possible. These results also show that in problems with a large number of scenarios, the adaptive addition of scenarios can yield computational savings of up to 80%.

Original languageEnglish (US)
Pages (from-to)1846-1880
Number of pages35
JournalSIAM Journal on Optimization
Issue number4
StatePublished - 2008


  • Benders decomposition
  • Conic programming
  • Interior point methods
  • Primal-dual methods
  • Semidefinite programming
  • Stochastic programming

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science


Dive into the research topics of 'On the implementation of interior point decomposition algorithms for two-stage stochastic conic programs'. Together they form a unique fingerprint.

Cite this