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.

19 pages, revised version

References in corpus (1)

• A Tractable Fault Detection and Isolation Approach for Nonlinear Systems with Probabilistic Performance

Cited by in corpus (21)

• Optimization under Uncertainty in the Era of Big Data and Deep Learning: When Machine Learning Meets Mathematical Programming
• On the Sample Size of Random Convex Programs with Structured Dependence on the Uncertainty (Extended Version)
• A Tractable Fault Detection and Isolation Approach for Nonlinear Systems with Probabilistic Performance
• A scenario approach for non-convex control design
• The scenario approach meets uncertain variational inequalities and game theory
• Sampling-based Reachability Analysis: A Random Set Theory Approach with Adversarial Sampling
• Safe Motion Planning against Multimodal Distributions based on a Scenario Approach
• From Uncertainty Data to Robust Policies for Temporal Logic Planning
• Exploiting structure of chance constrained programs via submodularity
• From Infinite to Finite Programs: Explicit Error Bounds with Applications to Approximate Dynamic Programming
• On the computational complexity and generalization properties of multi-stage and recursive scenario programs
• Scenario approach for minmax optimization with emphasis on the nonconvex case: positive results and caveats
• Dynamic Anomaly Detection with High-fidelity Simulators: A Convex Optimization Approach
• A Randomized Nonlinear Rescaling Method in Large-Scale Constrained Convex Optimization
• Corporative Stochastic Approximation with Random Constraint Sampling for Semi-Infinite Programming
• Uniform Risk Bounds for Learning with Dependent Data Sequences
• Probability Distribution-free General Scenario Programming
• A Sequential Learning Algorithm for Probabilistically Robust Controller Tuning
• Column-Randomized Linear Programs: Performance Guarantees and Applications
• Convex programming in optimal control and information theory
• An Inexact Primal-Dual Algorithm for Semi-Infinite Programming