On the computational complexity and generalization properties of multi-stage and stage-wise coupled scenario programs

DOI10.1016/J.SYSCONLE.2016.05.009zbMATH Open1344.93062OpenAlexW2414860269MaRDI QIDQ313286FDOQ313286

Kostas Margellos, John Lygeros, Nikolaos Kariotoglou

Publication date: 9 September 2016

Published in: Systems \& Control Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.sysconle.2016.05.009

Recommendations

• Stochastic programming approach to optimization under uncertainty
• On complexity of stochastic programming problems
• Computational complexity of stochastic programming: Monte Carlo sampling approach
• On complexity of multistage stochastic programs
• Scenario Reduction Techniques in Stochastic Programming

zbMATH Keywords

uncertain systemsapproximate dynamic programmingscenario approachrandomized optimization

Mathematics Subject Classification ID

Convex programming (90C25) Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Abstract computational complexity for mathematical programming problems (90C60) Control/observation systems with incomplete information (93C41)

Cites Work

• Robust optimization
• The Scenario Approach to Robust Control Design
• Title not available (Why is that?)
• The Linear Programming Approach to Approximate Dynamic Programming
• The Exact Feasibility of Randomized Solutions of Uncertain Convex Programs
• Handbook of Monte Carlo Methods
• The scenario approach for stochastic model predictive control with bounds on closed-loop constraint violations
• Worst-case violation of sampled convex programs for optimization with uncertainty
• Tractable approximations to robust conic optimization problems
• A Scenario Approach for Non-Convex Control Design
• On the Connection Between Compression Learning and Scenario Based Single-Stage and Cascading Optimization Problems
• Performance Bounds for the Scenario Approach and an Extension to a Class of Non-Convex Programs
• Random Convex Programs
• On the sample complexity of probabilistic analysis and design methods
• Stochastic Optimization on Continuous Domains With Finite-Time Guarantees by Markov Chain Monte Carlo Methods
• The Linear Programming Approach to Reach-Avoid Problems for Markov Decision Processes
• Randomized Solutions to Convex Programs with Multiple Chance Constraints
• Verification of discrete time stochastic hybrid systems: a stochastic reach-avoid decision problem
• On the sample size of random convex programs with structured dependence on the uncertainty

Cited In (2)

• Stochastic reachability of a target tube: theory and computation
• Exploiting structure of chance constrained programs via submodularity

Uses Software

• ECOS

This page was built for publication: On the computational complexity and generalization properties of multi-stage and stage-wise coupled scenario programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q313286)