Randomized Solutions to Convex Programs with Multiple Chance Constraints

Abstract

The scenario-based optimization approach (`scenario approach') provides an intuitive way of approximating the solution to chance-constrained optimization programs, based on finding the optimal solution under a finite number of sampled outcomes of the uncertainty (`scenarios'). A key merit of this approach is that it neither assumes knowledge of the uncertainty set, as it is common in robust optimization, nor of its probability distribution, as it is usually required in stochastic optimization. Moreover, the scenario approach is computationally efficient as its solution is based on a deterministic optimization program that is canonically convex, even when the original chance-constrained problem is not. Recently, researchers have obtained theoretical foundations for the scenario approach, providing a direct link between the number of scenarios and bounds on the constraint violation probability. These bounds are tight in the general case of an uncertain optimization problem with a single chance constraint. However, this paper shows that these bounds can be improved in situations where the constraints have a limited `support rank', a new concept that is introduced for the first time. This property is typically found in a large number of practical applications---most importantly, if the problem originally contains multiple chance constraints (e.g. multi-stage uncertain decision problems), or if a chance constraint belongs to a special class of constraints (e.g. linear or quadratic constraints). In these cases the quality of the scenario solution is improved while the same bound on the constraint violation probability is maintained, and also the computational complexity is reduced.

This manuscript is the preprint of a paper submitted to the SIAM Journal on Optimization and it is subject to SIAM copyright. SIAM maintains the sole rights of distribution or publication of the work in all forms and media. If accepted, the copy of record will be available at http://www.siam.org

Cited by in corpus (19)

• The Scenario Approach for Stochastic Model Predictive Control with Bounds on Closed-Loop Constraint Violations
• On the Sample Size of Random Convex Programs with Structured Dependence on the Uncertainty (Extended Version)
• A scenario approach for non-convex control design
• Particle Model Predictive Control: Tractable Stochastic Nonlinear Output-Feedback MPC
• Probably Approximately Correct Nash Equilibrium Learning
• Scenario Model Predictive Control for Data-based Energy Management in Plug-in Hybrid Electric Vehicles
• Data-driven Decision Making with Probabilistic Guarantees (Part 1): A Schematic Overview of Chance-constrained Optimization
• From Uncertainty Data to Robust Policies for Temporal Logic Planning
• A Posteriori Probabilistic Bounds of Convex Scenario Programs with Validation Tests
• Exploiting structure of chance constrained programs via submodularity
• Chance-constrained optimization with tight confidence bounds
• Near-Optimal Rapid MPC using Neural Networks: A Primal-Dual Policy Learning Framework
• On the connection between compression learning and scenario based optimization
• Combating Conservativeness in Data-Driven Optimization under Uncertainty: A Solution Path Approach
• On the computational complexity and generalization properties of multi-stage and recursive scenario programs
• A priori data-driven robustness guarantees on strategic deviations from generalised Nash equilibria
• Parametric Scenario Optimization under Limited Data: A Distributionally Robust Optimization View
• Scenario-Based Trajectory Optimization in Uncertain Dynamic Environments
• Convexity and monotonicity in nonlinear optimal control under uncertainty