Polynomiality of Primal-Dual Algorithms for Semidefinite Linear Complementarity Problems Based on the Kojima-Shindoh-Hara Family of Directions

Kojima, Shindoh and Hara proposed a family of search directions for the semidefinite linear complementarity problem (SDLCP) and established polynomial convergence of a feasible shortstep path-following algorithm based on a particular direction of their family. The question of whether polynomiality could be established for any direction of their family thus remained an open problem. This paper answers this question in the affirmative by establishing the polynomiality of primal-dual interior-point algorithms for SDLCP based on any direction of the Kojima, Shindoh and Hara family of search directions. We show that the polynomial iterationcomplexity bounds of two well-known algorithms for linear programming, namely the short-step path-following algorithm of Kojima et al. and Monteiro and Adler, and the predictor-corrector algorithm of Mizuno et al., carry over to the context of SDLCP. Keywords: Semidefinite programming, interior-point methods, polynomial complexity, pathfollowing methods,..