Probabilistic Guarantees in Robust Optimization

Bertsimas, D, den Heretog, D and Pauphilet, J (2021) Probabilistic Guarantees in Robust Optimization. SIAM Journal on Optimization, 31 (4). pp. 2893-2920. ISSN 1052-6234 OPEN ACCESS


We develop a general methodology for deriving 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 analogue of the Rademacher and Gaussian complexities encountered in high-dimensional statistics, and which connects the geometry of the uncertainty set with an 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. Our methodology recovers most of the results available in the related literature using first principles and extends them to new uncertainty sets and nonlinear constraints. We also derive improved a posteriori bounds, i.e., significantly tighter bounds which depend on the resulting robust solution.

More Details

Item Type: Article
Subject Areas: Management Science and Operations
Additional Information:

© 2021, Society for Industrial and Applied Mathematics

Date Deposited: 23 Nov 2021 10:28
Date of first compliant deposit: 23 Nov 2021
Last Modified: 21 May 2024 01:24

Export and Share


Accepted Version - Text


View details on Dimensions' website

Downloads from LBS Research Online

View details

Actions (login required)

Edit Item Edit Item