×

On the computational complexity and generalization properties of multi-stage and stage-wise coupled scenario programs. (English) Zbl 1344.93062

Summary: We discuss the computational complexity and feasibility properties of scenario sampling techniques for uncertain optimization programs. We propose an alternative way of dealing with a special class of stage-wise coupled programs and compare it with existing methods in the literature in terms of feasibility and computational complexity. We identify tradeoffs between different methods depending on the problem structure and the desired probability of constraint satisfaction. To illustrate our results, an example from the area of approximate dynamic programming is considered.

MSC:

93C41 Control/observation systems with incomplete information
90C60 Abstract computational complexity for mathematical programming problems
68Q25 Analysis of algorithms and problem complexity
90C25 Convex programming
90C39 Dynamic programming

Software:

ECOS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ben-Tal, A.; El Ghaoui, L.; Nemirovski, A., Robust Optimization (2009), Princeton University Press · Zbl 1221.90001
[2] Bertsimas, D.; Sim, M., Tractable approximations to robust conic optimization problems, Math. Program., 107, 1-2, 5-36 (2006) · Zbl 1134.90026
[3] Calafiore, G. C.; Campi, M. C., The scenario approach to robust control design, IEEE Trans. Automat. Control, 51, 5, 742-753 (2006) · Zbl 1366.93457
[4] Campi, M. C.; Garatti, S., The exact feasibility of randomized solutions of uncertain convex programs, SIAM J. Optim., 19, 3, 1211-1230 (2008) · Zbl 1180.90235
[5] Lecchini, A.; Lygeros, J.; Maciejowski, J., Stochastic optimization on continuous domains with finite-time guarantees by Markov chain Monte Carlo methods, IEEE Trans. Automat. Control, 55, 12, 2858-2863 (2010) · Zbl 1368.90121
[6] Kanamori, T.; Takeda, A., Worst-case violation of sampled convex programs for optimization with uncertainty, J. Optim. Theory Appl., 152, 1, 171-197 (2012) · Zbl 1272.90037
[7] Mohajerin, P.; Sutter, T.; Lygeros, J., Performance bounds for the scenario approach and an extension to a class of non-convex programs, IEEE Trans. Automat. Control, 60, 1, 46-58 (2015) · Zbl 1360.90251
[8] Schildbach, G.; Fagiano, L.; Morari, M., Randomized solutions to convex programs with multiple chance constraints, SIAM J. Optim., 23, 4, 2479-2501 (2013) · Zbl 1316.90035
[9] Calafiore, G. C.; Lyons, D., Random convex programs for distributed multi-agent consensus, (European Control Conference (2013), IEEE), 250-255
[10] de Farias, D. P.; Van Roy, B., The linear programming approach to approximate dynamic programming, Oper. Res., 51, 6, 850-865 (2003) · Zbl 1165.90666
[11] Calafiore, G. C., Random convex programs, SIAM J. Optim., 20, 6, 3427-3464 (2010) · Zbl 1211.90168
[12] Grammatico, S.; Zhang, X.; Margellos, K.; Goulart, P.; Lygeros, J., A scenario approach for non-convex control design, IEEE Trans. Automat. Control, 61, 2, 334-345 (2016) · Zbl 1359.93448
[13] Schildbach, G.; Fagiano, L.; Frei, C.; Morari, M., The scenario approach for stochastic model predictive control with bounds on closed-loop constraint violations, Automatica, 50, 12, 3009-3018 (2014) · Zbl 1309.93193
[14] Zhang, X.; Grammatico, S.; Schildbach, G.; Goulart, P.; Lygeros, J., On the sample size of random convex programs with structured dependence on the uncertainty, Automatica, 60, 182-188 (2015) · Zbl 1331.93230
[15] Prékopa, A., Stochastic Programming (1995), Springer · Zbl 0834.90098
[16] Margellos, K.; Prandini, M.; Lygeros, J., On the connection between compression learning and scenario based single-stage and cascading optimization problems, IEEE Trans. Automat. Control, 60, 10, 2716-2721 (2015) · Zbl 1360.68693
[17] Alamo, T.; Tempo, R.; Luque, A., On the sample complexity of probabilistic analysis and design methods, (Persp. in Math. System Theory, Control, and Signal Processing (2010), Springer), 39-50 · Zbl 1197.93075
[18] Nesterov, Y., Universal gradient methods for convex optimization problems, Math. Program., 1-24 (2013)
[19] Domahidi, A.; Chu, E.; Boyd, S., Ecos: An socp solver for embedded systems, (European Control Conference (2013), IEEE), 3071-3076
[21] Kariotoglou, N.; Summers, S.; Summers, T.; Kamgarpour, M.; Lygeros, J., Approximate dynamic programming for stochastic reachability, (European Control Conference (2013), IEEE), 584-589
[22] Summers, S.; Lygeros, J., Verification of discrete time stochastic hybrid systems: A stochastic reach-avoid decision problem, Automatica, 46, 12, 1951-1961 (2010) · Zbl 1371.93220
[23] Kroese, D. P.; Taimre, T.; Botev, Z. I., Handbook of Monte Carlo Methods, Vol. 706 (2011), John Wiley & Sons · Zbl 1213.65001
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.