Large-step predictor-corrector interior point method for sufficient linear complementarity problems based on the algebraic equivalent transformation

Abstract

We introduce a new predictor-corrector interior-point algorithm for solving P⁎(κ)-linear complementarity problems which works in a wide neighbourhood of the central path. We use the technique of algebraic equivalent transformation of the centering equations of the central path system. In this technique, we apply the function φ(t)=t in order to obtain the new search directions. We define the new wide neighbourhood Dφ. In this way, we obtain the first interior-point method, where not only the central path system is transformed, but the definition of the neighbourhood is also modified taking into consideration the algebraic equivalent transformation technique. This gives a new direction in the research of interior-point algorithms. We prove that the interior-point method has O((1+κ)nlog⁡((x0)Ts0ϵ)) iteration complexity. Furthermore, we show the efficiency of the proposed predictor-corrector algorithm by providing numerical results. To our best knowledge, this is the first predictor-corrector interior-point algorithm which works in the Dφ neighbourhood using φ(t)=t.

Keywords

• Predictor-corrector interior-point algorithm
• P⁎(κ)-linear complementarity problems
• Wide neighbourhood
• Algebraic equivalent transformation technique