EXTRAPOLATION FROM THE PAST METHOD FOR VARIATIONAL INEQUALITIES IN A HILBERT SPACE
Abstract
The article considers variational inequalities with operators acting in a Hilbert space. For these problems, variants of the Extrapolation from the Past method have been proposed and studied. A sub-linear efficiency estimate for the gap function is proved. The strong convergence of the Extrapolation from the Past method for variational inequalities with uniformly monotone operators is proved. The linear rate of convergence of the Extrapolation from the Past method for variational inequalities with operators satisfying the generalized strong monotonicity condition is proved. An adaptive version of the algorithm is proposed. Regularized variants of the algorithm are proposed and theorems on their strong convergence are proved.
References
Korpelevich G. M. An extragradient method for finding saddle points and for other problems. Matecon. 1976. Vol. 12. No. 4. P. 747–756.
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. Issue 5. P. 845–848.
Gidel G., Berard H., Vincent P., Lacoste-Julien S. A Variational Inequality Perspective on Generative Adversarial Networks. arXiv preprint arXiv:1802.10551. 2018.
Patriksson M. Nonlinear programming and variational inequality problems: A unified approach. Dordrecht: Kluwer Academic Publishers, 1999. xiv + 334 p.
Nagurney A. Network economics: A variational inequality approach. Dordrecht: Kluwer Academic Publishers, 1999. 325 p.
Alber Y., Ryazantseva I. Nonlinear Ill Posed Problems of Monotone Type. Dordrecht: Springer, 2006. 410 p.
Kassay G., Radulescu V. D. Equilibrium Problems and Applications. London: Academic Press, 2019. xx + 419 p.
Polyak R. Finding Nonlinear Production–Consumption Equilibrium. arXiv preprint arXiv:2204.04496. 2022.
Konnov I. V. Combined relaxation methods for variational inequalities. Berlin, Heidelberg, New York: Springer–Verlag, 2001. 181 p.
Bauschke H. H., Combettes P. L. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Berlin-Heidelberg-New York: Springer, 2011. 408 p.
Semenov V. V. Variational inequalities: theory and algorithms. Kyiv: "Kyiv University", 2021. 167 p.
Nemirovski A. Prox-method with rate of convergence O(1/T) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. on Optim. 2004. Vol. 15. P. 229–251.
Nesterov Y. Dual Extrapolation and Its Applications to Solving Variational Inequalities and Related Problems. Math. Program. 2007. V. 109. No. 2-3. P. 319–344.
Mainge P.-E. Strong convergence of projected subgradient methods for nonsmooth and nonstrictly convex minimization. Set-Valued Analysis. 2008. Vol. 16. P. 899–912.
Opial Z. Weak convergence of the sequence of successive approximations for nonexpansive mappings. Bull. Amer. Math. Soc. 1967. Vol. 73. P. 591–597.
Popov L. D. On schemes for the formation of a master sequence in a regularized extragradient method for solving variational inequalities. Russian Mathematics. 2004. Vol. 48. Issue 1. P. 67–76.
Malitsky Yu. V., Semenov V. V. An extragradient algorithm for monotone variational inequalities. Cybernetics and Systems Analysis. 2014. Vol. 50. P. 271–277.
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.
Mokhtari A., Ozdaglar A., Pattathil S. Convergence rate of O(1/k) for optimistic gradient and extra-gradient methods in smooth convex-concave saddle point problems. arXiv preprint arXiv:1906.01115. 2020.
Denysov S., Semenov V. Theoretical Bound of the Complexity of Some Extragradient-Type Algorithms for Variational Inequalities in Banach Spaces. Selected Papers of the VIII International Scientific Conference “Information Technology and Implementation” (IT&I-2021). Workshop Proceedings, Kyiv, Ukraine, December 1-3, 2021. CEUR Workshop Proceeedings, vol. 3179. 2022. P. 144–155.
Semenov V. V., Denisov S. V. Convergence of the Method of Extrapolation from the Past for Variational Inequalities in Uniformly Convex Banach Spaces. Cybernetics and Systems Analysis. 2022. Vol. 58. Iss. 4. P. 564–575.
Lyashko S. I., Semenov V. V. A New Two-Step Proximal Algorithm of Solving the Problem of Equilibrium Programming. In: B. Goldengorin (ed.) Optimization and Its Applications in Control and Data Sciences. Springer Optimization and Its Applications, vol. 115. Springer, Cham, 2016. P. 315–325.
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, vol. 836. Springer, Cham, 2019. P. 50–58.
Semenov V. V. A Version of the Mirror descent Method to Solve Variational Inequalities. Cybernetics and Systems Analysis. 2017. Vol. 53. P. 234–243.
Semenov V. V. A variant of mirror descent method for solving variational inequalities. In: Polyakova, L. N. (ed.) Constructive Nonsmooth Analysis and Related Topics (dedicated to the memory of V. F. Demyanov). IEEE, 2017. P. 281–284.
Nomirovskii D. A., Rublyov V. V., Semenov V. V. Convergence of Two-Stage Method with Bregman Divergence for Solving Variational Inequalities. Cybernetics and Systems Analysis. 2019. Vol. 55. P. 359–368.
Semenov V. V., Denisov S. V., Kravets A. V. Adaptive Two-Stage Bregman Method for Variational Inequalities. Cybernetics and Systems Analysis. 2021. Vol. 57. Issue 6. P. 959–967.
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. Issue 5. P. 784–792.
Vedel Y., Semenov V. Adaptive Extraproximal Algorithm for the Equilibrium Problem in Hadamard Spaces. In: Olenev N., Evtushenko Y., Khachay M., Malkova V. (eds.) Optimization and Applications. OPTIMA 2020. Lecture Notes in Computer Science, vol. 12422. Springer, Cham, 2020. P. 287–300.
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. Issue 6. P. 978–989.
Semenov V., Vedel Y. Convergence of adaptive methods for equilibrium problems in Hadamard spaces. Proceedings of the 7th International Conference “Information Technology and Interactions" (IT&I-2020). Workshops Proceedings Kyiv, Ukraine, December 02-03, 2020. CEUR Workshop Proceedings, vol. 2845. 2021. P. 321–335.
Denisov S., Semenov V., Vedel Y. Adaptive Algorithm for Variational Inequality Problem Over the Set of Solutions the Equilibrium Problem. 2020 IEEE 2nd International Conference on Advanced Trends in Information Theory (ATIT), Kyiv, Ukraine, 2020. P. 325–329.
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. Issue 1. P. 91–100.
Khanh P. D., Vuong P. T. Modified projection method for strongly pseudomonotone variational inequalities. J. Glob. Optim. 2014. Vol. 58. P. 341–350.
Bakushinskii A. B., Goncharskii A. V. Iterative Methods for Solving Ill-Posed Problems. Moscow: Nauka, 1989. 126 p.
Browder F. Existence and approximation of solutions of nonlinear variational inequalities. Proc. Nat. Acad. Sci. USA. 1966. Vol. 56. No. 4. P. 1080–1086.
Browder F. E. Convergence of approximants of fixed points of nonexpansive nonlinear mappings in Banach spaces. Arch. Rational Mech. Anal. 1967. Vol. 24. P. 82–90.
Combettes P. L., Hirstoaga S. A. Equilibrium Programming in Hilbert Spaces. J. Nonlinear Convex Anal. 2005. Vol. 6. P. 117–136.
Apostol R. Ya., Grynenko A. A., Semenov V. V. Iterative algorithms for monotone bilevel variational inequalities. J. Num. Appl. Math. 2012. No. 1 (107). P. 3–14. (In Ukrainian)
