Все выпуски

В первой части работы получена оценка скорости сходимости ранее известного ускоренного метода первого порядка AGMsDR на классе задач минимизации, вообще говоря, невыпуклых функций с $M$-липшицевым градиентом и удовлетворяющих условию Поляка – Лоясиевича. При реализации метода не требуется знать параметр $\mu^{PL}>0$ из условия Поляка – Лоясиевича, при этом метод демонстрирует линейную скорость сходимости (сходимость со скоростью геометрической прогрессии со знаменателем $\left.\left(1 - \frac{\mu^{PL}}{M}\right)\right)$. Ранее для метода была доказана сходимость со скоростью $O\left(\frac1{k^2}\right)$ на классе выпуклых задач с $M$-липшицевым градиентом. А также сходимость со скоростью геометрической прогрессии, знаменатель которой $\left(1 - \sqrt{\frac{\mu^{SC}}{M}}\right)$, но только если алгоритму известно значение параметра сильной выпуклости $\mu^{SC}>0$. Новизна результата заключается в том, что удается отказаться от использования методом значения параметра $\mu^{SC}>0$ и при этом сохранить линейную скорость сходимости, но уже без корня в знаменателе прогрессии.

Во второй части представлена новая модификация метода AGMsDR для решения задач, допускающих альтернированную минимизацию (Alternating AGMsDR). Доказываются аналогичные оценки скорости сходимости на тех же классах оптимизационных задач.

Таким образом, представлены адаптивные ускоренные методы с оценкой сходимости $O\left(\min\left\lbrace\frac{M}{k^2},\,\left(1-{\frac{\mu^{PL}}{M}}\right)^{(k-1)}\right\rbrace\right)$ на классе выпуклых функций с $M$-липшицевым градиентом, которые удовлетворяют условию Поляка – Лоясиевича. При этом для работы метода не требуются значения параметров $M$ и $\mu^{PL}$. Если же условие Поляка – Лоясиевича не выполняется, то можно утверждать, что скорость сходимости равна $O\left(\frac1{k^2}\right)$, но при этом методы не требуют никаких изменений.

Также рассматривается адаптивная каталист-оболочка неускоренного градиентного метода, которая позволяет доказать оценку скорости сходимости $O\left(\frac1{k^2}\right)$. Проведено экспериментальное сравнение неускоренного градиентного метода с адаптивным выбором шага, ускоренного с помощью адаптивной каталист-оболочки с методами AGMsDR, Alternating AGMsDR, APDAGD (Adaptive Primal-Dual Accelerated Gradient Descent) и алгоритмом Синхорна для задачи, двойственной к задаче оптимального транспорта.

Проведенные вычислительные эксперименты показали более быструю работу метода Alternating AGMsDR по сравнению как с неускоренным градиентным методом, ускоренным с помощью адаптивной каталист-оболочки, так и с методом AGMsDR, несмотря на асимптотически одинаковые гарантии скорости сходимости $O\left(\frac1{k^2}\right)$. Это может быть объяснено результатом о линейной скорости сходимости метода Alternating AGMsDR на классе задач, удовлетворяющих условию Поляка – Лоясиевича. Гипотеза была проверена на квадратичных задачах. Метод Alternating AGMsDR показал более быструю сходимость по сравнению с методом AGMsDR.

Проблема разработки эффективных численных методов для невыпуклых (в том числе негладких) задач довольно актуальна в связи с широкой распространенностью таких задач в приложениях. Работа посвящена субградиентным методам для задач минимизации липшицевых $\mu$-слабо выпуклых функций, причем не обязательно гладких. Хорошо известно, что для пространств большой размерности субградиентные методы имеют невысокие скоростные гарантии даже на классе выпуклых функций. При этом, если выделить подкласс функций, удовлетворяющих условию острого минимума, а также использовать шаг Поляка, можно гарантировать линейную скорость сходимости субградиентного метода. Однако возможны ситуации, когда значения функции или субградиента численному методу доступны лишь с некоторой погрешностью. В таком случае оценка качества выдаваемого этим численным методом приближенного решения может зависеть от величины погрешности. В настоящей статье для субградиентного метода с шагом Поляка исследованы ситуации, когда на итерациях используется неточная информация о значении целевой функции или субградиента. Доказано, что при определенном выборе начальной точки субградиентный метод с аналогом шага Поляка сходится со скоростью геометрической прогрессии на классе $\mu$-слабо выпуклых функций с острым минимумом в случае аддитивной неточности в значениях субградиента. В случае когда как значение функции, так и значение ее субградиента в текущей точке известны с погрешностью, показана сходимость в некоторую окрестность множества точных решений и получены оценки качества выдаваемого решения субградиентным методом с соответствующим аналогом шага Поляка. Также в статье предложен субградиентный метод с клиппированным шагом и получена оценка качества выдаваемого им решения на классе $\mu$-слабо выпуклых функций с острым минимумом. Проведены численные эксперименты для задачи восстановления матрицы малого ранга. Они показали, что эффективность исследуемых алгоритмов может не зависеть от точности локализации начального приближения внутри требуемой области, а неточность в значениях функции и субградиента может влиять на количество итераций, необходимых для достижения приемлемого качества решения, но почти не влияет на само качество решения.