Conic reformulations for Kullback-Leibler divergence constrained distributionally robust optimization and applications
DOI:
https://doi.org/10.11121/ijocta.01.2021.001001Keywords:
Distributionally robust optimization, Stochastic programming, Conic programming, Newsvendor Problem, Uncapacitated Facility Location ProblemAbstract
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.
Downloads
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
How to Cite
Issue
Section
License
Copyright (c) 2021 Burak Kocuk
This work is licensed under a Creative Commons Attribution 4.0 International License.
Articles published in IJOCTA are made freely available online immediately upon publication, without subscription barriers to access. All articles published in this journal are licensed under the Creative Commons Attribution 4.0 International License (click here to read the full-text legal code). This broad license was developed to facilitate open access to, and free use of, original works of all types. Applying this standard license to your work will ensure your right to make your work freely and openly available.
Under the Creative Commons Attribution 4.0 International License, authors retain ownership of the copyright for their article, but authors allow anyone to download, reuse, reprint, modify, distribute, and/or copy articles in IJOCTA, so long as the original authors and source are credited.
The readers are free to:
- Share — copy and redistribute the material in any medium or format
- Adapt — remix, transform, and build upon the material
- for any purpose, even commercially.
- The licensor cannot revoke these freedoms as long as you follow the license terms.
under the following terms:
- Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
This work is licensed under a Creative Commons Attribution 4.0 International License.
