Ускоренный спуск по случайному направлению с неевклидовой прокс-структурой

Рассматриваются задачи гладкой выпуклой оптимизации, для численного решения которых полный градиент недоступен. В 2011 г. Ю.Е. Нестеровым были предложены ускоренные безградиентные методы решения таких задач. Поскольку рассматривались только задачи безусловной оптимизации, то использовалась евклидова прокс-структура. Однако если заранее знать, например, что решение задачи разреженно, а точнее, что расстояние от точки старта до решения в 1-норме и в 2-норме близки, то более выгодно выбирать не евклидову прокс-структуру, связанную с 2-нормой, а прокс-структуру, связанную с 1-нормой. Полное обоснование этого утверждения проводится в статье. Предлагается ускоренный метод спуска по случайному направлению с неевклидовой прокс-структурой для решения задачи безусловной оптимизации (в дальнейшем подход предполагается расширить на ускоренный безградиентный метод). Получены оценки скорости сходимости метода. Показаны сложности переноса описанного подхода на задачи условной оптимизации.