IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v67y2021i6p3387-3402.html
   My bibliography  Save this article

From Data to Decisions: Distributionally Robust Optimization Is Optimal

Author

Listed:
  • Bart P. G. Van Parys

    (Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139)

  • Peyman Mohajerin Esfahani

    (Delft Center for Systems and Control, Technische Universiteit Delft, 2628 CD Delft, Netherlands)

  • Daniel Kuhn

    (Risk Analytics and Optimization Chair, Ecole Polytechnique Fédérale de Lausanne, CH-1015 Lausanne, Switzerland)

Abstract

We study stochastic programs where the decision maker cannot observe the distribution of the exogenous uncertainties but has access to a finite set of independent samples from this distribution. In this setting, the goal is to find a procedure that transforms the data to an estimate of the expected cost function under the unknown data-generating distribution, that is, a predictor , and an optimizer of the estimated cost function that serves as a near-optimal candidate decision, that is, a prescriptor . As functions of the data, predictors and prescriptors constitute statistical estimators. We propose a meta-optimization problem to find the least conservative predictors and prescriptors subject to constraints on their out-of-sample disappointment. The out-of-sample disappointment quantifies the probability that the actual expected cost of the candidate decision under the unknown true distribution exceeds its predicted cost. Leveraging tools from large deviations theory, we prove that this meta-optimization problem admits a unique solution: The best predictor-prescriptor-pair is obtained by solving a distributionally robust optimization problem over all distributions within a given relative entropy distance from the empirical distribution of the data.

Suggested Citation

  • Bart P. G. Van Parys & Peyman Mohajerin Esfahani & Daniel Kuhn, 2021. "From Data to Decisions: Distributionally Robust Optimization Is Optimal," Management Science, INFORMS, vol. 67(6), pages 3387-3402, June.
    • Handle: RePEc:inm:ormnsc:v:67:y:2021:i:6:p:3387-3402
    DOI: 10.1287/mnsc.2020.3678
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.2020.3678
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.2020.3678?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Hailin Sun & Huifu Xu, 2016. "Convergence Analysis for Distributionally Robust Optimization and Equilibrium Problems," Mathematics of Operations Research, INFORMS, vol. 41(2), pages 377-401, May.
    2. Vishal Gupta, 2019. "Near-Optimal Bayesian Ambiguity Sets for Distributionally Robust Optimization," Management Science, INFORMS, vol. 65(9), pages 4242-4260, September.
    3. Panos Parpas & Berk Ustun & Mort Webster & Quang Kha Tran, 2015. "Importance Sampling in Stochastic Programming: A Markov Chain Monte Carlo Approach," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 358-377, May.
    4. Henry Lam, 2016. "Robust Sensitivity Analysis for Stochastic Systems," Mathematics of Operations Research, INFORMS, vol. 41(4), pages 1248-1275, November.
    5. Aharon Ben-Tal & Dick den Hertog & Anja De Waegenaere & Bertrand Melenberg & Gijs Rennen, 2013. "Robust Solutions of Optimization Problems Affected by Uncertain Probabilities," Management Science, INFORMS, vol. 59(2), pages 341-357, April.
    6. James E. Smith & Robert L. Winkler, 2006. "The Optimizer's Curse: Skepticism and Postdecision Surprise in Decision Analysis," Management Science, INFORMS, vol. 52(3), pages 311-322, March.
    7. Erick Delage & Yinyu Ye, 2010. "Distributionally Robust Optimization Under Moment Uncertainty with Application to Data-Driven Problems," Operations Research, INFORMS, vol. 58(3), pages 595-612, June.
    8. Georg Pflug & David Wozabal, 2007. "Ambiguity in portfolio selection," Quantitative Finance, Taylor & Francis Journals, vol. 7(4), pages 435-442.
    9. A. Ahmadi-Javid, 2012. "Entropic Value-at-Risk: A New Coherent Risk Measure," Journal of Optimization Theory and Applications, Springer, vol. 155(3), pages 1105-1123, December.
    10. Henry Lam, 2019. "Recovering Best Statistical Guarantees via the Empirical Divergence-Based Distributionally Robust Optimization," Operations Research, INFORMS, vol. 67(4), pages 1090-1105, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Dimitris Bertsimas & Shimrit Shtern & Bradley Sturt, 2023. "A Data-Driven Approach to Multistage Stochastic Linear Optimization," Management Science, INFORMS, vol. 69(1), pages 51-74, January.
    2. Phan-Anh-Huy Nguyen & Ping-Yu Hsu, 2023. "Robust and High-Accessibility Ranking Method for Crowdsourcing-Based Decision Making," Group Decision and Negotiation, Springer, vol. 32(5), pages 1211-1236, October.
    3. Wei Zhang & Kai Wang & Alexandre Jacquillat & Shuaian Wang, 2023. "Optimized Scenario Reduction: Solving Large-Scale Stochastic Programs with Quality Guarantees," INFORMS Journal on Computing, INFORMS, vol. 35(4), pages 886-908, July.
    4. Xiaotie Chen & David L. Woodruff, 2023. "Software for Data-Based Stochastic Programming Using Bootstrap Estimation," INFORMS Journal on Computing, INFORMS, vol. 35(6), pages 1218-1224, November.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Jose Blanchet & Karthyek Murthy, 2019. "Quantifying Distributional Model Risk via Optimal Transport," Mathematics of Operations Research, INFORMS, vol. 44(2), pages 565-600, May.
    2. Maximilian Blesch & Philipp Eisenhauer, 2023. "Robust Decision-Making under Risk and Ambiguity," Rationality and Competition Discussion Paper Series 463, CRC TRR 190 Rationality and Competition.
    3. Aleksandrina Goeva & Henry Lam & Huajie Qian & Bo Zhang, 2019. "Optimization-Based Calibration of Simulation Input Models," Operations Research, INFORMS, vol. 67(5), pages 1362-1382, September.
    4. Zhi Chen & Melvyn Sim & Huan Xu, 2019. "Distributionally Robust Optimization with Infinitely Constrained Ambiguity Sets," Operations Research, INFORMS, vol. 67(5), pages 1328-1344, September.
    5. Jun-ya Gotoh & Michael Jong Kim & Andrew E. B. Lim, 2020. "Worst-case sensitivity," Papers 2010.10794, arXiv.org.
    6. Shunichi Ohmori, 2021. "A Predictive Prescription Using Minimum Volume k -Nearest Neighbor Enclosing Ellipsoid and Robust Optimization," Mathematics, MDPI, vol. 9(2), pages 1-16, January.
    7. L. Jeff Hong & Zhiyuan Huang & Henry Lam, 2021. "Learning-Based Robust Optimization: Procedures and Statistical Guarantees," Management Science, INFORMS, vol. 67(6), pages 3447-3467, June.
    8. Vishal Gupta, 2019. "Near-Optimal Bayesian Ambiguity Sets for Distributionally Robust Optimization," Management Science, INFORMS, vol. 65(9), pages 4242-4260, September.
    9. Ran Ji & Miguel A. Lejeune, 2021. "Data-Driven Optimization of Reward-Risk Ratio Measures," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 1120-1137, July.
    10. Steffen Rebennack, 2022. "Data-driven stochastic optimization for distributional ambiguity with integrated confidence region," Journal of Global Optimization, Springer, vol. 84(2), pages 255-293, October.
    11. Ren, Ke & Bidkhori, Hoda, 2023. "A study of data-driven distributionally robust optimization with incomplete joint data under finite support," European Journal of Operational Research, Elsevier, vol. 305(2), pages 754-765.
    12. Postek, K.S. & den Hertog, D. & Melenberg, B., 2015. "Computationally Tractable Counterparts of Distributionally Robust Constraints on Risk Measures (revision of CentER DP 2014-031)," Discussion Paper 2015-047, Tilburg University, Center for Economic Research.
    13. Luo, Fengqiao & Mehrotra, Sanjay, 2019. "Decomposition algorithm for distributionally robust optimization using Wasserstein metric with an application to a class of regression models," European Journal of Operational Research, Elsevier, vol. 278(1), pages 20-35.
    14. Andrew J. Keith & Darryl K. Ahner, 2021. "A survey of decision making and optimization under uncertainty," Annals of Operations Research, Springer, vol. 300(2), pages 319-353, May.
    15. Yannan Chen & Hailin Sun & Huifu Xu, 2021. "Decomposition and discrete approximation methods for solving two-stage distributionally robust optimization problems," Computational Optimization and Applications, Springer, vol. 78(1), pages 205-238, January.
    16. Haolin Ruan & Zhi Chen & Chin Pang Ho, 2023. "Adjustable Distributionally Robust Optimization with Infinitely Constrained Ambiguity Sets," INFORMS Journal on Computing, INFORMS, vol. 35(5), pages 1002-1023, September.
    17. Jun-Ya Gotoh & Michael Jong Kim & Andrew E. B. Lim, 2017. "Calibration of Distributionally Robust Empirical Optimization Models," Papers 1711.06565, arXiv.org, revised May 2020.
    18. Corlu, Canan G. & Akcay, Alp & Xie, Wei, 2020. "Stochastic simulation under input uncertainty: A Review," Operations Research Perspectives, Elsevier, vol. 7(C).
    19. Zhu, Zhicheng & Xiang, Yisha & Zhao, Ming & Shi, Yue, 2023. "Data-driven remanufacturing planning with parameter uncertainty," European Journal of Operational Research, Elsevier, vol. 309(1), pages 102-116.
    20. Guanglin Xu & Samuel Burer, 2018. "A data-driven distributionally robust bound on the expected optimal value of uncertain mixed 0-1 linear programming," Computational Management Science, Springer, vol. 15(1), pages 111-134, January.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:67:y:2021:i:6:p:3387-3402. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.