×

Probabilistic guarantees in robust optimization. (English) Zbl 1481.90238

Summary: We develop a general methodology for deriving probabilistic guarantees for solutions of robust optimization problems. Our analysis applies broadly to any convex compact uncertainty set and to any constraint affected by uncertainty in a concave manner, under minimal assumptions on the underlying stochastic process. Namely, we assume that the coordinates of the noise vector are light-tailed (sub-Gaussian) but not necessarily independent. We introduce the notion of robust complexity of an uncertainty set, which is a robust analogue of the Rademacher and Gaussian complexities encountered in high-dimensional statistics, and which connects the geometry of the uncertainty set with an a priori probabilistic guarantee. Interestingly, the robust complexity involves the support function of the uncertainty set, which also plays a crucial role in the robust counterpart theory for robust linear and nonlinear optimization. For a variety of uncertainty sets of practical interest, we are able to compute it in closed form or derive valid approximations. Our methodology recovers most of the results available in the related literature using first principles and extends them to new uncertainty sets and nonlinear constraints. We also derive improved a posteriori bounds, i.e., significantly tighter bounds which depend on the resulting robust solution.

MSC:

90C17 Robustness in mathematical programming
90C25 Convex programming
65K05 Numerical mathematical programming methods

Software:

ROME
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] O. Baron, J. Milner, and H. Naseraldin, Facility location: A robust optimization approach, Prod. Oper. Manage., 20 (2011), pp. 772-785.
[2] A. Ben-Tal, D. den Hertog, and J.-P. Vial, Deriving robust counterparts of nonlinear uncertain inequalities, Math. Program., 149 (2015), pp. 265-299. · Zbl 1308.65089
[3] A. Ben-Tal, L. El Ghaoui, and A. Nemirovski, Robust Optimization, Princeton Ser. Appl. Math. 28, Princeton University Press, 2009. · Zbl 1221.90001
[4] A. Ben-Tal and A. Nemirovski, Robust solutions of linear programming problems contaminated with uncertain data, Math. Program., 88 (2000), pp. 411-424. · Zbl 0964.90025
[5] D. Bertsimas, D. B. Brown, and C. Caramanis, Theory and applications of robust optimization, SIAM Rev., 53 (2011), pp. 464-501, https://doi.org/10.1137/080734510. · Zbl 1233.90259
[6] D. Bertsimas, V. Gupta, and N. Kallus, Data-driven robust optimization, Math. Program., 167 (2018), pp. 235-292. · Zbl 1397.90298
[7] D. Bertsimas, D. Pachamanova, and M. Sim, Robust linear optimization under general norms, Oper. Res. Lett., 32 (2004), pp. 510-516. · Zbl 1054.90046
[8] D. Bertsimas and M. Sim, The price of robustness, Oper. Res., 52 (2004), pp. 35-53. · Zbl 1165.90565
[9] D. Bertsimas and M. Sim, Tractable approximations to robust conic optimization problems, Math. Program., 107 (2006), pp. 5-36. · Zbl 1134.90026
[10] C. E. Bonferroni, Teoria statistica delle classi e calcolo delle probabilita, Pubbl. R Ist. Sup. Sci. Econom. Commericiali Firenze, 8 (1936), pp. 3-62. · Zbl 0016.41103
[11] G. Calafiore and M. C. Campi, Uncertain convex programs: Randomized solutions and confidence levels, Math. Program., 102 (2005), pp. 25-46. · Zbl 1177.90317
[12] G. C. Calafiore and M. C. Campi, The scenario approach to robust control design, IEEE Trans. Automat. Control, 51 (2006), pp. 742-753. · Zbl 1366.93457
[13] M. C. Campi and S. Garatti, The exact feasibility of randomized solutions of uncertain convex programs, SIAM J. Optim., 19 (2008), pp. 1211-1230, https://doi.org/10.1137/07069821X. · Zbl 1180.90235
[14] 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), pp. 470-485. · Zbl 1226.90051
[15] Z. Chen, D. Kuhn, and W. Wiesemann, Data-Driven Chance Constrained Programs over Wasserstein Balls, preprint, https://arxiv.org/abs/1809.00210, 2018.
[16] D. P. De Farias and B. Van Roy, On constraint sampling in the linear programming approach to approximate dynamic programming, Math. Oper. Res., 29 (2004), pp. 462-478. · Zbl 1082.90124
[17] E. Delage and S. Mannor, Percentile optimization for Markov decision processes with parameter uncertainty, Oper. Res., 58 (2010), pp. 203-213. · Zbl 1226.90128
[18] E. Delage and Y. Ye, Distributionally robust optimization under moment uncertainty with application to data-driven problems, Oper. Res., 58 (2010), pp. 595-612. · Zbl 1228.90064
[19] L. Dümbgen and G. Walther, Rates of convergence for random approximations of convex sets, Adv. in Appl. Probab., 28 (1996), pp. 384-393. · Zbl 0861.60022
[20] E. Erdoğan and G. Iyengar, Ambiguous chance constrained problems and robust optimization, Math. Program., 107 (2006), pp. 37-61. · Zbl 1134.90028
[21] P. M. Esfahani and D. Kuhn, Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations, Math. Program., 171 (2018), pp. 115-166. · Zbl 1433.90095
[22] V. Gabrel, C. Murat, and A. Thiele, Recent advances in robust optimization: An overview, Eur. J. Oper. Res., 235 (2014), pp. 471-483. · Zbl 1305.90390
[23] R. Gao and A. J. Kleywegt, Distributionally Robust Stochastic Optimization with Wasserstein Distance, preprint, https://arxiv.org/abs/1604.02199, 2016.
[24] J. Goh and M. Sim, Distributionally robust optimization and its tractable approximations, Oper. Res., 58 (2010), pp. 902-917. · Zbl 1228.90067
[25] V. Gupta, Near-optimal Bayesian ambiguity sets for distributionally robust optimization, Management Sci., 65 (2019), pp. 4242-4260.
[26] Y. A. Guzman, L. R. Matthews, and C. A. Floudas, New a priori and a posteriori probabilistic bounds for robust counterpart optimization I: Unknown probability distributions, Comput. Chem. Engrg., 84 (2016), pp. 568-598.
[27] Y. A. Guzman, L. R. Matthews, and C. A. Floudas, New a priori and a posteriori probabilistic bounds for robust counterpart optimization II: A priori bounds for known symmetric and asymmetric probability distributions, Comput. Chem. Engrg., 101 (2017), pp. 279-311.
[28] Y. A. Guzman, L. R. Matthews, and C. A. Floudas, New a priori and a posteriori probabilistic bounds for robust counterpart optimization III: Exact and near-exact a posteriori expressions for known probability distributions, Comput. Chem. Engrg., 103 (2017), pp. 116-143.
[29] G. A. Hanasusanto, V. Roitch, D. Kuhn, and W. Wiesemann, A distributionally robust perspective on uncertainty quantification and chance constrained programming, Math. Program., 151 (2015), pp. 35-62. · Zbl 1328.90090
[30] G. A. Hanasusanto, V. Roitch, D. Kuhn, and W. Wiesemann, Ambiguous joint chance constraints under mean and dispersion information, Oper. Res., 65 (2017), pp. 751-767. · Zbl 1387.90271
[31] K. Holmberg, M. Rönnqvist, and D. Yuan, An exact algorithm for the capacitated facility location problems with single sourcing, Eur. J. Oper. Res., 113 (1999), pp. 544-559. · Zbl 0947.90059
[32] L. J. Hong, Z. Huang, and H. Lam, Learning-based robust optimization: Procedures and statistical guarantees, Management Sci., 67 (2021), pp. 3447-3467, https://doi.org/10.1287/mnsc.2020.3640.
[33] T. Kanamori and A. Takeda, Worst-case violation of sampled convex programs for optimization with uncertainty, J. Optim. Theory Appl., 152 (2012), pp. 171-197. · Zbl 1272.90037
[34] D. Kuhn, P. M. Esfahani, V. A. Nguyen, and S. Shafieezadeh-Abadeh, Wasserstein distributionally robust optimization: Theory and applications in machine learning, in Operations Research & Management Science in the Age of Analytics, INFORMS, 2019, pp. 130-166.
[35] Z. Li, Q. Tang, and C. A. Floudas, A comparative theoretical and computational study on robust counterpart optimization II: Probabilistic guarantees on constraint satisfaction, Ind. Eng. Chem. Res., 51 (2012), pp. 6769-6788.
[36] J. Luedtke and S. Ahmed, A sample approximation approach for optimization with probabilistic constraints, SIAM J. Optim., 19 (2008), pp. 674-699, https://doi.org/10.1137/070702928. · Zbl 1177.90301
[37] A. W. Marshall and I. Olkin, Multivariate Chebyshev inequalities, Ann. Math. Statist., 31 (1960), pp. 1001-1014. · Zbl 0244.60013
[38] H. Namkoong and J. C. Duchi, Stochastic gradient methods for distributionally robust optimization with f-divergences, Adv. Neural Inform. Process. Syst., 29 (2016), pp. 2208-2216.
[39] A. Nemirovski and A. Shapiro, Scenario Approximations of Chance Constraints, Springer, 2006. · Zbl 1181.90248
[40] P. Rigollet and J.-C. Hütter, High Dimensional Statistics, Lecture Notes for Course 18.657, MIT, 2017, http://www-math.mit.edu/ rigollet/PDFs/RigNotes17.pdf.
[41] R. T. Rockafellar, Convex Analysis, Princeton University Press, 2015.
[42] E. Roos, D. den Hertog, A. Ben-Tal, F. de Ruiter, and J. Zhen, Approximation of hard uncertain convex inequalities, available on Optimization Online, June 2018.
[43] B. P. Van Parys, P. M. Esfahani, and D. Kuhn, From data to decisions: Distributionally robust optimization is optimal, Management Sci., 67 (2021), pp. 3387-3402, https://doi.org/10.1287/mnsc.2020.3678.
[44] M. J. Wainwright, High-Dimensional Statistics: A Non-asymptotic Viewpoint, Cambridge Ser. Statist. Probab. Math. 48, Cambridge University Press, 2019. · Zbl 1457.62011
[45] W. Xie, On distributionally robust chance constrained programs with Wasserstein distance, Math. Program. Ser. A, 186 (2021), pp. 115-155. · Zbl 1459.90141
[46] Y. Xie, J. Snoeyink, and J. Xu, Efficient algorithm for approximating maximum inscribed sphere in high dimensional polytope, in Proceedings of the Twenty-Second Annual Symposium on Computational Geometry, ACM, 2006, pp. 21-29. · Zbl 1153.68550
[47] H. Xu, C. Caramanis, and S. Mannor, Optimization under probabilistic envelope constraints, Oper. Res., 60 (2012), pp. 682-699. · Zbl 1251.90301
[48] W. Yang and H. Xu, Distributionally robust chance constraints for non-linear uncertainties, Math. Program., 155 (2016), pp. 231-265. · Zbl 1347.90064
[49] İ. Yan\ikoğlu and D. den Hertog, Safe approximations of ambiguous chance constraints using historical data, INFORMS J. Comput., 25 (2013), pp. 666-681.
[50] J. Zhen and D. den Hertog, Computing the maximum volume inscribed ellipsoid of a polytopic projection, INFORMS J. Comput., 30 (2018), pp. 31-42. · Zbl 1446.90069
[51] S. Zymler, D. Kuhn, and B. Rustem, Distributionally robust joint chance constraints with second-order moment information, Math. Program., 137 (2013), pp. 167-198. · 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.