Non-asymptotic confidence bounds for the optimal value of a stochastic program. (3rd September 2017)

• Record Type: Journal Article
• Authors: Guigues, Vincent; Juditsky, Anatoli; Nemirovski, Arkadi
• Is Part Of: Optimization methods and software. Volume 32:Number 5(2017)
• Page Start: 1033
• Page End: 1058
• Publication Date: 2017-09-03
• Subjects: Sample Average Approximation -- confidence interval -- MinMax Stochastic Optimization -- stochastically constrained problems; 90C15 -- 90C90 -- 90C30; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2017.1350177
• Languages: English
• ISSNs: 1055-6788

Abstract

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 behaviour of the proposed bounds.