Sample Average Approximation for Stochastic Dominance Constrained Programs

Jian Hu (jianhunorthwestern.edu)
Tito Homem-de-Mello (thmellouic.edu)
Sanjay Mehrotra (mehrotraiems.northwestern.edu)

Abstract: In this paper we study optimization problems with second-order stochastic dominance constraints. This class of problems has been receiving increasing attention in the literature as it allows for the modeling of optimization problems where a risk-averse decision maker wants to ensure that the solution produced by the model dominates certain benchmarks. Here we deal with the case of multi-variate stochastic dominance under general distributions and nonlinear functions. We introduce the concept of C-dominance, which generalizes some notions of multi-variate dominance found in the literature. We apply the Sample Average Approximation (SAA) method to this problem, which results in a semi-infinite program, and study asymptotic convergence of optimal values and optimal solutions, as well as the rate of convergence of the feasibility set of the resulting semi-infinite program as the sample size goes to infinity. We develop a finitely convergent method to find an epsilon-optimal solution of the SAA problem. We also give methods to construct practical statistical lower and upper bounds for the true optimal objective value.

Keywords: Stochastic Programming, Stochastic Dominance, Sample Average Approximation, Semi-infinite Programming, Convex Programming, Cutting Plane Algorithms

Category 1: Stochastic Programming

Category 2: Nonlinear Optimization

Citation: Manuscript, Department of Industrial Engineering and Management Sciences, Northwestern University

Download: [PDF]

Entry Submitted: 07/08/2009
Entry Accepted: 07/08/2009
Entry Last Modified: 10/19/2010

Modify/Update this entry