Randomized solutions to convex programs with multiple chance constraints
From MaRDI portal
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.
Recommendations
- Uncertain convex programs: randomized solutions and confidence levels
- Scenario approximations of chance constraints
- On the sample size of random convex programs with structured dependence on the uncertainty
- Convex Approximations of Chance Constrained Programs
- Exploiting structure of chance constrained programs via submodularity
Cited in
(35)- Uncertain convex programs: randomized solutions and confidence levels
- Data-driven tuning for chance constrained optimization: analysis and extensions
- Risk and complexity in scenario optimization
- Random sampling with removal
- Exploiting structure of chance constrained programs via submodularity
- A randomized relaxation method to ensure feasibility in stochastic control of linear systems subject to state and input constraints
- The wait-and-judge scenario approach applied to antenna array design
- The scenario approach for stochastic model predictive control with bounds on closed-loop constraint violations
- Stochastic MPC with offline uncertainty sampling
- Probabilistic feasibility guarantees for convex scenario programs with an arbitrary number of discarded constraints
- Random algorithms for solving convex inequalities
- Random convex programs
- On the computational complexity and generalization properties of multi-stage and stage-wise coupled scenario programs
- Scenario-based model predictive control for multi-echelon supply chain management
- The Exact Feasibility of Randomized Solutions of Uncertain Convex Programs
- Controller design through random sampling: an example
- Random linear programs with many variables and few constraints
- Consistency of the scenario approach
- Beyond Chance-Constrained Convex Mixed-Integer Optimization: A Generalized Calafiore-Campi Algorithm and the notion of $S$-optimization
- Networked parallel algorithms for robust convex optimization via the scenario approach
- scientific article; zbMATH DE number 7626803 (Why is no real title available?)
- Chance constraint programming problems with parameters as exponential random variable
- Scenario approach for minmax optimization with emphasis on the nonconvex case: positive results and caveats
- Scenario approximations of chance constraints
- Automated driving: the role of forecasts and uncertainty -- a control perspective
- Efficient Scenario Generation for Heavy-Tailed Chance Constrained Optimization
- On Conditional Risk Assessments in Scenario Optimization
- Constrained Monotone Mean-Variance Problem with Random Coefficients
- Chance-constrained programs with convex underlying functions: a bilevel convex optimization perspective
- Enhanced branch-and-bound algorithm for chance constrained programs with Gaussian mixture models
- Parametric scenario optimization under limited data: a distributionally robust optimization view
- Non-convex scenario optimization
- Wait-and-judge scenario optimization
- Distributionally robust optimization
- On the sample size of random convex programs with structured dependence on the uncertainty
This page was built for publication: Randomized solutions to convex programs with multiple chance constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5408228)
