On the local superlinear convergence of a Newton-type method for LCP under weak conditions

Abstract

The paper proposes a damped Newton-type algorithm for linear complementarity problems (LCP). The algorithm is based on a special transformation of the LCP into an equivalent nonlinear system of equations and modifies a method proposed in a preceding paper of the author

At first, results on global convergence are proved for LCP with Po-matrices. In particular, it is shown that all occuring subproblems are solvable and each accumulation point generated by the algorithm solves the LCP. Then, motivated by interior-point methods, the paper studies the local convergence to nondegenerated solutions of LCP with positive semi-definite matrices. To prove results, both on the local superlinear and the global convergence, suitably perturbed Newton subproblems will be introduced

In contrast with many interior-point methods the algorithm can also have a superlinear rate of convergence if the LCP is degenerate. In particular, it converges Q-superlinearly under some strong second order condition. Furthermore, the Newton-ty algorithm is not restricted to positive iterates. However, no polynomial complexity for solving positive semi-definite LCP by the proposed algorithm is known

Keywords:

• Linear Complementarity Problem
• Newton's Method
• Global and Superlinear Convergence
• Interior-Point Methods
• Noninterior-Point Methods