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

Yanjun Wang; Shisen Liu

doi:10.3934/jimo.2021132

Article Contents

2022, Volume 18, Issue 5: 3719-3733. Doi: 10.3934/jimo.2021132

This issue Previous Article Two-level optimization approach with accelerated proximal gradient for objective measures in sparse speech reconstruction Next Article Steepest-descent block-iterative methods for a finite family of quasi-nonexpansive mappings

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

Yanjun Wang^1, and
Shisen Liu^2, ,

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
^* Corresponding author: Shisen Liu

Received: November 2020

Revised: April 2021

Early access: August 2021

Published: November 2022

Abstract / Introduction Full Text(HTML) Figure(2) / Table(2) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: 90C15, 90C25, 90C59.

Citation:

Full Text(HTML)

Figure 1. Changes of the optimal value in single chance constrained program

Download: Full-size image PowerPoint slide

Figure 2. Changes of the optimal value in joint chance constrained program

Download: Full-size image PowerPoint slide

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.