On the computational complexity and generalization properties of multi-stage and recursive scenario programs
arXiv:1412.4203
Abstract
We discuss the computational complexity and feasibility properties of scenario based techniques for uncertain optimization programs. We consider different solution alternatives ranging from the standard scenario approach to recursive variants, and compare feasibility as a function of the total computation burden. We identify trade-offs between the different methods depending on the problem structure and the desired probability of constraint satisfaction. Our motivation for this work stems from the applicability and complexity reduction when making decisions by means of recursive algorithms. We illustrate our results on an example from the area of approximate dynamic programming
References in corpus (5)
- The Scenario Approach for Stochastic Model Predictive Control with Bounds on Closed-Loop Constraint Violations
- Performance Bounds for the Scenario Approach and an Extension to a Class of Non-convex Programs
- Randomized Solutions to Convex Programs with Multiple Chance Constraints
- Stochastic optimization on continuous domains with finite-time guarantees by Markov chain Monte Carlo methods
- On the connection between compression learning and scenario based optimization