Robust non-convex optimization with structured constraints: complexity bounds and guaranteed reliability level of the scenario solution

In this paper, we show how a separable structure between decision and uncertain variables in the constraints of non-convex robust scenario optimization problems can be exploited to bound the complexity associated with the solution. The resulting bounds are easily computable, and can be solved prior to determining the solution to the non-convex scenario program. Leveraging the scenario approach theory, these bounds can be used to find suitable certifications of the risk (a posteriori, once the scenarios are collected). Furthermore, this result can be exploited to determine the size of the scenario sample necessary to provide a user-chosen reliability level of the solution, for which we discuss both a one-shot and an iterative resolution approach.