Optimization Online


On the Implementation of Interior Point Decomposition Algorithms for Two-Stage Stochastic Conic

Sanjay Mehortra (mehrotra***at***iems.northwestern.edu)
Gokhan Ozevin (gokhan.ozevin***at***zsassociates.com)

Abstract: 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 Mehrotra and \"{Ozevin} \cite{MO04a,MO04b} and Zhao \cite{GZ01}, 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 than the theoretical algorithms analyzed in \cite{MO04a,MO04b,GZ01}. We give a method for generating a suitable starting point; 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 Markowitz portfolio selection model. The computational results show that an efficient and stable implementation of primal decomposition method is possible. These results also show that in problems with large number of scenarios adaptive addition of scenarios can yield computational savings up to $80\%$.\\

Keywords: Stochastic Programming, Conic Programming, Semidefinite Programming, Benders Decomposition, Interior Point Methods, Primal-Dual Methods

Category 1: Stochastic Programming

Category 2: Linear, Cone and Semidefinite Programming

Category 3: Applications -- OR and Management Sciences (Finance and Economics )

Citation: Industrial Engineering and Management Science Technical Report 2005-04, Northwestern University

Download: [PDF]

Entry Submitted: 10/31/2005
Entry Accepted: 10/31/2005
Entry Last Modified: 10/31/2005

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society