Skip to main content

Please enter a keyword and click the arrow to search the site

Probabilistic Guarantees in Robust Optimization


SIAM Journal on Optimization


Management Science and Operations

Authors / Editors

Bertsimas D;den Hertog D;Pauphilet J


Publication Year



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.

Available on ECCH


Select up to 4 programmes to compare

Select one more to compare
subscribe_image_desktop 5949B9BFE33243D782D1C7A17E3345D0

Sign up to receive our latest news and business thinking direct to your inbox