New multiplier method for solving linear complementarity problems

Abstract

A new multiplier method for solving the linear complementarity problem LCP(q,M) is proposed. By introducing a Lagrangian of LCP(q,M), a new smooth merit function θ(χ, λ) for LCP(q,M) is constructed. Based on it, a simple damped Newton-type algorithm with multiplier self-adjusting step is presented. When M is a P-matrix, the sequence {θ(χ^k, λ^k)} (where {(χ^k, λ^k)} is generated by the algorithm) is globally linearly convergent to zero and convergent in a finite number of iterations if the solution is degenerate. Numerical results suggest that the method is highly effcient and promising.