Geodesic
Lower bounds on the convergence rate of the Markov symmetric random search
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 51 (2011) no. 9, pp. 1630-1644 
A. S. Tikhomirov. Lower bounds on the convergence rate of the Markov symmetric random search. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 51 (2011) no. 9, pp. 1630-1644. http://geodesic.mathdoc.fr/item/ZVMMF_2011_51_9_a5/
@article{ZVMMF_2011_51_9_a5,
     author = {A. S. Tikhomirov},
     title = {Lower bounds on the convergence rate of the {Markov} symmetric random search},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1630--1644},
     year = {2011},
     volume = {51},
     number = {9},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2011_51_9_a5/}
}
TY  - JOUR
AU  - A. S. Tikhomirov
TI  - Lower bounds on the convergence rate of the Markov symmetric random search
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2011
SP  - 1630
EP  - 1644
VL  - 51
IS  - 9
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2011_51_9_a5/
LA  - ru
ID  - ZVMMF_2011_51_9_a5
ER  - 
%0 Journal Article
%A A. S. Tikhomirov
%T Lower bounds on the convergence rate of the Markov symmetric random search
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2011
%P 1630-1644
%V 51
%N 9
%U http://geodesic.mathdoc.fr/item/ZVMMF_2011_51_9_a5/
%G ru
%F ZVMMF_2011_51_9_a5

Voir la notice de l'article provenant de la source Math-Net.Ru

The convergence rate of the Markov random search algorithms designed for finding the extremizer of a function is investigated. It is shown that, for a wide class of random search methods that possess a natural symmetry property, the number of evaluations of the objective function needed to find the extremizer accurate to cannot grow slower than $|\ln\varepsilon|$.

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

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

[3] 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

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

[5] Zhigljavsky A., Žilinskas A., Stochastic global optimization, Springer, Berlin, 2008 | MR | Zbl

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

[7] 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 | DOI | Zbl

[8] Yin G., “Rates of convergence for a class of global stochastic optimization algorithms”, SIAM J. Optimizat., 10:1 (1999), 99–120 | DOI | 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] Lopatin A. S., “Metod otzhiga”, Stokhasticheskaya optimizatsiya v informatike, 1 (2005), 133–149

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

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

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

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

[15] 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

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

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

[18] 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

[19] Tikhomirov A. S., “O bystrykh variantakh algoritma otzhiga (simulated annealing)”, Stokhastich. optimizatsiya v informatike, 2009, no. 5, 65–90

[20] Tikhomirov A. S., “O skorosti skhodimosti algoritma simulated annealing”, Zh. vychisl. matem. i matem. fiz., 50:1 (2010), 24–37 | MR | Zbl

[21] Tikhomirov A. S., “O modelirovanii sluchainykh vektorov s monotonnymi simmetrichnymi plotnostyami”, Vestn. Novgorodskogo gos. un-ta. Ser. Tekhn. nauki, 2004, no. 28, 111–113