Вестник НовГУ

Вестник НовГУ > 2013 > №75 Т.2 > Тихомиров А.С. Нижние оценки трудоемкости марковского симметричного случайного поиска на торе

Тихомиров А.С. Нижние оценки трудоемкости марковского симметричного случайного поиска на торе

УДК 519.626
Т и х о м и р о в А. С. Нижние оценки трудоемкости марковского симметричного случайного поиска на торе // Вестн. Новг. гос. ун-та. Сер.: Физико-математические науки. 2013. № 75. Т.2. С.44-47. Библиогр. 22 назв.

К л ю ч е в ы е с л о в а: случайный поиск, глобальная оптимизация, стохастическая оптимизация

Исследуется трудоемкость марковских алгоритмов случайного поиска экстремума функции. Показано, что для широкого класса случайных поисков, обладающих естественным свойством симметрии, число вычислений целевой функции, необходимое для достижения требуемой точности ε решения задачи, не может расти медленнее, чем | lnε | .
-----------------------------------------------------------------------------
UDC 519.626
T i k h o m i r o v A. S. Lower estimates for the computational complexity of Markov symmetric random search on the torus // Vestnik NovSU. Issue: Physico-Mathematical Sciences. 2013. № 75. V.2. P.44-47. The reference list 22 items.

K e y w o r d s: random search, global optimization, stochastic optimization

The computational complexity of Markov random search algorithms designed for finding the extremum of function 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 | lnε | .

Загрузить (471 КБ)