Two-stage stochastic semidefinite programming and decomposition based interior point methods

Abstract

We introduce two stage stochastic semidefinite programs with recourse and present a Benders decomposition based linearly convergent interior point algorithm to solve them. This extends the results in Zhao [16] wherein it was shown that the logarithmic barrier associated with the recourse function of two-stage stochastic linear programs with recourse behaves as a strongly self-concordant barrier on the first stage solutions. In this paper we develop the necessary theory. A companion paper [8] addresses implementation issues for the theoretical algorithm of this paper.