Self-adaptive projection-based prediction-correction method for constrained variational inequalities

Abstract

The problems studied in this paper are a class of monotone constrained variational inequalities VI (S, f) in which S is a convex set with some linear constraints. By introducing Lagrangian multipliers to the linear constraints, such problems can be solved by some projection type prediction-correction methods. We focus on the mapping f that does not have an explicit form. Therefore, only its function values can be employed in the numerical methods. The number of iterations is significantly dependent on a parameter that balances the primal and dual variables. To overcome potential difficulties, we present a self-adaptive prediction-correction method that adjusts the scalar parameter automatically. Convergence of the proposed method is proved under mild conditions. Preliminary numerical experiments including some traffic equilibrium problems indicate the effectiveness of the proposed methods.

Keywords

Proximal point algorithm / variational inequality / prediction-correction

References

[1] Auslender A., Haddou M. An interior proximal point method for convex linearly constrained problems and its extension to variational inequalities. Mathematical Programming, 1995, 71: 77-100.

[2] Auslender A., Teboulle M. Lagrangian duality and related multiplier methods for variational inequality problems. SIAM Journal on Optimization, 2000, 10(4): 1097-1115.

[3] Bertsekas D. P., Tsitsiklis J. N. Parallel and Distributed Computation, Numerical Methods, 1989, Englewood Cliffs: Prentice-Hall.

[4] Golub G. H., von Matt U. Quadratically constrained least squares and quadratic problems. Numerische Mathmatik, 1990, 59: 561-580.

[5] He B. S. Inexact implicit methods for monotone general variational inequalities. Mathematical Programming, 1999, 86: 199-217.

[6] He B. S., Liao L. -Z. Improvements of some projection methods for monotone nonlinear variational inequalities. Journal of Optimization Theory and Applications, 2002, 112: 111-128.

[7] He B. S., Liao L. -Z., Yuan X. M. A LQP based interior prediction-correction method for nonlinear complementarity problems. Journal of Computational Mathematics, 2006, 24(1): 33-44.

[8] He B. S., Yuan X. M., Zhang J. J. Z. Comparison of two kinds of prediction-correction methods for monotone variational inequalities. Computational Optimization and Applications, 2004, 27: 247-267.

[9] Korpelevich G. M. The Extragradient method for finding saddle points and other problems. Ekonomika i Matematicheskie Metody, 1976, 12: 747-756.

[10] Nagurney A., Zhang D. Projected Dynamical Systems and Variational Inequalities with Applications, 1996, Boston, Dordrecht, London: Kluwer Academic Publishers.

[11] Rockafellar R. T. Monotone operators and the proximal point algorithm. SIAM Journal of Control and Optimization, 1976, 14(5): 877-898.

[12] Teboulle M. Convergence of proximal-like algorithms. SIAM Journal on Optimization, 1997, 7: 1069-1083.