zbMATH — the first resource for mathematics

Unified framework of extragradient-type methods for pseudomonotone variational inequalities. (English) Zbl 1039.49014
Summary: We propose a unified framework of extragradient-type methods for solving pseudomonotone variational inequalities, which allows one to take different stepsize rules and requires the computation of only two projections at each iteration. It is shown that the modified extragradient method of A. N. Iusem and B. F. Svaiter [Optimization 42, No. 4, 309–321 (1977; Zbl 0891.90135)] falls within this framework with a short stepsize and so does the method of M. V. Solodov and B. F.Svaiter [SIAM J. Control Optimization 37, No. 3, 765–776 (1999; Zbl 0959.49007)] with a long stepsize. It is further demonstrated that the algorithmic framework is globally convergent under mild assumptions and is sublinearly convergent if in addition a projection-type error bound holds locally. Preliminary numerical experiments are reported.

49J40 Variational inequalities
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
Full Text: DOI
[1] Iusem, A. N., and Svaiter, B. F., A Variant of Korpelevich’s Method for Variational Inequalities with a New Search Strategy, Optimization, Vol. 42, pp. 309–321, 1997. · Zbl 0891.90135 · doi:10.1080/02331939708844365
[2] Solodov, M. V., and Svaiter, B. F., A New Projection Method for Variational Inequality Problems, SIAM Journal on Control and Optimization, Vol. 37, pp. 765–776, 1999. · Zbl 0959.49007 · doi:10.1137/S0363012997317475
[3] Harker, P. T., and Pang, J. S., Finite-Dimensional Variation Inequality and Nonlinear Complementarity Problems: A Survey of Theory, Algorithms, and Applications, Mathematical Programming, Vol. 48, pp. 161–220, 1990. · Zbl 0734.90098 · doi:10.1007/BF01582255
[4] Glowinski, R., Numerical Methods for Nonlinear Variational Problems, Springer Verlag, Berlin, Germany, 1984. · Zbl 0536.65054
[5] Giannessi, F., and Maugeri, A., Variational Inequalities and Network Equilibrium Problems, Plenum Press, New York, NY, 1995. · Zbl 0834.00044
[6] Ferris, C., and Pang, J. S., Complementarity and Variational Problems: State of the Art, SIAM Publications, Philadelphia, Pennsylvania, 1997. · Zbl 0891.90158
[7] Korpelevich, G. M., The Extragradient Method for Finding Saddle Points and Other Problems, Matecon, Vol. 12, pp. 747–756, 1976. · Zbl 0342.90044
[8] Khobotov, E. N., Modification of the Extragradient Method for Solving Variational Inequalities and Certain Optimization Problems, USSR Computational Mathematics and Mathematical Physics, Vol. 27, pp. 120–127, 1987. · Zbl 0665.90078 · doi:10.1016/0041-5553(87)90058-9
[9] Iusem, A. N., An Iterative Algorithm for the Variational Inequality Problem, Computational and Applied Mathematics, Vol. 13, pp. 103–114, 1994. · Zbl 0811.65049
[10] Marcotte, P., Application of Khoboto’vs Algorithm to Variational Inequalities and Network Equilibrium Problems, Information Systems and Operational Research, Vol. 29, pp. 258–270, 1991. · Zbl 0781.90086 · doi:10.1080/03155986.1991.11732174
[11] Sun, D., A New Stepsize Skill for Solving a Class of Nonlinear Projection Equations, Journal of Computational Mathematics, Vol. 13, pp. 357–368, 1995. · Zbl 0854.65048
[12] Solodov, M. V., and Tseng, P., Modified Projection-Type Methods for Monotone Variational Inequalities, SIAM Journal on Control and Optimization, Vol. 34, pp. 1814–1830, 1996. · Zbl 0866.49018 · doi:10.1137/S0363012994268655
[13] Konnov, I. V., A Class of Combined Iterative Methods for Solving Variational Inequalities, Journal of Optimization Theory and Applications, Vol. 94, pp. 677–693, 1997. · Zbl 0892.90172 · doi:10.1023/A:1022605117998
[14] He, B. S., A Class of Projection and Contraction Methods for Monotone Variational Inequalities, Applied Mathematics and Optimization, Vol. 35, pp. 69–76, 1997. · Zbl 0865.90119 · doi:10.1007/BF02683320
[15] Zarantonello, E. H., Projections on Convex Sets in Hilbert Space and Spectral Theory, Contributions to Nonlinear Functional Analysis, Edited by E. H. Zarantonello, Academic Press, New York, NY, 1971. · Zbl 0281.47043
[16] Calamai, P. H., and MorÁ, J. J., Projected Gradient Methods for Linearly Constrained Problems, Mathematical Programming, Vol. 39, pp. 93–116, 1987. · Zbl 0634.90064 · doi:10.1007/BF02592073
[17] Wang, C. Y., and Zhao, F., Directional Derivatives of Optimal Value Functions in Mathematical Programming, Journal of Optimization Theory and Applications, Vol. 82, pp. 397–404, 1994. · Zbl 0844.90091 · doi:10.1007/BF02191862
[18] Kinderlehrer, D., and Stampacchia, G., An Introduction to Variational Inequalities and Their Applications, Academic Press, New York, NY, 1980. · Zbl 0457.35001
[19] Luo, Z. Q., and Tseng, P., Error Bound and Convergence Analysis of Matrix Splitting Algorithms for the Affine Variational Inequality Problem, SIAM Journal on Optimization, Vol. 2, pp. 43–54, 1992. · Zbl 0777.49010 · doi:10.1137/0802004
[20] Tseng, P., On Linear Convergence of Iterative Methods for the Variational Inequality Problem, Journal of Computational and Applied Mathematics, Vol. 60, pp. 237–252, 1995. · Zbl 0835.65087 · doi:10.1016/0377-0427(94)00094-H
[21] Luo, Z. Q., and Tseng, P., On the Linear Convergence of Descent Methods for Convex Essentially Smooth Minimization, SIAM Journal on Control and Optimization, Vol. 30, pp. 408–425, 1992. · Zbl 0756.90084 · doi:10.1137/0330025
[22] Zanni, L., On the Convergence Rate of Two Projection Methods for Variational Inequalities in Rn, Calcolo, Vol. 29, pp. 193–212, 1992. · Zbl 0794.65060 · doi:10.1007/BF02576182
[23] Zanni, L., Convergence Properties of a Projection Method for Affine Variational Inequality Problems, Matematiche (Catania), Vol. 49, pp. 359–377, 1994. · Zbl 1006.65072
[24] Polyak, B. T., Introduction to Optimization, Optimization Software, New York, NY, 1987.
[25] Pang, J. S., and Gabriel, A., NE/SQP: A Robust Algorithm for the Nonlinear Complementarity Problem, Mathematical Programming, Vol. 60, pp. 295–337, 1993. · Zbl 0808.90123 · doi:10.1007/BF01580617
[26] Harker, P. T., Accelerating the Convergence of the Diagonalization and Projection Algorithms for Finite-Dimensional Variational Inequalities, Mathematical Programming, Vol. 41, pp. 25–59, 1988. · Zbl 0825.49019 · doi:10.1007/BF01580752
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.