Об адаптивных ускоренных методах и их модификациях для альтернированной минимизации

В первой части работы получена оценка скорости сходимости ранее известного ускоренного метода первого порядка AGMsDR на классе задач минимизации, вообще говоря, невыпуклых функций с $M$-липшицевым градиентоми удовлетворяющих условию Поляка–Лоясиевича. При реализации метода не требуется знать параметр $\mu^{PL}>0$ из условия Поляка–Лоясиевича, при этом метод демонстрирует линейную скорость сходимости (сходимость со скоростью геометрической прогрессии со знаменателем $(1-\frac{\mu^{PL}}{M})$. Ранее для метода была доказана сходимость со скоростью $O(\frac{1}{k^2})$ на классе выпуклых задач с $M$-липшицевым градиентом. А также сходимость со скоростью геометрической прогрессии, знаменатель которой $(1-\sqrt{\frac{\mu^{SC}}{M}})$, но только если алгоритму известно значение параметра сильной выпуклости $\mu^{SC}>0$. Новизна результата заключается в том, что удается отказаться от использования методом значения параметра $\mu^{SC}>0$ и при этом сохранить линейную скорость сходимости, но уже без корня в знаменателе прогрессии.
Во второй части представлена новая модификация метода AGMsDR для решения задач, допускающих альтернированную минимизацию (Alternating AGMsDR). Доказываются аналогичные оценки скорости сходимости на тех же классах оптимизационных задач.
Таким образом, представлены адаптивные ускоренные методы с оценкой сходимости $O(\min\{\frac{M}{k^2}, (1-\frac{\mu^{PL}}{M})^{k-1}\}) $ на классе выпуклых функций с $M$-липшицевым градиентом, которые удовлетворяют условию Поляк–Лоясиевича. При этом для работы метода не требуются значения параметров $M$ и $\mu^{PL}$. Если же условие Поляка–Лоясиевича не выполняется, то можно утверждать, что скорость сходимости равна $O(\frac{1}{k^2})$, но при этом методы не требуют никаких изменений.
Также рассматривается адаптивная каталист-оболочка неускоренного градиентного метода, которая позволяет доказать оценку скорости сходимости $O(\frac{1}{k^2})$. Проведено экспериментальное сравнение неускоренного градиентного метода с адаптивным выбором шага, ускоренного с помощью адаптивной каталист-оболочки с методами AGMsDR, Alternating AGMsDR, APDAGD (Adaptive Primal-Dual Accelerated Gradient Descent) и алгоритмом Синхорна для задачи, двойственной к задаче оптимального транспорта.
Проведенные вычислительные эксперименты показали более быструю работу метода Alternating AGMsDR по сравнению как с неускоренным градиентным методом, ускоренным с помощью адаптивной каталист-оболочки, так и с методом AGMsDR, несмотря на асимптотически одинаковые гарантии скорости сходимости $O(\frac{1}{k^2})$. Это может быть объяснено результатом о линейной скорости сходимости метода Alternating AGMsDR на классе задач, удовлетворяющих условию Поляка–Лоясиевича. Гипотеза была проверена на квадратичных задачах. Метод Alternating AGMsDR показал более быструю сходимость по сравнению с методом AGMsDR.