Conic reformulations for Kullback-Leibler divergence constrained distributionally robust optimization and applications
In this paper, we consider a Kullback-Leibler divergence constrained distributionally robust optimization model. This model considers an ambiguity set that consists of all distributions whose Kullback-Leibler divergence to an empirical distribution is bounded. Utilizing the fact that this divergence measure has an exponential cone representation, we obtain the robust counterpart of the Kullback-Leibler divergence constrained distributionally robust optimization problem as a dual exponential cone constrained program under mild assumptions on the underlying optimization problem. The resulting conic reformulation of the original optimization problem can be directly solved by a commercial conic programming solver. We specialize our generic formulation to two classical optimization problems, namely, the Newsvendor Problem and the Uncapacitated Facility Location Problem. Our computational study in an outof-sample analysis shows that the solutions obtained via the distributionally robust optimization approach yield significantly better performance in terms of the dispersion of the cost realizations while the central tendency deteriorates only slightly compared to the solutions obtained by stochastic programming.
[1] Birge, J. R., & Louveaux, F. (2011). Introduction to stochastic programming. Springer Science & Business Media.
[2] Shapiro, A., Dentcheva, D., & Ruszczy´nski, A. (2014). Lectures on stochastic programming: modeling and theory. Society for Industrial and Applied Mathematics.
[3] Ben-Tal, A., & Nemirovski, A. (2002). Robust optimization–methodology and applications. Mathematical Programming, 92(3), 453-480.
[4] Ben-Tal, A., El Ghaoui, L., & Nemirovski, A. (2009). Robust optimization. Princeton University Press.
[5] Bertsimas, D., Brown, D. B., & Caramanis, C. (2011). Theory and applications of robust optimization. SIAM Review, 53(3), 464-501.
[6] Popescu, I. (2007). Robust mean-covariance solutions for stochastic optimization. Operations Research, 55(1), 98–112.
[7] Delage, E. and Ye, Y. (2010). Distributionally robust optimization under moment uncertainty with application to data-driven problems. Operations Research, 58(3), 595-612.
[8] Wiesemann, W., Kuhn, D., & Sim, M. (2014). Distributionally robust convex optimization. Operations Research, 62(6), 1358-1376.
[9] Gao, R. & Kleywegt, A. J. (2016). Distributionally robust stochastic optimization with Wasserstein distance. Optimization Online.
[10] Mohajerin Esfahani, P. & Kuhn, D. (2018). Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations. Mathematical Programming, 171(1), 115-166.
[11] Hanasusanto, G. A., & Kuhn, D. (2018). Conic programming reformulations of twostage distributionally robust linear programs over Wasserstein balls. Operations Research, 66(3), 849-869.
[12] Xie, W. (2019). On distributionally robust chance constrained programs with Wasserstein distance. Mathematical Programming, 1- 41.
[13] 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.
[14] Klabjan, D., Simchi-Levi, D., & Song, M. (2013). Robust stochastic lot-sizing by means of histograms. Production and Operations Management, 22(3), 691-710.
[15] Jiang, R., & Guan, Y. (2016). Data-driven chance constrained stochastic program. Mathematical Programming, 158(1-2), 291-327.
[16] Yanıko˘glu, I., den Hertog, D., & Kleijnen, J. ˙ P. (2016). Robust dual-response optimization. IIE Transactions, 48(3), 298-312.
[17] Lam, H. (2019). Recovering best statistical guarantees via the empirical divergence-based distributionally robust optimization. Operations Research, 67(4), 1090-1105.
[18] Zymler, S., Kuhn, D., & Rustem, B. (2013). Distributionally robust joint chance constraints with second-order moment information. Mathematical Programming, 137(1-2), 167-198.
[19] Yanıko˘glu, I., & den Hertog, D. (2013). ˙ Safe approximations of ambiguous chance constraints using historical data. INFORMS Journal on Computing, 25(4), 666-681.
[20] Xie, W., & Ahmed, S. (2018). On deterministic reformulations of distributionally robustjoint chance constrained optimization problems. SIAM Journal on Optimization, 28(2), 1151-1182.
[21] Yanıko˘glu, I. (2019). Robust reformulations ˙ of ambiguous chance constraints with discrete probability distributions. An International Journal of Optimization and Control: Theories & Applications, 9(2), 236-252.
[22] Nesterov, Y., & Nemirovski, A. (1994). Interior-point polynomial algorithms in convex programming. Society for Industrial and Applied Mathematics.
[23] Serrano, S. A. (2015). Algorithms for unsymmetric cone optimization and an implementation for problems with the exponential cone. PhD Thesis. Stanford University.
[24] Dahl, J., & Andersen, E. D. (2019). A primaldual interior-point algorithm for nonsymmetric exponential-cone optimization. Optimization Online.
[25] Kullback, S., & Leibler, R. A. (1951). On information and sufficiency. Annals of Mathematical Statistics, 22(1), 79-86.
[26] Hu, Z., & Hong, L. J. (2013). KullbackLeibler divergence constrained distributionally robust optimization. Optimization Online.
[27] Chen, Y., Guo, Q., Sun, H., Li, Z., Wu, W., & Li, Z. (2018). A distributionally robust optimization model for unit commitment based on Kullback–Leibler divergence. IEEE Transactions on Power Systems, 33(5), 5147-5160.
[28] Li, Z., Wu, W., Zhang, B., & Tai, X. (2018). Kullback–Leibler divergence-based distributionally robust optimisation model for heat pump day-ahead operational schedule to improve PV integration. IET Generation, Transmission & Distribution, 12(13), 3136- 3144.
[29] MOSEK ApS. (2020). MOSEK optimizer API for Python.
[30] Hanasusanto, G. A., Kuhn, D., Wallace, S. W., & Zymler, S. (2015). Distributionally robust multi-item newsvendor problems with multimodal demand distributions. Mathematical Programming, 152(1-2), 1-32.
[31] Natarajan, K., Sim, M., & Uichanco, J. (2018). Asymmetry and ambiguity in newsvendor models. Management Science, 64(7), 3146-3167.
[32] Lee, S., Kim, H., & Moon, I. (2020). A data-driven distributionally robust newsvendor model with a Wasserstein ambiguity set. Journal of the Operational Research Society, 1-19.
[33] Lu, M., Ran, L., & Shen, Z. J. M. (2015). Reliable facility location design under uncertain correlated disruptions. Manufacturing & Service Operations Management, 17(4), 445-455.
[34] Santiv´a˜nez, J. A., & Carlo, H. J. (2018). Reliable capacitated facility location problem with service levels. EURO Journal on Transportation and Logistics, 7(4), 315-341.
[35] Basciftci, B., Ahmed, S., & Shen, S. (2020). Distributionally robust facility location problem under decision-dependent stochastic demand. European Journal of Operational Research. doi:10.1016/j.ejor.2020.11.002.
[36] Noyan, N., Rudolf, G., & Lejeune, M. (2018). Distributionally robust optimization with decision-dependent ambiguity set. Optimization Online.
[37] MOSEK ApS. (2020). MOSEK modeling cookbook.
[38] Ben-Tal, A., & Nemirovski, A. (2001). Lectures on modern convex optimization: analysis, algorithms, and engineering applications. Society for Industrial and Applied Mathematics.
[39] Scarf, H. A. (1958). A min-max solution of an inventory problem. In: K. J. Arrow, S. Karlin and H. E. Scarf, Eds., Studies in the Mathematical Theory of Inventory and Production, Stanford University Press, California, 201-209.
[40] Erlenkotter, D. (1978). A dual-based procedure for uncapacitated facility location. Operations Research, 26(6), 992-1009.
[41] Conn, A. R., & Cornuejols, G. (1990). A projection method for the uncapacitated facility location problem. Mathematical Programming, 46(1-3), 273-298.
[42] Fawzi, H., Saunderson, J., & Parrilo, P. A. (2019). Semidefinite approximations of the matrix logarithm. Foundations of Computational Mathematics, 19(2), 259-296.
[43] Luo, F., & Mehrotra, S. (2020). Distributionally robust optimization with decision dependent ambiguity sets. Optimization Letters, 14, 2565-2594.