Paper Info
Title
Decomposition-Based Interior Point Methods for Two-Stage Stochastic Semidefinite Programming
Abstract
We introduce two-stage stochastic semidefinite programs with recourse and present an interior point algorithm for solving these problems using Bender’s decomposition. This decomposition algorithm and its analysis extend Zhao’s results [Math. Program., 90 (2001), pp. 507-536] for stochastic linear programs. The convergence results are proved by showing that the logarithmic barrier associated with the recourse function of two-stage stochastic semidefinite programs with recourse is a strongly self-concordant barrier on the first stage solutions. The short-step variant of the algorithm requires $O(\sqrt{p+Kr} \ln \mu^0/\epsilon)$ Newton iterations to follow the first stage central path from a starting value of the barrier parameter $\mu^0$ to a terminating value &egr;. The long-step variant requires $O((p+Kr) \ln \mu^0/\epsilon)$ damped Newton iterations. The calculation of the gradient and Hessian of the recourse function and the first stage Newton direction decomposes across the second stage scenarios.
Year
DOI
Venue
2007
10.1137/050622067
SIAM Journal on Optimization
Keywords
Field
DocType
decomposition-based interior point methods,stage solution,interior point algorithm,stage central path,newton iteration,barrier parameter,stage scenario,recourse function,two-stage stochastic semidefinite programming,decomposition algorithm,two-stage stochastic semidefinite program,stage newton direction decomposes,interior point methods,interior point method,semidefinite programming,stochastic programming,benders decomposition
Convergence (routing),Discrete mathematics,Mathematical optimization,Hessian matrix,Logarithm,Stochastic programming,Interior point method,Semidefinite programming,Benders' decomposition,Mathematics
Journal
Volume
Issue
ISSN
18
1
1052-6234
Citations 
PageRank 
References 
9
0.63
3
Authors
2
Name
Order
Citations
PageRank
Sanjay Mehrotra152177.18
M. Go¨khan O¨zevin290.63