Learning-Based Robust Optimization: Procedures and Statistical Guarantees

References

• Ben-Tal A , Nemirovski A (1998) Robust convex optimization. Math. Oper. Res. 23(4):769–805.Link, Google Scholar
• Ben-Tal A , Nemirovski A (1999) Robust solutions of uncertain linear programs. Oper. Res. Lett. 25(1):1–13.Crossref, Google Scholar
• Ben-Tal A , Nemirovski A (2000) Robust solutions of linear programming problems contaminated with uncertain data. Math. Programming 88(3):411–424.Crossref, Google Scholar
• Ben-Tal A , El Ghaoui L , Nemirovski A (2009) Robust Optimization (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Ben-Tal A , Den Hertog D , De Waegenaere A , Melenberg B , Rennen G (2013) Robust solutions of optimization problems affected by uncertain probabilities. Management Sci. 59(2):341–357.Link, Google Scholar
• Bertsimas D , Sim M (2004) The price of robustness. Oper. Res. 52(1):35–53.Link, Google Scholar
• Bertsimas D , Sim M (2006) Tractable approximations to robust conic optimization problems. Math. Programming 107(1–2):5–36.Crossref, Google Scholar
• Bertsimas D , Brown DB , Caramanis C (2011) Theory and applications of robust optimization. SIAM Rev. 53(3):464–501.Crossref, Google Scholar
• Bertsimas D , Gupta V , Kallus N (2018) Data-driven robust optimization. Math. Programming 167(2):235–292.Crossref, Google Scholar
• Bertsimas D , Pachamanova D , Sim M (2004) Robust linear optimization under general norms. Oper. Res. Lett. 32(6):510–516.Crossref, Google Scholar
• Blanchet J , Kang Y (2016) Sample out-of-sample inference based on Wasserstein distance. Preprint, submitted May 4, https://arxiv.org/abs/1605.01340.Google Scholar
• Boyd S , Vandenberghe L (2004) Convex Optimization (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Calafiore GC (2017) Repetitive scenario design. IEEE Trans. Automatic Control 62(3):1125–1137.Crossref, Google Scholar
• Calafiore G , Campi MC (2005) Uncertain convex programs: Randomized solutions and confidence levels. Math. Programming 102(1):25–46.Crossref, Google Scholar
• Calafiore GC , Campi MC (2006) The scenario approach to robust control design. IEEE Trans. Automatic Control 51(5):742–753.Crossref, Google Scholar
• Calafiore GC , El Ghaoui L (2006) On distributionally robust chance-constrained linear programs. J. Optim. Theory Appl. 130(1):1–22.Crossref, Google Scholar
• Calafiore GC , Dabbene F , Tempo R (2011) Research on probabilistic methods for control system design. Automatica 47(7):1279–1293.Crossref, Google Scholar
• Campi MC , Carè A (2013) Random convex programs with L_1-regularization: Sparsity and generalization. SIAM J. Control Optim. 51(5):3532–3557.Crossref, Google Scholar
• Campi MC , Garatti S (2008) The exact feasibility of randomized solutions of uncertain convex programs. SIAM J. Optim. 19(3):1211–1230.Crossref, Google Scholar
• Campi MC , Garatti S (2011) A sampling-and-discarding approach to chance-constrained optimization: Feasibility and optimality. J. Optim. Theory Appl. 148(2):257–280.Crossref, Google Scholar
• Campi MC , Garatti S (2018) Wait-and-judge scenario optimization. Math. Programming 167(1):155–189.Crossref, Google Scholar
• Carè A , Garatti S , Campi MC (2014) FAST: Fast algorithm for the scenario technique. Oper. Res. 62(3):662–671.Link, Google Scholar
• Chamanbaz M , Dabbene F , Tempo R , Venkataramanan V , Wang QG (2016) Sequential randomized algorithms for convex optimization in the presence of uncertainty. IEEE Trans. Automatic Control 61(9):2565–2571.Crossref, Google Scholar
• Charnes A , Cooper WW (1959) Chance-constrained programming. Management Sci. 6(1):73–79.Link, Google Scholar
• Charnes A , Cooper WW , Symonds GH (1958) Cost horizons and certainty equivalents: An approach to stochastic programming of heating oil. Management Sci. 4(3):235–263.Link, Google Scholar
• Chen X , Sim M , Sun P (2007) A robust optimization perspective on stochastic programming. Oper. Res. 55(6):1058–1071.Link, Google Scholar
• Chen W , Sim M , Sun J , Teo CP (2010) From CVaR to uncertainty set: Implications in joint chance-constrained optimization. Oper. Res. 58(2):470–485.Link, Google Scholar
• De Farias DP , Van Roy B (2004) On constraint sampling in the linear programming approach to approximate dynamic programming. Math. Oper. Res. 29(3):462–478.Link, Google Scholar
• Delage E , Ye Y (2010) Distributionally robust optimization under moment uncertainty with application to data-driven problems. Oper. Res. 58(3):595–612.Link, Google Scholar
• Dentcheva D , Lai B , Ruszczyński A (2004) Dual methods for probabilistic optimization problems. Math. Methods Oper. Res. 60(2):331–346.Crossref, Google Scholar
• Donoho DL , Gasko M (1992) Breakdown properties of location estimates based on halfspace depth and projected outlyingness. Ann. Statist. 20(4):1803–1827.Crossref, Google Scholar
• Duchi J , Glynn P , Namkoong H (2016) Statistics of robust optimization: A generalized empirical likelihood approach. Preprint, submitted October 11, https://arxiv.org/abs/1610.03425.Google Scholar
• Durrett R (2010) Probability: Theory and Examples (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• El Ghaoui L , Oks M , Oustry F (2003) Worst-case value-at-risk and robust portfolio optimization: A conic programming approach. Oper. Res. 51(4):543–556.Link, Google Scholar
• El Ghaoui L , Oustry F , Lebret H (1998) Robust solutions to uncertain semidefinite programs. SIAM J. Optim. 9(1):33–52.Crossref, Google Scholar
• Erdoğan E , Iyengar G (2006) Ambiguous chance constrained problems and robust optimization. Math. Programming 107(1–2):37–61.Crossref, Google Scholar
• Goh J , Sim M (2010) Distributionally robust optimization and its tractable approximations. Oper. Res. 58(4, part 1):902–917.Link, Google Scholar
• Goldfarb D , Iyengar G (2003) Robust portfolio selection problems. Math. Oper. Res. 28(1):1–38.Link, Google Scholar
• Gupta V (2019) Near-optimal ambiguity sets for distributionally robust optimization. Management Sci. 65(9):3949–4450.Link, Google Scholar
• Hallin M , Paindaveine D , Šiman M , Wei Y , Serfling R , Zuo Y , Kong L , Mizera I (2010) Multivariate quantiles and multiple-output regression quantiles: From L_1 optimization to halfspace depth. Ann. Statist. 38(2):635–669.Crossref, Google Scholar
• Hanasusanto GA , Roitch V , Kuhn D , Wiesemann W (2015) A distributionally robust perspective on uncertainty quantification and chance constrained programming. Math. Programming 151(1):35–62.Crossref, Google Scholar
• Hanasusanto GA , Roitch V , Kuhn D , Wiesemann W (2017) Ambiguous joint chance constraints under mean and dispersion information. Oper. Res. 65(3):751–767.Link, Google Scholar
• Hastie T , Tibshirani R , Friedman J (2009) Unsupervised learning. The Elements of Statistical Learning: Data Mining, Inference, and Prediction (Springer, New York), 485–585.Crossref, Google Scholar
• Hodges JL (1955) A bivariate sign test. Ann. Math. Statist. 26(3):523–527.Crossref, Google Scholar
• Hong LJ , Yang Y , Zhang L (2011) Sequential convex approximations to joint chance constrained programs: A Monte Carlo approach. Oper. Res. 59(3):617–630.Link, Google Scholar
• Hu Z , Hong LJ , Zhang L (2013) A smooth Monte Carlo approach to joint chance-constrained programs. IIE Trans. 45(7):716–735.Crossref, Google Scholar
• Jiang R , Guan Y (2016) Data-driven chance constrained stochastic program. Math. Programming 158(1–2):291–327.Crossref, Google Scholar
• Lagoa CM , Barmish BR (2002) Distributionally robust Monte Carlo simulation: A tutorial survey. Camacho EF, Basanez L, de la Puente JA, eds. Proc. IFAC World Congress, vol. 35, issue 1, subvolume E (IFAC, New York), 1–12.Google Scholar
• Lam H (2019) Recovering best statistical guarantees via the empirical divergence-based distributionally robust optimization. Oper. Res. 67(4):1090–1105.Abstract, Google Scholar
• Lam H , Mottet C (2017) Tail analysis without parametric models: A worst-case perspective. Oper. Res. 65(6):1696–1711.Link, Google Scholar
• Lam H , Zhou E (2017) The empirical likelihood approach to quantifying uncertainty in sample average approximation. Oper. Res. Lett. 45(4):301–307.Crossref, Google Scholar
• Lejeune MA , Ruszczynski A (2007) An efficient trajectory method for probabilistic production-inventory-distribution problems. Oper. Res. 55(2):378–394.Link, Google Scholar
• Li B , Jiang R , Mathieu JL (2019) Ambiguous risk constraints with moment and unimodality information. Math. Programming 173(1–2):151–192.Crossref, Google Scholar
• Li J , Liu RY (2008) Multivariate spacings based on data depth: I. Construction of nonparametric multivariate tolerance regions. Ann. Statist. 36(3):1299–1323.Crossref, Google Scholar
• Lim AE , Shanthikumar JG , Shen ZM (2006) Model uncertainty, robust optimization, and learning. Johnson MP , Norman B , Secomandi N , eds. Models, Methods, and Applications for Innovative Decision Making, TutORials in Operations Research (INFORMS, Catonsville, MD), 66–94.Link, Google Scholar
• Liu H , Wasserman L , Lafferty JD (2012) Exponential concentration for mutual information estimation with application to forests. Pereira F , Burges CJC , Bottou L , Weinberger KQ , eds. Advances in Neural Information Processing Systems , vol. 25 (Curran Associates, Red Hook, NY), 2537–2545.Google Scholar
• Liu RY (1990) On a notion of data depth based on random simplices. Ann. Statist. 18(1):405–414.Crossref, Google Scholar
• Luedtke J (2014) A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support. Math. Programming 146(1–2):219–244.Crossref, Google Scholar
• Luedtke J , Ahmed S (2008) A sample approximation approach for optimization with probabilistic constraints. SIAM J. Optim. 19(2):674–699.Crossref, Google Scholar
• Luedtke J , Ahmed S , Nemhauser GL (2010) An integer programming approach for linear programs with probabilistic constraints. Math. Programming 122(2):247–272.Crossref, Google Scholar
• Mahalanobis PC (1936) On the generalized distance in statistics. Proc. National Inst. Sci. 2(1):49–55.Google Scholar
• Marandi A , Ben-Tal A , den Hertog D , Melenberg B (2019) Extending the scope of robust quadratic optimization. Preprint, submitted September 4, https://arxiv.org/abs/1909.01762.Google Scholar
• Margellos K , Goulart P , Lygeros J (2014) On the road between robust optimization and the scenario approach for chance constrained optimization problems. IEEE Trans. Automatic Control 59(8):2258–2263.Crossref, Google Scholar
• Miller BL , Wagner HM (1965) Chance constrained programming with joint constraints. Oper. Res. 13(6):930–945.Link, Google Scholar
• Moon K , Hero A (2014) Multivariate f-divergence estimation with confidence. Ghahramani Z , Welling M , Cortes C , eds. Advances in Neural Information Processing Systems , vol. 27 (Curran Associates, Red Hook, NY), 2420–2428.Google Scholar
• Murr MR , Prékopa A (2000) Solution of a product substitution problem using stochastic programming. Uryasev SP , ed. Probabilistic Constrained Optimization (Springer, Boston), 252–271.Crossref, Google Scholar
• Nemirovski A (2003) On tractable approximations of randomly perturbed convex constraints. Proc. 42nd IEEE Conf. Decision Control, vol. 3 (IEEE, New York), 2419–2422.Google Scholar
• Nemirovski A , Shapiro A (2006) Convex approximations of chance constrained programs. SIAM J. Optim. 17(4):969–996.Crossref, Google Scholar
• Pál D , Póczos B , Szepesvári C (2010) Estimation of Rényi entropy and mutual information based on generalized nearest-neighbor graphs. Lafferty JD , Williams CKI , Shawe-Taylor J , Zemel RS , Culotta A, eds. Advances in Neural Information Processing Systems , vol. 23 (Curran Associates, Red Hook, NY), 1849–1857.Google Scholar
• Póczos B , Schneider JG (2012) Nonparametric estimation of conditional information and divergences. Lawrence ND , Girolami M , eds. Proc. 15th Internat. Conf. Artificial Intelligence Statist., vol. 22 (PMLR), 914–923.Google Scholar
• Póczos B , Xiong L , Schneider J (2012) Nonparametric divergence estimation with applications to machine learning on distributions. Preprint, submitted February 14, https://arxiv.org/abs/1202.3758.Google Scholar
• Popescu I (2005) A semidefinite programming approach to optimal-moment bounds for convex classes of distributions. Math. Oper. Res. 30(3):632–657.Link, Google Scholar
• Prékopa A (1970) On probabilistic constrained programming. Kuhn HW, ed. Proc. Princeton Sympos. Math. Programming (Princeton University Press, Princeton, NJ), 113–138.Google Scholar
• Prékopa A (2003) Probabilistic programming. Ruszczynski A , Shapiro A , eds. Stochastic Programming (Elsevier, Amsterdam), 267–351.Crossref, Google Scholar
• Prékopa A , Szántai T (1978) Flood control reservoir system design using stochastic programming. Balinski ML , Lemarechal C , eds. Mathematical Programming in Use (Springer, Berlin), 138–151.Crossref, Google Scholar
• Prékopa A , Rapcsák T , Zsuffa I (1978) Serially linked reservoir system design using stochastic programing. Water Resources Res. 14(4):672–678. Crossref, Google Scholar
• Scarf H (1958) A min-max solution of an inventory problem. Arrow K , Karlin S , Scarf H , eds. Studies in the Mathematical Theory of Inventory and Production (Stanford University Press, Stanford, CA), 201–209.Google Scholar
• Schildbach G , Fagiano L , Morari M (2013) Randomized solutions to convex programs with multiple chance constraints. SIAM J. Optim. 23(4):2479–2501.Crossref, Google Scholar
• Scott CD , Nowak RD (2006) Learning minimum volume sets. J. Machine Learn. Res. 7:665–704.Google Scholar
• Serfling R (2002) Quantile functions for multivariate analysis: Approaches and applications. Statistica Neerlandica 56(2):214–232.Crossref, Google Scholar
• Serfling RJ (2009) Approximation Theorems of Mathematical Statistics (Wiley, New York).Google Scholar
• Shi Y , Zhang J , Letaief KB (2015) Optimal stochastic coordinated beamforming for wireless cooperative networks with CSI uncertainty. IEEE Trans. Signal Processing 63(4):960–973.Crossref, Google Scholar
• Tukey JW (1975) Mathematics and the picturing of data. James RD, ed. Proc. Internat. Congress Mathematicians (Canadian Mathematical Congress, Ottawa), vol. 2, 523–531.Google Scholar
• Tulabandhula T , Rudin C (2014) Robust optimization using machine learning for uncertainty sets. Preprint, submitted July 4, https://arxiv.org/abs/1407.1097.Google Scholar
• Van Parys BP , Goulart PJ , Kuhn D (2016) Generalized Gauss inequalities via semidefinite programming. Math. Programming 156(1–2):271–302.Crossref, Google Scholar
• Wang Q , Kulkarni SR , Verdú S (2009) Divergence estimation for multidimensional densities via k -nearest-neighbor distances. IEEE Trans. Inform. Theory 55(5):2392–2405.Crossref, Google Scholar
• Wang Z , Glynn PW , Ye Y (2016) Likelihood robust optimization for data-driven problems. Comput. Management Sci. 13(2):241–261.Crossref, Google Scholar
• Wiesemann W , Kuhn D , Sim M (2014) Distributionally robust convex optimization. Oper. Res. 62(6):1358–1376.Link, Google Scholar
• Zuo Y (2003) Projection-based depth functions and associated medians. Ann. Statist. 31(5):1460–1490.Crossref, Google Scholar