Simulation-based optimization using simulated annealing with confidence interval

This paper develops a variant of simulated annealing (SA) algorithm for solving discrete stochastic optimization problems where the objective function is stochastic and can be evaluated only through Monte Carlo simulations. In the proposed variant of SA, the Metropolis criterion depends on whether the objective function values indicate statistically significant difference at each iteration. The differences between objective function values are considered to be statistically significant based on confidence intervals associated with these values. Unlike the original SA, our method uses a constant temperature. We show that the configuration that has been visited most often in the first m iterations converges almost surely to a global optimizer.