О сложности вычисления глобального экстремума в одном классе многоэкстремальных задач

Рассматривается задача безусловной глобальной минимизации липшицевой функции в $E^n$ и сеточный метод ее решения с точностью $\varepsilon_0>0$. Известно, что в общем случае требуется $O(\varepsilon_0^{-n})$ вычислений функции. Вводится специальный класс функций со степенным ростом порядка $O(\varepsilon^{rn})$, $r\in(0,1]$, меры множества $\varepsilon$-оптимальных точек. Показано, что для последовательного алгоритма поиска типа метода ветвей и границ общее количество вычислений функции в указанном классе может быть снижено до $O(\varepsilon_0^{-n(1-r)})$ при $r<1$ и до $O(\ln\varepsilon_0^{-1})$ при $r=1$.