Complexity analysis of primal-dual algorithms for the semidefinite linear complementarity problem

Abstract

In this paper a primal-dual path-following interior-point algorithm for the monotone semidefinite linear complementarity problem is presented. The algorithm is based on Nesterov-Todd search directions and on a suitable proximity for tracing approximately the central-path. We provide an unified analysis for both long and small-update primal-dual algorithms. Finally, the iteration bounds for these algorithms are obtained.

Keywords

• semidefinite linear complementarity problems
• interior point methods
• long and small-update primal-dual algorithms
• polynomial complexity