Mehrotra and Özevin [SIAM J. Optim., 19 (2009), pp. 1846-1880] computationally found that a weighted primal barrier decomposition algorithm significantly outperforms the equally weighted barrier decomposition proposed and analyzed in [G. Zhao, Math. Program., 90 (2001), pp. 507-536; S. Mehrotra and M. G. Özevin, Oper. Res., 57 (2009), pp. 964-974; S. Mehrotra and M. G. Özevin, SIAM J. Optim., 18 (2007), pp. 206-222]. Here we consider a weighted barrier that allows us to analyze iteration complexity of algorithms in all of the aforementioned publications in a unified framework. In particular, we prove self-concordance parameter values for the weighted barrier and using these values give a worst-case iteration complexity bound for the weighted decomposition algorithm.
- Benders decomposition
- Large scale optimization
- Linear-quadratic programming
- Nondifferentiable convex optimization
- Two stage stochastic programming
ASJC Scopus subject areas
- Theoretical Computer Science