Skip to main content

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

Probabilistic Guarantees in Robust Optimization

Journal

SIAM Journal on Optimization

Subject

Management Science and Operations

Authors / Editors

Bertsimas D;den Hertog D;Pauphilet J

Biographies

Publication Year

2021

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.

Available on ECCH

No


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