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.
Citation
Technical Report, 2007-07 Dept. of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL