×

Distributionally robust polynomial chance-constraints under mixture ambiguity sets. (English) Zbl 1469.41005

A summary of the paper can be given by the authors’ conclusion as follows.
“Computing or even approximating the feasible set associated with a distributionally robust chance-constraint is a challenging problem. We have described a systematic numerical scheme which provides a monotone sequence (a hierarchy) of inner approximations, all in the form \(\{\mathbf{x} \in \mathbf{X} : w_d (\mathbf{x}) < \varepsilon\}\) for some polynomial of increasing degree \(d\), with strong asymptotic guarantees as \(d\) increases. To the best of our knowledge it is the first result of this type at this level of generality. Of course this comes with a price as the polynomial which defines each approximation is obtained by solving a semidefinite program whose size increases with its degree. Therefore and so far, this approach is limited to problems of small dimension (except perhaps if some sparsity can be exploited). So in its present form this contribution should be considered as complementary (rather than a competitor) to other algorithmic approaches where scalability is of primary importance. However it may also provide useful insights and a benchmark (for small dimension problems) for the latter approaches.”
With some ad-hoc adjustments, the framework presented in this paper can be extended to consider problems with only first- and second-order moments knowledge (no information about the distributions contributing to the mixture) and/or distributionally robust joint chance-constraints.
The approach is a non trivial extension of the numerical scheme proposed in [J. B. Lasserre, “Representation of chance-constraints with strong asymptotic properties”, IEEE Control Syst. Lett. 1, 50–55 (2017)].

MSC:

41A29 Approximation with constraints
49M29 Numerical methods involving duality
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
68T37 Reasoning under uncertainty in the context of artificial intelligence
90C22 Semidefinite programming
90C59 Approximation methods and heuristics in mathematical programming

Software:

GloptiPoly; GitHub; Mosek

References:

[1] Ash, R., Real Analysis and Probability (1972), Boston: Academic Press Inc., Boston · Zbl 1381.28001
[2] Billingsley, P., Convergence of Probability Measures (1968), New York: Wiley, New York · Zbl 0172.21201
[3] Calafiore, G., Dabbene, F.: Probabilistic and randomized methods for design under uncertainty. Springer (2006) · Zbl 1085.90001
[4] Calafiore, GC; El Ghaoui, L., On distributionally robust chance-constrained linear programs, J. Optim. Theory Appl., 130, 1-22 (2006) · Zbl 1143.90021
[5] Charnes, A.; Cooper, WW, Chance constrained programming, Manag. Sci., 6, 73-79 (1959) · Zbl 0995.90600
[6] Chen, W.; Sim, M.; Sun, J.; Teo, CP, From CVaR to uncertainty set: implications in joint chance-constrained optimization, Oper. Res., 58, 2, 470-485 (2010) · Zbl 1226.90051
[7] de Klerk, E., Kuhn, D., Postek, K.: Distributionally robust optimization with polynomial densities: theory, models and algorithms. arXiv:1805.03588 · Zbl 1467.90030
[8] Delage, E.; Ye, Y., Distributionally robust optimization under moment uncertainty with applications to data-driven problems, Oper. Res., 58, 595-612 (2010) · Zbl 1228.90064
[9] Di Zioa, M.; Guarneraa, U.; Roccib, R., A mixture of mixture models for a classification problem: the unity measure error, Comput. Stat. Data Anal., 51, 2573-2585 (2007) · Zbl 1161.62373
[10] Doob, JL, Measure Theory (1994), New York: Springer, New York · Zbl 0791.28001
[11] Duan, C., Fang, W., Jiang, L., Yao, L., Liu, J.: Distributionally robust chance-constrained voltage-concerned DC-OPF with Wasserstein metric (2017). arXiv:1706.05538
[12] Erdogan, E.; Iyengar, G., Ambiguous chance constrained problems and robust optimization, Math. Program. Sér. B, 107, 37-61 (2006) · Zbl 1134.90028
[13] El Ghaoui, L.; Oks, M.; Oustry, F., Worst-case value-at-risk and robust portfolio optimization: a conic programming approach, Oper. Res., 51, 543-556 (2003) · Zbl 1165.91397
[14] Hanasusanto, GA; Roitch, V.; Kuhn, D.; Wiesemann, W., Ambiguous joint chance constraints under mean and dispersion information, Oper. Res., 65, 751-767 (2017) · Zbl 1387.90271
[15] Hanasusanto, GA; Roitch, V.; Kuhn, D.; Wiesemann, W., A distributionally robust perspective on uncertainty quantification and chance constrained programming, Math. Program., 151, 35-62 (2015) · Zbl 1328.90090
[16] Henrion, R., Structural properties of linear probabilistic constraints, Optimization, 56, 425-440 (2007) · Zbl 1149.90110
[17] Henrion, R.; Strugarek, C., Convexity of chance constraints with independent random variables, Comput. Optim. Appl., 41, 263-276 (2008) · Zbl 1168.90568
[18] Henrion, D.; Lasserre, JB; Lofberg, J., Gloptipoly 3: moments, optimization and semidefinite programming, Optim. Methods Softw., 24, 761-779 (2009) · Zbl 1178.90277
[19] Henrion, D.; Lasserre, JB; Savorgnan, C., Approximate volume and integration for basic semi-algebraic sets, SIAM Rev., 51, 722-743 (2009) · Zbl 1179.14037
[20] Henrion, D.; Korda, M., Convex computation of the region of attraction of polynomial control systems, IEEE Trans. Autom. Control, 59, 297-312 (2014) · Zbl 1360.93601
[21] Jasour, AM; Aybat, NS; Lagoa, CM, Semidefinite programming for chance constrained optimization over semi-algebraic sets, SIAM J. Optim., 25, 3, 1411-1440 (2015) · Zbl 1317.90237
[22] Jasour, A., Lagoa, C.: Convex constrained semialgebraic volume optimization: application in systems and control (2017). arXiv:1701.08910
[23] Jiang, R.; Guan, Y., Data-driven chance constrained stochastic program, Math. Program., 158, 291-327 (2016) · Zbl 1346.90640
[24] Korda, M.; Henrion, D.; Jones, CN, Convex computation of the maximum controlled invariant set for polynomial control systems, SIAM J. Control Optim., 52, 5, 2944-2969 (2014) · Zbl 1311.49073
[25] Lasserre, JB, Representation of chance-constraints with strong asymptotic properties, IEEE Control Syst. Lett., 1, 50-55 (2017)
[26] Lasserre, JB, The K-moment problem for continuous linear functionals, Trans. Am. Math. Soc., 365, 2489-2504 (2013) · Zbl 1275.44003
[27] Lasserre, JB, A “Joint+Marginal” approach to parametric polynomial optimization, SIAM J. Optim., 20, 1995-2022 (2010) · Zbl 1204.65067
[28] Lasserre, JB, Moments, Positive Polynomials and Their Applications (2010), London: Imperial College Press, London · Zbl 1211.90007
[29] Lasserre, JB, Lebesgue decomposition in action via semidefinite relaxations, Adv. Comput. Math., 42, 1129-1148 (2016) · Zbl 1353.90085
[30] Lasserre, JB; Netzer, T., SOS approximations of nonnegative polynomials via simple high degree perturbations, Math. Zeitschrift, 256, 99-112 (2006) · Zbl 1122.13005
[31] Lasserre, JB, Computing gaussian and exponential measures of semi-algebraic sets, Adv. Appl. Math., 91, 137-163 (2017) · Zbl 1370.28002
[32] Li, P.; Wendt, M.; Wozny, G., A probabilistically constrained model predictive controller, Automatica, 38, 1171-1176 (2002) · Zbl 1002.93507
[33] Marron, JS; Wand, MP, Exact mean integrated squared error, Ann. Stat., 20, 712-736 (1992) · Zbl 0746.62040
[34] Miller, B.; Wagner, H., Chance-constrained programming with joint constraints, Oper. Res., 13, 930-945 (1965) · Zbl 0132.40102
[35] Mosek, A ps: Mosek Matlab Toolbox (2017)
[36] Nemirovski, A.; Shapiro, A., Convex approximations of chance constrained programs, SIAM J. Optim., 17, 969-996 (2006) · Zbl 1126.90056
[37] Prékopa, A.: Probabilistic programming. In: Stochastic Programming. Handbooks in Operations Research and Management Science, vol. 10, pp. 267-351. Elsevier (2003) · Zbl 1115.90001
[38] Putinar, M., Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J., 42, 969-984 (1993) · Zbl 0796.12002
[39] Shapiro, A.; Dentcheva, D.; Ruszczynski, A., Lecture on Stochastic Programming: Modeling and Theory (2014), Philadelphia: SIAM, Philadelphia · Zbl 1302.90003
[40] Tong, X.; Sun, H.; Luo, X.; Zheng, Q., Distributionally robust chance constrained optimization for economic dispatch in renewable energy integrated systems, J. Glob. Optim., 70, 131-158 (2018) · Zbl 1411.90243
[41] Ackooij, W.: Convexity statements for linear probability constraints with Gaussian technology matrices and copulae correlated rows (2017). doi:10.13140/RG.2.2.11723.69926
[42] van Ackooij, W.; Malick, J., Eventual convexity of probability constraints with elliptical distributions, Math. Program., 175, 1, 1-27 (2018) · Zbl 1421.90101
[43] Wang, S., Li, J., Peng, C.: Distributionally robust chance-constrained program surgery planning with downstream resource. In: Proceedings 2017 International Conference on Service Systems and Service Management, Dalian, China (2017)
[44] Waki, H.; Kim, S.; Kojima, M.; Muramatsu, M., Sums of squares and semidefinite programming relaxations for polynomial optimization problems with structured sparsity, SIAM J. Optim., 17, 218-242 (2006) · Zbl 1109.65058
[45] Wang, S.I., Chaganti, A.T., Liang, P.: Estimating mixture models via mixtures of polynomials. In: Proceedings of the 28th International Conference on Neural Information Processing Systems (NIPS’15), Montreal, pp. 487-495 (2015)
[46] Weisser, T.: MomentOpt.jl, v.0.1.0. https://github.com/lanl-ansi/MomentOpt.jl
[47] Xie, W.; Ahmed, S., Distributionally robust chance constrained optimal power flow with renewables: a conic reformulation, IEEE Trans. Power Syst., 30, 5, 2790-2799 (2017)
[48] Xie, W.; Ahmed, S., On deterministic reformulations of distributionally robust joint chance constrained optimization problems, SIAM J. Optim., 28, 1151-1182 (2018) · Zbl 1390.90412
[49] Xu, D.: The applications of mixtures of normal distributions in empirical finance: a selected survey, Working Papers 0904, University of Waterloo, Department of Economics, revised September (2009)
[50] Yang, W.; Huan, X., Distributionally robust chance constraints for non-linear uncertainties, Math. Program., 155, 231-265 (2016) · Zbl 1347.90064
[51] Zhang, Y.; Shen, S.; Mathieu, J., Distributionally robust chance-constrained optimal power flow with uncertain renewables and uncertain reserves provided by loads, IEEE Trans. Power Syst., 32, 1378-1388 (2016)
[52] Zymler, S.; Kuhn, D.; Rustem, B., Distributionally robust joint chance constraints with second-order moment information, Math. Program., 137, 167-198 (2013) · Zbl 1286.90103
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.