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

Вестник НовГУ > 2016 > 4 (95) > Тихомиров А.С. Нижняя оценка трудоемкости одного класса марковских монотонных алгоритмов случайного поиска

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

УДК 519.676
Т и х о м и р о в А. С. Нижняя оценка трудоемкости одного класса марковских монотонных алгоритмов случайного поиска // Вестн. Новг. гос. ун-та. Сер.: Технические науки. 2016. № 4 (95). С.57–60. Библиогр. 17 назв.

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

Исследуется трудоемкость одного класса марковских монотонных алгоритмов случайного поиска. Показано, что для рассмотренного класса случайных поисков, число вычислений целевой функции, необходимое для достижения требуемой точности ε решения задачи, не может расти медленнее, чем | lnε| .
-----------------------------------------------------------------------------
UDC 519.676
T i k h o m i r o v A. S. A lower bound on the computational complexity of one class of the Markov monotonous random search algorithms // Vestnik NovSU. Issue: Engineering Sciences. 2016. № 4 (95). P.57–60. The reference list 17 items.

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

The computational complexity of one class of the Markov monotonous random search algorithms is investigated. It is shown that, for a considered class of random search methods the number of the objective function evaluations needed to find the extremizer accurate to ε cannot increase more slowly than | lnε| .

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