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

Abstract

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.