Cybernetics And Systems Analysis logo
Інформація редакції Аннотації статей Автори Архів
Кібернетика та Системний Аналіз
Міжнародний Науково-Теоретичний Журнал
Том 60 >>> № 3 ТРАВЕНЬ — ЧЕРВЕНЬ 2024
-->

DOI 10.34229/KCA2522-9664.24.3.6
УДК 517.988

В.В. СЕМЕНОВ
Київський національний університет імені Тараса Шевченка, Київ, Україна,
 semenov.volodya@gmail.com

О.С. ХАРЬКОВ
Київський національний університет імені Тараса Шевченка, Київ, Україна,
 olehharek@gmail.com


СИЛЬНА ЗБІЖНІСТЬ РЕГУЛЯРИЗОВАНОГО АЛГОРИТМУ
ОПЕРАТОРНОЇ ЕКСТРАПОЛЯЦІЇ ДЛЯ ВАРІАЦІЙНИХ НЕРІВНОСТЕЙ

Анотація. Запропоновано та досліджено новий алгоритм для розв’язання варіаційних нерівностей в гільбертових просторах. Запропонований ітераційний алгоритм є регуляризованим за допомогою схеми Гальперна методом операторної екстраполяції. За обсягом необхідних для здійснення ітераційного кроку обчислень алгоритм має перевагу над екстраградієнтним методом Корпелевич та методом екстраполяції з минулого. Для варіаційних нерівностей з монотонними, ліпшицевими операторами, що діють в гільбертовому просторі, доведено теорему про сильну збіжність методу.

Ключові слова: варіаційна нерівність, сідлова задача, монотонний оператор, метод операторної екстраполяції, метод Гальперна, регуляризація, сильна збіжність.


повний текст

СПИСОК ЛІТЕРАТУРИ

  1. Vedel Y.I., Sandrakov G.V., Semenov V.V. An adaptive two-stage proximal algorithm for equilibrium problems in Hadamard spaces. Cybernetics and Systems Analysis. 2020. Vol. 56, N 6. P. 978–989. https://doi.org/10.1007/s10559-020-00318-6.

  2. Vedel Y.I., Denisov S.V., Semenov V.V. An adaptive algorithm for the variational inequality over the set of solutions of the equilibrium problem. Cybernetics and Systems Analysis. 2021. Vol. 57, N 1. P. 91–100. https://doi.org/10.1007/s10559-021-00332-2.

  3. Semenov V.V., Denisov S.V., Kravets A.V. Adaptive two-stage Bregman method for variational inequalities. Cybernetics and Systems Analysis. 2021. Vol. 57, N 6. P. 959–967. https://doi.org/10.1007/s10559-021-00421-2.

  4. Semenov V.V., Denisov S.V., Sandrakov G.V., Kharkov O.S. Convergence of the operator extrapolation method for variational inequalities in Banach spaces. Cybernetics and Systems Analysis. 2022. Vol. 58, N 5. P. 740–753. https://doi.org/10.1007/s10559-022-00507-5.

  5. Lions J. L., Stampacchia G. Variational inequalities. Commun. Pure Appl. Math. 1967. Vol. XX. P. 493–519.

  6. Киндерлерер Д., Стампаккья Г. Введение в вариационные неравенства и их приложения. Москва: Мир, 1983. 256 c.

  7. Байокки К., Капело А. Вариационные и квазивариационные неравенства. Москва: Наука, 1988. 448 c.

  8. Nagurney A. Network economics: A variational inequality approach. Dordrecht: Kluwer Academic Publishers, 1999. 325 p.

  9. Nedi A., Ozdaglar A. Subgradient methods for saddle-point problems. Journal of Optimization Theory and Applications. 2009. Vol. 142. P. 205–228. https://doi.org/10.1007/ s10957-009-9522-7.

  10. Урясьев С.П. Адаптивные алгоритмы стохастической оптимизации и теории игр. Москва: Наука, 1990. 184 с.

  11. Bakushinskii A.B., Goncharskii A.V. Iterative methods for solving ill-posed problems. Moscow: Nauka, 1989. 126 p.

  12. Facchinei F., Pang J.-S. Finite-dimensional variational inequalities and complementarily problem. Vol. 2. New York: Springer, 2003. 666 p.

  13. Alber Y., Ryazantseva I. Nonlinear ill posed problems of monotone type. Dordrecht: Springer, 2006. 410 p.

  14. Bauschke H.H., Combettes P.L. Convex analysis and monotone operator theory in Hilbert spaces. Berlin; Heidelberg; New York: Springer, 2011. 408 p.

  15. 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.

  16. Wang J.-K., Abernethy J., Levy K.Y. No-regret dynamics in the Fenchel game: А unified framework for algorithmic convex optimization. аrXiv preprint arXiv:2111.11309.2021.

  17. Gidel G., Berard H., Vincent P., Lacoste-Julien S. A variational inequality perspective on generative adversarial networks. arXiv preprint arXiv:1802.10551.2018.

  18. Korpelevich G.M. An extragradient method for finding saddle points and for other problems. Matecon. 1976. Vol. 12, N 4. P. 747–756.

  19. Хоботов Е.Н. О модификации экстраградиентного метода для решения вариационных неравенств и некоторых задач оптимизации. Журнал вычислительной математики и математической физики. 1987. Т. 27, № 10. С. 1462–1473.

  20. Nadezhkina N., Takahashi W. Weak convergence theorem by an extragradient method for nonexpansive mappings and monotone mappings. Journal of Optimization Theory and Applications. 2006. Vol. 128. P. 191–201.

  21. Verlan D.A., Semenov V.V., Chabak L.M. A strongly convergent modified extragradient method for variational inequalities with non-lipschitz operators. Journal of Automation and Information Sciences. 2015. Vol. 47, Iss. 7. P. 31–46. https://doi.org/10.1615/ JAutomatInfScien.v47.i7.40.

  22. Denisov S.V., Nomirovskii D.A., Rublyov B.V., Semenov V.V. Convergence of extragradient algorithm with monotone step size strategy for variational inequalities and operator equations. Journal of Automation and Information Sciences. 2019. Vol. 51. Iss. 6. P. 12–24. https://doi.org/10.1615/JAutomatInfScien.v51.i6.20.

  23. Tseng P. A modified forward-backward splitting method for maximal monotone mappings. SIAM Journal on Control and Optimization. 2000. Vol. 38. P. 431–446.

  24. 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. https://doi.org/10.1007/s10957-010-9757-3.

  25. Censor Y., Gibali A., Reich S. Extensions of Korpelevich’s extragradient method for the variational inequality problem in Euclidean space. Optimization. 2012. Vol. 61, Iss. 9. P. 1119–1132. https://doi.org/10.1080/02331934.2010.539689.

  26. Semenov V.V. Modified extragradient method with Bregman divergence for variational inequalities. Journal of Automation and Information Sciences. 2018. Vol. 50, Iss. 8. P. 26–37. https://doi.org/10.1615/JAutomatInfScien.v50.i8.30.

  27. Bach F., Levy K.Y. A universal algorithm for variational inequalities adaptive to smoothness and noise. arXiv preprint arXiv:1902.01637.2019.

  28. Popov L.D. A modification of the Arrow-Hurwicz method for search of saddle points. Mathematical Notes of the Academy of Sciences of the USSR. 1980. Vol. 28, Iss. 5. P. 845–848.

  29. Mokhtari A., Ozdaglar A., Pattathil S. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: proximal point approach. arXiv preprint arXiv:1901.08511.2019.

  30. Chabak L., Semenov V., Vedel Y. A new non-Euclidean proximal method for equilibrium problems. In: Chertov O., Mylovanov T., Kondratenko Y., Kacprzyk J., Kreinovich V., Stefanuk V. (eds.) Recent developments in data science and intelligent analysis of information. ICDSIAI 2018. Advances in intelligent systems and computing, Springer, Cham, 2019. Vol. 836. P. 50–58. https://doi.org/10.1007/978-3-319-97885-7_6.

  31. Vedel Y.I., Sandrakov G.V., Semenov V.V., Chabak L.M. Convergence of a two-stage proximal algorithm for the equilibrium problem in Hadamard spaces. Cybernetics and Systems Analysis. 2020. Vol. 56, N 5. P. 784–792. https://doi.org/10.1007/s10559-020-00299-6.

  32. Malitsky Y., Tam M.K. A forward-backward splitting method for monotone inclusions without cocoercivity. SIAM Journal on Optimization. 2020. Vol. 30. P. 1451–1472. https://doi.org/10.1137/18M1207260.

  33. Iiduka H., Takahashi W. Weak convergence of a projection algorithm for variational inequalities in a Banach space. Journal of Mathematical Analysis and Applications. 2008. Vol. 339, N 1. P. 668–679. https://doi.org/10.1016/j.jmaa.2007.07.019.

  34. Shehu Y. Single projection algorithm for variational inequalities in Banach spaces with application to contact problem. Acta Math. Sci. 2020. Vol. 40. P. 1045–1063. https://doi.org/10.1007/s10473-020-0412-2.

  35. Yang J., Cholamjiak P., Sunthrayuth P. Modified Tseng’s splitting algorithms for the sum of two monotone operators in Banach spaces. AIMS Mathematics. 2021. Vol. 6, Iss. 5. P. 4873–4900. https://doi.org/10.3934/math.2021286.

  36. Halpern B. Fixed points of nonexpanding maps. Bull. Amer. Math. Soc. 1967. Vol. 73. P. 957–961.

  37. Xu H.K. Viscosity approximation methods for nonexpansive mappings. J. Math. Anal. Appl. 2004. Vol. 298. P. 279–291. https://doi.org/10.1016/j.jmaa.2004.04.059.

  38. Mainge P.-E. Strong convergence of projected subgradient methods for nonsmooth and nonstrictly convex minimization. Set-Valued Analysis. 2008. Vol. 16. P. 899–912.

  39. Gorbunov E., Loizou N., Gidel G. Extragradient method: last-iterate convergence for monotone variational inequalities and connections with cocoercivity. arXiv preprint arXiv: 2110.04261.2021. https://doi.org/10.48550/arXiv.2110.04261.

  40. Yoon T., Ryu E.K. Accelerated algorithms for smooth convex-concave minimax problems with rate on squared gradient norm. Proceedings of the 38th International Conference on Machine Learning. Proceedings of Machine Learning Research. 2021. Vol. 139. P. 12098–12109.




Інформація редакції Аннотації статей Автори Архів
Журнал Тематичні Розділи Редакція Редакційна колегія Приклади документів Передплата Контакти
© 2024 Kibernetika.org. All rights reserved.