On feasibility of sample average approximation solutions
From MaRDI portal
Publication:5116547
DOI10.1137/19M1253447zbMATH Open1448.90064arXiv1904.00137OpenAlexW3047112552MaRDI QIDQ5116547FDOQ5116547
Publication date: 18 August 2020
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1904.00137
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
convergencefeasibilitysample average approximation methodexponential rate(multistage) stochastic programming
Cites Work
- Title not available (Why is that?)
- High-Dimensional Probability
- Title not available (Why is that?)
- A two-stage stochastic programming framework for transportation planning in disaster response
- Uncertain convex programs: randomized solutions and confidence levels
- The empirical behavior of sampling methods for stochastic programming
- The sample average approximation method for stochastic discrete optimization
- Asymptotic behavior of statistical estimators and of optimal solutions of stochastic optimization problems
- Monte Carlo bounding techniques for determinig solution quality in stochastic programs
- The sample average approximation method applied to stochastic routing problems: a computational study
- Lectures on stochastic programming. Modeling and theory.
- The Exact Feasibility of Randomized Solutions of Uncertain Convex Programs
- Multistage Stochastic Optimization
- On complexity of stochastic programming problems
- Uniform exponential convergence of sample average random functions under general sampling with applications in stochastic programming
- A note on uniform exponential convergence of sample average approximation of random functions
- Stochastic Convex Programming: Relatively Complete Recourse and Induced Feasibility
- Convex functions and their applications. A contemporary approach
- Combinatorial Set Theory
- Convergence Analysis of Sample Average Approximation of Two-Stage Stochastic Generalized Equations
- Introduction to the Scenario Approach
Cited In (3)
Uses Software
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)
