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

P. Mohajerin Esfahani; Tobias Sutter; John Lygeros

doi:10.1109/TAC.2014.2330702

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

P. Mohajerin Esfahani, Tobias Sutter, John Lygeros

Research output: Contribution to journal › Article › Scientific › peer-review

97 Citations (Scopus)

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.

Original language	English
Article number	6832537
Pages (from-to)	46-58
Journal	IEEE Transactions on Automatic Control
Volume	60
Issue number	1
DOIs	https://doi.org/10.1109/TAC.2014.2330702
Publication status	Published - 2015
Externally published	Yes

Bibliographical note

Op verzoek van PM Esfahani geregistreerd in Pure vanwege een aanvraag in het kader van het H2020-programma. door het ontbreken van de TU Delft affiliatie geen research output van de TU Delft.

Keywords

Chance-constrained programs
performance bound
randomized algorithm
scenario program
semi-infinite programming
uncertain convex optimization

Access to Document

10.1109/TAC.2014.2330702

Cite this

@article{ff8a437f35a24552b5aa00374112c091,

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

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.",

keywords = "Chance-constrained programs, performance bound, randomized algorithm, scenario program, semi-infinite programming, uncertain convex optimization",

author = "{Mohajerin Esfahani}, P. and Tobias Sutter and John Lygeros",

note = "Op verzoek van PM Esfahani geregistreerd in Pure vanwege een aanvraag in het kader van het H2020-programma. door het ontbreken van de TU Delft affiliatie geen research output van de TU Delft. ",

year = "2015",

doi = "10.1109/TAC.2014.2330702",

language = "English",

volume = "60",

pages = "46--58",

journal = "IEEE Transactions on Automatic Control",

issn = "0018-9286",

publisher = "IEEE",

number = "1",

}

TY - JOUR

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

AU - Mohajerin Esfahani, P.

AU - Sutter, Tobias

AU - Lygeros, John

N1 - Op verzoek van PM Esfahani geregistreerd in Pure vanwege een aanvraag in het kader van het H2020-programma. door het ontbreken van de TU Delft affiliatie geen research output van de TU Delft.

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

KW - Chance-constrained programs

KW - performance bound

KW - randomized algorithm

KW - scenario program

KW - semi-infinite programming

KW - uncertain convex optimization

UR - http://www.scopus.com/inward/record.url?scp=84937562834&partnerID=8YFLogxK

U2 - 10.1109/TAC.2014.2330702

DO - 10.1109/TAC.2014.2330702

M3 - Article

AN - SCOPUS:84937562834

SN - 0018-9286

VL - 60

SP - 46

EP - 58

JO - IEEE Transactions on Automatic Control

JF - IEEE Transactions on Automatic Control

IS - 1

M1 - 6832537

ER -

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

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this