Метод случайной неградиентной минимизации выпуклых функций

В докладе будут установлены оценки сложности методов выпуклой оптимизации, использующих только информацию о значениях минимизируемой функции (но не о ее производных). Направления одномерного поиска в данном методе — нормально распределенные случайные векторы. Оказывается, что такой метод, как правило, требует лишь в $n$ раз большего числа операций по сравнению с, где $n$ — размерность пространства. Этот результат имеет место как для гладких, так и для негладких задач. В последнем случае будет также описана ускоренная схема, в которой математическое ожидание скорости сходимости составляет $O(n^2/k^2)$, где $k$ — счетчик числа итераций. В задачах стохастической оптимизации будет предложена схема нулевого порядка и обоснована оценка математического ожидания скорости сходимости вида $O(n/k^{1/2})$. Буду также представлены некоторые оценки скорости сходимости случайного неградиентного метода для поиска стационарных точек невыпуклых функций как в гладком, так и в негладком случае. Теоретические результаты подтверждаются предварительными вычислительными экспериментами.