Optimization Online


Stochastic Approximation approach to Stochastic Programming

Anatoli Juditsky (Anatoli.Juditsky***at***imag.fr)
Guanghui Lan (glan***at***isye.gatech.edy)
Arkadi Nemirovski (nemirovs***at***isye.gatech.edu)
Alexander Shapiro (ashapiro***at***isye.gatech.edu)

Abstract: In this paper we consider optimization problems where the objective function is given in a form of the expectation. A basic difficulty of solving such stochastic optimization problems is that the involved multidimensional integrals (expectations) cannot be computed with high accuracy. The aim of this paper is to compare two computational approaches based on Monte Carlo sampling techniques, namely, the Stochastic Approximation (SA) and the Sample Average Approximation (SAA) methods. Both approaches, the SA and SAA methods, have a long history. Current opinion is that the SAA method can efficiently use a specific (say linear) structure of the considered problem, while the SA approach is a crude subgradient method which often performs poorly in practice. We intend to demonstrate that a properly modified SA approach can be competitive and even significantly outperform the SAA method for a certain class of convex stochastic problems. We extend the analysis to the case of convex-concave stochastic saddle point problems, and present (in our opinion highly encouraging) results of numerical experiments.

Keywords: stochastic approximation, sample average approximation method, stochastic programming, Monte-Carlo sampling, complexity, saddle point, minimax problems, mirror descent algorithms

Category 1: Convex and Nonsmooth Optimization

Category 2: Stochastic Programming


Download: [PDF]

Entry Submitted: 09/26/2007
Entry Accepted: 09/26/2007
Entry Last Modified: 10/03/2007

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 Programming Society