УДК 517.988
СХОДИМОСТЬ ДВУХЭТАПНОГО МЕТОДА С РАСХОЖДЕНИЕМ БРЭГМАНА
ДЛЯ ВАРИАЦИОННЫХ НЕРАВЕНСТВ
Аннотация. Предложен новый двухэтапный метод для приближенного решения вариационных неравенств с псевдомонотонными и липшицевыми операторами, который является модификацией нескольких известных двухэтапных алгоритмов с использованием расхождения Брэгмана вместо евклидового расстояния. Как и другие подобные схемы, данный метод в некоторых случаях позволяет явно учесть структуру допустимого множества задачи. Доказана теорема сходимости метода. Для монотонного оператора и выпуклого компактного допустимого множества получены неасимптотические оценки его эффективности.
Ключевые слова: вариационное неравенство, псевдомонотонность, монотонность, условие Липшица, двухэтапный метод, расхождение Брэгмана, сходимость.
ПОЛНЫЙ ТЕКСТ
Номировский Дмитрий Анатолиевич,
доктор физ.-мат. наук, профессор кафедры Киевского национального университета
имени Тараса Шевченко,
kashpir74@gmail.com
Рублев Богдан Владиславович,
доктор физ.-мат. наук, профессор кафедры Киевского национального университета
имени Тараса Шевченко,
rublyovbv@gmail.com
Семёнов Владимир Викторович,
доктор физ.-мат. наук, профессор кафедры Киевского национального университета
имени Тараса Шевченко,
semenov.volodya@gmail.com
СПИСОК ЛИТЕРАТУРЫ
- Konnov I.V. Combined relaxation methods for variational inequalities. Berlin; Heidelberg; New York: Springer-Verlag, 2001. 181 p.
- Nagurney A. Network economics: A variational inequality approach. Dordrecht: Kluwer Academic Publishers, 1999. 325 p.
- Корпелевич Г.М. Экстраградиентный метод для отыскания седловых точек и других задач. Экономика и мат. методы. 1976. Т. 12, № 4. С. 747–756.
- Nemirovski A. Prox-method with rate of convergence for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization. 2004. Vol. 15. P. 229–251.
- Auslender A., Teboulle M. Interior projection-like methods for monotone variational inequalities. Mathematical Programming. 2005. Vol. 104, Iss. 1. P. 39–68.
- Nesterov Yu. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programming. 2007. Vol. 109, Iss. 2–3. P. 319–344.
- Нурминский Е.А. Использование дополнительных малых воздействий в фейеровских моделях итеративных алгоритмов. Журнал вычисл. математики и мат. физики. 2008. T. 48, № 12. С. 2121–2128.
- Семенов В.В. О методе параллельной проксимальной декомпозиции для решения задач выпуклой оптимизации. Проблемы управления и информатики. 2010. № 2. С. 42–46.
- Censor Y., Gibali A., Reich S. The subgradient extragradient method for solving variational inequalities in Hilbert space. Journal of Optimization Theory and Applications. 2011. Vol. 148. P. 318–335.
- Ляшко С.И., Семенов В.В., Войтова Т.А. Экономичная модификация метода Корпелевич для монотонных задач о равновесии. Кибернетика и системный анализ. 2011. № 4. C. 146–154.
- Семенов В.В. Сильно сходящийся метод расщепления для системы операторных включений с монотонными операторами. Проблемы управления и информатики. 2014. № 3. С. 22–32.
- Семенов В.В. Гибридные методы расщепления для системы операторных включений с монотонными операторами. Кибернетика и системный анализ. 2014. Т. 50, № 5. C. 104–112.
- Верлань Д.А., Семенов В.В., Чабак Л.М. Сильно сходящийся модифицированный экстраградиентный метод для вариационных неравенств с нелипшицевыми операторами. Проблемы управления и информатики. 2015. № 4. С. 37–50.
- Денисов С.В., Семенов В.В., Чабак Л.М. Сходимость модифицированного экстраградиентного метода для вариационных неравенств с нелипшицевыми операторами. Кибернетика и системный анализ. 2015. Т. 51, № 5. С. 102–110.
- Попов Л.Д. Модификация метода Эрроу–Гурвица поиска седловых точек. Мат. заметки. 1980. Т. 28, № 5. С. 777–784.
- Малицкий Ю.В., Семенов В.В. Вариант экстраградиентного алгоритма для монотонных вариационных неравенств. Кибернетика и системный анализ. 2014. Т. 50, № 2. C. 125–131.
- Семенов В.В. Вариант метода зеркального спуска для вариационных неравенств. Кибернетика и системный анализ. 2017. Т. 53, № 2. C. 83–93.
- Lyashko S.I., Semenov V.V. A new two-step proximal algorithm of solving the problem of equilibrium programming. In: Goldengorin B. (ed.). Optimization and Its Applications in Control and Data Sciences. Springer Optimization and Its Applications. Cham: Springer, 2016. Vol. 115. P. 315–325.
- Брэгман Л.М. Релаксационный метод нахождения общей точки выпуклых множеств и его применение для решения задач выпуклого программирования. Журн. вычисл. математики и мат. физики. 1967. № 3. С. 620–631.
- Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. Москва: Наука, 1979. 384 с.
- Beck A. First-order methods in optimization. Philadelphia: Society for Industrial and Applied Mathematics, 2017. 479 p.
- Семенов В.В. Модифицированный экстраградиентный метод с расхождением Брэгмана для вариационных неравенств. Проблемы управления и информатики. 2018. № 4. С. 43–53.
- Lorenz D.A., Schopfer F., Wenger S. The linearized Bregman method via split feasibility problems. Analysis and generalizations. SIAM Journal on Imaging Sciences. 2014. Vol. 7, Iss. 2. P. 1237–1262.