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 sem idefinite linear complementarity problem (SDLCP) and established polynomial convergence of a feasible short-step path-following algorithm based on a p articular direction of their family. The question of whether polynomiality could be established for any direction of their family thus remained an ope n problem. This paper answers this question in the affirmative by establish ing the polynomiality of primal-dual interior-point algorithms for SDLCP ba sed on any direction of the Kojima, Shindoh and Hara family of search direc tions. We show that the polynomial iteration-complexity bounds of two well- known algorithms for linear programming,namely the short-step path-followin g algorithm of Kojima et al. and Monteiro and Adler, and the predictor-corr ector algorithm of Mizuno et al., carry over to the context of SDLCP.