Self-concordant Tree and Decomposition Based Interior Point Methods for Stochastic Convex Optimization Problem

Michael Chen(michael-chennorthwestern.edu)
Sanjay Mehrotra(mehrotraiems.northwestern.edu)

Abstract: We consider barrier problems associated with two and multistage stochastic convex optimization problems. We show that the barrier recourse functions at any stage form a self-concordant family with respect to the barrier parameter. We also show that the complexity value of the first stage problem increases additively with the number of stages and scenarios. We use these results to propose a prototype primal interior point decomposition algorithm for the two-stage and multistage stochastic convex optimization problems admitting self-concordant barriers.

Keywords: Stochastic Programming; Interior Point Method; Self-concordant; Barrier; Decomposition;

Category 1: Stochastic Programming

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: Technical Report 2007-04 Department of Industrial Engineering and Management Sciences, Robert R. McCormick School of Engineering, Northwestern University, Evanston, Illinois 60208.

Download: [Postscript][Compressed Postscript][PDF]

Entry Submitted: 05/23/2007
Entry Accepted: 05/25/2007
Entry Last Modified: 05/23/2007

Modify/Update this entry