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 & 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

W. ChenM. SimJ. 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.  Google Scholar

[8]

X. ChenM. Sim and P. Sun, A robust optimization perspective on stochastic programming, Oper. Res., 55 (2007), 1058-1071.  doi: 10.1287/opre.1070.0441.  Google Scholar

[9]

Z. ChenM. Sim and H. Xu, Distributionally robust optimization with infinitely constrained ambiguity sets, Oper. Res., 67 (2019), 1328-1344.  doi: 10.1287/opre.2018.1799.  Google Scholar

[10]

S.-S. CheungA. 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.  Google Scholar

[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.  Google Scholar

[12]

R. Gao and A.J. Kleywegt, Distributionally robust stochastic optimization with Wasserstein distance, arXiv preprint, arXiv: 1604.02199. Google Scholar

[13]

S. GuoH. 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.  Google Scholar

[14]

L. J. HongY. 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.  Google Scholar

[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.  Google Scholar

[16]

Z. Lin and Z. Bai, Probability Inequalities, Springer Science and Business Media, 2011. Google Scholar

[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.  Google Scholar

[18]

A. Nemirovski and A. Shapiro, Convex approximations of chance constrained programs, SIAM J. Optim., 17 (2006), 969-996.  doi: 10.1137/050622328.  Google Scholar

[19]

B. K. PagnoncelliS. 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.  Google Scholar

[20]

I. Popescu, Robust mean-covariance solutions for stochastic optimization, Oper. Res., 55 (2007), 98-112.  doi: 10.1287/opre.1060.0353.  Google Scholar

[21]

K. PostekA. Ben-TalD. 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.  Google Scholar

[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.  Google Scholar

[23]

G. Salvendy (Ed.), Handbook of Industrial Engineering: Technology and Operations Management, John Wiley and Sons, 2001. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[26]

W. Xie, S. Ahmed and R. Jiang, Optimized Bonferroni approximations of distributionally robust joint chance constraints, Mathematical Programming, (2019), 1–34. Google Scholar

[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.  Google Scholar

[28]

M. ZaghianG.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.  Google Scholar

[29]

Y. ZhaoW. ZhangW. GuoS. 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.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

W. ChenM. SimJ. 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.  Google Scholar

[8]

X. ChenM. Sim and P. Sun, A robust optimization perspective on stochastic programming, Oper. Res., 55 (2007), 1058-1071.  doi: 10.1287/opre.1070.0441.  Google Scholar

[9]

Z. ChenM. Sim and H. Xu, Distributionally robust optimization with infinitely constrained ambiguity sets, Oper. Res., 67 (2019), 1328-1344.  doi: 10.1287/opre.2018.1799.  Google Scholar

[10]

S.-S. CheungA. 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.  Google Scholar

[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.  Google Scholar

[12]

R. Gao and A.J. Kleywegt, Distributionally robust stochastic optimization with Wasserstein distance, arXiv preprint, arXiv: 1604.02199. Google Scholar

[13]

S. GuoH. 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.  Google Scholar

[14]

L. J. HongY. 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.  Google Scholar

[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.  Google Scholar

[16]

Z. Lin and Z. Bai, Probability Inequalities, Springer Science and Business Media, 2011. Google Scholar

[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.  Google Scholar

[18]

A. Nemirovski and A. Shapiro, Convex approximations of chance constrained programs, SIAM J. Optim., 17 (2006), 969-996.  doi: 10.1137/050622328.  Google Scholar

[19]

B. K. PagnoncelliS. 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.  Google Scholar

[20]

I. Popescu, Robust mean-covariance solutions for stochastic optimization, Oper. Res., 55 (2007), 98-112.  doi: 10.1287/opre.1060.0353.  Google Scholar

[21]

K. PostekA. Ben-TalD. 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.  Google Scholar

[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.  Google Scholar

[23]

G. Salvendy (Ed.), Handbook of Industrial Engineering: Technology and Operations Management, John Wiley and Sons, 2001. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[26]

W. Xie, S. Ahmed and R. Jiang, Optimized Bonferroni approximations of distributionally robust joint chance constraints, Mathematical Programming, (2019), 1–34. Google Scholar

[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.  Google Scholar

[28]

M. ZaghianG.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.  Google Scholar

[29]

Y. ZhaoW. ZhangW. GuoS. 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.  Google Scholar

Figure 1.  Changes of the optimal value in single chance constrained program
Figure 2.  Changes of the optimal value in joint chance constrained program
Table 1.  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
Table 2.  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 & 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 & 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 & 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 & 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 & 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 & Management Optimization, 2021  doi: 10.3934/jimo.2021169

[7]

Philippe Ciarlet. Korn's inequalities: The linear vs. the nonlinear case. Discrete & 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 & 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 & 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 & 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 & Continuous Dynamical Systems, 2017, 37 (6) : 3059-3078. doi: 10.3934/dcds.2017131

[12]

Jochen Merker. Generalizations of logarithmic Sobolev inequalities. Discrete & Continuous Dynamical Systems - S, 2008, 1 (2) : 329-338. doi: 10.3934/dcdss.2008.1.329

[13]

Bin Zhou, Hailin Sun. Two-stage stochastic variational inequalities for Cournot-Nash equilibrium with risk-averse players under uncertainty. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 521-535. doi: 10.3934/naco.2020049

[14]

Yuan Tan, Qingyuan Cao, Lan Li, Tianshi Hu, Min Su. A chance-constrained stochastic model predictive control problem with disturbance feedback. Journal of Industrial & Management Optimization, 2021, 17 (1) : 67-79. doi: 10.3934/jimo.2019099

[15]

V. V. Zhikov, S. E. Pastukhova. Korn inequalities on thin periodic structures. Networks & Heterogeneous Media, 2009, 4 (1) : 153-175. doi: 10.3934/nhm.2009.4.153

[16]

Barbara Brandolini, Francesco Chiacchio, Cristina Trombetti. Hardy type inequalities and Gaussian measure. Communications on Pure & Applied Analysis, 2007, 6 (2) : 411-428. doi: 10.3934/cpaa.2007.6.411

[17]

Friedemann Brock, Francesco Chiacchio, Giuseppina di Blasio. Optimal Szegö-Weinberger type inequalities. Communications on Pure & Applied Analysis, 2016, 15 (2) : 367-383. doi: 10.3934/cpaa.2016.15.367

[18]

Hongxia Yin. An iterative method for general variational inequalities. Journal of Industrial & Management Optimization, 2005, 1 (2) : 201-209. doi: 10.3934/jimo.2005.1.201

[19]

Xiaoli Chen, Jianfu Yang. Improved Sobolev inequalities and critical problems. Communications on Pure & Applied Analysis, 2020, 19 (7) : 3673-3695. doi: 10.3934/cpaa.2020162

[20]

Juan Luis Vázquez, Nikolaos B. Zographopoulos. Hardy type inequalities and hidden energies. Discrete & Continuous Dynamical Systems, 2013, 33 (11&12) : 5457-5491. doi: 10.3934/dcds.2013.33.5457

2020 Impact Factor: 1.801

Metrics

  • PDF downloads (76)
  • HTML views (132)
  • Cited by (0)

Other articles
by authors

[Back to Top]