Abstract
We consider the monotone variational inequality problem in a Hilbert space and describe a projection-type method with inertial terms under the following properties: (a) The method generates a strongly convergent iteration sequence; (b) The method requires, at each iteration, only one projection onto the feasible set and two evaluations of the operator; (c) The method is designed for variational inequality for which the underline operator is monotone and uniformly continuous; (d) The method includes an inertial term. The latter is also shown to speed up the convergence in our numerical results. A comparison with some related methods is given and indicates that the new method is promising.
Similar content being viewed by others
References
Alvarez, F., Attouch, H.: An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with dam**. Set-Valued Anal. 9, 3–11 (2001)
Apostol, R.Y., Grynenko, A.A., Semenov, V.V.: Iterative algorithms for monotone bilevel variational inequalities. J. Comp. Appl. Math. 107, 3–14 (2012)
Attouch, H., Goudon, X., Redont, P.: The heavy ball with friction. I. The continuous dynamical system. Commun. Contemp. Math 2(1), 1–34 (2000)
Attouch, H., Czarnecki, M.O.: Asymptotic control and stabilization of nonlinear oscillators with non-isolated equilibria. J. Differ. Equ. 179(1), 278–310 (2002)
Attouch, H., Peypouquet, J., Redont, P.: A dynamical approach to an inertial forward-backward algorithm for convex minimization. SIAM J. Optim. 24, 232–256 (2014)
Aubin, J.-P., Ekeland, I.: Applied Nonlinear Analysis. Wiley, New York (1984)
Baiocchi, C., Capelo, A.: Variational and Quasivariational Inequalities; Applications to Free Boundary Problems. Wiley, New York (1984)
Bauschke, H. H., Combettes, P. L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, CMS Books in Mathematics. Springer, New York (2011)
Bauschke, H. H., Combettes, P.L.: A weak-to-strong convergence principle for Fejér-monotone methods in Hilbert spaces. Math. Oper. Res. 26, 248–264 (2001)
Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1), 183–202 (2009)
Bot, R. I., Csetnek, E. R., Hendrich, C.: Inertial Douglas-Rachford splitting for monotone inclusion. Appl. Math. Comput 256, 472–487 (2015)
Bot, R. I., Csetnek, E. R.: An inertial alternating direction method of multipliers. Minimax Theory Appl. 1, 29–49 (2016)
Bot, R. I., Csetnek, E. R.: An inertial forward-backward-forward primal-dual splitting algorithm for solving monotone inclusion problems. Numer. Algorithms 71, 519–540 (2016)
Cegielski, A.: Iterative Methods for Fixed Point Problems in Hilbert Spaces, Lecture Notes in Mathematics 2057. Springer, Berlin (2012). ISBN 978-3-642-30900-7
Ceng, L.-C., Hadjisavvas, N., Wong, N.-C.: Strong convergence theorem by a hybrid extragradient-like approximation method for variational inequalities and fixed point problems. J. Glob. Optim 46, 635–646 (2010)
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.: The subgradient extragradient method for solving variational inequalities in Hilbert space. J. Optim. Theory Appl. 148, 318–335 (2011)
Chen, C., Chan, R. H., Ma, S., Yang, J.: Inertial proximal ADMM for linearly constrained separable convex optimization. SIAM J. Imaging Sci. 8, 2239–2267 (2015)
Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, Volume II. Springer Series in Operations Research. Springer, New York (2003)
Glowinski, R., Lions, J.-L., Trémolierès, R.: Numerical Analysis of Variational Inequalities. North-Holland, Amsterdam (1981)
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. 26, pp 265–284. AMS, Providence (1990)
He, Y. R.: A new double projection algorithm for variational inequalities. J. Comput. Appl. Math. 185, 166–173 (2006)
He, B.-S., Yang, Z.-H., Yuan, X.-M.: An approximate proximal-extragradient type method for monotone variational inequalities. J. Math. Anal. Appl. 300, 362–374 (2004)
Hieu, D. V., Anh, P. K., Muu, L. D.: Modified hybrid projection methods for finding common solutions to variational inequality problems. Comput. Optim. Appl. 66, 75–96 (2017)
Iusem, A. N., Nasri, M.: Korpelevich method for variational inequality problems in Banach spaces. J. Glob. Optim. 50, 59–76 (2011)
Iusem, A. N., Svaiter, B. F.: A variant of Korpelevich method for variational inequalities with a new search strategy. Optimization 42, 309–321 (1997)
Iusem, A.N., Gárciga Otero, R.: Inexact versions of proximal point and augmented Lagrangian algorithms in Banach spaces. Numer. Funct. Anal. Optim. 22, 609–640 (2001)
Kanzow, C., Shehu, Y.: Strong convergence of a double projection-type method for monotone variational inequalities in Hilbert spaces. J. Fixed Point Theory Appl. 20, 51 (2018)
Kinderlehrer, D., Stampacchia, G.: An Introduction to Variational Inequalities and Their Applications. Academic Press, New York (1980)
Korpelevich, G. M.: The extragradient method for finding saddle points and other problems. Ekonomika i Mat. Metody 12, 747–756 (1976)
Konnov, I. V.: Combined Relaxation Methods for Variational Inequalities. Springer, Berlin (2001)
Lorenz, D. A., Pock, T.: An inertial forward-backward algorithm for monotone inclusions. J. Math. Imaging Vis. 51, 311–325 (2015)
Lyashko, S. I., Semenov, V. V., Voitova, T. A.: Low-cost modification of Korpelevich’s method for monotone equilibrium problems. Cybernet. Systems Anal. 47, 631–639 (2011)
Khobotov, E. N.: Modification of the extragradient method for solving variational inequalities and certain optimization problems. USSR Comput. Math. Math. Phys. 27, 120–127 (1989)
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)
Maingé, P. E., Gobinddass, M. L.: Convergence of one-step projected gradient methods for variational Inequalities. J. Optim. Theory Appl. 171, 146–168 (2016)
Maingé, P. E.: Numerical approach to monotone variational inequalities by a one-step projected reflected gradient method with line-search procedure. Comp. Math. Appl. 72(3), 720–728 (2016)
Maingé, P. E.: Regularized and inertial algorithms for common fixed points of nonlinear operators. J. Math. Anal. Appl. 344, 876–887 (2008)
Maingé, P.-E.: Convergence theorems for inertial KM-type algorithms. J. Comput. Appl. Math. 219(1), 223–236 (2008)
Malitsky, Yu.: Projected reflected gradient methods for monotone variational inequalities. SIAM J. Optim. 25, 502–520 (2015)
Malitsky, Yu. V., Semenov, V. V.: A hybrid method without extrapolation step for solving variational inequality problems. J. Global Optim. 61, 193–202 (2015)
Malitsky, Y. V., Semenov, V. V.: An extragradient algorithm for monotone variational inequalities. Cybernet. Syst. Anal. 50, 271–277 (2014)
Mashreghi, J., Nasri, M.: Forcing strong convergence of Korpelevich’s method in Banach spaces with its applications in game theory. Nonlinear Anal. 72, 2086–2099 (2010)
Nadezhkina, N., Takahashi, W.: Strong convergence theorem by a hybrid method for nonexpansive map**s and Lipschitz-continuous monotone map**s. SIAM J. Optim. 16, 1230–1241 (2006)
Nagurney, A.: Network Economics: a Variational Inequality Approach. Kluwer Academic Publishers, Dordrecht (1999)
Ochs, P., Brox, T., Pock, T.: iPiasco: inertial proximal algorithm for strongly convex optimization. J. Math. Imaging Vis 53, 171–181 (2015)
Polyak, B. T.: Some methods of speeding up the convergence of iterarive methods. Zh. Vychisl. Mat. Mat. Fiz. 4, 1–17 (1964)
Popov, L. D.: A modification of the Arrow-Hurwicz method for finding saddle points. Math. Notes 28, 845–848 (1980)
Shehu, Y., Iyiola, O. S.: Strong convergence result for monotone variational inequalities. Numer. Algor. 76, 259–282 (2017)
Shehu, Y., Iyiola, O. S.: Iterative algorithms for solving fixed point problems and variational inequalities with uniformly continuous monotone operators. Numer. Algor. 79(2), 529–553 (2018)
Solodov, M.V., Svaiter, B.F.: A new projection method for variational inequality problems. SIAM J. Control Optim. 37, 765–776 (1999)
Lions, J.-L., Stampacchia, G.: Variational inequalities. Comm. Pure Appl. Math. 20, 493–519 (1967)
Tseng, P.: A modified forward-backward splitting method for maximal monotone map- **s. SIAM J. Control Optim. 38, 431–446 (2000)
Takahashi, W.: Nonlinear Functional Analysis. Yokohama Publishers, Yokohama (2000)
Acknowledgements
Discussion with Christian Kanzow is gratefully acknowledged.
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.
The research of this author is supported by the ERC grant at the IST.
Rights and permissions
About this article
Cite this article
Shehu, Y., Li, XH. & Dong, QL. An efficient projection-type method for monotone variational inequalities in Hilbert spaces. Numer Algor 84, 365–388 (2020). https://doi.org/10.1007/s11075-019-00758-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-019-00758-y