Optimization Online


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

Vincent Guigues (vguigues***at***fgv.br)
Anatoli Juditsky (anatoli.juditsky***at***imag.fr)
Arkadi Nemirovski (nemirovs***at***isye.gatech.edu)

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 small simulation study illustrating the numerical behavior of the proposed bounds.

Keywords: Sample Average Approximation; confidence interval; MinMax Stochastic Optimization; stochastically constrained problems

Category 1: Stochastic Programming


Download: [PDF]

Entry Submitted: 01/27/2016
Entry Accepted: 01/27/2016
Entry Last Modified: 12/10/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society