Компьютерные исследования и моделирование
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Компьютерные исследования и моделирование:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Компьютерные исследования и моделирование, 2022, том 14, выпуск 2, страницы 357–376
DOI: https://doi.org/10.20537/2076-7633-2022-14-2-357-376
(Mi crm973)
 

МАТЕМАТИЧЕСКИЕ ОСНОВЫ И ЧИСЛЕННЫЕ МЕТОДЫ МОДЕЛИРОВАНИЯ

Tensor methods for strongly convex strongly concave saddle point problems and strongly monotone variational inequalities
[Тензорные методы для сильно выпуклых сильно вогнутых седловых задач и сильно монотонных вариационных неравенств]

P. A. Ostroukhovab, R. A. Kamalovac, P. E. Dvurechenskiid, A. V. Gasnikovabe

a Moscow Institute of Physics and Technology, 9 Institutskiy per., Dolgoprudny, Moscow Region, 141701, Russia
b Institute for Information Transmission Problems of Russian Academy of Sciences, 19/1 Bolshoy Karetny per., Moscow, 127051, Russia
c V. A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences, 65 Profsoyuznaya st., Moscow, 117997, Russia
d Weierstrass Institute for Applied Analysis and Stochastics, 39 Mohrenstraße, Berlin, 10117, Germany
e Caucasus Mathematical Center, Adyghe State University, 208 Pervomayskaya st., Maykop, Adyghe, 385000, Russia
Список литературы:
Аннотация: В данной статье предлагаются методы оптимизации высокого порядка (тензорные методы) для решения двух типов седловых задач. Первый тип — это классическая мин-макс-постановка для поиска седловой точки функционала. Второй тип — это поиск стационарной точки функционала седловой задачи путем минимизации нормы градиента этого функционала. Очевидно, что стационарная точка не всегда совпадает с точкой оптимума функции. Однако необходимость в решении подобного типа задач может возникать в случае, если присутствуют линейные ограничения. В данном случае из решения задачи поиска стационарной точки двойственного функционала можно восстановить решение задачи поиска оптимума прямого функционала. В обоих типах задач какие-либо ограничения на область определения целевого функционала отсутствуют. Также мы предполагаем, что целевой функционал является $\mu$-сильно выпуклым и $\mu$-сильно вогнутым, а также что выполняется условие Липшица для его $p$-й производной.
Для задач типа «мин-макс» мы предлагаем два алгоритма. Так как мы рассматриваем сильно выпуклую и сильно вогнутую задачу, первый алгоритм использует существующий тензорный метод для решения выпуклых вогнутых седловых задач и ускоряет его с помощью техники рестартов. Таким образом удается добиться линейной скорости сходимости. Используя дополнительные предположения о выполнении условий Липшица для первой и второй производных целевого функционала, можно дополнительно ускорить полученный метод. Для этого можно «переключиться» на другой существующий метод для решения подобных задач в зоне его квадратичной локальной сходимости. Так мы получаем второй алгоритм, обладающий глобальной линейной сходимостью и локальной квадратичной сходимостью.
Наконец, для решения задач второго типа существует определенная методология для тензорных методов в выпуклой оптимизации. Суть ее заключается в применении специальной «обертки» вокруг оптимального метода высокого порядка. Причем для этого условие сильной выпуклости не является необходимым. Достаточно лишь правильным образом регуляризовать целевой функционал, сделав его таким образом сильно выпуклыми сильно вогнутым. В нашей работе мы переносим эту методологию на выпукло-вогнутые функционалы и используем данную «обертку» на предлагаемом выше алгоритме с глобальной линейной сходимостью и локальной квадратичной сходимостью.
Так как седловая задача является частным случаем монотонного вариационного неравенства, предлагаемые методы также подойдут для поиска решения сильно монотонных вариационных неравенств.
Ключевые слова: вариационное неравенство, седловая задача, гладкость высокого порядка, тензорные методы, минимизация нормы градиента.
Финансовая поддержка Номер гранта
Министерство науки и высшего образования Российской Федерации 0714-2020-0005
Работа П. Остроухова и А. Гасникова выполнена при поддержке Министерства науки и высшего образования Российской Федерации (госзадание), № 075-00337-20-03, номер проекта 0714-2020-0005.
Поступила в редакцию: 12.02.2022
Принята в печать: 13.02.2022
Тип публикации: Статья
УДК: 519.853.62
Язык публикации: английский
Образец цитирования: P. A. Ostroukhov, R. A. Kamalov, P. E. Dvurechenskii, A. V. Gasnikov, “Tensor methods for strongly convex strongly concave saddle point problems and strongly monotone variational inequalities”, Компьютерные исследования и моделирование, 14:2 (2022), 357–376
Цитирование в формате AMSBIB
\RBibitem{OstKamDvu22}
\by P.~A.~Ostroukhov, R.~A.~Kamalov, P.~E.~Dvurechenskii, A.~V.~Gasnikov
\paper Tensor methods for strongly convex strongly concave saddle point problems and strongly monotone variational inequalities
\jour Компьютерные исследования и моделирование
\yr 2022
\vol 14
\issue 2
\pages 357--376
\mathnet{http://mi.mathnet.ru/crm973}
\crossref{https://doi.org/10.20537/2076-7633-2022-14-2-357-376}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/crm973
  • https://www.mathnet.ru/rus/crm/v14/i2/p357
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Компьютерные исследования и моделирование
    Статистика просмотров:
    Страница аннотации:114
    PDF полного текста:47
    Список литературы:21
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024