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: [email protected]

[PS] [IP PAGE] [SEARCH AGAIN]