Abstract
In this paper, we study the relationship of some projection-type methods for monotone nonlinear variational inequalities and investigate some improvements. If we refer to the Goldstein–Levitin–Polyak projection method as the explicit method, then the proximal point method is the corresponding implicit method. Consequently, the Korpelevich extragradient method can be viewed as a prediction-correction method, which uses the explicit method in the prediction step and the implicit method in the correction step. Based on the analysis in this paper, we propose a modified prediction-correction method by using better prediction and correction stepsizes. Preliminary numerical experiments indicate that the improvements are significant.
Similar content being viewed by others
References
GLOWINSKI, R., Numerical Methods for Nonlinear Variational Problems, Springer Verlag, New York, NY, 1984.
HARKER, P. T., and PANG, J. S., Finite-Dimensional Variational Inequality and Nonlinear Complementarity Problems: A Survey of Theory, Algorithms, and Applications, Mathematical Programming, Vol. 48, pp. 161-220, 1990.
XIAO, B., and Harker, P. T., A Nonsmooth Newton Method for Variational Inequalities, I: Theory, Mathematical Programming, Vol. 65, pp. 151-194, 1994.
XIAO, B., and HARKER, P. T., A Nonsmooth Newton Method for Variational Inequalities, II: Numerical Results, Mathematical Programming, Vol. 65, pp. 195-216, 1994.
PANG, J. S., Inexact Newton Methods for the Nonlinear Complementarity Problem, Mathematical Programming, Vol. 36, pp. 54-71, 1986.
PANG, J. S., and QI, L., Nonsmooth Equations: Motiû ation and Algorithms, SIAM Journal on Optimization, Vol. 3, pp. 443-465, 1993.
MANGASARIAN, O. L., Solution of Symmetric Linear Complementarity Problems by Iterative Methods, Journal of Optimization Theory and Applications, Vol. 22, pp. 465-485, 1979.
HE, B. S., A Projection and Contraction Method for a Class of Linear Complementarity Problems and Its Application in Convex Quadratic Programming, Applied Mathematics and Optimization, Vol. 25, pp. 247-262, 1992.
HE, B. S., A New Method for a Class of Linear Variational Inequalities, Mathematical Programming, Vol. 66, pp. 137-144, 1994.
HE, B. S., Solving a Class of Linear Projection Equations, Numerische Mathematik, Vol. 68, pp. 71-80, 1994.
GOLDSTEIN, A. A., Convex Programming in Hilbert Space, Bulletin of the American Mathematical Society, Vol. 70, pp. 709-710, 1964.
LEVITIN, E. S., and POLYAK, B. T., Constrained Minimization Problems, USSR Computational Mathematics and Mathematical Physics, Vol. 6, pp. 1-50, 1966.
BERTSEKAS, D. P., and GAFNI, E. M., Projection Methods for Variational Inequalities with Application to the Traffic Assignment Problem, Mathematical Programming Study, Vol. 17, pp. 139-159, 1982.
KORPELEVICH, G. M., The Extragradient Method for Finding Saddle Points and Other Problems, Ekonomika i Matematicheskie Metody, Vol. 12, pp. 747-756, 1976.
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.
HE, B. S., A Class of Projection and Contraction Methods for Monotone Variational Inequalities, Applied Mathematics and Optimization, Vol. 35, pp. 69-76, 1997.
SUN, D. F., A Class of Iterative Methods for Solving Nonlinear Projection Equations, Journal of Optimization Theory and Applications, Vol. 91, pp. 123-140, 1996.
ROCKAFELLAR, R. T., Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming, Mathematics of Operations Research, Vol. 1, pp. 97-116, 1976.
BERTSEKAS, D. P., and TSITSIKLIS, J. N., Parallel and Distributed Computation: Numerical Methods, Prentice-Hall, Englewood Cliffs, New Jersey, 1989.
HARKER, P. T., and PANG, J. S., A Damped Newton Method for the Linear Complementarity Problem, Lectures in Applied Mathematics Vol. 26, pp. 265-284, 1990.
MARCOTEE, P., and DUSSAULT, J. P., A Note on a Globally Convergent Newton Method for Solving Variational Inequalities, Operation Research Letters, Vol. 6, pp. 35-42, 1987.
TAJI, K., FUKUSHIMA, M., and IBARAKI, T., A Globally Convergent Newton Method for Solving Strongly Monotone Variational Inequalities, Mathematical Programming, Vol. 58, pp. 369-383, 1993.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
He, B.S., Liao, L.Z. Improvements of Some Projection Methods for Monotone Nonlinear Variational Inequalities. Journal of Optimization Theory and Applications 112, 111–128 (2002). https://doi.org/10.1023/A:1013096613105
Issue Date:
DOI: https://doi.org/10.1023/A:1013096613105