## Superlinear convergence of an algorithm for monotone linear complementarity problems,
when no strictly complementary solution exists

### Jos F. Sturm

A new predictor--corrector interior point algorithm for solving monotone linear
complementarity problems (LCP) is proposed, and it is shown to be superlinearly convergent
with at least order 1.5, even if the LCP has no strictly complementary solution. Unlike
Mizuno's recent algorithm (Mizuno, 1996), the fast local convergence is attained without
any need for estimating the optimal partition. In the special case that a strictly
complementary solution does exist, the order of convergence becomes quadratic. The proof
relies on an investigation of the asymptotic behavior of first and second order
derivatives that are associated with trajectories of weighted centers for LCP.

AMS 1991 subject classification: 90C33.

Key words: monotone linear complementarity problem, primal-dual interior point method,
superlinear convergence, central path.

Report 9656/A,
Econometric Institute, Erasmus University Rotterdam,
P.O. Box 1738, 3000 DR Rotterdam, The Netherlands,
September 30, 1996.
http://www.eur.nl/few/ei/

Contact: sturm@opres.few.eur.nl