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

Journal article (2015)

Authors

P. Mohajerin Esfahani ETH Zürich

Tobias Sutter ETH Zürich

John Lygeros ETH Zürich

Chance-constrained programs Performance bound Randomized algorithm Scenario program Semi-infinite programming Uncertain convex optimization

To reference this document use:

http://resolver.tudelft.nl/uuid:ff8a437f-35a2-4552-b5aa-00374112c091

More Info

expand_more

Published Date

2015

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

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.