# American Institute of Mathematical Sciences

doi: 10.3934/jimo.2021132
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

## Relaxation schemes for the joint linear chance constraint based on probability inequalities

 1 School of Mathematics, Shanghai University of Finance and Economics, Shanghai 200433, China 2 Department of Applied Mathematics, The Hong Kong Polytechnic University, Hong Kong, China

* Corresponding author: Shisen Liu

Received  November 2020 Revised  April 2021 Early access August 2021

This paper is concerned with the joint chance constraint for a system of linear inequalities. We discuss computationally tractble relaxations of this constraint based on various probability inequalities, including Chebyshev inequality, Petrov exponential inequalities, and others. Under the linear decision rule and additional assumptions about first and second order moments of the random vector, we establish several upper bounds for a single chance constraint. This approach is then extended to handle the joint linear constraint. It is shown that the relaxed constraints are second-order cone representable. Numerical test results are presented and the problem of how to choose proper probability inequalities is discussed.

Citation: Yanjun Wang, Shisen Liu. Relaxation schemes for the joint linear chance constraint based on probability inequalities. Journal of Industrial and Management Optimization, doi: 10.3934/jimo.2021132
##### References:
 [1] R. Ahlswede and A. Winter, Strong converse for identification via quantum channels, IEEE Transactions on Information Theory, 48 (2002), 569-579.  doi: 10.1109/18.985947. [2] S. Ahmed and W. Xie, Relaxations and approximations of chance constraints under finite distributions, Math. Program., 170 (2018), 43-65.  doi: 10.1007/s10107-018-1295-z. [3] X. Bai, J. Sun and X. Zheng, An augmented Lagrangian decomposition method for chance-constrained optimization problems, INFORMS Journal on Computing, (2020). doi: 10.1287/ijoc.2020.1001. [4] A. Ben-Tal and A. Nemirovski, Robust solutions of uncertain linear programs, Oper. Res. Lett., 25 (1999), 1-13.  doi: 10.1016/S0167-6377(99)00016-4. [5] A. Ben-Tal and A. Nemirovski, On safe tractable approximations of chance-constrained linear matrix inequalities, Math. Oper. Res., 34 (2009), 1-25.  doi: 10.1287/moor.1080.0352. [6] D. Bertsimas and V. Goyal, On the approximability of adjustable robust convex optimization under uncertainty, Math. Methods Oper. Res., 77 (2013), 323-343.  doi: 10.1007/s00186-012-0405-6. [7] W. Chen, M. Sim, J. Sun and C.-P. Teo, From CVaR to uncertainty set: Implications in joint chance-constrained optimization, Oper. Res., 58 (2010), 470-485.  doi: 10.1287/opre.1090.0712. [8] X. Chen, M. Sim and P. Sun, A robust optimization perspective on stochastic programming, Oper. Res., 55 (2007), 1058-1071.  doi: 10.1287/opre.1070.0441. [9] Z. Chen, M. Sim and H. Xu, Distributionally robust optimization with infinitely constrained ambiguity sets, Oper. Res., 67 (2019), 1328-1344.  doi: 10.1287/opre.2018.1799. [10] S.-S. Cheung, A. M.-C. So and K. Wang, Linear matrix inequalities with stochastically dependent perturbations and applications to chance-constrained semidefinite optimization, SIAM J. Optim., 22 (2012), 1394-1430.  doi: 10.1137/110822906. [11] V. Feldman, C. Guzmán and S. Vempala, Statistical query algorithms for mean vector estimation and stochastic convex optimization, Mathematics of Operations Research, (2021). doi: 10.1287/moor.2020.1111. [12] R. Gao and A.J. Kleywegt, Distributionally robust stochastic optimization with Wasserstein distance, arXiv preprint, arXiv: 1604.02199. [13] S. Guo, H. Xu and L. Zhang, Convergence analysis for mathematical programs with distributionally robust chance constraint, SIAM J. Optim., 27 (2017), 784-816.  doi: 10.1137/15M1036592. [14] L. J. Hong, Y. Yang and L. Zhang, Sequential convex approximations to joint chance constrained programs: A Monte Carlo approach, Oper. Res., 59 (2011), 617-630.  doi: 10.1287/opre.1100.0910. [15] R. Jiang and Y. Guan, Data-driven chance constrained stochastic program, Math. Program., 158 (2016), 291-327.  doi: 10.1007/s10107-015-0929-7. [16] Z. Lin and Z. Bai, Probability Inequalities, Springer Science and Business Media, 2011. [17] P. Mohajerin Esfahani and D. Kuhn, Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations, Math. Program., 171 (2018), 115-166.  doi: 10.1007/s10107-017-1172-1. [18] A. Nemirovski and A. Shapiro, Convex approximations of chance constrained programs, SIAM J. Optim., 17 (2006), 969-996.  doi: 10.1137/050622328. [19] B. K. Pagnoncelli, S. Ahmed and A. Shapiro, Sample average approximation method for chance constrained programming: Theory and applications, J. Optim. Theory Appl., 142 (2009), 399-416.  doi: 10.1007/s10957-009-9523-6. [20] I. Popescu, Robust mean-covariance solutions for stochastic optimization, Oper. Res., 55 (2007), 98-112.  doi: 10.1287/opre.1060.0353. [21] K. Postek, A. Ben-Tal, D. den Hertog and B. Melenberg, Robust optimization with ambiguous stochastic constraints under mean and dispersion information, Oper. Res., 66 (2018), 814-833.  doi: 10.1287/opre.2017.1688. [22] R. T. Rockafellar and R. J.-B. Wets, Scenarios and policy aggregation in optimization under uncertainty, Math. Oper. Res., 16 (1991), 119-147.  doi: 10.1287/moor.16.1.119. [23] G. Salvendy (Ed.), Handbook of Industrial Engineering: Technology and Operations Management, John Wiley and Sons, 2001. [24] J. E. Smith, Generalized Chebychev inequalities: Theory and applications in decision analysis, Oper. Res., 43 (1995), 807-825.  doi: 10.1287/opre.43.5.807. [25] W. Xie and S. Ahmed, Bicriteria approximation of chance-constrained covering problems, Oper. Res., 68 (2020), 516-533.  doi: 10.1287/opre.2019.1866. [26] W. Xie, S. Ahmed and R. Jiang, Optimized Bonferroni approximations of distributionally robust joint chance constraints, Mathematical Programming, (2019), 1–34. [27] W. Yang and H. Xu, Strong converse for identification via quantum channels, Math. Program., 155 (2016), 231-265.  doi: 10.1007/s10107-014-0842-5. [28] M. Zaghian, G.J. Lim and A. Khabazian, A chance-constrained programming framework to handle uncertainties in radiation therapy treatment planning, European J. Oper. Res., 266 (2018), 736-745.  doi: 10.1016/j.ejor.2017.10.018. [29] Y. Zhao, W. Zhang, W. Guo, S. Yu and F. Song, Exponential state observers for nonlinear systems with incremental quadratic constraints and output nonlinearities, Journal of Control, Automation and Electrical Systems, 29 (2018), 127-135.  doi: 10.1007/s40313-018-0369-8.

show all references

##### References:
 [1] R. Ahlswede and A. Winter, Strong converse for identification via quantum channels, IEEE Transactions on Information Theory, 48 (2002), 569-579.  doi: 10.1109/18.985947. [2] S. Ahmed and W. Xie, Relaxations and approximations of chance constraints under finite distributions, Math. Program., 170 (2018), 43-65.  doi: 10.1007/s10107-018-1295-z. [3] X. Bai, J. Sun and X. Zheng, An augmented Lagrangian decomposition method for chance-constrained optimization problems, INFORMS Journal on Computing, (2020). doi: 10.1287/ijoc.2020.1001. [4] A. Ben-Tal and A. Nemirovski, Robust solutions of uncertain linear programs, Oper. Res. Lett., 25 (1999), 1-13.  doi: 10.1016/S0167-6377(99)00016-4. [5] A. Ben-Tal and A. Nemirovski, On safe tractable approximations of chance-constrained linear matrix inequalities, Math. Oper. Res., 34 (2009), 1-25.  doi: 10.1287/moor.1080.0352. [6] D. Bertsimas and V. Goyal, On the approximability of adjustable robust convex optimization under uncertainty, Math. Methods Oper. Res., 77 (2013), 323-343.  doi: 10.1007/s00186-012-0405-6. [7] W. Chen, M. Sim, J. Sun and C.-P. Teo, From CVaR to uncertainty set: Implications in joint chance-constrained optimization, Oper. Res., 58 (2010), 470-485.  doi: 10.1287/opre.1090.0712. [8] X. Chen, M. Sim and P. Sun, A robust optimization perspective on stochastic programming, Oper. Res., 55 (2007), 1058-1071.  doi: 10.1287/opre.1070.0441. [9] Z. Chen, M. Sim and H. Xu, Distributionally robust optimization with infinitely constrained ambiguity sets, Oper. Res., 67 (2019), 1328-1344.  doi: 10.1287/opre.2018.1799. [10] S.-S. Cheung, A. M.-C. So and K. Wang, Linear matrix inequalities with stochastically dependent perturbations and applications to chance-constrained semidefinite optimization, SIAM J. Optim., 22 (2012), 1394-1430.  doi: 10.1137/110822906. [11] V. Feldman, C. Guzmán and S. Vempala, Statistical query algorithms for mean vector estimation and stochastic convex optimization, Mathematics of Operations Research, (2021). doi: 10.1287/moor.2020.1111. [12] R. Gao and A.J. Kleywegt, Distributionally robust stochastic optimization with Wasserstein distance, arXiv preprint, arXiv: 1604.02199. [13] S. Guo, H. Xu and L. Zhang, Convergence analysis for mathematical programs with distributionally robust chance constraint, SIAM J. Optim., 27 (2017), 784-816.  doi: 10.1137/15M1036592. [14] L. J. Hong, Y. Yang and L. Zhang, Sequential convex approximations to joint chance constrained programs: A Monte Carlo approach, Oper. Res., 59 (2011), 617-630.  doi: 10.1287/opre.1100.0910. [15] R. Jiang and Y. Guan, Data-driven chance constrained stochastic program, Math. Program., 158 (2016), 291-327.  doi: 10.1007/s10107-015-0929-7. [16] Z. Lin and Z. Bai, Probability Inequalities, Springer Science and Business Media, 2011. [17] P. Mohajerin Esfahani and D. Kuhn, Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations, Math. Program., 171 (2018), 115-166.  doi: 10.1007/s10107-017-1172-1. [18] A. Nemirovski and A. Shapiro, Convex approximations of chance constrained programs, SIAM J. Optim., 17 (2006), 969-996.  doi: 10.1137/050622328. [19] B. K. Pagnoncelli, S. Ahmed and A. Shapiro, Sample average approximation method for chance constrained programming: Theory and applications, J. Optim. Theory Appl., 142 (2009), 399-416.  doi: 10.1007/s10957-009-9523-6. [20] I. Popescu, Robust mean-covariance solutions for stochastic optimization, Oper. Res., 55 (2007), 98-112.  doi: 10.1287/opre.1060.0353. [21] K. Postek, A. Ben-Tal, D. den Hertog and B. Melenberg, Robust optimization with ambiguous stochastic constraints under mean and dispersion information, Oper. Res., 66 (2018), 814-833.  doi: 10.1287/opre.2017.1688. [22] R. T. Rockafellar and R. J.-B. Wets, Scenarios and policy aggregation in optimization under uncertainty, Math. Oper. Res., 16 (1991), 119-147.  doi: 10.1287/moor.16.1.119. [23] G. Salvendy (Ed.), Handbook of Industrial Engineering: Technology and Operations Management, John Wiley and Sons, 2001. [24] J. E. Smith, Generalized Chebychev inequalities: Theory and applications in decision analysis, Oper. Res., 43 (1995), 807-825.  doi: 10.1287/opre.43.5.807. [25] W. Xie and S. Ahmed, Bicriteria approximation of chance-constrained covering problems, Oper. Res., 68 (2020), 516-533.  doi: 10.1287/opre.2019.1866. [26] W. Xie, S. Ahmed and R. Jiang, Optimized Bonferroni approximations of distributionally robust joint chance constraints, Mathematical Programming, (2019), 1–34. [27] W. Yang and H. Xu, Strong converse for identification via quantum channels, Math. Program., 155 (2016), 231-265.  doi: 10.1007/s10107-014-0842-5. [28] M. Zaghian, G.J. Lim and A. Khabazian, A chance-constrained programming framework to handle uncertainties in radiation therapy treatment planning, European J. Oper. Res., 266 (2018), 736-745.  doi: 10.1016/j.ejor.2017.10.018. [29] Y. Zhao, W. Zhang, W. Guo, S. Yu and F. Song, Exponential state observers for nonlinear systems with incremental quadratic constraints and output nonlinearities, Journal of Control, Automation and Electrical Systems, 29 (2018), 127-135.  doi: 10.1007/s40313-018-0369-8.
Changes of the optimal value in single chance constrained program
Changes of the optimal value in joint chance constrained program
Comparison of different probability inequalities under 0.05 confidence level}
 Inequality Type $\mathbb{E}$($\xi_1, \xi_2$) Var($\xi_1, \xi_2$) bound($\xi_1, \xi_2$) $x^*$ optimal value Chebyshev (0, 0) ($0.1^2, 0.2^2$) - $(0.2627, -0.5084)^T$ 0.7634 Petrov (0, 0) ($0.1^2, 0.2^2$) $[\pm0.3], [\pm0.3]$ $(0.2510, -0.5528)^T$ 0.7287 Hoeffding (0, 0) - $[\pm0.3], [\pm0.3]$ $(0.2040, -0.6678)^T$ 0.6584
 Inequality Type $\mathbb{E}$($\xi_1, \xi_2$) Var($\xi_1, \xi_2$) bound($\xi_1, \xi_2$) $x^*$ optimal value Chebyshev (0, 0) ($0.1^2, 0.2^2$) - $(0.2627, -0.5084)^T$ 0.7634 Petrov (0, 0) ($0.1^2, 0.2^2$) $[\pm0.3], [\pm0.3]$ $(0.2510, -0.5528)^T$ 0.7287 Hoeffding (0, 0) - $[\pm0.3], [\pm0.3]$ $(0.2040, -0.6678)^T$ 0.6584
Comparison of different probability inequalities under 0.05 confidence level}
 Inequality Type $\mathbb{E}$($\xi_1, \xi_2$) Var($\xi_1, \xi_2$) bound($\xi_1, \xi_2$) $x^*$ optimization value Chebyshev (0, 0) ($0.1^2, 0.2^2$) - $(0.0584, -0.1573)^T$ 1.3251 Petrov (0, 0) ($0.1^2, 0.2^2$) $[\pm0.3], [\pm0.3]$ $(-0.1472, -0.5511)^T$ 1.1078 Hoeffding (0, 0) - $[\pm0.3], [\pm0.3]$ $(-0.0824, -0.8908)^T$ 0.7459
 Inequality Type $\mathbb{E}$($\xi_1, \xi_2$) Var($\xi_1, \xi_2$) bound($\xi_1, \xi_2$) $x^*$ optimization value Chebyshev (0, 0) ($0.1^2, 0.2^2$) - $(0.0584, -0.1573)^T$ 1.3251 Petrov (0, 0) ($0.1^2, 0.2^2$) $[\pm0.3], [\pm0.3]$ $(-0.1472, -0.5511)^T$ 1.1078 Hoeffding (0, 0) - $[\pm0.3], [\pm0.3]$ $(-0.0824, -0.8908)^T$ 0.7459
 [1] Jianxun Liu, Shengjie Li, Yingrang Xu. Quantitative stability of the ERM formulation for a class of stochastic linear variational inequalities. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021083 [2] Rong Hu, Ya-Ping Fang, Nan-Jing Huang. Levitin-Polyak well-posedness for variational inequalities and for optimization problems with variational inequality constraints. Journal of Industrial and Management Optimization, 2010, 6 (3) : 465-481. doi: 10.3934/jimo.2010.6.465 [3] Stanisław Migórski, Yi-bin Xiao, Jing Zhao. Fully history-dependent evolution hemivariational inequalities with constraints. Evolution Equations and Control Theory, 2020, 9 (4) : 1089-1114. doi: 10.3934/eect.2020047 [4] Mohammad Safdari. The regularity of some vector-valued variational inequalities with gradient constraints. Communications on Pure and Applied Analysis, 2018, 17 (2) : 413-428. doi: 10.3934/cpaa.2018023 [5] Masahiro Kubo, Noriaki Yamazaki. Elliptic-parabolic variational inequalities with time-dependent constraints. Discrete and Continuous Dynamical Systems, 2007, 19 (2) : 335-359. doi: 10.3934/dcds.2007.19.335 [6] Yu Chen, Yonggang Li, Bei Sun, Chunhua Yang, Hongqiu Zhu. Multi-objective chance-constrained blending optimization of zinc smelter under stochastic uncertainty. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021169 [7] Philippe Ciarlet. Korn's inequalities: The linear vs. the nonlinear case. Discrete and Continuous Dynamical Systems - S, 2012, 5 (3) : 473-483. doi: 10.3934/dcdss.2012.5.473 [8] Xiaojun Chen, Guihua Lin. CVaR-based formulation and approximation method for stochastic variational inequalities. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 35-48. doi: 10.3934/naco.2011.1.35 [9] Xiantao Xiao, Jian Gu, Liwei Zhang, Shaowu Zhang. A sequential convex program method to DC program with joint chance constraints. Journal of Industrial and Management Optimization, 2012, 8 (3) : 733-747. doi: 10.3934/jimo.2012.8.733 [10] Jean Dolbeault, Maria J. Esteban, Michał Kowalczyk, Michael Loss. Improved interpolation inequalities on the sphere. Discrete and Continuous Dynamical Systems - S, 2014, 7 (4) : 695-724. doi: 10.3934/dcdss.2014.7.695 [11] Jean Dolbeault, Maria J. Esteban, Gaspard Jankowiak. Onofri inequalities and rigidity results. Discrete and Continuous Dynamical Systems, 2017, 37 (6) : 3059-3078. doi: 10.3934/dcds.2017131 [12] Jochen Merker. Generalizations of logarithmic Sobolev inequalities. Discrete and Continuous Dynamical Systems - S, 2008, 1 (2) : 329-338. doi: 10.3934/dcdss.2008.1.329 [13] Francis Akutsah, Akindele Adebayo Mebawondu, Hammed Anuoluwapo Abass, Ojen Kumar Narain. A self adaptive method for solving a class of bilevel variational inequalities with split variational inequality and composed fixed point problem constraints in Hilbert spaces. Numerical Algebra, Control and Optimization, 2021  doi: 10.3934/naco.2021046 [14] Bin Zhou, Hailin Sun. Two-stage stochastic variational inequalities for Cournot-Nash equilibrium with risk-averse players under uncertainty. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 521-535. doi: 10.3934/naco.2020049 [15] Yuan Tan, Qingyuan Cao, Lan Li, Tianshi Hu, Min Su. A chance-constrained stochastic model predictive control problem with disturbance feedback. Journal of Industrial and Management Optimization, 2021, 17 (1) : 67-79. doi: 10.3934/jimo.2019099 [16] V. V. Zhikov, S. E. Pastukhova. Korn inequalities on thin periodic structures. Networks and Heterogeneous Media, 2009, 4 (1) : 153-175. doi: 10.3934/nhm.2009.4.153 [17] Barbara Brandolini, Francesco Chiacchio, Cristina Trombetti. Hardy type inequalities and Gaussian measure. Communications on Pure and Applied Analysis, 2007, 6 (2) : 411-428. doi: 10.3934/cpaa.2007.6.411 [18] Friedemann Brock, Francesco Chiacchio, Giuseppina di Blasio. Optimal Szegö-Weinberger type inequalities. Communications on Pure and Applied Analysis, 2016, 15 (2) : 367-383. doi: 10.3934/cpaa.2016.15.367 [19] Hongxia Yin. An iterative method for general variational inequalities. Journal of Industrial and Management Optimization, 2005, 1 (2) : 201-209. doi: 10.3934/jimo.2005.1.201 [20] Xiaoli Chen, Jianfu Yang. Improved Sobolev inequalities and critical problems. Communications on Pure and Applied Analysis, 2020, 19 (7) : 3673-3695. doi: 10.3934/cpaa.2020162

2020 Impact Factor: 1.801

## Tools

Article outline

Figures and Tables