An approximation scheme for stochastic programs with secondorder dominance constraints

Yongchao  Liu; Hailin   Sun; Huifu  Xu

doi:10.3934/naco.2016021

Article Contents

2016, Volume 6, Issue 4: 473-490. Doi: 10.3934/naco.2016021

This issue Previous Article Solving higher index DAE optimal control problems Next Article 2D system analysis via dual problems and polynomial matrix inequalities

An approximation scheme for stochastic programs with second order dominance constraints

1.
Department of Mathematics, Dalian Maritime University, Dalian 116026
2.
School of Economics and Management, Nanjing University of Science and Techonolyogy, Nanjing, 210049
3.
School of Mathematics, University of Southampton, SO17 1BJ, Southampton

Received: September 2015

Revised: November 2016

Published: December 2016

Abstract / Introduction Related Papers Cited by

Abstract

It is well known that second order dominance relation between two random variables can be described by a system of stochastic semi-infinite inequalities indexed by $\mathcal R$, the set of all real number. In this paper, we show the index set can be reduced to the support set of the dominated random variable strengthening a similar result established by Dentcheva and Ruszczyński [9] for discrete random variables. Viewing the semi-infinite constraints as an extreme robust risk measure, we relax it by replacing it with entropic risk measure and regarding the latter as an approximation of the former in an optimization problem with second order dominance constraints. To solve the entropic approximation problem, we apply the well known sample average approximation method to discretize it. Detailed analysis is given to quantify both the entropic approximation and sample average approximation for various statistical quantities including the optimal value, the optimal solutions and the stationary points obtained from solving the sample average approximated problem. The numerical scheme provides an alternative to the mainstream numerical methods for this important class of stochastic programs.

Keywords:

Mathematics Subject Classification: Primary: 90C15, 90C31.

Citation:

Related Papers

Cited by

References

[1]	E. Anderson, H. Xu and D. Zhang, CVaR approximations for minimax and robust convex optimization, manuscript, 2013.
[2]	R. J. Aumann, Integrals of set-valued functions, Journal of Mathematical Analysis and Applications, 12 (1965), 1-12.
[3]	J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, Springer Series in Operational Research, Springer, New York, 2000.doi: 10.1007/978-1-4612-1394-9.
[4]	G. Calafiore and M. C. Campi, Uncertain convex programs: randomized solutions and confidence levels, Mathematical Programming, 102 (2005), 25-46.doi: 10.1007/s10107-003-0499-y.
[5]	X. Chen, Smoothing methods for nonsmooth, novonvex minimization, Mathematical Programming, 134 (2012), 71-99.doi: 10.1007/s10107-012-0569-0.
[6]	F. H. Clarke, Optimization and Nonsmooth Analysis, Wiley, New York, 1983.
[7]	D. Dentcheva, R. Henrion and A. Ruszczyński, Stability and sensitivity of optimization problems with first order stochastic dominance constraints, SIAM Journal on Optimization, 18 (2007), 322-333.doi: 10.1137/060650118.
[8]	D. Dentcheva and W. Römisch, Stability and sensitivity of stochastic dominance constrained optimization models, SIAM Journal on Optimization, 23 (2013), 1672-1688.doi: 10.1137/120886790.
[9]	D. Dentcheva and A. Ruszczyński, Optimization with stochastic dominance constraints, SIAM Journal on Optimization, 14 (2003), 548-566.doi: 10.1137/S1052623402420528.
[10]	D. Dentcheva and A. Ruszczyński, Optimality and duality theory for stochastic optimization with nonlinear dominance constraints, Mathematical Programming, 99 (2004), 329-350.doi: 10.1007/s10107-003-0453-z.
[11]	Y. Ermoliev and V. Norkin, Sample average approximation method for compound stochastic optimization problems, SIAM Journal on Optimization, 23 (2013), 2231-2263.doi: 10.1137/120863277.
[12]	C. I. Fábián, G. Mitra and D.Roman, Processing second-order stochastic dominance models using cutting-plane representations, Mathematical Programming, 130 (2011), 33-57.doi: 10.1007/s10107-009-0326-1.
[13]	H. Föllmer and T. Knispel, Entropic risk measures: coherence vs. convexity, model ambiguity, and robust large deviations, Stochastics and Dynamics, 11 (2011), 333-351.doi: 10.1142/S0219493711003334.
[14]	M. Gugat, Error bounds for infinite systems of convex inequalities without Slater's condition, Mathematical Programming, 88 (2000), 255-275.doi: 10.1007/s101070050016.
[15]	C. Hess, Set-valued integration and set-valued probability theory: an overview, Handbook of measure theory, North-Holland, Amsterdam, I-II (2002), 617-673.doi: 10.1016/B978-044450263-6/50015-4.
[16]	T. Homem-de-Mello, A cutting surface method for uncertain linear programs with polyhedral stochastic dominance constraints, SIAM Journal on Optimization, 20 (2010), 1250-1273.doi: 10.1137/08074009X.
[17]	J. Hu, T. Homen-De-Mello and S. Mehrotra, Sample average approximation of stochastic dominance constrained programs, Mathematical Programming, 133 (2012), 171-201.doi: 10.1007/s10107-010-0428-9.
[18]	P. Kall, Approximation to Optimization Problems: An Elementary Review, Mathematics of Operations Research, 11 (1986), 9-18.doi: 10.1287/moor.11.1.9.
[19]	D. Klatte, On the stability of local and global optimal solutions in parametric problems of nonlinear programming, Part I: Basic results, Seminarbericht Nr. 75, Sektion Mathematik, Humboldt-Universität zu Berlin, Berlin, (1985) 1-21.
[20]	D. Klatte, A note on quantitative stability results in nonlinear optimization, Seminarbericht Nr. 90, Sektion Mathematik, Humboldt-Universität zu Berlin, Berlin, (1987), 77-86.
[21]	H. Levy, Stochastic dominance and expected utility: survey and analysis, Management Science, 38 (1992), 555-593.
[22]	G. H. Lin, M. W. Xu and J. J. Ye, On solving simple bilevel programs with a nonconvex lower level program, Mathematical Programming, 144 (2014), 277-305.doi: 10.1007/s10107-013-0633-4.
[23]	Y. Liu and H. Xu, Stability analysis of stochastic programs with second order dominance constraints, Mathematical Programming, 142 (2013), 435-460.doi: 10.1007/s10107-012-0585-0.
[24]	Y. Liu, W. Römisch and H. Xu, Quantitative stability analysis of stochastic generalized equations, SIAM Journal on Optimization, 24 (2014), 467-497.doi: 10.1137/120880434.
[25]	Y. Liu and H. Xu, Entropic approximation for mathematical programs with robust equilibrium constraints, SIAM Journal on Optimization, 24Z (2014), 933-958.doi: 10.1137/130931011.
[26]	A. Müller and M. Scarsini, Stochastic Orders and Decision Under Risk, Institute of mathematical statistics, Hayward, CA, 1991.
[27]	D. Ralph and H. Xu, Asympototic analysis of stationary points of sample average two stage stochastic programs: A generalized equation approach, Mathematics of Operations Research, 36 (2011), 568-592.doi: 10.1287/moor.1110.0506.
[28]	S. M. Robinson and R. J-B. Wets, Stability in two-stage stochastic programming, SIAM Journal on Control and Optimization, 25 (1987), 1409-1416.doi: 10.1137/0325077.
[29]	S. M. Robinson, Analysis of sample-path optimization, Mathematics of Operations Research, 21 (1996), 513-528.doi: 10.1287/moor.21.3.513.
[30]	R. T. Rockafellar and R. J-B. Wets, Variational Analysis, Springer, Berlin, 1998.doi: 10.1007/978-3-642-02431-3.
[31]	A. Ruszczyński and A. Shapiro, Stochastic Programming, Handbook in Operations Research and Management Science, Elsevier, 2003.
[32]	A. Shapiro and H. Xu, Uniform laws of large numbers for set-valued mappings and subdifferentials of random functions, Journal of Mathematical Analysis and Applications, 325 (2007), 1390-1399.doi: 10.1016/j.jmaa.2006.02.078.
[33]	H. Sun, H. Xu, R. Meskarian and Y. Wang, Exact penalization, level function method, and modified cutting-plane method for stochastic programs with second order stochastic dominance constraints, SIAM Journal on Optimization, 23 (2013), 602-631.doi: 10.1137/110850815.
[34]	H. Xu, Uniform exponential convergence of sample average random functions under general sampling with applications in stochastic programming, Journal of Mathematical Analysis and Applications, 368 (2010), 692-710.doi: 10.1016/j.jmaa.2010.03.021.
[35]	H. Xu and D. Zhang, Smooth sample average approximation of stationary points in nonsmooth stochastic optimization and applications, Mathematical Programming, 119 (2009), 371-401.doi: 10.1007/s10107-008-0214-0.
[36]	J. Zhang, H. Xu and L. W. Zhang, Quantitative stability analysis of stochastic quasi-variational inequality problems and applications, Manusicript, 2014.