An iterative two-step algorithm for linear complementarity problems (Q1338826)

For the symmetric linear complementarity problem: find \(x \in \mathbb{R}^ n\) such that \(Ax - b \geq 0\), \(x \geq c\), \((x - c)^ T(Ax - b) = 0\), where \(A\) is a given \(n \times n\) real symmetric positive definite matrix, and \(b,c\) are vectors in \(\mathbb{R}^ n\), many iterative methods are developed especially for cases, where the matrix \(A\) is large and sparse. Between them, three are widely used in practice: the successive overrelaxation method with projection, the preconditioned conjugate gradient method combined with an active set strategy and the multigrid methods. The last ones are the fastest but need additional data for the auxiliary problems. The authors copy the philosophy of the multigrid methods and present a method being a combination of the two first above mentioned. In each step of the authors' algorithm an application of the successive overrelaxation method with projection is used to determine an approximation of the optimal active set. Next, it uses the preconditioned conjugate gradient method to solve the reduced residual system of linear equations. The convergence of the new method is proved and numerically tested, also in comparison with several other methods, for the obstacle problem with different obstacles. For problems of dimension up to 24000 variables the solutions are found in less than 7 iterations, requiring about 10 matrix- vector calculations each. It is worth to mention that the above problem is equivalent to the convex programming problem: \(\min f(x) : = x^ TAx/2 - x^ Tb\), s.t. \(x \in S\), where \(S = \{y \in \mathbb{R}^ n \mid y_ i \geq c_ i\), \(i = 1,2, \dots, n\}\).