Abstract
A fast iterative method for the solution of large, sparse, symmetric, positive definite linear complementarity problems is presented. The iterations reduce to linear iterations in a neighborhood of the solution if the problem is nondegenerate. The variational setting of the method guarantees global convergence.
As an application, we consider a discretization of a Dirichlet obstacle problem by triangular linear finite elements. In contrast to usual iterative methods, the observed rate of convergence does not deteriorate with step size.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Braess D (1981) The contraction number of a multigrid method for solving the Poisson equation. Numerische Mathematik 37:387–404
Brandt A (1977) multilevel adaptive solutions to boundary value problems. Math Computation 31:333–390
Brandt A, Cryer CW (1980) Multigrid algorithms for the solution of linear complementarity problems arising from free boundary problems. MRC Report No. 2131, Mathematics Research Center, University of Wisconsin, Madison, WI
Brezzi F, Hager WW, Raviart PA (1977) Error estimates for the finite element solution of variational inequalities, Part 1. Primal theory, Numerische Mathematik 28:431–443
Cottle RW, Golub GH, Sacher RS (1978) On the solution of large, structured linear complementarity problems: The block partitioned case. Appl Math Optim 4:347–363
Cottle RW, Sacher RS (1977) On the solution of large, structured linear complementarity problems: The tridiagonal case. Appl Math Optim 3:321–340
Glowinski R, Lions J-L, Trémolières R (1981) Numerical analysis of variational inequalities. North Holland, Amsterdam
Hackbusch W (1978) On the multigrid method applied to difference equations. Computing 20:291–306
Hackbusch W (1981) On the convergence of multigrid iterations. Beiträge zur Numerischen Mathematik 9:213–239
Hackbusch W, Trottenberg U (eds) (1982) Multigrid methods. Proceedings Köln 1981, Lecture Notes in Mathematics 960. Springer-Verlag, Berlin
Hackbusch W, Mittelmann HD (To appear) On multigrid methods for variational inequalities. Numerische Mathematik
Mangasarian OL (1977) Solution of symmetric complementarity problems by iterative methods. J Opt Theory Appl 22:465–485
Mosco U, Scarpini F (1975) Complementarity systems and approximation of variational inequalities. RAIRO R-1:83-104
Wesseling P (1980) The rate of convergence of a multiple grid method. In: Watson GA (ed) Proceedings Dundee 1979, Lecture Notes in Mathematics 733. Springer-Verlag, Berlin
Author information
Authors and Affiliations
Additional information
The results presented here were announced at the XI. International Symposium on Mathematical Programming, Bonn, August 1982.
Rights and permissions
About this article
Cite this article
Mandel, J. A multilevel iterative method for symmetric, positive definite linear complementarity problems. Appl Math Optim 11, 77–95 (1984). https://doi.org/10.1007/BF01442171
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01442171