Optimization Online


Dynamic Stochastic Approximation for Multi-stage Stochastic Optimization

Guanghui Lan (george.lan***at***isye.gatech.edu)
Zhiqiang Zhou (zzhoubrian***at***gatech.edu)

Abstract: In this paper, we consider multi-stage stochastic optimization problems with convex objectives and conic constraints at each stage. We present a new stochastic first-order method, namely the dynamic stochastic approximation (DSA) algorithm, for solving these types of stochastic optimization problems. We show that DSA can achieve an optimal ${\cal O}(1/\epsilon^4)$ rate of convergence in terms of the total number of required scenarios when applied to a three-stage stochastic optimization problem. We further show that this rate of convergence can be improved to ${\cal O}(1/\epsilon^2)$ when the objective function is strongly convex. We also discuss variants of DSA for solving more general multi-stage stochastic optimization problems with the number of stages $T > 3$. The developed DSA algorithms only need to go through the scenario tree once in order to compute an $\epsilon$-solution of the multi-stage stochastic optimization problem. To the best of our knowledge, this is the first time that stochastic approximation type methods are generalized for multi-stage stochastic optimization with $T \ge 3$.

Keywords: Stochastic approximation, multi-stage stochastic optimization, stochastic dynamic programming

Category 1: Convex and Nonsmooth Optimization

Category 2: Stochastic Programming


Download: [PDF]

Entry Submitted: 07/11/2017
Entry Accepted: 07/11/2017
Entry Last Modified: 07/11/2017

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