Sample average approximation method for compound stochastic optimization problems

Ermoliev YM & Norkin V (2013). Sample average approximation method for compound stochastic optimization problems. SIAM Journal on Optimization 23 (4): 2231-2263. DOI:10.1137/120863277.

Full text not available from this repository.


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.

Item Type: Article
Uncontrolled 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
Research Programs: Advanced Systems Analysis (ASA)
Bibliographic Reference: SIAM Journal on Optimization; 23(4):2231-2263 (Published online 19 November 2013)
Depositing User: IIASA Import
Date Deposited: 15 Jan 2016 08:48
Last Modified: 25 Feb 2016 08:51

Actions (login required)

View Item View Item

International Institute for Applied Systems Analysis (IIASA)
Schlossplatz 1, A-2361 Laxenburg, Austria
Phone: (+43 2236) 807 0 Fax:(+43 2236) 71 313