Abstract
We develop versions of the subgradient extragradient method for variational inequalities in Hilbert spaces and establish sufficient conditions for their convergence. First we prove a sufficient condition for a weak convergence of a recent existing algorithm under relaxed assumptions. Then, we propose two other algorithms. Both weak and strong convergence of the considered algorithms are studied. Under additional strong pseudomonotonicity and Lipschitz continuity assumptions, we obtain also a \(Q\)-linear convergence rate of these algorithms. Our results improve some recent contributions in the literature. Illustrative numerical experiments are also provided by the end of the paper.
Similar content being viewed by others
References
Antipin, A.S.: On a method for convex programs using a symmetrical modification of the Lagrange function. Ekon. Mat. Metody 12, 1164–1173 (1976)
Ceng, L.C., Teboulle, M., Yao, J.C.: Weak convergence of an iterative method for pseudomonotone variational inequalities and fixed-point problems. J. Optim. Theory Appl. 146, 19–31 (2010)
Censor, Y., Gibali, A., Reich, S.: The subgradient extragradient method for solving variational inequalities in Hilbert space. J. Optim. Theory Appl. 148, 318–335 (2011)
Censor, Y., Gibali, A., Reich, S.: Strong convergence of subgradient extragradient methods for the variational inequality problem in Hilbert space. Optim. Methods Softw. 26, 827–845 (2011)
Censor, Y., Gibali, A., Reich, S.: Extensions of Korpelevich’s extragradient method for the variational inequality problem in Euclidean space. Optimization 61, 1119–1132 (2011)
Cottle, R.W., Yao, J.C.: Pseudo-monotone complementarity problems in Hilbert space. J. Optim. Theory Appl. 75, 281–295 (1992)
Denisov, S.V., Semenov, V.V., Chabak, L.M.: Convergence of the modified extragradient method for variational inequalities with non-Lipschitz operators. Cybern. Syst. Anal. 51, 757–765 (2015)
Dong, Q.L., Jiang, D., Gibali, A.: A modified subgradient extragradient method for solving the variational inequality problem. Numer. Algorithms 79, 927–940 (2018)
Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer Series in Operations Research, vols. I and II. Springer, New York (2003)
Goebel, K., Reich, S.: Uniform Convexity, Hyperbolic Geometry, and Nonexpansive Mappings. Dekker, New York (1984)
Halpern, B.: Fixed points of nonexpanding maps. Proc. Am. Math. Soc. 73, 957–961 (1967)
Harker, P.T., Pang, J.S.: A damped-Newton method for the linear complementarity problem. In: Allgower, G., Georg, K. (eds.) Computational Solution of Nonlinear Systems of Equations. Lectures in Appl. Math., vol. 26, pp. 265–284. AMS, Providence (1990)
He, B.S.: A class of new methods for monotone variational inequalities. Appl. Math. Optim. 35, 69–76 (1997)
Hieu, D.V., Thong, D.V.: New extragradient-like algorithms for strongly pseudomonotone variational inequalities. J. Glob. Optim. 70, 385–399 (2018)
Iusem, A.N., Nasri, M.: Korpelevich’s method for variational inequality problems in Banach spaces. J. Glob. Optim. 50, 59–76 (2011)
Karamardian, S., Schaible, S.: Seven kinds of monotone maps. J. Optim. Theory Appl. 66, 37–46 (1990)
Khanh, P.D.: A new extragradient method for strongly pseudomonotone variational inequalities. Numer. Funct. Anal. Optim. 37, 1131–1143 (2016)
Kinderlehrer, D., Stampacchia, G.: An Introduction to Variational Inequalities and Their Applications. Academic Press, New York (1980)
Konnov, I.V.: Combined Relaxation Methods for Variational Inequalities. Springer, Berlin (2000)
Korpelevich, G.M.: The extragradient method for finding saddle points and other problems. Ekon. Mat. Metody 12, 747–756 (1976)
Kraikaew, R., Saejung, S.: Strong convergence of the Halpern subgradient extragradient method for solving variational inequalities in Hilbert spaces. J. Optim. Theory Appl. 163, 399–412 (2014)
Lyashko, S.I., Semenov, V.V., Voitova, T.A.: Low-cost modification of Korpelevich’s method for monotone equilibrium problems. Cybern. Syst. Anal. 47, 631–639 (2011)
Maingé, P.E.: A hybrid extragradient-viscosity method for monotone operators and fixed point problems. SIAM J. Control Optim. 47, 1499–1515 (2008)
Opial, Z.: Weak convergence of the sequence of successive approximations for nonexpansive mappings. Bull. Am. Math. Soc. 73, 591–597 (1967)
Ortega, J.M., Rheinboldt, W.C.: Iterative Solution of Nonlinear Equations in Several Variables. Academic Press, New York (1970)
Shehu, Y., Iyiola, O.S.: Strong convergence result for monotone variational inequalities. Numer. Algorithms 76, 259–282 (2017)
Stampacchia, G.: Formes bilineaires coercitives sur les ensembles convexes. C. R. Acad. Sci. 258, 4413–4416 (1964)
Thong, D.V., Gibali, A.: Extragradient methods for solving non-Lipschitzian pseudo-monotone variational inequalities. J. Fixed Point Theory Appl. 21, 20 (2019)
Thong, D.V., Hieu, D.V.: Weak and strong convergence theorems for variational inequality problems. Numer. Algorithms 78, 1045–1060 (2018)
Thong, D.V., Hieu, D.V.: Modified subgradient extragradient method for variational inequality problems. Numer. Algorithms 79, 597–610 (2018)
Thong, D.V., Hieu, D.V.: Inertial extragradient algorithms for strongly pseudomonotone variational inequalities. J. Comput. Appl. Math. 314, 80–98 (2018)
Tseng, P.: A modified forward-backward splitting method for maximal monotone mappings. SIAM J. Control Optim. 38, 431–446 (1998)
Vuong, P.T.: On the weak convergence of the extragradient method for solving pseudo-monotone variational inequalities. J. Optim. Theory Appl. 176, 399–409 (2018)
Vuong, P.T., Shehu, Y.: Convergence of an extragradient-type method for variational inequality with applications to optimal control problems. Numer. Algorithms 81, 269–291 (2018)
Xu, H.K.: Iterative algorithms for nonlinear operators. J. Lond. Math. Soc. 66, 240–256 (2002)
Yang, J., Liu, H., Liu, Z.: Modified subgradient extragradient algorithms for solving monotone variational inequalities. Optimization 67, 2247–2258 (2018)
Yao, Y., Postolache, M.: Iterative methods for pseudomonotone variational inequalities and fixed point problems. J. Optim. Theory Appl. 155, 273–287 (2012)
Acknowledgements
The first author is supported by the National Foundation for Science and Technology Development (NAFOSTED) of Vietnam under the grant number 101.01-2020.23. A significant part of the paper was completed during a scientific stay of the authors at the Vietnam Institute for Advanced Study in Mathematics (VIASM), whose support and hospitality are gratefully appreciated. The third named author is funded by Vietnam National Foundation for Science and Technology Development (NAFOSTED) under grant number 101.01-2020.09. The authors are very thankful to the Editor and the two anonymous Reviewers for their valuable remarks and suggestions.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Khanh, P.Q., Thong, D.V. & Vinh, N.T. Versions of the Subgradient Extragradient Method for Pseudomonotone Variational Inequalities. Acta Appl Math 170, 319–345 (2020). https://doi.org/10.1007/s10440-020-00335-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10440-020-00335-9
Keywords
- Extragradient method
- Subgradient extragradient method
- Variational inequality
- Pseudomonotonicity
- Weak and strong convergence
- \(Q\)-linear convergence rate