Inexact Alternating Direction Method for Variational Inequality Problems with Linear Equality Constraints

Authors: Min Sun, Jing Liu

Abstract:

In this article, a new inexact alternating direction method(ADM) is proposed for solving a class of variational inequality problems. At each iteration, the new method firstly solves the resulting subproblems of ADM approximately to generate an temporal point ˜xk, and then the multiplier yk is updated to get the new iterate yk+1. In order to get xk+1, we adopt a new descent direction which is simple compared with the existing prediction-correction type ADMs. For the inexact ADM, the resulting proximal subproblem has closedform solution when the proximal parameter and inexact term are chosen appropriately. We show the efficiency of the inexact ADM numerically by some preliminary numerical experiments.

Keywords: variational inequality problems, alternating direction method, global convergence

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1088300

References:

[1] S.Dafernos, Traffic equilibrium and variational inequalities. Transportation Science, 1980, 14: 42-54.
[2] Larsson T., Patriksson M., Equilibrium characterizations of soltions to side constrained asymmetric traffic assignment models. Le Matematiche, 1994, 49: 249-280.
[3] Leblanc L., Chifflet J., Mahey P., Packet routing in telecommunication networks with path and flow restrictions. Networks, 1999, 11(2): 188- 197.
[4] Gabay D., Applications of the method of multipliers to variational inequalities. In Fortin M, Glowinski R. eds, Augmented Lagrangian Methods: Applications to the Solution of Boundary-Valued Problems. North-Holland, Amsterdam, 299-331, 1983.
[5] Gabay D., Mercier B., A dual algorithm for the solution of nonlinear variational problems via finite-element approximations, Computers and Mathematics with Applications, 1976, 2(1): 17-40.
[6] Eaves B.C., On the basic theorem of complementarity. Mathematical Programming, 1971, 1: 68-75.
[7] Tao M, Yuan X.M., An inexact parallel splitting augmented Lagrangian method for monotone variational inequalities with separable structures. Comput. Optim. Appl., 2012, 52(2): 439-461.
[8] Tao M., A modified proximal-based decomposition method for variational inequalities. Journal of Nanjing University Mathematical Biquarterly, 2009, 26(1): 14-26.
[9] Han, D.R., Hong, K.Lo: Solving variational inequality problems with linear constraints by a proximal decomposition algorithm. Journal of Global Optimization, 2004, 28: 97-113.
[10] Peng Z., Zhu W.X., A partial inexact alternating direction method for structured variational inequalities. Optimization, 2012, 1-13, iFirst.