An approximation scheme for stochastic programs with second order dominance constraints

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

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

Abstract
Related Papers

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 & 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). Google Scholar
[2]	R. J. Aumann, Integrals of set-valued functions,, Journal of Mathematical Analysis and Applications, 12 (1965), 1. Google Scholar
[3]	J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems,, Springer Series in Operational Research, (2000). doi: 10.1007/978-1-4612-1394-9. Google Scholar
[4]	G. Calafiore and M. C. Campi, Uncertain convex programs: randomized solutions and confidence levels,, Mathematical Programming, 102 (2005), 25. doi: 10.1007/s10107-003-0499-y. Google Scholar
[5]	X. Chen, Smoothing methods for nonsmooth, novonvex minimization,, Mathematical Programming, 134 (2012), 71. doi: 10.1007/s10107-012-0569-0. Google Scholar
[6]	F. H. Clarke, Optimization and Nonsmooth Analysis,, Wiley, (1983). Google Scholar
[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. doi: 10.1137/060650118. Google Scholar
[8]	D. Dentcheva and W. Römisch, Stability and sensitivity of stochastic dominance constrained optimization models,, SIAM Journal on Optimization, 23 (2013), 1672. doi: 10.1137/120886790. Google Scholar
[9]	D. Dentcheva and A. Ruszczyński, Optimization with stochastic dominance constraints,, SIAM Journal on Optimization, 14 (2003), 548. doi: 10.1137/S1052623402420528. Google Scholar
[10]	D. Dentcheva and A. Ruszczyński, Optimality and duality theory for stochastic optimization with nonlinear dominance constraints,, Mathematical Programming, 99 (2004), 329. doi: 10.1007/s10107-003-0453-z. Google Scholar
[11]	Y. Ermoliev and V. Norkin, Sample average approximation method for compound stochastic optimization problems,, SIAM Journal on Optimization, 23 (2013), 2231. doi: 10.1137/120863277. Google Scholar
[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. doi: 10.1007/s10107-009-0326-1. Google Scholar
[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. doi: 10.1142/S0219493711003334. Google Scholar
[14]	M. Gugat, Error bounds for infinite systems of convex inequalities without Slater's condition,, Mathematical Programming, 88 (2000), 255. doi: 10.1007/s101070050016. Google Scholar
[15]	C. Hess, Set-valued integration and set-valued probability theory: an overview,, Handbook of measure theory, I-II (2002), 617. doi: 10.1016/B978-044450263-6/50015-4. Google Scholar
[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. doi: 10.1137/08074009X. Google Scholar
[17]	J. Hu, T. Homen-De-Mello and S. Mehrotra, Sample average approximation of stochastic dominance constrained programs,, Mathematical Programming, 133 (2012), 171. doi: 10.1007/s10107-010-0428-9. Google Scholar
[18]	P. Kall, Approximation to Optimization Problems: An Elementary Review,, Mathematics of Operations Research, 11 (1986), 9. doi: 10.1287/moor.11.1.9. Google Scholar
[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, (1985), 1. Google Scholar
[20]	D. Klatte, A note on quantitative stability results in nonlinear optimization,, Seminarbericht Nr. 90, (1987), 77. Google Scholar
[21]	H. Levy, Stochastic dominance and expected utility: survey and analysis,, Management Science, 38 (1992), 555. Google Scholar
[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. doi: 10.1007/s10107-013-0633-4. Google Scholar
[23]	Y. Liu and H. Xu, Stability analysis of stochastic programs with second order dominance constraints,, Mathematical Programming, 142 (2013), 435. doi: 10.1007/s10107-012-0585-0. Google Scholar
[24]	Y. Liu, W. Römisch and H. Xu, Quantitative stability analysis of stochastic generalized equations,, SIAM Journal on Optimization, 24 (2014), 467. doi: 10.1137/120880434. Google Scholar
[25]	Y. Liu and H. Xu, Entropic approximation for mathematical programs with robust equilibrium constraints,, SIAM Journal on Optimization, 24Z (2014), 933. doi: 10.1137/130931011. Google Scholar
[26]	A. Müller and M. Scarsini, Stochastic Orders and Decision Under Risk,, Institute of mathematical statistics, (1991). Google Scholar
[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. doi: 10.1287/moor.1110.0506. Google Scholar
[28]	S. M. Robinson and R. J-B. Wets, Stability in two-stage stochastic programming,, SIAM Journal on Control and Optimization, 25 (1987), 1409. doi: 10.1137/0325077. Google Scholar
[29]	S. M. Robinson, Analysis of sample-path optimization,, Mathematics of Operations Research, 21 (1996), 513. doi: 10.1287/moor.21.3.513. Google Scholar
[30]	R. T. Rockafellar and R. J-B. Wets, Variational Analysis,, Springer, (1998). doi: 10.1007/978-3-642-02431-3. Google Scholar
[31]	A. Ruszczyński and A. Shapiro, Stochastic Programming,, Handbook in Operations Research and Management Science, (2003). Google Scholar
[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. doi: 10.1016/j.jmaa.2006.02.078. Google Scholar
[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. doi: 10.1137/110850815. Google Scholar
[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. doi: 10.1016/j.jmaa.2010.03.021. Google Scholar
[35]	H. Xu and D. Zhang, Smooth sample average approximation of stationary points in nonsmooth stochastic optimization and applications,, Mathematical Programming, 119 (2009), 371. doi: 10.1007/s10107-008-0214-0. Google Scholar
[36]	J. Zhang, H. Xu and L. W. Zhang, Quantitative stability analysis of stochastic quasi-variational inequality problems and applications,, Manusicript, (2014). Google Scholar

show all references

References:

[1]	E. Anderson, H. Xu and D. Zhang, CVaR approximations for minimax and robust convex optimization,, manuscript, (2013). Google Scholar
[2]	R. J. Aumann, Integrals of set-valued functions,, Journal of Mathematical Analysis and Applications, 12 (1965), 1. Google Scholar
[3]	J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems,, Springer Series in Operational Research, (2000). doi: 10.1007/978-1-4612-1394-9. Google Scholar
[4]	G. Calafiore and M. C. Campi, Uncertain convex programs: randomized solutions and confidence levels,, Mathematical Programming, 102 (2005), 25. doi: 10.1007/s10107-003-0499-y. Google Scholar
[5]	X. Chen, Smoothing methods for nonsmooth, novonvex minimization,, Mathematical Programming, 134 (2012), 71. doi: 10.1007/s10107-012-0569-0. Google Scholar
[6]	F. H. Clarke, Optimization and Nonsmooth Analysis,, Wiley, (1983). Google Scholar
[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. doi: 10.1137/060650118. Google Scholar
[8]	D. Dentcheva and W. Römisch, Stability and sensitivity of stochastic dominance constrained optimization models,, SIAM Journal on Optimization, 23 (2013), 1672. doi: 10.1137/120886790. Google Scholar
[9]	D. Dentcheva and A. Ruszczyński, Optimization with stochastic dominance constraints,, SIAM Journal on Optimization, 14 (2003), 548. doi: 10.1137/S1052623402420528. Google Scholar
[10]	D. Dentcheva and A. Ruszczyński, Optimality and duality theory for stochastic optimization with nonlinear dominance constraints,, Mathematical Programming, 99 (2004), 329. doi: 10.1007/s10107-003-0453-z. Google Scholar
[11]	Y. Ermoliev and V. Norkin, Sample average approximation method for compound stochastic optimization problems,, SIAM Journal on Optimization, 23 (2013), 2231. doi: 10.1137/120863277. Google Scholar
[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. doi: 10.1007/s10107-009-0326-1. Google Scholar
[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. doi: 10.1142/S0219493711003334. Google Scholar
[14]	M. Gugat, Error bounds for infinite systems of convex inequalities without Slater's condition,, Mathematical Programming, 88 (2000), 255. doi: 10.1007/s101070050016. Google Scholar
[15]	C. Hess, Set-valued integration and set-valued probability theory: an overview,, Handbook of measure theory, I-II (2002), 617. doi: 10.1016/B978-044450263-6/50015-4. Google Scholar
[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. doi: 10.1137/08074009X. Google Scholar
[17]	J. Hu, T. Homen-De-Mello and S. Mehrotra, Sample average approximation of stochastic dominance constrained programs,, Mathematical Programming, 133 (2012), 171. doi: 10.1007/s10107-010-0428-9. Google Scholar
[18]	P. Kall, Approximation to Optimization Problems: An Elementary Review,, Mathematics of Operations Research, 11 (1986), 9. doi: 10.1287/moor.11.1.9. Google Scholar
[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, (1985), 1. Google Scholar
[20]	D. Klatte, A note on quantitative stability results in nonlinear optimization,, Seminarbericht Nr. 90, (1987), 77. Google Scholar
[21]	H. Levy, Stochastic dominance and expected utility: survey and analysis,, Management Science, 38 (1992), 555. Google Scholar
[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. doi: 10.1007/s10107-013-0633-4. Google Scholar
[23]	Y. Liu and H. Xu, Stability analysis of stochastic programs with second order dominance constraints,, Mathematical Programming, 142 (2013), 435. doi: 10.1007/s10107-012-0585-0. Google Scholar
[24]	Y. Liu, W. Römisch and H. Xu, Quantitative stability analysis of stochastic generalized equations,, SIAM Journal on Optimization, 24 (2014), 467. doi: 10.1137/120880434. Google Scholar
[25]	Y. Liu and H. Xu, Entropic approximation for mathematical programs with robust equilibrium constraints,, SIAM Journal on Optimization, 24Z (2014), 933. doi: 10.1137/130931011. Google Scholar
[26]	A. Müller and M. Scarsini, Stochastic Orders and Decision Under Risk,, Institute of mathematical statistics, (1991). Google Scholar
[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. doi: 10.1287/moor.1110.0506. Google Scholar
[28]	S. M. Robinson and R. J-B. Wets, Stability in two-stage stochastic programming,, SIAM Journal on Control and Optimization, 25 (1987), 1409. doi: 10.1137/0325077. Google Scholar
[29]	S. M. Robinson, Analysis of sample-path optimization,, Mathematics of Operations Research, 21 (1996), 513. doi: 10.1287/moor.21.3.513. Google Scholar
[30]	R. T. Rockafellar and R. J-B. Wets, Variational Analysis,, Springer, (1998). doi: 10.1007/978-3-642-02431-3. Google Scholar
[31]	A. Ruszczyński and A. Shapiro, Stochastic Programming,, Handbook in Operations Research and Management Science, (2003). Google Scholar
[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. doi: 10.1016/j.jmaa.2006.02.078. Google Scholar
[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. doi: 10.1137/110850815. Google Scholar
[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. doi: 10.1016/j.jmaa.2010.03.021. Google Scholar
[35]	H. Xu and D. Zhang, Smooth sample average approximation of stationary points in nonsmooth stochastic optimization and applications,, Mathematical Programming, 119 (2009), 371. doi: 10.1007/s10107-008-0214-0. Google Scholar
[36]	J. Zhang, H. Xu and L. W. Zhang, Quantitative stability analysis of stochastic quasi-variational inequality problems and applications,, Manusicript, (2014). Google Scholar

[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 & 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 & 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 & Management Optimization, 2011, 7 (2) : 317-345. doi: 10.3934/jimo.2011.7.317
[4]	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
[5]	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 & Management Optimization, 2017, 13 (5) : 1-15. doi: 10.3934/jimo.2018198
[6]	Meng Xue, Yun Shi, Hailin Sun. Portfolio Optimization with Relaxation of Stochastic Second Order Dominance Constraints via Conditional Value at Risk. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-22. doi: 10.3934/jimo.2019071
[7]	Pablo Ochoa. Approximation schemes for non-linear second order equations on the Heisenberg group. Communications on Pure & 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 & Continuous Dynamical Systems - A, 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 & Management Optimization, 2009, 5 (4) : 697-703. doi: 10.3934/jimo.2009.5.697
[11]	Nikolai Dokuchaev. On strong causal binomial approximation for stochastic processes. Discrete & Continuous Dynamical Systems - B, 2014, 19 (6) : 1549-1562. doi: 10.3934/dcdsb.2014.19.1549
[12]	Ariadna Farrés, Àngel Jorba. On the high order approximation of the centre manifold for ODEs. Discrete & Continuous Dynamical Systems - B, 2010, 14 (3) : 977-1000. doi: 10.3934/dcdsb.2010.14.977
[13]	Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[14]	Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial & Management Optimization, 2013, 9 (1) : 171-189. doi: 10.3934/jimo.2013.9.171
[15]	Shiyun Wang, Yong-Jin Liu, Yong Jiang. A majorized penalty approach to inverse linear second order cone programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 965-976. doi: 10.3934/jimo.2014.10.965
[16]	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 & Management Optimization, 2015, 11 (4) : 1111-1125. doi: 10.3934/jimo.2015.11.1111
[17]	Mou-Hsiung Chang, Tao Pang, Moustapha Pemy. Finite difference approximation for stochastic optimal stopping problems with delays. Journal of Industrial & Management Optimization, 2008, 4 (2) : 227-246. doi: 10.3934/jimo.2008.4.227
[18]	Xiaojun Chen, Guihua Lin. CVaR-based formulation and approximation method for stochastic variational inequalities. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 35-48. doi: 10.3934/naco.2011.1.35
[19]	Yanfeng Guo, Jinqiao Duan, Donglong Li. Approximation of random invariant manifolds for a stochastic Swift-Hohenberg equation. Discrete & Continuous Dynamical Systems - S, 2016, 9 (6) : 1701-1715. doi: 10.3934/dcdss.2016071
[20]	Ralf Banisch, Carsten Hartmann. A sparse Markov chain approximation of LQ-type stochastic control problems. Mathematical Control & Related Fields, 2016, 6 (3) : 363-389. doi: 10.3934/mcrf.2016007

Impact Factor:

American Institute of Mathematical Sciences