Аннотация 3
1. Введение 3
1.1. Основные понятия 5
1.2. Связанные работы 5
2. Поиск потенциалов 6
2.1. Основная теорема 6
2.2. Скорость сходимости экстраградиентного метода 7
3. Постановка задачи поиска потенциалов 9
3.1. Постановка задачи в виде принадлежности некоторому конусу 9
3.2. Постановка задачи в виде динамической системы 12
4. Анализ задачи по поиску потенциалов 14
4.1. Неподвижные точки 14
4.2. Динамика на прямой 15
4.3. Прямой недостаточно 19
5. Заключение 19
Аннотация
В данной работе мы развиваем подход (Taylor et al. ((2018))) по поиску потенциалов. Обычно для доказательства через потенциалы требуется решить задачу полуопределенного программирования(SDP) из O(k) линейных матричных неравенств(LMIs), где к - количество итераций. В нашем же подходе мы показываем, что в определенных случаях достаточно использовать лишь константное количество неравенств. В качестве демонстрации эффективности нашего подхода мы приводим альтернативное доказательство сходимости последней итерации экстраградиентного метода для отрицательно комонотонного случая, по аналогии с (Gorbunov et al. ((2022b))).
В работе мы предложили альтернативный метод поиска потенциалов, который в отличии от стандартного подхода (Taylor et al. ((2018)), Taylor and Bach ((2021))) требует проверки всего константного количества линейных матричных неравенств. С помощью данного подхода мы установили альтернативное доказательство скорости сходимости последней итерации экстраградиентного метода в комонотонном случае. Также мы провели анализ задачи поиска потенциалов и связали задачу поиска потенциалов вида Pk + kQk с динамикой на прямой в некотором компактном выпуклом множестве.
Тем не менее до сих пор остается множество открытых вопросов. Так с помощью нашего подхода непонятно как работать со скоростями сходимости по типу O(k2). Также в качестве будущих направлений для исследований мы отмечаем дальнейший анализ динамики сформулированной для задачи поиска потенциалов. Тут однако может пригодиться серьезное вовлечение в алгебраическую геометрию и компьютерную алгебру.
