Optimization Online


Probabilistic guarantees in Robust Optimization

Dimitris Bertsimas(dbertsim***at***mit.edu)
Dick den Hertog(d.denhertog***at***uvt.nl)
Jean Pauphilet(jpauph***at***mit.edu)

Abstract: We develop a general methodology to derive probabilistic guarantees for solutions of robust optimization problems. Our analysis applies broadly to any convex compact uncertainty set and to any constraint affected by uncertainty in a concave manner. In particular, we introduce the notion of robust complexity of an uncertainty set, which is a robust analog of the Rademacher or Gaussian complexity encountered in high-dimensional statistics, and which drives our results. For a variety of uncertainty sets of practical interest, we are able to compute it in closed form or derive valid approximations. To the best of our knowledge, our methodology recovers and extends all the results available in the literature. We also derive improved a posteriori bounds, i.e., bounds which depend on the resulting robust solution. Besides being significantly tighter than a priori bounds, a posteriori bounds can notably be computed for any general convex uncertainty set.

Keywords: Robust optimization; Support function; Uncertainty set; Concentration inequality

Category 1: Robust Optimization

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: September 2019

Download: [PDF]

Entry Submitted: 09/19/2019
Entry Accepted: 09/19/2019
Entry Last Modified: 09/19/2019

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