A LOWER BOUND ON THE COMPUTATIONAL COMPLEXITY OF ONE CLASS OF THE SIMULATED ANNEALING ALGORITHMS
The computational complexity of one class of the simulated annealing algorithms is investigated. It is shown that, for a wide class of random search methods which possess a natural symmetry property, the number of the objective function evaluations needed to find the extremum accurate to ε cannot increase more slowly than.