The sample average approximation method for stochastic discrete optimization (Q2784421)

The authors study a Monte Carlo simulation-based approach to stochastic discrete optimization problems of the form \(\min_{x\in S}\{g(x):= E_PG(x, W)\}\), where \(W\) is a random vector having probability distribution \(P\), \(S\) is a finite set, \(G(x,w)\) is a real-valued function of two (vector) variables \(x\) and \(w\), and \(E_PG(x, W)= \int G(x, w) P(dw)\) is the corresponding expected value.NEWLINENEWLINENEWLINEThey discuss convergence rates, stopping rules, and computational complexity of this procedure and present a numerical example for the stochastic knapsack problem.