Abstract
A new iterative algorithm is proposed for solving the variational inequality problem with a monotone and Lipschitz continuous mapping in a Hilbert space. The algorithm is based on the following two well-known methods: the Popov algorithm and so-called subgradient extragradient algorithm. An advantage of the algorithm is the computation of only one value of the inequality mapping and one projection onto the admissible set per one iteration. The weak convergence of sequences generated by the proposed algorithm is proved.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
J. L. Lions, Certain Methods of Solution of Nonlinear Boundary-Value Problems [Russian translation], Mir, Moscow (1972).
D. Kinderlerer and G. Stampacchia, An Introduction to Variational Inequalities and Their Applications [Russian translation], Mir, Moscow (1983).
C. Baiocchi and A. Capelo, Variational and Quasivariational Inequalities [Russian translation], Nauka, Moscow (1988).
I. V. Konnov, “On systems of variational inequalities,” Izv. Vyssh. Uchebn. Zaved., Mat., No. 12, 79–88 (1997).
A. Nagurney, Network Economics: A Variational Inequality Approach, Kluwer, Dordrecht (1999).
V. V. Semenov and N. V. Semenova, “A vector problem of optimal control in a Hilbert space,” Cybernetics and Systems Analysis, 41, No. 2, 255–266 (2005).
E. G. Golshtein and N. V. Tretyakov, Modified Lagrange Functions: Theory and Optimization Methods [in Russian], Nauka, Moscow (1989).
A. B. Bakushinskii and A. V. Goncharskii, Ill-Posed Problems: Numerical Methods and Applications [in Russian], Mosk. Gos. Univ., Moscow (1989).
I. V. Konnov, Combined Relaxation Methods for Variational Inequalities, Springer, Berlin-Heidelberg–New York (2001).
F. Facchinei and J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problem, Vol. 2, Springer, New York (2003).
V. V. Vasin and I. I. Eremin, Operators and Iterative Fejer Processes: Theory and Applications [in Russian], Regular and Chaotic Dynamics, Moscow–Izhevsk (2005).
B. N. Pshenichnyi and M. U. Kalzhanov, “A method for solving variational inequalities,” Cybernetics and Systems Analysis, 28, No. 6, 846–853 (1992).
V. V. Kalashnikov and N. I. Kalashnikova, “Solution of two-level variational inequality,” Cybernetics and Systems Analysis, 30, No. 4, 623–625 (1994)
V. M. Panin, V. V. Skopetskii, and T. V. Lavrina, “Models and methods of finite-dimensional variational inequalities,” Cybernetics and Systems Analysis, 36, No. 6, 47–64 (2000).
N. Xiu and J. Zhang, “Some recent advances in projection-type methods for variational inequalities,” J. Comput. Appl. Math., 152, 559–585 (2003).
N. Nadezhkina and W. Takahashi, “Strong convergence theorem by a hybrid method for nonexpansive mappings and Lipschitz-continuous monotone mappings,” SIAM J. Optim., 16, No. 4, 1230–1241 2006.
Nadezhkina and W. Takahashi, “Weak convergence theorem by an extragradient method for nonexpansive mappings and monotone mappings,” J. Optim. Theory and Appl., 128, 191–201 (2006).
E. A. Nurminskii, “The use of additional diminishing disturbances in Fejer models of iterative algorithms,” Zh. Vychisl. Mat. Mat. Fiziki, 48, No. 12, 2121–2128 (2008).
V. V. Semenov, “On the parallel proximal decomposition method for solving problems of convex optimization,” Journal of Automation and Information Sciences, No. 2, 42–46 (2010).
Yu. V. Malitsky and V. V. Semenov, “New theorems on the strong convergence of the proximal method for the problem of equilibrium programming,” Zh. Obchisl. Prykl. Mat., No. 3 (102), 79–88 (2010).
V. V. Semenov, “On the convergence of methods for solving two-level variational inequalities with monotone mappings,” Zh. Obchisl. Prykl. Mat., No. 2 (101), 120–128 (2010).
S. V. Denisov and V. V. Semenov, “A proximal algorithm for two-level variational inequalities: Strong convergence,” Zh. Obchisl. Prykl. Mat., No. 3 (106), 27–32 (2011).
V. V. Semenov, “Parallel decomposition of variational inequalities with monotone mappings,” Zh. Obchisl. Prykl. Mat., No. 2 (108), 53–58 (2012).
A. S. Antipin, “On a convex programming method using a symmetrical modification of the Lagrange function,” Ekonomika i Mat. Metody, 12, No. 6, 1164–1173 (1976).
G. M. Korpelevich, “An extragradient method for finding saddle points and for other problems,” Ekonomika i Mat. Metody, 12, No. 4, 747–756 (1976).
E. N. Hobotov, “On a modification of the extragradient method for solving variational inequalities and some optimization problems,” Zh. Vychisl. Mat. Mat. Fiz., 27, No. 10, 1462–1473 (1987).
A. V. Zykina and N. V. Melen’chuk, “A two-step extragradient method for variational inequalities,” Izv. Vyssh. Uchebn. Zaved., Mat., 9, 82–85 (2010).
D. N. Zaporozhets, A. V. Zykina, and N. V. Melen’chuk, “Comparative analysis of extragradient methods for solving variational inequalities for some problems,” Automatics and Telemechanics, No. 4, 32–46 (2012).
T. A. Voitova, S. V. Denisov, and V. V. Semenov, “A strongly convergent modified version of the Korpelevich method for equilibrium programming problems,” Zh. Obchisl. Prykl. Mat., No. 1 (104), 10–23 (2011).
R. Ya. Apostol, A. A. Grinenko, and V. V. Semenov, “Iterative algorithms for monotone two-level variational inequalities,” Zh. Obchisl. Prykl. Mat., No. 1 (107) 3–14 (2012).
L. D. Popov, “A modification of the Arrow-Hurwicz method for searching for saddle points,” Mat. Zametki, 28, No. 5, 777–784 (1980).
Y. Censor, A. Gibali, and S. Reich, “The subgradient extragradient method for solving variational inequalities in Hilbert space,” J. Optim. Theory and Appl., 148, 318–335 (2011).
S. I. Lyashko, V. V. Semenov, and T. A. Voitova, “Low-cost modification of Korpelevich’s methods for monotone equilibrium problems,” Cybernetics and Systems Analysis, 47, No. 4, 631–640 (2011).
H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Springer, Berlin–Heidelberg–New York (2011).
Z. Opial, “Weak convergence of the sequence of successive approximations for nonexpansive mappings,” Bull. Amer. Math. Soc., 73, 591–597 (1967).
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was financed by the Verkhovna Rada of Ukraine (the nominal grant of the Verkhovna Rada of Ukraine for 2013 to support scientific researches of young scientists) and the State Fund for Fundamental Researches of Ukraine (project GP/F49/061).
Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 125–131, March–April, 2014.
Rights and permissions
About this article
Cite this article
Malitsky, Y.V., Semenov, V.V. An Extragradient Algorithm for Monotone Variational Inequalities. Cybern Syst Anal 50, 271–277 (2014). https://doi.org/10.1007/s10559-014-9614-8
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10559-014-9614-8