×

zbMATH — the first resource for mathematics

Modified extragradient method for variational inequalities and verification of solution existence. (English) Zbl 1045.49017
Summary: We propose a modified extragradient method for solving variational inequalities (VI) which has the following nice features: (i) The generated sequence possesses an expansion property with respect to the starting point; (ii) the existence of the solution to a VI problem can be verified through the behavior of the generated sequence from the fact that the iterative sequence diverges to infinity if and only if the solution set is empty. Global convergence of the method is guaranteed under mild conditions. Our preliminary computational experience is also reported.

MSC:
49J40 Variational inequalities
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Cottle, R. W., Pang, J. S., and Stone, R. E., The Linear Complementarity Problem, Academic Press, New York, NY, 1992. · Zbl 0757.90078
[2] Ferris, M. C., and Pang, J. S., Engineering and Economic Applications of Complementarity Problems, SIAM Review, Vol. 39, pp. 669-713, 1997. · Zbl 0891.90158 · doi:10.1137/S0036144595285963
[3] Ferris, M. C., and Pang, J. S., Complementarity and Variational Problems: State of Art, SIAM Publications, Philadelphia, Pennsylvania, 1997.
[4] Harker, P. T., and Pang, J. S., Finite-Dimensional Variational Inequality and Nonlinear Complementarity Problems: A Survey of Theory, Algorithm, and Applications, Mathematical Programming, Vol. 48, pp. 161-220, 1990. · Zbl 0734.90098 · doi:10.1007/BF01582255
[5] Kinderlehrer, D., and Stampacchia, G., An Introduction to Variational Inequalities and Their Applications, Academic Press, New York, NY, 1980. · Zbl 0457.35001
[6] Glowinski, R., Numerical Methods for Nonlinear Variational Inequality Problems, Springer Verlag, New York, NY, 1984. · Zbl 0536.65054
[7] Crouzeix, J. P., Pseudomonotone Variational Inequality Problems: Existence of Solutions, Mathematical Programming, Vol. 78, pp. 305-314, 1997. · Zbl 0887.90167
[8] Sun, D., A Class of Iterative Methods for Solving Nonlinear Projection Equations, Journal of Optimization Theory and Applications, Vol. 91, pp. 123-140, 1996. · Zbl 0871.90091 · doi:10.1007/BF02192286
[9] Korpelevich, G. M., The Extragradient Method for Finding Saddle Points and Other Problems, Matecon, Vol. 12, pp. 747-756, 1976. · Zbl 0342.90044
[10] Khobotov, E. N., Modification of the Extragradient Method for Solving Variational Inequalities and Certain Optimization Problem, USSR Computational Mathematics and Mathematical Physics, Vol. 27, pp. 120-127, 1987. · Zbl 0665.90078 · doi:10.1016/0041-5553(87)90058-9
[11] Sibony, M., Méthodes Itératives pour les Equations et Inéquations aux Dérivées Partielles Nonlinéares de Type Monotone, Calcolo, Vol. 7, pp. 65-183, 1970. · Zbl 0225.35010 · doi:10.1007/BF02575559
[12] Bakusinskji, A. B., and Polyak, B. T., On the Solution of Variational Inequalities, Soviet Mathematics Doklady, Vol. 15, pp. 1705-1710, 1974.
[13] 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
[14] 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
[15] 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
[16] 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
[17] Konnov, I. V., A Class of Combined Iterative Methods for Solving Variational Inequalities, Vol. 94, pp. 677-693, 1997. · Zbl 0892.90172
[18] Xiu, N. H., Wang, C. Y., and Zhang, J. Z., Convergence Properties of Projection and Contraction Methods for Variational Inequalities Problems, Applied Mathematics and Optimization, Vol. 43, pp. 147-168, 2001. · Zbl 0980.90093 · doi:10.1007/s002450010023
[19] Wang, Y. J., Xiu, N. H., and Wang, C. Y., A New Version of Extragradient Method for Variational Inequality Problems, Computers and Mathematics with Applications, Vol. 42, pp. 969-979, 2001. · Zbl 0993.49005 · doi:10.1016/S0898-1221(01)00213-9
[20] Wang, Y. J., Xiu, N. H., and Wang, C. Y., Unified Framework of Extragradient-Type Methods for Pseudomonotone Variational Inequalities, Journal of Optimization Theory and Applications, Vol. 111, pp. 641-656, 2001. · Zbl 1039.49014 · doi:10.1023/A:1012606212823
[21] Xiu, N. H., and Zhang, J. Z., Some Recent Advances in Projection-Type Methods for Variational Inequalities, Journal of Computational and Applied Mathematics (to appear). · Zbl 1018.65083
[22] 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
[23] Solodov, M. V., and Svaiter, B. F., Forcing Strong Convergence of Proximal Point Iterations in Hilbert Space, Mathematical Programming, Vol. 87, pp. 189-202, 2000. · Zbl 0971.90062
[24] 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
[25] Mangasarian, O. L., and Solodov, M. V., Nonlinear Complementarity as Unconstrained and Constrained Minimization, Mathematical Programming, Vol. 62B, pp. 277-297, 1993. · Zbl 0813.90117 · doi:10.1007/BF01585171
[26] Kanzow, C., Some Equation-Based Methods for the Linear Complementarity Problem, Optimization Methods Software, Vol. 3, pp. 327-340, 1994. · doi:10.1080/10556789408805573
[27] Geiger, C., and Kanzow, C., On the Solution of Monotone Complementarity Problems, Computational Optimization and Applications, Vol. 5, pp. 155-172, 1996. · Zbl 0859.90113 · doi:10.1007/BF00249054
[28] Mathiesen, L., An Algorithm Based on a Sequence of Linear Complementarity Problems Applied to a Walrasian Equilibrium Model: An Example, Mathematical Programming, Vol. 37, pp. 1-18, 1987. · Zbl 0613.90098 · doi:10.1007/BF02591680
[29] Jiang, H. Y., and Qi, L. Q., A New Nonsmooth Equations Approach to Nonlinear Complementarity Problems, SIAM Journal on Control and Optimization, Vol. 35, pp. 178-193, 1997. · Zbl 0872.90097 · doi:10.1137/S0363012994276494
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.