Optimization Online


Sample Average Approximation Method for Compound Stochastic Optimization Problems

Yuri Ermoliev (ermoliev***at***iiasa.ac.at)
Vladimir Norkin (vladimir.norkin***at***gmail.com)

Abstract: The paper studies stochastic optimization (programming) problems with compound functions containing expectations and extreme values of other random functions as arguments. Compound functions arise in various applications. A typical example is a variance function of nonlinear outcomes. Other examples include stochastic minimax problems, econometric models with latent variables, and multilevel and multicriteria stochastic optimization problems. As a solution technique a sample average approximation (SAA) method (also known as statistical or empirical (sample) mean method) is used. The method consists in approximation of all expectation functions by their empirical means and solving the resulting approximate deterministic optimization problems. In stochastic optimization, this method is widely used for optimization of standard expectation functions under constraints. In this paper, SAA method is extended to general compound stochastic optimization problems. The conditions for convergence in mean, almost surely, and rate of convergence are established. The study of the convergence rate is based on properties of Rademacher averages of functional sets, concentration inequalities for bounded random functions, and the concept of uniform normalized convergence of random variables. The convergence results are applicable both for discrete and continuous stochastic optimization problems.

Keywords: Stochastic optimization; compound functions; sample average approximation; normalized convergence; uniform normalized convergence; uniform law of large numbers; concentration inequalities; Rademacher averages; rate of convergence.

Category 1: Stochastic Programming

Category 2: Applications -- Science and Engineering (Statistics )

Citation: SIAM J. OPTIM., Vol. 23, No. 4, pp. 2231–2263.


Entry Submitted: 06/30/2013
Entry Accepted: 07/01/2013
Entry Last Modified: 12/25/2013

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