Optimization Online


New variant on the Mizuno-Todd-Ye predictor-corrector algorithm

Tibor Illés (illes***at***math.elte.hu)
Marianna Nagy (nmariann***at***cs.elte.hu)

Abstract: We analyze a version of the Mizuno-Todd-Ye predictor-corrector interior point algorithm for the P_*(\kappa)-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_*(\kappa)-matrices. To derive a formulation of the complexity for this algorithm we are using a |1/v - 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+\kappa)^{3/2}\sqrt{n}L).

Keywords: linear complementarity problem, sufficient matrix, P_*(\kappa)-matrix, interior point method, Mizuno--Todd--Ye predictor-corrector algorithm

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Applications -- OR and Management Sciences

Citation: Operations Research Reports 04-01, Eötvös Loránd University, H-1117 Budapest, Pázmány Péter sétány 1/c


Entry Submitted: 11/29/2004
Entry Accepted: 11/29/2004
Entry Last Modified: 05/29/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society