On feasibility of sample average approximation solutions
From MaRDI portal
Publication:5116547
Abstract: When there are infinitely many scenarios, the current studies of two-stage stochastic programming problems rely on the relatively complete recourse assumption. However, such assumption can be unrealistic for many real-world problems. This motivates us to study general stochastic programming problems where the sample average approximation (SAA) solutions are not necessarily feasible. When the problems are convex and the true solutions lie in the interior of feasible solutions, we show the portion of infeasible SAA solutions decays exponentially as the sample size increases. We also study functions with chain-constrained domain, and show the portion of SAA solutions having a low degree of feasibility decays exponentially as the sample size increases. This result is then extended to multistage stochastic programming.
Recommendations
- On sample average approximation for two-stage stochastic programs without relatively complete recourse
- General feasibility bounds for sample average approximation via Vapnik-Chervonenkis dimension
- Sample average approximation of expected value constrained stochastic programs
- Robust Stochastic Approximation Approach to Stochastic Programming
- Sample average approximation methods for a class of stochastic variational inequality problems
Cites work
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 1324223 (Why is no real title available?)
- A note on uniform exponential convergence of sample average approximation of random functions
- A two-stage stochastic programming framework for transportation planning in disaster response
- Asymptotic behavior of statistical estimators and of optimal solutions of stochastic optimization problems
- Combinatorial Set Theory
- Convergence analysis of sample average approximation of two-stage stochastic generalized equations
- Convex functions and their applications. A contemporary approach
- High-dimensional probability. An introduction with applications in data science
- Introduction to the Scenario Approach
- Lectures on stochastic programming. Modeling and theory.
- Monte Carlo bounding techniques for determinig solution quality in stochastic programs
- Multistage stochastic optimization
- On complexity of stochastic programming problems
- Stochastic Convex Programming: Relatively Complete Recourse and Induced Feasibility
- The Exact Feasibility of Randomized Solutions of Uncertain Convex Programs
- The empirical behavior of sampling methods for stochastic programming
- The sample average approximation method applied to stochastic routing problems: a computational study
- The sample average approximation method for stochastic discrete optimization
- Uncertain convex programs: randomized solutions and confidence levels
- Uniform exponential convergence of sample average random functions under general sampling with applications in stochastic programming
Cited in
(4)- Sample average approximation with sparsity-inducing penalty for high-dimensional stochastic programming
- Sampling Constraints in Average: The Example of Hugoniot Curves
- General feasibility bounds for sample average approximation via Vapnik-Chervonenkis dimension
- On sample average approximation for two-stage stochastic programs without relatively complete recourse
This page was built for publication: On feasibility of sample average approximation solutions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5116547)
