Stopping criterion for a simulation-based optimization method

We consider a new simulation-based optimization method called the nested partitions (NP) method. This method generates a Markov chain and solving the optimization problem is equivalent to maximizing the stationary distribution of this Markov chain over certain states. The method may therefore be considered a Monte Carlo sampler that samples from the stationary distribution. We show that the Markov chain converges geometrically fast to the true stationary distribution, and use these results to derive a stopping criterion for the method