Using vector divisions in solving the linear complementarity problem

摘要

The linear complementarity problem LCP(M,q) is to find a vector z in IRn satisfying zT(Mz+q)=0, Mz+q⩾0,z⩾0, where M=(mij)∈IRn×n and q∈IRn are given. In this paper, we use the fact that solving LCP(M,q) is equivalent to solving the nonlinear equation F(x)=0 where F is a function from IRn into itself defined by F(x)=(M+I)x+(M−I)|x|+q. We build a sequence of smooth functions F̃(p,x) which is uniformly convergent to the function F(x). We show that, an approximation of the solution of the LCP(M,q) (when it exists) is obtained by solving F̃(p,x)=0 for a parameter p large enough. Then we give a globally convergent hybrid algorithm which is based on vector divisions and the secant method for solving LCP(M,q). We close our paper with some numerical simulations to illustrate our theoretical results, and to show that this method can solve efficiently large-scale linear complementarity problems.