Ускоренные методы для седловых задач

В последнее время было показано, как на основе обычного ускоренного градиентного метода решения задач гладкой выпуклой оптимизации можно получить ускоренные методы для более сложных задач (со структурой) и задач, по ходу решения которых используется различная локальная информация о поведении функции (стохастический градиент, гессиан и т.п.). “Ускоренные” методы здесь означает, с одной стороны, наличие некоторого единого и достаточно общего способа ускорения. С другой стороны, это означает и “оптимальность” методов, что часто удается строго доказать. В настоящей работе предпринята попытка построить в том же духе теорию ускоренных методов решения гладких выпукло-вогнутых седловых задач со структурой. Основным результатом статьи является получение в некотором смысле необходимых и достаточных условий, при которых сложность решения нелинейных выпукло-вогнутых седловых задач со структурой по числу вычислений градиентов композитов по прямым переменным равна по порядку аналогичной сложности решения билинейных задач со структурой. Библ. 30.