Optimization Online


From Data to Decisions: Distributionally Robust Optimization is Optimal

Bart P.G. Van Parys (vanparys***at***mit.edu)
Peyman Mohajerin Esfahani (p.mohajerinesfahani***at***tudelft.nl)
Daniel Kuhn (daniel.kuhn***at***epfl.ch)

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, i.e., a predictor, and an optimizer of the estimated cost function that serves as a near-optimal candidate decision, i.e., 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.

Keywords: Data-Driven Optimization, Distributionally Robust Optimization, Large Deviations Theory, Relative Entropy, Convex Optimization, Observed Fisher Information

Category 1: Stochastic Programming

Category 2: Robust Optimization

Category 3: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )


Download: [PDF]

Entry Submitted: 04/12/2017
Entry Accepted: 04/13/2017
Entry Last Modified: 01/07/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society