Performance Bounds for the Scenario Approach and an Extension to a Class of Non-convex Programs

Authors

Peyman Mohajerin Esfahani, Tobias Sutter, John Lygeros

Year

2013

Journal Paper

Algorithm

Scenario Approach

Source

IEEE Transactions on Automatic Control

Identifiers

arXiv 1307.0345 DOI 10.1109/TAC.2014.2330702

Abstract¶

We consider the Scenario Convex Program (SCP) for two classes of optimization problems that are not tractable in general: Robust Convex Programs (RCPs) and Chance-Constrained Programs (CCPs). We establish a probabilistic bridge from the optimal value of SCP to the optimal values of RCP and CCP in which the uncertainty takes values in a general, possibly infinite dimensional, metric space. We then extend our results to a certain class of non-convex problems that includes, for example, binary decision variables. In the process, we also settle a measurability issue for a general class of scenario programs, which to date has been addressed by an assumption. Finally, we demonstrate the applicability of our results on a benchmark problem and a problem in fault detection and isolation.

Summary¶

Refines scenario-approach guarantees by bounding how the sampled scenario program relates to the robust and chance-constrained problem values over general uncertainty spaces. The paper also extends the framework to a class of nonconvex programs, including binary decisions, and resolves a measurability assumption that had often been left implicit in scenario-program analyses.