When Is Two-Stage Sample Robust Optimization Asymptotically Optimal? A Simple Perspective

Abstract

Two-stage sample robust optimization with linear decision rules is a standard data-driven approach to two-stage stochastic linear programs with unknown distributions. \cite{bertsimas2022two} established that this approach is asymptotically optimal under several conditions. Most are mild, but one is technical, and whether it follows from the others was left as an open question. We resolve this open question through a single geometric feature of the support set: simpleness, the property that every vertex is incident to exactly as many edges as the ambient dimension. When the support set is simple, the technical condition is automatic, and asymptotic optimality holds under the remaining standard assumptions. When the support set is not simple, there exists a problem instance on which the technical condition fails, and asymptotic optimality breaks down. This settles the open question in the negative and yields a sharp dichotomy. The dichotomy has direct practical consequences, since widely used support sets may not be simple. For such supports, we provide a polynomial-time algorithm that certifies the technical condition at any given vertex using only its incident edge directions. Our case study illustrates the effectiveness of our algorithm.