This paper presents stochastic decomposition (SD) algorithms for two classes of stochastic programming problems: 1) two-stage stochastic quadratic-linear programming (SQLP) in which a quadratic program defines the objective function in the first stage and a linear program defines the value function in the second stage; 2) two-stage stochastic quadratic-quadratic programming (SQQP) which has quadratic programming problems in both stages. Similar to their stochastic linear programming (SLP) predecessor, these iterative schemes in SD approximate the objective function using piecewise affine/quadratic minorants and then apply a stochastic proximal mapping to obtain the next iterate. In this paper, we show that under some assumptions, the proximal mapping applied in SD obeys a contraction mapping property even though the approximations are based on sequential random samples. Following that, we demonstrate that under those assumptions, SD can provide a sequence of solutions converging to the optimal solution with the sublinear convergence rate in both SQLP and SQQP problems. Finally, we present an ``in-sample'' stopping rule to assess the optimality gap by constructing consistent bootstrap estimators.
Article
View Asymptotic results of Stochastic Decomposition for Two-stage Stochastic Quadratic Programming