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

Abstract

Mehrotra and Ozevin [7] computationally found that a weighted primal barrier decomposition algorithm significantly outperforms the barrier decomposition proposed and analyzed in [11; 6; 8]. Thispaper provides a theoretical foundation for the weighted barrier decomposition algorithm (WBDA)in [7]. Although the worst case analysis of the WBDA achieves a first-stage iteration complexitybound that is worse than the bound shown for the decomposition algorithms of [11] and [6; 8],under a probabilistic assumption we show that the worst case iteration complexity of WBDA isindependent of the number of scenarios in the problem. The probabilistic assumption uses a novelconcept of self-concordant random variables.