An ℓ2inf>-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 $\mathit{ϵ}$ ‐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 $O\left(nlog{\mathit{ϵ}}^{‐1}\right)$ which coincides with the best known iteration bound for infeasible interior‐point methods.