On the rate of convergence of the simulated annealing algorithm

A. S. Tikhomirov

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 50 (2010) no. 1, pp. 24-37

Résumé

The convergence rate of the simulated annealing algorithm is examined. It is shown that, if the objective function is nonsingular, then the number of its evaluations required to obtain the desired accuracy $\varepsilon$ in the solution can be a slowly (namely, logarithmically) growing function as $\varepsilon$ approaches zero.

Bibliographie

[1] Ermakov S. M., Zhiglyavskii A. A., “O sluchainom poiske globalnogo ekstremuma”, Teoriya veroyatnostei i ee primeneniya, 1983, no. 1, 129–136 | MR

[2] Ermakov S. M., Zhiglyavskii A. A., Kondratovich M. V., “O sravnenii nekotorykh protsedur sluchainogo poiska globalnogo ekstremuma”, Zh. vychisl. matem. i matem. fiz., 29:2 (1989), 163–170 | MR

[3] Rastrigin L. A., Statisticheskie metody poiska, Nauka, M., 1968 | MR

[4] Vaisbopd E. M., Yudin D. B., “Mnogoekstpemalnaya stokhasticheskaya apppoksimatsiya”, Izv. AN SSSR. Tekhn. kibepnetika, 1968, no. 5, 3–13 | MR

[5] Zhiglyavskii A. A., Matematicheskaya teoriya globalnogo sluchainogo poiska, Izd-vo LGU, L., 1985 | MR

[6] Zhiglyavskii A. A., Zhilinskas A. G., Metody poiska globalnogo ekstremuma, Nauka, M., 1991 | MR

[7] Zhigljavsky A., Zilinskas A., Stochastic global optimization, Springer, Berlin, 2008 | MR | Zbl

[8] Spall J. C., Introduction to stochastic search and optimization: estimation, simulation, and control, Wiley, New Jersey, 2003 | MR | Zbl

[9] Abakarov A. Sh., Sushkov Yu. A., “Statisticheskoe issledovanie sluchainogo poiska”, Matem. modeli. Teoriya i prilozh., 2, Izd-vo NIIKh SPbGU, SPb., 2002, 70–86

[10] Spall J. C., Hill S. D., Stark D. R., “Theoretical framework for comparing several stochastic optimization approaches”, Probabilistic and Randomized Methods for Design Under Uncertainty, Springer, London, 2006, 99–117 | Zbl

[11] Yin G., “Rates of convergence for a class of global stochastic optimization algorithms”, SIAM J. Optimizat., 10:1 (1999), 99–120 | DOI | MR | Zbl

[12] Tikhomirov A. S., Nekrutkin V. V., “Markovskii monotonnyi poisk ekstremuma. Obzor nekotorykh teoreticheskikh rezultatov”, Matem. modeli. Teoriya i prilozh., 4, VVM, SPb., 2004, 3–47

[13] Tikhomirov A., Stojunina T., Nekrutkin V., “Monotonous random search on a torus: Integral upper bounds for the complexity”, J. Statistical Planning and Inference, 137:12 (2007), 4031–4047 | DOI | MR | Zbl

[14] Tikhomirov A. S., “Ob odnorodnom markovskom monotonnom poiske ekstremuma”, Zh. vychisl. matem. i matem. fiz., 46:3 (2006), 379–394 | MR | Zbl

[15] Tikhomirov A. S., “O skorosti skhodimosti odnorodnogo markovskogo monotonnogo poiska ekstremuma”, Zh. vychisl. matem. i matem. fiz., 47:5 (2007), 817–828 | MR

[16] Nekrutkin V. V., Tikhomirov A. S., “Speed of convergence as a function of given accuracy for random search methods”, Acta Appl. Math., 33 (1993), 89–108 | DOI | MR | Zbl

[17] Vasilev F. P., Chislennye metody resheniya ekstremalnykh zadach, Nauka, M., 1980 | MR

[18] Karmanov V. G., Matematicheskoe programmirovanie, Fizmatlit, M., 2000 | Zbl

[19] Nemirovskii A. S., Yudin D. B., Slozhnost zadach i effektivnost metodov optimizatsii, Nauka, M., 1979 | MR

[20] Sukharev A. G., Minimaksnye algoritmy v zadachakh chislennogo analiza, Nauka, M., 1989 | MR | Zbl

[21] Ivanov V. V., “Ob optimalnykh algoritmakh minimizatsii funktsii nekotorykh klassov”, Kibernetika, 1972, no. 4, 81–94 | Zbl

[22] Granichin O. N., Polyak B. T., Randomizirovannye algoritmy otsenivaniya i optimizatsii pri pochti proizvolnykh pomekhakh, Nauka, M., 2003

[23] Tikhomirov A. S., Ob odnom algoritme markovskogo neodnorodnogo poiska ekstremuma, Dep. v VINITI No 532-V2004, 30.03.04. Dep., 32 pp.

[24] Shiryaev A. N., Veroyatnost, Nauka, M., 1989 | MR

[25] Kolmogorov A. N., Fomin S. V., Elementy teorii funktsii i funktsionalnogo analiza, Nauka, M., 1989 | MR