On the convergence of iterative methods for symmetric linear complementarity problems

We prove convergence of the whole sequence generated by any of a large class of iterative algorithms for the symmetric linear complementarity problem (LCP), under the only hypothesis that a quadratic form associated with the LCP is bounded below on the nonnegative orthant. This hypothesis holds when the matrix is strictly copositive, and also when the matrix is copositive plus and the LCP is feasible. The proof is based upon the linear convergence rate of the sequence of functional values of the quadratic form. As a by-product, we obtain a decomposition result for copositive plus matrices. Finally, we prove that the distance from the generated sequence to the solution set (and the sequence itself, if its limit is a locally unique solution) have a linear rate of R-convergence.Research for this work was partially supported by CNPq grant No. 301280/86.     

Solution of nonsymmetric linear complementarity problems by iterative methods

Convergence is established for iterative algorithms for the solution of the nonsymmetric linear complementarity problem of findingz such thatMz+q0,z0,z ^T(Mz+q)=0, whereM is a givenn×n real matrix, not necessarily symmeetric, andq is a givenn-vector. It is first shown that, if the spectral radius of a matrix related toM is less than one, then the iterates generated by the general algorithm converge to a solution of the linear complementarity problem. It turns out that convergence properties are quite similar to those of linear systems of equations. As specific cases, two important classes of matrices, Minkowski matrices and quasi-dominant diagonal matrices, are shown to satisfy this convergence condition.The author is grateful to Professor O. L. Mangasarian and the referees for their substantive suggestions and corrections.     

Solution of symmetric linear complementarity problems by iterative methods

A unified treatment is given for iterative algorithms for the solution of the symmetric linear complementarity problem: $$Mx + q \geqslant 0, x \geqslant 0, x^T (Mx + q) = 0$$ , whereM is a givenn×n symmetric real matrix andq is a givenn×1 vector. A general algorithm is proposed in which relaxation may be performed both before and after projection on the nonnegative orthant. The algorithm includes, as special cases, extensions of the Jacobi, Gauss-Seidel, and nonsymmetric and symmetric successive over-relaxation methods for solving the symmetric linear complementarity problem. It is shown first that any accumulation point of the iterates generated by the general algorithm solves the linear complementarity problem. It is then shown that a class of matrices, for which the existence of an accumulation point that solves the linear complementarity problem is guaranteed, includes symmetric copositive plus matrices which satisfy a qualification of the type: $$Mx + q > 0 for some x in R^n $$ . Also included are symmetric positive-semidefinite matrices satisfying this qualification, symmetric, strictly copositive matrices, and symmetric positive matrices. Furthermore, whenM is symmetric, copositive plus, and has nonzero principal subdeterminants, it is shown that the entire sequence of iterates converges to a solution of the linear complementarity problem.     

An iterative two-step algorithm for linear complementarity problems

Summary. We propose an algorithm for the numerical solution of large-scale symmetric positive-definite linear complementarity problems. Each step of the algorithm combines an application of the successive overrelaxation method with projection (to determine an approximation of the optimal active set) with the preconditioned conjugate gradient method (to solve the reduced residual systems of linear equations). Convergence of the iterates to the solution is proved. In the experimental part we compare the efficiency of the algorithm with several other methods. As test example we consider the obstacle problem with different obstacles. For problems of dimension up to 24\,000 variables, the algorithm finds the solution in less then 7 iterations, where each iteration requires about 10 matrix-vector multiplications. Received July 14, 1993 / Revised version received February 1994     

Two-stage parallel iterative methods for the symmetric linear complementarity problem

In this paper, we propose a two-stage parallel iterative method for solving the symmetric linear complementarity problem. When implemented in a parallel computing environment, the method decomposes the problem into subproblems which are solved by certain iterative procedures concurrently on separate processors. Convergence of the overall method is established under some mild assumptions on how the inner iterations are terminated. Applications of the proposed method to solve strictly convex quadratic programs are discused and numerical results on both a sequential computer (IBM 4381) and a super-computer (CRAYX-MP/24) are reported.This research was based on work supported by the National Science Foundation under grant ECS-8407240 and by a 1986 University Research and Development grant from Cray Research Inc.     

Corrector-predictor methods for sufficient linear complementarity problems

We present a new corrector-predictor method for solving sufficient linear complementarity problems for which a sufficiently centered feasible starting point is available. In contrast with its predictor-corrector counterpart proposed by Miao, the method does not depend on the handicap κ of the problem. The method has \(O((1+\kappa)\sqrt{n}L)\)-iteration complexity, the same as Miao’s method, but our error estimates are sightly better. The algorithm is quadratically convergent for problems having a strictly complementary solution. We also present a family of infeasible higher order corrector-predictor methods that are superlinearly convergent even in the absence of strict complementarity. The algorithms of this class are globally convergent for general positive starting points. They have \(O((1+\kappa)\sqrt{n}L)\)-iteration complexity for feasible, or “almost feasible”, starting points and O((1+κ)² nL)-iteration complexity for “sufficiently large” infeasible starting points.     

Interior point methods for linear complementarity problems

A short survey of interior point methods for linear complementarity problems with emphasis on algorithms that have both polynomial complexity and superlinear convergence is presented. Some recent results obtained by the author and his collaborators are briefly summarized and several directions of future research are proposed. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Inexact multisplitting methods for linear complementarity problems

We present an inexact multisplitting method for solving the linear complementarity problems, which is based on the inexact splitting method and the multisplitting method. This new method provides a specific realization for the multisplitting method and generalizes many existing matrix splitting methods for linear complementarity problems. Convergence for this new method is proved when the coefficient matrix is an _H+$H_{+}$-matrix. Then, two specific iteration forms for this inexact multisplitting method are presented, where the inner iterations are implemented either through a matrix splitting method or through a damped Newton method. Convergence properties for both these specific forms are analyzed, where the system matrix is either an _H+$H_{+}$-matrix or a symmetric matrix.     

Convergence of SSOR methods for linear complementarity problems

In this paper, by applying the SSOR splitting, we propose two new iterative methods for solving the linear complementarity problem LCP (M,q). Convergence results for these two methods are presented when M is an H-matrix (and also an M-matrix). Finally, two numerical examples are given to show the efficiency of the presented methods.     

On finite termination of an iterative method for linear complementarity problems

Based on a well-known reformulation of the linear complementarity problem (LCP) as a nondifferentiable system of nonlinear equations, a Newton-type method will be described for the solution of LCPs. Under certain assumptions, it will be shown that this method has a finite termination property, i.e., if an iterate is sufficiently close to a solution of LCP, the method finds this solution in one step. This result will be applied to a recently proposed algorithm by Harker and Pang in order to prove that their algorithm also has the finite termination property.     

Nonlinear relaxation methods for solving symmetric linear complementarity problems

A family of iterative algorithms is presented for the solution of the symmetric linear complementarity problem,

Shifted skew-symmetric iteration methods for nonsymmetric linear complementarity problems

We present a shifted skew-symmetric iteration method for solving the nonsymmetric positive definite or positive semidefinite linear complementarity problems. This method is based on the symmetric and skew-symmetric splitting of the system matrix, which has been adopted to establish efficient splitting iteration methods for solving the nonsymmetric systems of linear equations. Global convergence of the method is proved, and the corresponding inexact splitting iteration scheme is established and analyzed in detail. Numerical results show that the new methods are feasible and effective for solving large sparse and nonsymmetric linear complementarity problems.     

Modulus-based matrix splitting methods for horizontal linear complementarity problems

Numerical Algorithms - In this paper, we extend modulus-based matrix splitting iteration methods to horizontal linear complementarity problems. We consider both standard and accelerated methods and...     

Smoothing methods for convex inequalities and linear complementarity problems

A smooth approximationp (x, ) to the plus function max{x, 0} is obtained by integrating the sigmoid function 1/(1 + e^–x ), commonly used in neural networks. By means of this approximation, linear and convex inequalities are converted into smooth, convex unconstrained minimization problems, the solution of which approximates the solution of the original problem to a high degree of accuracy for sufficiently large. In the special case when a Slater constraint qualification is satisfied, an exact solution can be obtained for finite. Speedup over MINOS 5.4 was as high as 1142 times for linear inequalities of size 2000 × 1000, and 580 times for convex inequalities with 400 variables. Linear complementarity problems are converted into a system of smooth nonlinear equations and are solved by a quadratically convergent Newton method. For monotone LCPs with as many as 10 000 variables, the proposed approach was as much as 63 times faster than Lemke's method.This material is based on research supported by Air Force Office of Scientific Research Grant F49620-94-1-0036 and National Science Foundation Grants CCR-9101801 and CCR-9322479.     

IGAOR and multisplitting IGAOR methods for linear complementarity problems

In this paper, we propose an interval version of the generalized accelerated overrelaxation methods, which we refer to as IGAOR, for solving the linear complementarity problems, LCP (M, q), and develop a class of multisplitting IGAOR methods which can be easily implemented in parallel. In addition, in regards to the H-matrix with positive diagonal elements, we prove the convergence of these algorithms and illustrate their efficiency through our numerical results.     

A multilevel iterative method for symmetric,positive definite linear complementarity problems

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.The results presented here were announced at the XI. International Symposium on Mathematical Programming, Bonn, August 1982.     

Parallel successive overrelaxation methods for symmetric linear complementarity problems and linear programs

A parallel successive overrelaxation (SOR) method is proposed for the solution of the fundamental symmetric linear complementarity problem. Convergence is established under a relaxation factor which approaches the classical value of 2 for a loosely coupled problem. The parallel SOR approach is then applied to solve the symmetric linear complementarity problem associated with the least norm solution of a linear program.This work was sponsored by the United States Army under Contract No. DAAG29-80-C-0041. This material is based on research sponsored by National Science Foundation Grant DCR-84-20963 and Air Force Office of Scientific Research Grants AFOSR-ISSA-85-00080 and AFOSR-86-0172.on leave from CRAI, Rende, Cosenza, Italy.     

More results on the convergence of iterative methods for the symmetric linear complementarity problem

In an earlier paper, the author has given some necessary and sufficient conditions for the convergence of iterative methods for solving the linear complementarity problem. These conditions may be viewed as global in the sense that they apply to the methods regardless of the constant vector in the linear complementarity problem. More precisely, the conditions characterize a certain class of matrices for which the iterative methods will converge, in a certain sense, to a solution of the linear complementarity problem for all constant vectors. In this paper, we improve on our previous results and establish necessary and sufficient conditions for the convergence of iterative methods for solving each individual linear complementarity problem with a fixed constant vector. Unlike the earlier paper, our present analysis applies only to the symmetric linear complementarity problem. Various applications to a strictly convex quadratic program are also given.The author gratefully acknowledges several stimulating conversations with Professor O. Mangasarian on the subject of this paper. He is also grateful to a referee, who has suggested Lemma 2.2 and the present (stronger) version of Theorem 2.1 as well as several other constructive comments.This research was based on work supported by the National Science Foundation under Grant No. ECS-81-14571, sponsored by the United States Army under Contract No. DAAG29-80-C-0041, and was completed while the author was visiting the Mathematics Research Center at the University of Wisconsin, Madison, Wisconsin.     

On convergence of two-stage splitting methods for linear complementarity problems

In this paper, we study the splitting method and two-stage splitting method for the linear complementarity problems. Convergence results for these two methods are presented when the system matrix is an H-matrix and the splittings used are H-splitting. Numerical experiments show that the two-stage splitting method has the same or even better numerical performance than the splitting method in some aspects under certain conditions.     

Necessary and sufficient conditions for the convergence of iterative methods for the linear complementarity problem

Necessary and sufficient conditions are established for the convergence of various iterative methods for solving the linear complementarity problem. The fundamental tool used is the classical notion of matrix splitting in numerical analysis. The results derived are similar to some well-known theorems on the convergence of iterative methods for square systems of linear equations. An application of the results to a strictly convex quadratic program is also given.This research was based on work supported by the National Science Foundation under Grant No. ECS-81-14571.The author gratefully acknowledges several comments by K. Truemper on the topics of this paper.