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

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|$. 
@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},
     publisher = {mathdoc},
     volume = {51},
     number = {9},
     year = {2011},
     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
PB  - mathdoc
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
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZVMMF_2011_51_9_a5/
%G ru
%F ZVMMF_2011_51_9_a5
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/