Non-asymptotic confidence bounds for the optimal value of a stochastic program

DOI10.1080/10556788.2017.1350177zbMATH Open1386.90091DBLPjournals/oms/GuiguesJN17arXiv1601.07592OpenAlexW2338512581WikidataQ57392867 ScholiaQ57392867MaRDI QIDQ4594844FDOQ4594844

Authors: Vincent Guigues, Arkadi Nemirovski, Anatoli Juditsky 

Publication date: 24 November 2017

Published in: Optimization Methods \& Software (Search for Journal in Brave)

Abstract: We discuss a general approach to building non-asymptotic confidence bounds for stochastic optimization problems. Our principal contribution is the observation that a Sample Average Approximation of a problem supplies upper and lower bounds for the optimal value of the problem which are essentially better than the quality of the corresponding optimal solutions. At the same time, such bounds are more reliable than "standard" confidence bounds obtained through the asymptotic approach. We also discuss bounding the optimal value of MinMax Stochastic Optimization and stochastically constrained problems. We conclude with a simulation study illustrating the numerical behavior of the proposed bounds.

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

Recommendations

• Simulation-based confidence bounds for two-stage stochastic programs
• Monte Carlo bounding techniques for determinig solution quality in stochastic programs
• Optimality functions in stochastic programming
• scientific article; zbMATH DE number 433030
• scientific article; zbMATH DE number 1163793

zbMATH Keywords

confidence intervalsample average approximationminmax stochastic optimizationstochastically constrained problems

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Nonlinear programming (90C30) Stochastic programming (90C15)

Cited In (27)

• Distributionally robust bottleneck combinatorial problems: uncertainty quantification and robust decision making
• Stochastic Bounds on Distributions of Optimal Value Functions with Applications to PERT, Network Flows and Reliability
• Asymptotic behaviors of semidefinite programming with a covariance perturbation
• Sample average approximation with heavier tails. I: Non-asymptotic bounds with weak assumptions and stochastic constraints
• On Monte-Carlo methods in convex stochastic optimization
• Sample average approximation with heavier tails II: localization in stochastic convex optimization and persistence results for the Lasso
• Consistency of Monte Carlo estimators for risk-neutral PDE-constrained optimization
• Confidence regions of two‐stage stochastic linear complementarity problems
• A central limit theorem and hypotheses testing for risk-averse stochastic programs
• Title not available (Why is that?)
• Confidence regions of stochastic variational inequalities: error bound approach
• Distributionally Favorable Optimization: A Framework for Data-Driven Decision-Making with Endogenous Outliers
• Decentralized and parallel primal and dual accelerated methods for stochastic convex programming problems
• A single cut proximal bundle method for stochastic convex composite optimization
• Logarithmic sample bounds for sample average approximation with capacity- or budget-constraints
• Sample Size Estimates for Risk-Neutral Semilinear PDE-Constrained Optimization
• First order asymptotics of the sample average approximation method to solve risk averse stochastic programs
• Stochastic approximation versus sample average approximation for Wasserstein barycenters
• Approximation of probabilistic constraints in stochastic programming problems with a probability measure kernel
• Variable neighborhood search for a two-stage stochastic programming problem with a quantile criterion
• Better optimization of nonlinear uncertain systems (bonus): a new algorithm for stochastic programming using reweighting through kernel density estimation
• Tractable reformulations of two-stage distributionally robust linear programs over the type-\(\infty\) Wasserstein ball
• High-probability complexity bounds for non-smooth stochastic convex optimization with heavy-tailed noise
• Sample average approximations of strongly convex stochastic programs in Hilbert spaces
• Bias reduction in sample-based optimization
• Title not available (Why is that?)
• Multistep stochastic mirror descent for risk-averse convex stochastic programs based on extended polyhedral risk measures

This page was built for publication: Non-asymptotic confidence bounds for the optimal value of a stochastic program

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