Optimization Online


Probabilistic guarantees in Robust Optimization

Dimitris Bertsimas (dbertsim***at***mit.edu)
Dick den Hertog (d.denhertog***at***uva.nl)
Jean Pauphilet (jpauphilet***at***london.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, under minimal assumptions on the underlying stochastic process. Namely, we assume that the coordinates of the noise vector are light-tailed (sub-Gaussian) but not necessarily independent. 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 connects geometry of the uncertainty set and a priori probabilistic guarantee. Interestingly, the robust complexity involves the support function of the uncertainty set, which also plays a crucial role in the robust counterpart theory for robust linear and nonlinear optimization. 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., significantly tighter bounds which depend on the resulting robust solution.

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

Category 1: Robust Optimization

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: January 2021

Download: [PDF]

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

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