An approximation scheme for stochastic programs with second
order dominance constraints

Yongchao  Liu; Hailin   Sun; Huifu  Xu

doi:10.3934/naco.2016021

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

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]	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 doi: 10.3934/fods.2020017
[2]	Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296
[3]	Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020 doi: 10.3934/dcdss.2020463
[4]	Manuel Friedrich, Martin Kružík, Jan Valdman. Numerical approximation of von Kármán viscoelastic plates. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 299-319. doi: 10.3934/dcdss.2020322
[5]	Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020 doi: 10.3934/naco.2020054
[6]	Weisong Dong, Chang Li. Second order estimates for complex Hessian equations on Hermitian manifolds. Discrete & Continuous Dynamical Systems - A, 2020 doi: 10.3934/dcds.2020377
[7]	Pierluigi Colli, Gianni Gilardi, Jürgen Sprekels. Deep quench approximation and optimal control of general Cahn–Hilliard systems with fractional operators and double obstacle potentials. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 243-271. doi: 10.3934/dcdss.2020213
[8]	Shasha Hu, Yihong Xu, Yuhan Zhang. Second-Order characterizations for set-valued equilibrium problems with variable ordering structures. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020164
[9]	Shenglan Xie, Maoan Han, Peng Zhu. A posteriori error estimate of weak Galerkin fem for second order elliptic problem with mixed boundary condition. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2020340
[10]	Soniya Singh, Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of second order impulsive systems with state-dependent delay in Banach spaces. Evolution Equations & Control Theory, 2020 doi: 10.3934/eect.2020103
[11]	Shengxin Zhu, Tongxiang Gu, Xingping Liu. AIMS: Average information matrix splitting. Mathematical Foundations of Computing, 2020, 3 (4) : 301-308. doi: 10.3934/mfc.2020012
[12]	Wenqiang Zhao, Yijin Zhang. High-order Wong-Zakai approximations for non-autonomous stochastic $ p $-Laplacian equations on $ \mathbb{R}^N $. Communications on Pure & Applied Analysis, 2021, 20 (1) : 243-280. doi: 10.3934/cpaa.2020265
[13]	Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102
[14]	Zhenzhen Wang, Tianshou Zhou. Asymptotic behaviors and stochastic traveling waves in stochastic Fisher-KPP equations. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2020323
[15]	Lorenzo Zambotti. A brief and personal history of stochastic partial differential equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 471-487. doi: 10.3934/dcds.2020264
[16]	Manil T. Mohan. First order necessary conditions of optimality for the two dimensional tidal dynamics system. Mathematical Control & Related Fields, 2020 doi: 10.3934/mcrf.2020045
[17]	Jiahao Qiu, Jianjie Zhao. Maximal factors of order $ d $ of dynamical cubespaces. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 601-620. doi: 10.3934/dcds.2020278
[18]	Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115
[19]	Siyang Cai, Yongmei Cai, Xuerong Mao. A stochastic differential equation SIS epidemic model with regime switching. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2020317
[20]	Xuhui Peng, Rangrang Zhang. Approximations of stochastic 3D tamed Navier-Stokes equations. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5337-5365. doi: 10.3934/cpaa.2020241

Impact Factor:

American Institute of Mathematical Sciences

An approximation scheme for stochastic programs with second order dominance constraints

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

An approximation scheme for stochastic programs with second order dominance constraints

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors