Performance evaluation for distributionally robust optimization with uncertain binary entries

We consider the data-driven stochastic programming problem with binary en tries where the probability of existence of each entry is not known, instead realization of data is provided. We applied the distributionally robust opti mization technique to minimize the worst-case expected cost taken over the ambiguity set based on the Kullback-Leibler divergence. We investigate the out-of-sample performance of the resulting optimal decision and analyze its dependence on the sparsity of the problem.

PDF

___

[1] Bertsimas, D., & Kallus, N. (2020). From predictive to prescriptive analytics. Management Science, 66(3), 1025-1044.
[2] Smith, J. E., & Winkler, R. L. (2006). The optimizer’s curse: Skepticism and postdecision surprise in decision analysis. Management Science, 52(3), 311-322.
[3] Esfahani, P. M., & Kuhn, D. (2018). Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations. Mathematical Programming, 171(1-2), 115-166.
[4] Charnes, A., & Cooper, W. W. (1959). Chance-constrained programming. Management science, 6(1), 73-79.
[5] Soyster, A. L. (1973). Convex programming with set-inclusive constraints and applications to inexact linear programming. Operations research, 21(5), 1154-1157.
[6] Ben-Tal, A., & Nemirovski, A. (1998). Robust convex optimization. Mathematics of operations research, 23(4), 769-805.
[7] Ben-Tal, A., & Nemirovski, A. (1999). Robust solutions of uncertain linear programs. Operations research letters, 25(1), 1-13.
[8] Ben-Tal, A., & Nemirovski, A. (2000). Robust solutions of linear programming problems contaminated with uncertain data. Mathematical programming, 88(3), 411-424.
[9] El Ghaoui, L., & Lebret, H. (1997). Robust solutions to least-squares problems with uncertain data. SIAM Journal on matrix analysis and applications, 18(4), 1035-1064.
[10] El Ghaoui, L., Oustry, F., & Lebret, H. (1998). Robust solutions to uncertain semidefinite programs. SIAM Journal on Optimization, 9(1), 33-52.
[11] Bertsimas, D., & Sim, M. (2004). The price of robustness. Operations research, 52(1), 35-53.
[12] Ben-Tal, A., Den Hertog, D., & Vial, J. P. (2015). Deriving robust counterparts of nonlinear uncertain inequalities. Mathematical programming, 149(1-2), 265-299.
[13] Ben-Tal, A., & Nemirovski, A. (2008). Selected topics in robust convex optimization. Mathematical Programming, 112(1), 125-158.
[14] Ben-Tal, A., El Ghaoui, L., & Nemirovski, A. (2009). Robust optimization (Vol. 28). Princeton University Press.
[15] Gorissen, B. L., Yanıkoglu, ˙I., & den Hertog, D. (2015). A practical guide to robust optimization. Omega, 53, 124-137.
[16] Gabrel, V., Murat, C., & Thiele, A. (2014). Recent advances in robust optimization: An overview. European journal of operational research, 235(3), 471-483.
[17] Sozuer, S., & Thiele, A. C. (2016). The state of robust optimization. In Robustness Analysis in Decision Aiding, Optimization, and Analytics (pp. 89-112). Springer, Cham.
[18] Delage, E., & Iancu, D. A. (2015). Robust multistage decision making. In The Operations Research Revolution (pp. 20-46). INFORMS.
[19] Bandi, C., & Bertsimas, D. (2012). Tractable stochastic analysis in high dimensions via robust optimization. Mathematical programming, 134(1), 23-70.
[20] Nemirovski, A. (2012). On safe tractable approximations of chance constraints. European Journal of Operational Research, 219(3), 707- 718.
[21] Ozmen, A., Weber, G. W., & Karimov, A. (2013). A new robust optimization tool applied on financial data.
[22] Savku, E., & Weber, G. W. (2018). A stochastic maximum principle for a markov regime-switching jump-diffusion model with delay and an application to finance. Journal of Optimization Theory and Applications, 179(2), 696-721.
[23] Kara, G., Ozmen, A., & Weber, G. W. ¨ (2019). Stability advances in robust portfolio optimization under parallelepiped uncertainty. Central European Journal of Operations Research, 27(1), 241-261.
[24] Baltas, I., Xepapadeas, A., & Yannacopoulos, A. N. (2019). Robust control of parabolic stochastic partial differential equations under model uncertainty. European Journal of Control, 46, 1-13.
[25] Sangaiah, A. K., Tirkolaee, E. B., Goli, A., & Dehnavi-Arani, S. (2019). Robust optimization and mixed-integer linear programming model for LNG supply chain planning problem. Soft Computing, 1-21.
26] Bertsimas, D., Gupta, V., & Kallus, N. (2018). Data-driven robust optimization. Mathematical Programming, 167(2), 235-292.
[27] Delage, E., & Ye, Y. (2010). Distributionally robust optimization under moment uncertainty with application to data-driven problems. Operations research, 58(3), 595-612.
[28] Ben-Tal, A., Bhadra, S., Bhattacharyya, C., & Nath, J. S. (2011). Chance constrained uncertain classification via robust optimization. Mathematical programming, 127(1), 145-173.
[29] Dupacova, J., & Kopa, M. (2012). Robustness in stochastic programs with risk constraints. Annals of Operations Research, 200(1), 55-74.
[30] Xu, H., Caramanis, C., & Mannor, S. (2012). A distributional interpretation of robust optimization. Mathematics of Operations Research, 37(1), 95-110.
[31] Zymler, S., Kuhn, D., & Rustem, B. (2013). Distributionally robust joint chance constraints with second-order moment information. Mathematical Programming, 137(1-2), 167-198.
[32] Sun, H., Gao, Z., Szeto, W. Y., Long, J., & Zhao, F. (2014). A distributionally robust joint chance constrained optimization model for the dynamic network design problem under demand uncertainty. Networks and Spatial Economics, 14(3-4), 409-433.
[33] Wiesemann, W., Kuhn, D., & Sim, M. (2014). Distributionally robust convex optimization. Operations Research, 62(6), 1358- 1376.
[34] Ben-Tal, A., Den Hertog, D., De Waegenaere, A., Melenberg, B., & Rennen, G. (2013). Robust solutions of optimization problems affected by uncertain probabilities. Management Science, 59(2), 341-357.
[35] Bayraksan, G., & Love, D. K. (2015). Datadriven stochastic programming using phidivergences. In The Operations Research Revolution (pp. 1-19). INFORMS.
[36] Bertsimas, D., & Van Parys, B. (2017). Bootstrap robust prescriptive analytics. arXiv preprint arXiv:1711.09974.