American Institute of Mathematical Sciences

Advanced
2016, 6(4): 473-490. doi: 10.3934/naco.2016021

An approximation scheme for stochastic programs with second order dominance constraints

Yongchao Liu 1, , Hailin Sun 2, and  Huifu Xu 3,

1. 

Department of Mathematics, Dalian Maritime University, Dalian 116026, China
2. 

School of Economics and Management, Nanjing University of Science and Techonolyogy, Nanjing, 210049, China
3. 

School of Mathematics, University of Southampton, SO17 1BJ, Southampton, United Kingdom

Received  September 2015 Revised  November 2016 Published  December 2016

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: Second order dominance, stochastic semiinfinite programming, sample average approximation., entropic approximation.
Mathematics Subject Classification: Primary: 90C15, 90C3.
Citation: Yongchao Liu, Hailin Sun, Huifu Xu. An approximation scheme for stochastic programs with second order dominance constraints. Numerical Algebra, Control and Optimization, 2016, 6 (4) : 473-490. doi: 10.3934/naco.2016021
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.

show all references

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.

[1]

Suxiang He, Pan Zhang, Xiao Hu, Rong Hu. A sample average approximation method based on a D-gap function for stochastic variational inequality problems. Journal of Industrial and Management Optimization, 2014, 10 (3) : 977-987. doi: 10.3934/jimo.2014.10.977
[2]

Mei Ju Luo, Yi Zeng Chen. Smoothing and sample average approximation methods for solving stochastic generalized Nash equilibrium problems. Journal of Industrial and Management Optimization, 2016, 12 (1) : 1-15. doi: 10.3934/jimo.2016.12.1
[3]

Mingzheng Wang, M. Montaz Ali, Guihua Lin. Sample average approximation method for stochastic complementarity problems with applications to supply chain supernetworks. Journal of Industrial and Management Optimization, 2011, 7 (2) : 317-345. doi: 10.3934/jimo.2011.7.317
[4]

Liu Yang, Xiaojiao Tong, Yao Xiong, Feifei Shen. A smoothing SAA algorithm for a portfolio choice model based on second-order stochastic dominance measures. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1171-1185. doi: 10.3934/jimo.2018198
[5]

Meng Xue, Yun Shi, Hailin Sun. Portfolio optimization with relaxation of stochastic second order dominance constraints via conditional value at risk. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2581-2602. doi: 10.3934/jimo.2019071
[6]

Martin Redmann, Peter Benner. Approximation and model order reduction for second order systems with Levy-noise. Conference Publications, 2015, 2015 (special) : 945-953. doi: 10.3934/proc.2015.0945
[7]

Pablo Ochoa. Approximation schemes for non-linear second order equations on the Heisenberg group. Communications on Pure and Applied Analysis, 2015, 14 (5) : 1841-1863. doi: 10.3934/cpaa.2015.14.1841
[8]

Marco Di Francesco, Simone Fagioli, Massimiliano D. Rosini. Many particle approximation of the Aw-Rascle-Zhang second order model for vehicular traffic. Mathematical Biosciences & Engineering, 2017, 14 (1) : 127-141. doi: 10.3934/mbe.2017009
[9]

Mohamed Assellaou, Olivier Bokanowski, Hasnaa Zidani. Error estimates for second order Hamilton-Jacobi-Bellman equations. Approximation of probabilistic reachable sets. Discrete and Continuous Dynamical Systems, 2015, 35 (9) : 3933-3964. doi: 10.3934/dcds.2015.35.3933
[10]

Xinmin Yang. On second order symmetric duality in nondifferentiable multiobjective programming. Journal of Industrial and Management Optimization, 2009, 5 (4) : 697-703. doi: 10.3934/jimo.2009.5.697
[11]

Nguyen Thi Hoai. Asymptotic approximation to a solution of a singularly perturbed linear-quadratic optimal control problem with second-order linear ordinary differential equation of state variable. Numerical Algebra, Control and Optimization, 2021, 11 (4) : 495-512. doi: 10.3934/naco.2020040
[12]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial and Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[13]

Ariadna Farrés, Àngel Jorba. On the high order approximation of the centre manifold for ODEs. Discrete and Continuous Dynamical Systems - B, 2010, 14 (3) : 977-1000. doi: 10.3934/dcdsb.2010.14.977
[14]

Nikolai Dokuchaev. On strong causal binomial approximation for stochastic processes. Discrete and Continuous Dynamical Systems - B, 2014, 19 (6) : 1549-1562. doi: 10.3934/dcdsb.2014.19.1549
[15]

Håkon Hoel, Gaukhar Shaimerdenova, Raúl Tempone. Multilevel Ensemble Kalman Filtering based on a sample average of independent EnKF estimators. Foundations of Data Science, 2020, 2 (4) : 351-390. doi: 10.3934/fods.2020017
[16]

Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial and Management Optimization, 2013, 9 (1) : 171-189. doi: 10.3934/jimo.2013.9.171
[17]

Shiyun Wang, Yong-Jin Liu, Yong Jiang. A majorized penalty approach to inverse linear second order cone programming problems. Journal of Industrial and Management Optimization, 2014, 10 (3) : 965-976. doi: 10.3934/jimo.2014.10.965
[18]

Xiaoni Chi, Zhongping Wan, Zijun Hao. Second order sufficient conditions for a class of bilevel programs with lower level second-order cone programming problem. Journal of Industrial and Management Optimization, 2015, 11 (4) : 1111-1125. doi: 10.3934/jimo.2015.11.1111
[19]

Vasso Anagnostopoulou. Stochastic dominance for shift-invariant measures. Discrete and Continuous Dynamical Systems, 2019, 39 (2) : 667-682. doi: 10.3934/dcds.2019027
[20]

Fabio Camilli, Francisco Silva. A semi-discrete approximation for a first order mean field game problem. Networks and Heterogeneous Media, 2012, 7 (2) : 263-277. doi: 10.3934/nhm.2012.7.263

 Impact Factor: 

Tools

Metrics

  • PDF downloads (198)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy