2008-07-05Buch DOI: 10.18452/8396
Convergence Analysis of a Weighted Barrier Decomposition Algorithm for Two Stage Stochastic Programming
Mehrotra and Ozevin  computationally found that a weighted primal barrier decomposition algorithm signiﬁcantly outperforms the barrier decomposition proposed and analyzed in [11; 6; 8]. Thispaper provides a theoretical foundation for the weighted barrier decomposition algorithm (WBDA)in . Although the worst case analysis of the WBDA achieves a ﬁrst-stage iteration complexitybound that is worse than the bound shown for the decomposition algorithms of  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.
Files in this item