Abstract
In this paper, we study the relationship between the forward-backward splitting method and the extra-gradient method for monotone variational inequalities. Both of the methods can be viewed as prediction-correction methods. The only difference is that they use different search directions in the correction-step. Our analysis explains theoretically why the extra-gradient methods usually outperform the forward-backward splitting methods. We suggest some modifications for the two methods and numerical results are given to verify the superiority of the modified methods.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
D.P. Bertsekas and J.N. Tsitsiklis, Parallel and Distributed Computation, Numerical Methods, Prentice-Hall: Englewood Cliffs, NJ, 1989.
R.W. Cottle, J.S. Pang, and R.E. Stone, The Linear Complementarity Problem: Academic Press: New York, 1992.
J. Douglas and H.H. Rachford, “On the numerical solution of the heat conduction problem in 2 and 3 space variables,” Trans. Amer. Math. Soc., vol. 82, pp. 421–439, 1956.
B.C. Eaves, “On the basic theorem of complementarity,” Mathematical Programming, vol. 1, pp. 68–75, 1971.
R. Glowinski, Numerical Methods for Nonlinear Variational Problems. Springer-Verlag: New York, Berlin, Heidelberg, Tokyo, 1984.
A.A. Goldstein, “Convex programming in Hilbert space,” Bulletin of American Mathematical Society, vol. 70, pp. 709–710, 1964.
P.T. Harker and J.S. Pang, “Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory algorithms and applications,” Mathematical Programming, vol. 48, pp. 161–220, 1990.
P.T. Harker and J.S. Pang, “A Damped-Newton method for the linear complementarity problem,” Lectures in Applied Mathematics, vol. 26, pp. 265–284, 1990.
B.S. He, “Aprojection and contraction method for a class of linear complementarity problem and its application in convex quadratic programming,” Applied Mathematics and Optimization, vol. 25, pp. 247–262, 1992.
B.S. He, “A new method for a class of linear variational inequalities,” Mathematical Programming, vol. 66, pp. 137–144, 1994.
B.S. He, “Solving a class of linear projection equations,” Numerische Mathematik, vol. 68, pp. 71–80, 1994.
B.S. He, “A class of projection and contraction methods for monotone variational inequalities,” Applied Mathematics & Optimization, vol. 35, pp. 69–76, 1997.
B.S. He, “Inexact implicit methods for monotone general variational inequalities,” Mathematical Programming, vol. 86, pp. 199–216, 1999.
B.S. He and L.Z. Liao, “Improvements of some projection methods for monotone nonlinear variational inequalities,” J. of Optimization Theory and Applications, vol. 112, pp. 111–128, 2002.
E.N. Khobotov, “Modification of the extragradient method for solving variational inequalities and certain optimization problems,” U.S.S.R. Comput. Math. Phys., vol. 27, pp. 120–127, 1987.
G.M. Korpelevich, “The extragradient method for finding saddle points and other problems,” Ekonomika i Matematchskie Metody, vol. 12, pp. 747–756, 1976.
E.S. Levitin and B.T. Polyak, “Constrained minimization problems,” USSR Computational Mathematics and Mathematical Physics, vol. 6, pp. 1–50, 1966.
P.L. Lions and B. Mercier, “Splitting algorithms for the sum of two nonlinear operators,” SIAM J. Numerical Analysis, vol. 16, pp. 964–979, 1979.
P. Marcotte, “Application of Khobotov's algorithm to variational inequalities and network equilibrium problems,” Inf. Syst. Oper. Res., vol. 29, pp. 258–270, 1984.
P. Marcotee and J.P. Dussault, “A note on a globally convergent newton method for solving variational inequalities,” Operation Research Letters, vol. 6, pp. 35–42, 1987.
R.T. Rockafellar, “Augmented lagrangians and applications of the proximal point algorithm in convex programming,” Mathematics of Operations Research, vol. 1, pp. 97–116, 1976.
M.V. Solodov and P. Tseng, “Modified projection-type methods for monotone variational inequalities,” SIAM J. Control Optim, vol. 34, pp. 1814–1830, 1996.
D. Sun, “A projection and contraction method for the no-linear complementary problem and its extensions,” Mathematica Numerica Sinica, vol. 16, pp. 183–194, 1994.
D. Sun, “A new stepsize skill for solving a class of nonlinear projection equations,” Journal of Computational Mathematics, vol. 13, pp. 357–368, 1995.
D. Sun, “A class of iterative methods for solving nonlinear projection equations,” Journal of Optimization Theory and Application, vol. 91, pp. 123–140, 1996.
K. Taji, M. Fukushima, and T. Ibaraki, “A globally convergent newton method for solving strongly monotone variational inequalities,” Mathematical Programming, vol. 58, pp. 369–383, 1993.
P. Tseng, “A modified forward-backword splitting method for maximal monotone mappings,” SIAM. J. Control. Optim., vol. 38, pp. 431–446, 2000.
G.L. Xue and Y.Y. Ye, “An efficient algorithm for minimizing a sum of Euclidean norms with applications,” SIAM J. Optim., vol. 7, pp. 1017–1036, 1997.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
He, B., Yuan, X. & Zhang, J.J. Comparison of Two Kinds of Prediction-Correction Methods for Monotone Variational Inequalities. Computational Optimization and Applications 27, 247–267 (2004). https://doi.org/10.1023/B:COAP.0000013058.17185.90
Issue Date:
DOI: https://doi.org/10.1023/B:COAP.0000013058.17185.90