New Variant on the Mizuno–Todd–Ye Predictor–corrector Algorithm for the Sufficient Matrix Linear Complementarity Problem

Tibor Illés, Marianna Nagy

Research output: Book/ReportScholarly edition


We analyze a version of the Mizuno-Todd-Ye predictor-corrector interior point algorithm for the P*(k)-matrix linear complementarity problem (LCP). We assume the existence of a strictly positive feasible solution. Our version of the Mizuno-Todd-Ye predictor-corrector algorithm is a generalization of Potra's (2002) conclusions on the LCP with P*(k)-matrices. To derive a formulation of the complexity for this algorithm we are using a ||{v}^{-1}-{v}|| proximity measure like Potra. Our algorithm is different from Miao's method (1995) in both the proximity measure used and the way of updating the centrality parameter. Our analysis is easier than the previosly stated results. We also show that the complexity of our algorithm is O((1+k))3/2nL.
Original languageEnglish
Place of PublicationBudapest
Number of pages25
Publication statusPublished - Oct 2004

Publication series

NameOperations Research Report
PublisherEötvös Loránd University
ISSN (Print)1215-5918


  • linear complementarity problem
  • interior point method
  • Mizuno–Todd–Ye predictor-corrector algorithm.

Cite this