Cybernetics And Systems Analysis logo
Editorial Board Announcements Abstracts Authors Archive
KIBERNETYKA TA SYSTEMNYI ANALIZ
International Theoretical Science Journal
Volume 60 >>> № 3 MAY — JUNE 2024
-->

DOI 10.34229/KCA2522-9664.24.3.6
UDC 517.988
V.V. Semenov1, O.S. Kharkov2


1 Taras Shevchenko National University of Kyiv, Kyiv, Ukraine

 semenov.volodya@gmail.com

2 Taras Shevchenko National University of Kyiv, Kyiv, Ukraine

 olehharek@gmail.com

STRONG CONVERGENCE OF THE REGULARIZED OPERATOR
EXTRAPOLATION ALGORITHM FOR VARIATIONAL INEQUALITIES

Abstract. The article proposes and investigates a new algorithm for solving variational inequalities in Hilbert spaces. The proposed iterative algorithm is regularized by the operator extrapolation method using the Halpern scheme. In terms of the amount of computation required for the iterative step, the algorithm has an advantage over the Korpelevich extragradient method and the method of extrapolation from the past. For variational inequalities with monotone, Lipschitz continuous operators acting in Hilbert space, a theorem on the strong convergence of the method is proved.

Keywords: variational inequality, saddle point problem, monotone operator, operator extrapolation method, Halpern method, regularization, strong convergence.


full text

REFERENCES

  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. Kinderlerer D., Stampacchia G. Introduction to variational inequalities and their applications [Russian translation]. Moscow: Mir, 1983. 256 p.

  7. Baiocchi K., Capelo A. Variational and quasi-variational inequalities [Russian translation]. Moscow: Nauka, 1988. 448 p.

  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. Uryasev S.P. Adaptive algorithms for stochastic optimization and game theory [in Russian]. Moscow: Nauka, 1990. 184 p.

  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. Khobotov E.N. On modification of the extragradient method for solving variational inequalities and some optimization problems. Journal of Computational Mathematics and Mathematical Physics. 1987. Vol. 27, N 10. P. 1462–1473.

  20. Nadezhkina N., Takahashi W. Weak convergence theorem by an extragradient method for nonexpansive mappings and monotone mappings. Zhurnal vychislitel'noy matematiki i matematicheskoy fiziki. 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.




Editorial Board Announcements Abstracts Authors Archive
about scope office editorial board instructions for authors subscriptions contacts
© 2024 Kibernetika.org. All rights reserved.