On sample average approximation for two-stage stochastic programs without relatively complete recourse

DOI10.1007/S10107-021-01753-9zbMATH Open1506.90177arXiv1912.13078OpenAlexW2997549357MaRDI QIDQ2097656FDOQ2097656

Authors: Rui Chen, James Luedtke 

Publication date: 14 November 2022

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: We investigate sample average approximation (SAA) for two-stage stochastic programs without relatively complete recourse, i.e., for problems in which there are first-stage feasible solutions that are not guaranteed to have a feasible recourse action. As a feasibility measure of the SAA solution, we consider the "recourse likelihood", which is the probability that the solution has a feasible recourse action. For $epsilonin(0,1)$, we demonstrate that the probability that a SAA solution has recourse likelihood below $1-epsilon$ converges to zero exponentially fast with the sample size. Next, we analyze the rate of convergence of optimal solutions of the SAA to optimal solutions of the true problem for problems with a finite feasible region, such as bounded integer programming problems. For problems with non-finite feasible region, we propose modified "padded" SAA problems and demonstrate in two cases that such problems can yield, with high confidence, solutions that are certain to have a feasible recourse decision. Finally, we conduct a numerical study on a two-stage resource planning problem that illustrates the results, and also suggests there may be room for improvement in some of the theoretical analysis.

Full work available at URL: https://arxiv.org/abs/1912.13078

Recommendations

• Sample average approximation in a two-stage stochastic linear program with quantile criterion
• A note on the sample average approximation method for stochastic mathematical programs with complementarity constraints
• Sample average approximation of expected value constrained stochastic programs
• Accelerated sample average approximation method for two-stage stochastic programming with binary first-stage variables
• Approximations to Stochastic Programs with Complete Recourse
• Convergence analysis of sample average approximation for a class of stochastic nonlinear complementarity problems: from two-stage to multistage
• Regularized sample average approximation approach for two-stage stochastic variational inequalities
• Adaptive sequential sample average approximation for solving two-stage stochastic linear programs
• A note on sample complexity of multistage stochastic programs
• Bounds for Two-Stage Stochastic Programs with Fixed Recourse

zbMATH Keywords

chance constraintsstochastic programmingmixed integer programmingsample average approximation

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Stochastic programming (90C15) Mixed integer programming (90C11)

Cites Work

• High-dimensional probability. An introduction with applications in data science
• Partitioning procedures for solving mixed-variables programming problems
• Large deviations techniques and applications.
• Uncertain convex programs: randomized solutions and confidence levels
• The sample average approximation method for stochastic discrete optimization
• Introduction to stochastic programming.
• A Sample Approximation Approach for Optimization with Probabilistic Constraints
• Lectures on Stochastic Programming
• Stochastic Programs with Fixed Recourse: The Equivalent Deterministic Program
• The Scenario Approach to Robust Control Design
• L-Shaped Linear Programs with Applications to Optimal Control and Stochastic Programming
• On the continuity of the value of a linear program and of related polyhedral-valued multifunctions
• Asymptotic behavior of statistical estimators and of optimal solutions of stochastic optimization problems
• A simulation-based approach to two-stage stochastic programming with recourse
• A branch and bound method for stochastic global optimization
• Monte Carlo bounding techniques for determinig solution quality in stochastic programs
• Adjustable robust solutions of uncertain linear programs
• Decomposition algorithms for two-stage chance-constrained programs
• The Exact Feasibility of Randomized Solutions of Uncertain Convex Programs
• A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support
• A reformulation-linearization technique for solving discrete and continuous nonconvex problems
• Epi‐consistency of convex stochastic programs
• Accelerating the regularized decomposition method for two stage stochastic linear problems
• Computational complexity of stochastic programming problems
• Tractable approximations to robust conic optimization problems
• On complexity of stochastic programming problems
• On the Road Between Robust Optimization and the Scenario Approach for Chance Constrained Optimization Problems
• Global optimization of semi-infinite programs via restriction of the right-hand side
• Convergence analysis of sample average approximation of two-stage stochastic generalized equations
• Optimal selectors for stochastic linear programs
• On feasibility of sample average approximation solutions

Cited In (4)

• Special issue: Global solution of integer, stochastic and nonconvex optimization problems
• General feasibility bounds for sample average approximation via Vapnik-Chervonenkis dimension
• Distributionally Favorable Optimization: A Framework for Data-Driven Decision-Making with Endogenous Outliers
• On feasibility of sample average approximation solutions

This page was built for publication: On sample average approximation for two-stage stochastic programs without relatively complete recourse

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