Optimization Online


An Adaptive Sequential Sample Average Approximation Framework for Solving Two-stage Stochastic Programs

Raghu Pasupathy (raghu.pasupathy***at***gmail.com)
Yongjia Song (yjsong.pku***at***gmail.com)

Abstract: We present adaptive sequential SAA (sample average approximation) algorithms to solve large-scale two-stage stochastic linear programs. The iterative algorithm framework we propose is organized into \emph{outer} and \emph{inner} iterations as follows: during each outer iteration, a sample-path problem is implicitly generated using a sample of observations or ``scenarios," and solved only \emph{imprecisely}, to within a tolerance chosen \emph{adaptively}, by balancing the estimated statistical error against solution error. The solutions from prior iterations serve as warm starts to aid efficient solution of the (piecewise linear convex optimization) sample-path problems generated on subsequent iterations. The generated scenarios can be independent and identically distributed (iid), or dependent, as in Monte Carlo generation using Latin-hypercube sampling, antithetic variates, or quasi-Monte Carlo. We characterize the almost sure and L1-norm convergence behavior of the distance of the generated stochastic iterates to the true solution set. We also characterize the corresponding convergence rate, and a sample size schedule that results in the best possible work complexity rate; the latter rate is Monte Carlo canonical and analogous to the $\mathcal{O}(\epsilon^{-2})$ optimal complexity for non-smooth convex optimization. We report extensive numerical tests that clearly indicate favorable performance over existing methods, due primarily to the use of a sequential framework, use of optimal sample sizes, and warm starts. The framework can be stopped in finite-time to return a solution endowed with a probabilistic guarantee on quality.

Keywords: Two-stage Stochastic Programming, Sequential Sampling, Retrospective Approximation

Category 1: Stochastic Programming

Citation: Submitted for publication

Download: [PDF]

Entry Submitted: 02/12/2019
Entry Accepted: 02/12/2019
Entry Last Modified: 11/24/2020

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