A full Nesterov-Todd step primal-dual path-following interior point algorithm for semidefinite linear complementarity problems

Abstract

In this paper, a feasible primal-dual path-following interior-point algorithm for monotone semidefinite
linear complementarity problems is proposed. At each iteration, the algorithm uses only full Nesterov-Todd feasible steps for tracing approximately the central-path and getting an approximated solution of this problem. Under a new appropriate choices of the threshold $\tau$ which defines the size of the neighborhood of the central-path and of the update barrier parameter $\theta$, we show that the algorithm is well-defined and enjoys the locally quadratically convergence. Moreover, we prove that the short-step algorithm deserves the best known iteration bound, namely, $O(\sqrt{n}\log\frac{n}{\epsilon})$. Finally, some numerical results are reported to show the practical performance of the algorithm.