TY - JOUR

T1 - Sample average approximation of stochastic dominance constrained programs

AU - Hu, Jian

AU - Homem-De-Mello, Tito

AU - Mehrotra, Sanjay

PY - 2012/6

Y1 - 2012/6

N2 - In this paper we study optimization problems with second-order stochastic dominance constraints. This class of problems 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 ε -optimal solution of the SAA problem. An important aspect of our contribution is the construction of practical statistical lower and upper bounds for the true optimal objective value. We also show that the bounds are asymptotically tight as the sample size goes to infinity.

AB - In this paper we study optimization problems with second-order stochastic dominance constraints. This class of problems 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 ε -optimal solution of the SAA problem. An important aspect of our contribution is the construction of practical statistical lower and upper bounds for the true optimal objective value. We also show that the bounds are asymptotically tight as the sample size goes to infinity.

KW - Convex programming

KW - Cutting plane algorithms

KW - Sample average approximation

KW - Semi-infinite programming

KW - Stochastic dominance

KW - Stochastic programming

UR - http://www.scopus.com/inward/record.url?scp=84862287150&partnerID=8YFLogxK

U2 - 10.1007/s10107-010-0428-9

DO - 10.1007/s10107-010-0428-9

M3 - Article

AN - SCOPUS:84862287150

SN - 0025-5610

VL - 133

SP - 171

EP - 201

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1-2

ER -