Conic reformulations for Kullback-Leibler divergence constrained distributionally robust optimization and applications

Authors

DOI:

https://doi.org/10.11121/ijocta.01.2021.001001

Keywords:

Distributionally robust optimization, Stochastic programming, Conic programming, Newsvendor Problem, Uncapacitated Facility Location Problem

Abstract

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 out-of-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.

Author Biography

Burak Kocuk, Sabanci University

Burak Kocuk is an assistant professor at the Industrial Engineering Program, Sabancı University. He ob- tained his BS degrees in Industrial Engineering and Mathematics and MS degree in Industrial Engineering from Boğazi¸ci University. He obtained his Ph.D. degree in Operations Research at the School of Industrial and Systems Engineering, Georgia Institute of Technology. Before joining Sabancı University, he was a postdoctoral fellow at the Tepper School of Business, Carnegie Mellon University. His current research focuses on mixed-integer nonlinear programming and stochastic optimization problems, from both theoretical and methodological aspects.

References

Birge, J. R., & Louveaux, F. (2011). Introduction to stochastic programming. Springer Science & Business Media.

Shapiro, A., Dentcheva, D., & Ruszczynski, A. (2014). Lectures on stochastic program- ming: modeling and theory. Society for Industrial and Applied Mathematics.

Ben-Tal, A., & Nemirovski, A. (2002). Robust optimization–methodology and applications. Mathematical Programming, 92(3), 453-480.

Ben-Tal, A., El Ghaoui, L., & Nemirovski, A. (2009). Robust optimization. Princeton University

Bertsimas, D., Brown, D. B., & Caramanis, C. (2011). Theory and applications of robust optimization. SIAM Review, 53(3), 464-501.

Popescu, I. (2007). Robust mean-covariance solutions for stochastic optimization. Opera- tions Research, 55(1):98–112.

Delage, E. and Ye, Y. (2010). Distributionally robust optimization under moment uncertainty with application to data-driven problems. Operations Research, 58(3):595-612.

Wiesemann, W., Kuhn, D., & Sim, M. (2014). Distributionally robust convex optimization. Operations Research, 62(6), 1358-1376.

Gao, R. & Kleywegt, A. J. (2016). Distributionally robust stochastic optimization with Wasserstein distance. Optimization Online.

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.

Hanasusanto, G. A., & Kuhn, D. (2018). Conic programming reformulations of twostage distributionally robust linear programs over Wasserstein balls. Operations Research, 66(3), 849-869.

Xie, W. (2019). On distributionally robust chance constrained programs with Wasserstein distance. Mathematical Programming, 1- 41.

Ben-Tal, A., Den Hertog, D., DeWaegenaere, A., Melenberg, B., & Rennen, G. (2013). Robust solutions of optimization problems affected by uncertain probabilities. Management Science, 59(2), 341-357.

Klabjan, D., Simchi-Levi, D., & Song, M. (2013). Robust stochastic lot-sizing by means of histograms. Production and Operations Management, 22(3), 691-710.

Jiang, R., & Guan, Y. (2016). Data-driven chance constrained stochastic program. Mathematical Programming, 158(1-2), 291-327.

Yan?ko?lu, I., den Hertog, D., & Kleijnen, J. P. (2016). Robust dual-response optimization. IIE Transactions, 48(3), 298-312.

Lam, H. (2019). Recovering best statistical guarantees via the empirical divergence-based distributionally robust optimization. Operations Research, 67(4), 1090-1105.

Zymler, S., Kuhn, D., & Rustem, B. (2013). Distributionally robust joint chance constraints with second-order moment information. Mathematical Programming, 137(1-2), 167-198.

Yan?ko?lu, I., & den Hertog, D. (2013). Safe approximations of ambiguous chance constraints using historical data. INFORMS Journal on Computing, 25(4), 666-681.

Xie, W., & Ahmed, S. (2018). On deterministic reformulations of distributionally robust joint chance constrained optimization problems. SIAM Journal on Optimization, 28(2), 1151-1182.

Yan?ko?lu, 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.

Nesterov, Y., & Nemirovski, A. (1994). Interior-point polynomial algorithms in convex programming. Society for Industrial and Applied Mathematics.

Serrano, S. A. (2015). Algorithms for unsymmetric cone optimization and an implementation for problems with the exponential cone. PhD Thesis. Stanford University.

Dahl, J., & Andersen, E. D. (2019). A primaldual interior-point algorithm for nonsymmetric exponential-cone optimization. Optimiza- tion Online.

Kullback, S., & Leibler, R. A. (1951). On information and sufficiency. Annals of Mathe- matical Statistics, 22(1), 79-86.

Hu, Z., & Hong, L. J. (2013). Kullback- Leibler divergence constrained distributionally robust optimization. Optimization Online.

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.

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.

MOSEK ApS. (2020). MOSEK optimizer API for Python.

Hanasusanto, G. A., Kuhn, D., Wallace, S. W., & Zymler, S. (2015). Distributionally robust multi-item newsvendor problems with multimodal demand distributions. Mathemat- ical Programming, 152(1-2), 1-32.

Natarajan, K., Sim, M., & Uichanco, J. (2018). Asymmetry and ambiguity in newsvendor models. Management Science, 64(7), 3146-3167.

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.

Lu, M., Ran, L., & Shen, Z. J. M. (2015). Reliable facility location design under uncertain correlated disruptions. Manufacturing & Ser- vice Operations Management, 17(4), 445-455.

Santivanez, J. A., & Carlo, H. J. (2018). Reliable capacitated facility location problem with service levels. EURO Journal on Trans- portation and Logistics, 7(4), 315-341.

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.

Noyan, N., Rudolf, G., & Lejeune, M. (2018). Distributionally robust optimization with decision-dependent ambiguity set. Optimization Online.

MOSEK ApS. (2020). MOSEK modeling cookbook.

Ben-Tal, A., & Nemirovski, A. (2001). Lectures on modern convex optimization: analysis, algorithms, and engineering applications. Society for Industrial and Applied Mathematics.

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 Pro- duction, Stanford University Press, California, 201-209.

Erlenkotter, D. (1978). A dual-based procedure for uncapacitated facility location. Operations Research, 26(6), 992-1009.

Conn, A. R., & Cornuejols, G. (1990). A projection method for the uncapacitated facility location problem. Mathematical Programming, 46(1-3), 273-298.

Fawzi, H., Saunderson, J., & Parrilo, P. A. (2019). Semidefinite approximations of the matrix logarithm. Foundations of Computational Mathematics, 19(2), 259-296.

Luo, F., & Mehrotra, S. (2020). Distributionally robust optimization with decision dependent ambiguity sets. Optimization Letters, 14, 2565-2594.

Downloads

Published

2021-04-19

How to Cite

Kocuk, B. (2021). Conic reformulations for Kullback-Leibler divergence constrained distributionally robust optimization and applications. An International Journal of Optimization and Control: Theories &Amp; Applications (IJOCTA), 11(2), 139–151. https://doi.org/10.11121/ijocta.01.2021.001001

Issue

Section

Research Articles