Optimization Online


Asymptotic results of Stochastic Decomposition for Two-stage Stochastic Quadratic Programming

Junyi Liu (junyiliu***at***usc.edu)
Suvrajeet Sen (s.sen***at***usc.edu)

Abstract: 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.

Keywords: Stochastic Programming, Convergence, Stopping Rules

Category 1: Stochastic Programming

Category 2: Convex and Nonsmooth Optimization


Download: [PDF]

Entry Submitted: 08/29/2018
Entry Accepted: 08/29/2018
Entry Last Modified: 10/15/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society