A multilevel iterative method for symmetric, positive definite linear complementarity problems. (English) Zbl 0539.65046

This paper presents a method for solving the constrained optimization problem \(\min f(x)=1/2x^ TAx-x^ Tb,\) \(x\geq c\) where A is a symmetric positive definite matrix. The method of solution consists of constructing a finite sequence of auxiliary problems \[ P_ k:\min f_ k(x^ k)=1/2(x^ k)^ TA_ kx^ k-(x^ k)^ Tb^ k,\quad x^ k\geq c^ k \] where \(x^ k\in V_ k=R^{V_ k}\) and \(\dim V_{k-1}<\dim V_ k.\)
The sequence is for \(k=1...m\) and \(k=m\) corresponds to the original problem. The algorithm starts with a feasible solution for \(P_ m\) and with various iterations, constructs approximate solutions to the problems \(P_ k\), \(k<m\) and from these a corrected value of \(x^ m\). Since the process is a variational one the procedure will always converge and there is numerical evidence that this convergence is rapid.
In the example given the method compares favourably with relaxation methods. The problem \(P_ m\) is said to be nondegenerate if \((x-c)+(Ax- b)>0\) where x is the solution. In such cases it is proved that this algorithm reduces to a linear iterative method and that the rate of convergence consequently depends on the spectral radius of a linear operator.
Reviewer: B.Burrows


65K05 Numerical mathematical programming methods
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
65F10 Iterative numerical methods for linear systems
Full Text: DOI


[1] Braess D (1981) The contraction number of a multigrid method for solving the Poisson equation. Numerische Mathematik 37:387-404 · Zbl 0461.65078 · doi:10.1007/BF01400317
[2] Brandt A (1977) multilevel adaptive solutions to boundary value problems. Math Computation 31:333-390 · Zbl 0373.65054 · doi:10.1090/S0025-5718-1977-0431719-X
[3] 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
[4] 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 · Zbl 0369.65030 · doi:10.1007/BF01404345
[5] 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 · Zbl 0391.90087 · doi:10.1007/BF01442149
[6] Cottle RW, Sacher RS (1977) On the solution of large, structured linear complementarity problems: The tridiagonal case. Appl Math Optim 3:321-340 · Zbl 0375.90048 · doi:10.1007/BF01448184
[7] Glowinski R, Lions J-L, Tr?moli?res R (1981) Numerical analysis of variational inequalities. North Holland, Amsterdam
[8] Hackbusch W (1978) On the multigrid method applied to difference equations. Computing 20:291-306 · Zbl 0391.65045 · doi:10.1007/BF02252378
[9] Hackbusch W (1981) On the convergence of multigrid iterations. Beitr?ge zur Numerischen Mathematik 9:213-239 · Zbl 0465.65054
[10] Hackbusch W, Trottenberg U (eds) (1982) Multigrid methods. Proceedings K?ln 1981, Lecture Notes in Mathematics 960. Springer-Verlag, Berlin
[11] Hackbusch W, Mittelmann HD (To appear) On multigrid methods for variational inequalities. Numerische Mathematik
[12] Mangasarian OL (1977) Solution of symmetric complementarity problems by iterative methods. J Opt Theory Appl 22:465-485 · Zbl 0341.65049 · doi:10.1007/BF01268170
[13] Mosco U, Scarpini F (1975) Complementarity systems and approximation of variational inequalities. RAIRO R-1:83-104 · Zbl 0338.49016
[14] 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 · Zbl 0437.65072
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.