An $$ell _{2}$$-neighborhood infeasible interior-point algorithm for linear complementarity problems

In this paper, we propose an infeasible interior-point algorithm for linear complementarity problems. In every iteration, the algorithm constructs an ellipse and searches an (varepsilon )-approximate solution of the problem along the ellipsoidal approximation of the central path. The theoretical iteration-complexity of the algorithm is derived and the algorithm is proved to be polynomial with the complexity bound (Oleft(nlog varepsilon ^{-1}right)) which coincides with the best known iteration bound for infeasible interior-point methods.