×

Chance-constrained sets approximation: a probabilistic scaling approach. (English) Zbl 1482.93365

Summary: In this paper, a sample-based procedure for obtaining simple and computable approximations of chance-constrained sets is proposed. The procedure allows to control the complexity of the approximating set, by defining families of simple-approximating sets of given complexity. A probabilistic scaling procedure then scales these sets to obtain the desired probabilistic guarantees. The proposed approach is shown to be applicable in several problems in systems and control, such as the design of stochastic model predictive control schemes or the solution of probabilistic set membership estimation problems.

MSC:

93C57 Sampled-data control/observation systems
93B45 Model predictive control

Software:

MPT
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] van Ackooij, W., Eventual convexity of chance constrained feasible sets, Optimization, 64, 5, 1263-1284 (2015) · Zbl 1321.49042
[2] van Ackooij, W.; Malick, J., Eventual convexity of probability constraints with elliptical distributions, Mathematical Programming, 175, 1, 1-27 (2019) · Zbl 1421.90101
[3] Ahmed, S.; Xie, W., Relaxations and approximations of chance constraints under finite distributions, Mathematical Programming, 170, 1, 43-65 (2018) · Zbl 1391.90422
[4] Alamo, T.; Bravo, J. M.; Camacho, E. F., Guaranteed state estimation by zonotopes, Automatica, 41, 6, 1035-1043 (2005) · Zbl 1091.93038
[5] Alamo, T.; Manzano, J. M.; Camacho, E. F., Robust design through probabilistic maximization, (Basar, T., Uncertainty in complex networked systems. In Honor of Roberto Tempo (2018), Birkhäuser), 247-274 · Zbl 1415.93089
[6] Alamo, T.; Mirasierra, V.; Dabbene, F.; Lorenzen, M., Safe approximations of chance constrained sets by probabilistic scaling, (2019 18th European control conference (2019), IEEE), 1380-1385
[7] Alamo, T.; Tempo, R.; Camacho, E. F., Randomized strategies for probabilistic solutions of uncertain feasibility and optimization problems, IEEE Transactions on Automatic Control, 54, 11, 2545-2559 (2009) · Zbl 1367.90106
[8] Alamo, T.; Tempo, R.; Luque, A.; Ramirez, D., Randomized methods for design of uncertain systems: Sample complexity and sequential algorithms, Automatica, 52, 160-172 (2015) · Zbl 1309.93192
[9] Ben-Tal, A.; Nemirovski, A., Robust convex optimization, Mathematics of Operations Research, 23, 769-805 (1998) · Zbl 0977.90052
[10] Beraldi, P.; Ruszczyński, A., A branch and bound method for stochastic integer problems under probabilistic constraints, Optimization Methods & Software, 17, 3, 359-382 (2002) · Zbl 1064.90030
[11] Boyd, S.; Vandenberghe, L., Convex optimization (2004), Cambridge University Press · Zbl 1058.90049
[12] Bravo, J. M.; Alamo, T.; Camacho, E. F., Bounded error identification of systems with time-varying parameters, IEEE Transactions on Automatic Control, 51, 7, 1144-1150 (2006) · Zbl 1366.93121
[13] Bremer, I.; Henrion, R.; Möller, A., Probabilistic constraints via SQP solver: Application to a renewable energy management problem, Computational Management Science, 12, 3, 435-459 (2015) · Zbl 1317.90216
[14] Buhmann, M. D., Radial basis functions, Acta Numerica, 9, 1-38 (2000) · Zbl 1004.65015
[15] Calafiore, G., Random convex programs, SIAM Journal of Optimization, 20, 3427-3464 (2010) · Zbl 1211.90168
[16] Calafiore, G.; Campi, M. C., The scenario approach to robust control design, IEEE Transactions on Automatic Control, 51, 5, 742-753 (2006) · Zbl 1366.93457
[17] Calafiore, G.; Dabbene, F.; Tempo, R., Research on probabilistic methods for control system design, Automatica, 47, 1279-1293 (2011) · Zbl 1219.93038
[18] Calafiore, G. C.; Ghaoui, L. E., On distributionally robust chance-constrained linear programs, Journal of Optimization Theory and Applications, 130, 1, 1-22 (2006) · Zbl 1143.90021
[19] Campi, M. C.; Garatti, S., The exact feasibility of randomized solutions of robust convex programs, SIAM Journal of Optimization, 19, 1211-1230 (2008) · Zbl 1180.90235
[20] Campi, M. C.; Garatti, S., A sampling-and-discarding approach to chance-constrained optimization: Feasibility and optimality, Journal of Optimization Theory and Applications, 148, 257-280 (2011) · Zbl 1211.90146
[21] Chamanbaz, M.; Dabbene, F.; Lagoa, C. M., Probabilistically robust AC optimal power flow, IEEE Transactions on Control of Network Systems, 6, 3, 1135-1147 (2019) · Zbl 1515.93045
[22] Chamanbaz, M.; Dabbene, F.; Lagoa, C., Algorithms for optimal AC power flow in the presence of renewable sources, (Webster, J., Wiley encyclopedia of electrical and electronics engineering (2020)), 1-13
[23] Chen, W.; Sim, M.; Sun, J.; Teo, C.-P., From CVaR to uncertainty set: Implications in joint chance-constrained optimization, Operations Research, 58, 2, 470-485 (2010) · Zbl 1226.90051
[24] Dabbene, F.; Henrion, D.; Lagoa, C. M., Simple approximations of semialgebraic sets and their applications to control, Automatica, 78, 110-118 (2017) · Zbl 1357.93058
[25] Dabbene, F.; Henrion, D.; Lagoa, C.; Shcherbakov, P., Randomized approximations of the image set of nonlinear mappings with applications to filtering, IFAC-PapersOnLine, 48, 14, 37-42 (2015)
[26] Dabbene, F.; Lagoa, C.; Shcherbakov, P., On the complexity of randomized approximations of nonconvex sets, (2010 IEEE international symposium on computer-aided control system design (2010), IEEE), 1564-1569
[27] Dentcheva, D.; Lai, B.; Ruszczyński, A., Dual methods for probabilistic optimization problems, Mathematical Methods of Operations Research, 60, 2, 331-346 (2004) · Zbl 1076.90038
[28] Dentcheva, D.; Prékopa, A.; Ruszczynski, A., Concavity and efficient points of discrete distributions in probabilistic programming, Mathematical Programming, 89, 1, 55-77 (2000) · Zbl 1033.90078
[29] Geng, X.; Xie, L., Data-driven decision making in power systems with probabilistic guarantees: Theory and applications of chance-constrained optimization, Annual Reviews in Control, 47, 341-363 (2019)
[30] Gover, E.; Krikorian, N., Determinants and the volumes of parallelotopes and zonotopes, Linear Algebra and its Applications, 433, 1, 28-40 (2010) · Zbl 1194.52009
[31] Henrion, R.; Strugarek, C., Convexity of chance constraints with independent random variables, Computational Optimization and Applications, 41, 2, 263-276 (2008) · Zbl 1168.90568
[32] Herceg, M.; Kvasnica, M.; Jones, C. N.; Morari, M., Multi-parametric toolbox 3.0, (2013 European control conference (2013), IEEE), 502-510
[33] Hewing, L.; Carron, A.; Wabersich, K. P.; Zeilinger, M. N., On a correspondence between probabilistic and robust invariant sets for linear systems, (2018 European control conference (2018), IEEE), 1642-1647
[34] Hewing, L., & Zeilinger, M. N. (2018). Stochastic model predictive control for linear systems using probabilistic reachable sets. In 2018 IEEE conference on decision and control (pp. 5182-5188).
[35] Jasour, A. M.; Aybat, N. S.; Lagoa, C. M., Semidefinite programming for chance constrained optimization over semialgebraic sets, SIAM Journal on Optimization, 25, 3, 1411-1440 (2015) · Zbl 1317.90237
[36] Kataoka, S., A stochastic programming model, Econometrica, 31, 1-2, 181-196 (1963) · Zbl 0125.09601
[37] Khachiyan, L., The problem of calculating the volume of a polyhedron is enumerably hard, Russian Mathematical Surveys, 44, 199-200 (1989) · Zbl 0692.68034
[38] Lagoa, C. M., On the convexity of probabilistically constrained linear programs, (Proceedings of the 38th IEEE conference on decision and control, Vol. 1 (1999)), 516-521
[39] Lasserre, J. B., Representation of chance-constraints with strong asymptotic guarantees, IEEE Control Systems Letters, 1, 1, 50-55 (2017)
[40] Le, V. T.H.; Stoica, C.; Alamo, T.; Camacho, E. F.; Dumur, D., Zonotopes: From guaranteed state-estimation to control (2013), Wiley
[41] Lejeune, M. A., Pattern-based modeling and solution of probabilistically constrained optimization problems, Operations Research, 60, 6, 1356-1372 (2012) · Zbl 1269.90071
[42] Lejeune, M. A.; Margot, F., Solving chance-constrained optimization problems with stochastic quadratic inequalities, Operations Research, 64, 4, 939-957 (2016) · Zbl 1348.90504
[43] Lejeune, M. A.; Prékopa, A., Relaxations for pro- babilistically constrained stochastic programming problems: Review and extensions, Annals of Operations Research, 1-22 (2018)
[44] Li, J.; Zhan, W.; Hu, Y.; Tomizuka, M., Generic tracking and probabilistic prediction framework and its application in autonomous driving, IEEE Transactions on Intelligent Transportation Systems, 21, 9, 3634-3649 (2020)
[45] Lorenzen, M.; Dabbene, F.; Tempo, R.; Allgöwer, F., Constraint-tightening and stability in stochastic model predictive control, IEEE Transactions on Automatic Control, 62, 7, 3165-3177 (2017) · Zbl 1370.93245
[46] Lorenzen, M.; Dabbene, F.; Tempo, R.; Allgöwer, F., Stochastic MPC with offline uncertainty sampling, Automatica, 81, 1, 176-183 (2017) · Zbl 1372.93183
[47] Luedtke, J.; Ahmed, S., A sample approximation approach for optimization with probabilistic constraints, SIAM Journal on Optimization, 2, 19, 674-699 (2008) · Zbl 1177.90301
[48] Mammarella, M., Alamo, T., Dabbene, F., & Lorenzen, M. (2020). Computationally efficient stochastic MPC: A probabilistic scaling approach. In Proc. of 4th IEEE conference on control technology and applications (pp. 25-30).
[49] Mammarella, M.; Capello, E.; Dabbene, F.; Guglieri, G., Sample-based SMPC for tracking control of fixed-wing UAV, IEEE Control Systems Letters, 2, 4, 611-616 (2018)
[50] Mammarella, M.; Lorenzen, M.; Capello, E.; Park, H.; Dabbene, F.; Guglieri, G., An offline-sampling SMPC framework with application to autonomous space maneuvers, IEEE Transactions on Control Systems Technology, 28, 2, 1-15 (2018)
[51] Mammarella, M.; Mirasierra, V.; Lorenzen, M.; Alamo, T.; Dabbene, F., Chance constrained sets approximation: A probabilistic scaling approach – extended version, 1-16 (2021), arXiv preprint arXiv:2101.06052
[52] Margellos, K.; Goulart, P.; Lygeros, J., On the road between robust optimization and the scenario approach for chance constrained optimization problems, IEEE Transactions on Automatic Control, 59, 8, 2258-2263 (2014) · Zbl 1360.90179
[53] Miller, B. L.; Wagner, H. M., Chance constrained programming with joint constraints, Operations Research, 13, 930-945 (1965) · Zbl 0132.40102
[54] Mirasierra, V.; Mammarella, M.; Dabbene, F.; Alamo, T., Prediction error quantification through probabilistic scaling, IEEE Control Systems Letters, 6, 1118-1123 (2022)
[55] Nemirovski, A., On safe tractable approximations of chance constraints, European Journal of Operational Research, 219, 3, 707-718 (2012) · Zbl 1253.90185
[56] Nemirovski, A.; Shapiro, A., Convex approximations of chance constrained programs, SIAM Journal on Optimization, 17, 4, 969-996 (2006) · Zbl 1126.90056
[57] Prékopa, A., Logarithmic concave measures with application to stochastic programming, Acta Scientiarum Mathematicarum, 32, 301-316 (1971) · Zbl 0235.90044
[58] Prékopa, A., Dual method for the solution of a one-stage stochastic programming problem with random RHS obeying a discrete probability distribution, Zeitschrift für Operations Research, 34, 6, 441-461 (1990) · Zbl 0724.90048
[59] Prékopa, A., Stochastic programming (1995), Kluwer Academic Publishers · Zbl 0863.90116
[60] Prékopa, A.; Rapcsák, T.; Zsuffa, I., Serially linked reservoir system design using stochastic programing, Water Resources Research, 14, 4, 672-678 (1978)
[61] Puig, V., Fault diagnosis and fault tolerant control using set-membership approaches: Application to real case studies, International Journal of Applied Mathematics and Computer Science, 20, 4, 619-635 (2010) · Zbl 1214.93061
[62] Sahinidis, N. V., Optimization under uncertainty: State-of-the-art and opportunities, Computers & Chemical Engineering, 28, 6-7, 971-983 (2004)
[63] Shapiro, A.; Dentcheva, D.; Ruszczyński, A., Lectures on stochastic programming: Modeling and theory (2014), SIAM · Zbl 1302.90003
[64] Tempo, R.; Calafiore, G. C.; Dabbene, F., Randomized algorithms for analysis and control of uncertain systems: With applications (2012), Springer Science & Business Media
[65] Vapnik, V. N., Statistical learning theory (1998), John Wiley and Sons: John Wiley and Sons New York · Zbl 0935.62007
[66] Vicino, A.; Zappa, G., Sequential approximation of feasible parameter sets for identification with set membership uncertainty, IEEE Transactions on Automatic Control, 41, 6, 774-785 (1996) · Zbl 0867.93026
[67] Yan, S., Goulart, P., & Cannon, M. (2018). Stochastic model predictive control with discounted probabilistic constraints. In 2018 European control conference (pp. 1003-1008).
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.