A general scenario theory for non-convex optimization and decision making

The scenario approach is a general methodology for data-based optimization that has attracted a great deal of attention in the past few years. It prescribes that one collects a record of previous cases (scenarios) from the same setup in which optimization is being conducted and makes a decision which attains optimality for the seen cases. Scenario optimization is by now very well understood for convex problems, where a theory exists that rigorously certifies the generalization properties of the solution, that is, the ability of the solution to perform well in connection to new situations. This theory theoretically supports the scenario methodology and justifies its use. This paper considers non-convex problems. While other contributions in the non-convex setup already exist, we here take a major departure from previous approaches. We suggest that the generalization level is evaluated only after the solution is found and its complexity in terms of the length of a support sub-sample (a notion precisely introduced in this paper) is assessed. As a consequence, the generalization level is stochastic and adjusted case by case to the available scenarios. This fact is key to obtain tig