УДК 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.
