Simulated annealing for discrete optimization with estimation

We extend the basic convergence results for the Simulated Annealing (SA) algorithm to a stochastic optimization problem where the objective function is stochastic and can be evaluated only through Monte Carlo simulation (hence, disturbed with random error). This extension is important when either the objective function cannot be evaluated exactly or such an evaluation is computationally expensive. We present a modified SA algorithm and show that under suitable conditions on the random error, the modified SA algorithm converges in probability to a global optimizer. Computational results and comparisons with other approaches are given to demonstrate the performance of the proposed modified SA algorithm.