Statistical Inferences for Termination of Markov Type Random Search Algorithms

摘要

In this paper, we consider the application of order statistics to establish the optimality in stochastic and heuristic optimization algorithms. A method for estimating the minimum value with an associated confidence interval is developed using the formalism of the theory of order statistics for i.i.d. variables; we examine it by computer simulation. We build a method for the estimation of confidence intervals of the minimum value using order statistics, implemented for optimality testing and stopping in Markov type random search algorithms. The efficiency of this approach is discussed, using the results of application to stochastic approximation and simulated annealing. Keywords Order statistics - Monte Carlo simulation - Continuous optimization - Simulated annealing - Stochastic approximation Communicated by B.T. Polyak.