Two-Stage Stochastic Semidefinite Programming and Decomposition Based Interior Point Methods

Sanjay Mehrotra (mehrotraiems.northwestern.edu)
M. Gokhan Ozevin (ozevinnorthwestern.edu)

Abstract: We introduce two-stage stochastic semidefinite programs with recourse and present a Benders decomposition based linearly convergent interior point algorithms to solve them. This extends the results of Zhao, who showed 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 addresses implementation issues for the theoretical algorithms of this paper.

Keywords: Stochastic Programming, Semidefinite Programming, Decomposition Methods, Interior Point Methods

Category 1: Stochastic Programming

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation:

Download: [PDF]

Entry Submitted: 01/05/2005
Entry Accepted: 01/07/2005
Entry Last Modified: 01/05/2005

Modify/Update this entry