Interior-Point Algorithms for Monotone Linear Complementarity Problem Based on Different Predictor Directions

In this paper, we introduce two parabolic target-space interior-point algorithms for solving monotone linear complementarity problems (LCPs). The first algorithm is based on a universal tangent direction, which has been recently proposed for linear optimization problems. We prove that this method has the best-known worst-case complexity bound. We extend onto this LCP its auto-correcting version proposed by Nesterov and prove its local quadratic convergence under the assumption of the existence of a unique and strictly complementarity solution. In our numerical experiments, we compare the new algorithms with a general method, recently developed for weighted monotone linear complementarity problems.

Funding: This research was supported by the National Research, Development and Innovation Office (NKFIH) [Grant 2024-1.2.3-HU-RIZONT-2024-00030]. The research of M. E.-Nagy and P. R. Rigó was individually supported by the János Bolyai Research Scholarship of the Hungarian Academy of Sciences (Magyar Tudományos Akadémia) [Grants 2024-2027 and 2025-2028, respectively].