Convergence Analysis of a Weighted Barrier Decomposition Algorithm for Two Stage Stochastic Programming

Sanjay Mehrotra(mehrotraiems.northwestern.edu)
Gokhan Ozevin(ozevinnorthwestern.edu)

Abstract: Mehrotra and Ozevin computationally found that a weighted primal barrier decomposition algorithm significantly outperforms the barrier decomposition proposed and analyzed in Zhao, and Mehrotra and Ozevin. This paper provides a theoretical foundation for the weighted barrier decomposition algorithm (WBDA). Although the worst case analysis of the WBDA achieves a first-stage iteration complexity bound that is worse than the bound shown for the decomposition algorithms of Zhao and Mehrotra and Ozevin, under a probabilistic assumption we show that the worst case iteration complexity of WBDA is independent of the number of scenarios in the problem. The probabilistic assumption uses a novel concept of self-concordant random variables.

Keywords: Two stage Stochastic Programming, linear-quadratic programming, Bender’s decomposition

Category 1: Stochastic Programming

Category 2: Linear, Cone and Semidefinite Programming

Citation: Technical Report, 2007-07 Dept. of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL

Download: [PDF]

Entry Submitted: 02/15/2008
Entry Accepted: 02/16/2008
Entry Last Modified: 02/15/2008

Modify/Update this entry