Optimization Online


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

Sanjay Mehrotra(mehrotra***at***iems.northwestern.edu)
Gokhan Ozevin(ozevin***at***northwestern.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

  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