A Mizuno-Todd-Ye type predictor-corrector algorithm for sufficient linear complimentarity problems

T. Illes, M. Nagy

Research output: Contribution to journalArticle

27 Citations (Scopus)

Abstract

We analyze a version of the Mizuno-Todd-Ye predictor-corrector interior point algorithm for the -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 [F.A. Potra, The Mizuno-Todd-Ye algorithm in a larger neighborhood of the central path, European Journal of Operational Research 143 (2002) 257-267] results on the LCP with -matrices. We are using a v−1 − v proximity measure like Potra to derive iteration complexity result for this algorithm . Our algorithm is different from Miao's method [J. Miao, A quadratically convergent -iteration algorithm for the P*(κ)-matrix linear complementarity problem, Mathematical Programming 69 (1995) 355-368] in both the proximity measure used and the way of updating the centrality parameter. Our analysis is easier than the previously stated results. We also show that the iteration complexity of our algorithm is .
Original languageEnglish
Pages (from-to)1097-1111
Number of pages14
JournalEuropean Journal of Operational Research
Volume181
Issue number3
DOIs
Publication statusPublished - 16 Sep 2007

Keywords

  • linear complementarity problem
  • sufficient matrix
  • interior point method
  • Mizuno–Todd–Ye predictor–corrector algorithm

Fingerprint Dive into the research topics of 'A Mizuno-Todd-Ye type predictor-corrector algorithm for sufficient linear complimentarity problems'. Together they form a unique fingerprint.

  • Cite this