Abstract
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 \({\mathcal{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. 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aretoulis, G.N., Kalfakakou, G.P., Striagka, F.Z.: Construction material supplier selection under multiple criteria. Oper. Res. (inprint, 2009)
Atlason J., Epelman M., Henderson G.: Call center staffing with simulation and cutting plane methods. Ann. Oper. Res. 127, 333–358 (2004)
Dembo A., Zeitouni O.: Large Deviations Techniques and Applications, 2nd edn. Springer, New York (1998)
Dentcheva D., Ruszczyński A.: Optimization with stochastic dominance constraints. SIAM J. Optim. 14(2), 548–566 (2003)
Dentcheva D., Ruszczyński A.: Optimality and duality theory for stochastic optimization problems with nonlinear dominance constraints. Math. Program. 99, 329–350 (2004)
Dentcheva D., Ruszczyński A.: Portfolio optimization with stochastic dominance constraints. J. Bank. Fin. 30, 433–451 (2006)
Dentcheva D., Ruszczyński A.: Optimization with multivariate stochastic dominance constraints. Math. Program. 117, 111–127 (2009)
Dentcheva D., Henrion R., Ruszczyński A.: Stability and sensitivity of optimization problems with first order stochastic dominance constraints. SIAM J. Optim. 18(1), 322–337 (2007)
Drapkin, D., Schultz, R.: An algorithm for stochastic programs with first-order dominance constraints induced by linear recourse. Manuscript, Department of Mathematics, University of Duisburg-Essen, Duisburg, Germany (2007)
Gollmer, R., Gotzes, U., Neise, F., Schultz, R.: Risk modeling via stochastic dominance in power systems with dispersed generation. Manuscript, Department of Mathematics, University of Duisburg-Essen, Duisburg, Germany (2007)
Hiriart-Urruty J., Lemaréchal C.: Convex Analysis and Minimization Algorithms I. Springer, New York (1993)
Homem-de-Mello T., Mehrotra S.: A cutting surface method for linear programs with polyhedral stochastic dominance constraints. SIAM J. Optim. 20(3), 1250–1273 (2009)
Horst R., Pardalos P.M., Thoai N.V.: Introduction to Global Optimization. Kluwer, Boston (1995)
Hu, J., Homem-de-Mello, T., Mehrotra, S.: Multi-criterion robust and stochastic dominance-constrained models with application to budget allocation in homeland security. Manuscript, available at. http://www.optimization-online.org/DB_HTML/2010/04/2605.html (2010)
Karoui N.E., Meziou A.: Constrained optimization with respect to stochastic dominance: Application to portfolio insurance. Math. Fin. 16(1), 103–117 (2006)
Kleywegt A.J., Shapiro A., Homem-de-Mello T.: The sample average approximation method for stochastic discrete optimiztion. SIAM J. Optim. 12, 479–502 (2001)
Luedtke J.: New formulations for optimization under stochastic dominance constraints. SIAM J. Optim. 19(3), 1433–1450 (2008)
Mak W.K., Morton D.P., Wood R.K.: Monte carlo bounding techniques for determining solution quality in stochastic programs. Oper. Res. Lett. 24, 47–56 (1999)
Müller A., Stoyan D.: Comparison Methods for Stochastic Models and Risks. Wiley, Chichester (2002)
Nemirovski A., Shapiro A.: Convex approximations of chance constrained programs. SIAM J. Optim. 17, 969–996 (2006)
Nie, Y., Wu, X., Homem-de-Mello, T.: Optimal path problems with second-order stochastic dominance constraints. Manuscript, Northwestern University (2009)
O’Brien, M.: Techniques for incorporating expected value constraints into stochastic programs. PHD Dissertation, Stanford University (2000)
Prato T., Herath G.: Multiple-criteria decision analysis for integrated catchment management. Ecol. Econ. 63(2–3), 627–632 (2007)
Rockafellar R.T., Wets R.J.-B.: Variational Analysis. Springer, Berlin (1998)
Roman D., Darby-Dowman K., Mitra G.: Portfolio construction based on stochastic dominance and target return distributions. Math. Program. 108, 541–569 (2006)
Shaked M., Shanthikumar J.G.: Stochastic Orders and their Applications. Academic Press, Boston (1994)
Shapiro A.: Monte Carlo sampling methods. In: Ruszczynski, A., Shapiro, A. (eds) Handbook of Stochastic Optimization, Elsevier Science Publishers B.V, Amsterdam (2003)
Shapiro A., Dentcheva D., Ruszczyński A.: Lectures on Stochastic Programming: Modeling and Theory. SIAM, Philadelphia (2009)
Vogel S.: A stochastic approach to stability in stochastic programming. J. Comput. Appl. Math. 56, 65–96 (1994)
von Neumann J., Morgenstern O.: Theory of Games and Economic Behavior, 2nd edn. Princeton University Press, Princeton (1947)
Wang W., Ahmed S.: Sample average approximation of expected value constrained stochastic programs. Oper. Res. Lett. 36, 515–519 (2008)
Yang K., Trewn J.: Multivariate Statistical Methods in Quality Management. McGraw-Hill, New York (2004)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Hu, J., Homem-de-Mello, T. & Mehrotra, S. Sample average approximation of stochastic dominance constrained programs. Math. Program. 133, 171–201 (2012). https://doi.org/10.1007/s10107-010-0428-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-010-0428-9
Keywords
- Stochastic programming
- Stochastic dominance
- Sample average approximation
- Semi-infinite programming
- Convex programming
- Cutting plane algorithms