A double step size method for linear complementarity problem

Solving a linear complementarity problem remains an NP-hard research topic. In this paper, we present a two-step size algorithm with an accelerated property for solving linear complementarity problems LCP(q,M) with M a positive matrix, in which we reformulate our problem as a system of nonlinear equations Fₚ(x)=0 where p is large. We use the inexact linear search technique, as well as the approximation of the Jacobian by the acceleration parameter, an efficient accelerated Newton and gradient descent method is developed. It is shown that the proposed method is convergent under some specific conditions. This method is derivative-free, which is advantageous for solving large-scale problems.