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

DOI10.1016/J.SYSCONLE.2016.05.009MaRDI QIDQ313286zbMATH OpenOpenAlexFDO

Authors Nikolaos Kariotoglou, Kostas Margellos, John Lygeros

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

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)

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

Cites work

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

Cited in

(2)

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

Describes a project that uses

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)