RUS  ENG
Полная версия
СЕМИНАРЫ

Семинар лаборатории ПреМоЛаб
9 февраля 2012 г. 16:00, г. Москва, Институт проблем передачи информации им. А. А. Харкевича РАН (Б. Каретный пер., 19, метро «Цветной бульвар»), ауд. 615


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

Ю. Е. Нестеров

Université Catholique de Louvain

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


© МИАН, 2024