Predictor-corrector interior-point algorithm for P * ( κ ) -linear complementarity problems based on a new type of algebraic equivalent transformation technique

The article co-authored by Tibor Illés and Petra Renáta Rigó was published in the European Journal of Operational Research. 

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 and Takács (2018) for linear optimization. The search direction discussed in this paper can be derived from positive-asymptotic kernel function using the function φ(t)=t² in the new type of AET. We prove that the IPA has O((1+4κ) √n log3nμ⁰/4ϵ) 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. 

https://doi.org/10.1016/j.ejor.2021.08.039