Predictor-corrector interior-point algorithm for sufficient linear complementarity problems based on a new type of algebraic equivalent transformation technique

Abstract

We propose a new predictor-corrector (PC) interior-point algorithm (IPA) for solving linear complementarity problem (LCP) with P_* (κ)-matrices. The introduced IPA uses a new type of algebraic equivalent transformation (AET) on the centering equations of the system defining the central path. The new technique was introduced by Darvay et al. [21] for linear optimization. The search direction discussed in this paper can be derived from positive-asymptotic kernel function using the function φ(t)=t^2 in the new type of AET. We prove that the IPA has O(1+4κ)√n log⁡〖(3nμ^0)/ε〗 iteration complexity, where κ is an upper bound of the handicap of the input matrix. To the best of our knowledge, this is the first PC IPA for P_* (κ)-LCPs which is based on this search direction.