Online Complexity Estimation for Repetitive Scenario Design
This work addresses the need for adaptive sample size selection in scenario optimization, offering a practical solution for repetitive design tasks, though it builds incrementally on existing scenario optimization literature.
The paper tackles the problem of repetitive scenario design by proposing an online method to learn the optimal sample size for achieving a desired risk level, proving its convergence for fixed-complexity problems and demonstrating efficiency on challenging cases like nonconvex constraints and time-varying distributions.
We consider the problem of repetitive scenario design where one has to solve repeatedly a scenario design problem and can adjust the sample size (number of scenarios) to obtain a desired level of risk (constraint violation probability). We propose an approach to learn on the fly the optimal sample size based on observed data consisting in previous scenario solutions and their risk level. Our approach consists in learning a function that represents the pdf (probability density function) of the risk as a function of the sample size. Once this function is known, retrieving the optimal sample size is straightforward. We prove the soundness and convergence of our approach to obtain the optimal sample size for the class of fixed-complexity scenario problems, which generalizes fully-supported convex scenario programs that have been studied extensively in the scenario optimization literature. We also demonstrate the practical efficiency of our approach on a series of challenging repetitive scenario design problems, including non-fixed-complexity problems, nonconvex constraints and time-varying distributions.