A new Ai-Zhang type interior point algorithm for sufficient linear complementarity problems

In this paper, we propose a new long-step interior point method for solving sufficient linear complementarity problems. The new algorithm combines two important approaches from the literature: the main ideas of the long-step interior point algorithm introduced by Ai and Zhang, and the algebraic equivalent transformation technique proposed by Darvay. Similarly to the method of Ai and Zhang, our algorithm also works in a wide neighbourhood of the central path and has the best known iteration complexity of short-step variants. We implemented the new method in Matlab and tested its efficiency on both sufficient and non-sufficient problem instances. In addition to presenting our numerical results, we also make some interesting observations regarding the analysis of Ai-Zhang type methods.