A PROJECTION AND CONTRACTION METHOD FOR A CLASS OF LINEAR COMPLEMENTARITY-PROBLEMS AND ITS APPLICATION IN CONVEX QUADRATIC-PROGRAMMING

In this paper we propose a new iterative method for solving a class of linear complementarity problems: u greater-than-or-equal-to 0, Mu + q greater-than-or-equal-to 0, u(T)(Mu + q) = 0, where M is a given l x l positive semidefinite matrix (not necessarily symmetric) and q is a given l-vector. The method makes two matrix-vector multiplications and a trivial projection onto the nonnegative orthant at each iteration, and the Euclidean distance of the iterates to the solution set monotonously converges to zero. The main advantages of the method presented are its simplicity, robustness, and ability to handle large problems with any start point. It is pointed out that the method may be used to solve general convex quadratic programming problems. Preliminary numerical experiments indicate that this method may be very efficient for large sparse problems.