Corrector-predictor methods for monotone linear complementarity problems in a wide neighborhood of the central path (Q2467158)

The author presents two versions of a corrector-predictor interior point method acting in a large neighborhood of the central path for monotone horizontal linear complementarity problems. The corrector step, based on a polynomial of order \(m_c\), increases both centrality and optimality. The linesearch procedure can be implemented in \(O(m_c n^{1+\alpha})\) arithmetic operations for some \(\alpha\in (0,1]\), or even in \(O(m_c n \log n)\) ones. In case of full matrices, the corrector step can be implemented in \(O(n^{3})\) arithmetic operations. The corrector step, based on a polynomial of order \(m_p\), increases optimality and ensures the superlinear convergence of the whole method even for degenerate problems. If \(m_p=O(n^{\omega})\) for some \(\omega \in (0,1)\), its implementation requires at most \(O(n^{3})\) arithmetic operations.