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

###
Renato D.C. Monteiro and Takashi Tsuchiya

Kojima, Shindoh and Hara proposed a family of search directions
for the semidefinite linear complementarity problem (SDLCP) and
established polynomial convergence of a feasible short-step
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 on 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
iteration-complexity 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.
Report Memorandum No 617 , The Institute of Statistical Mathematics,
4-6-7 Minami-Azabu, Minato-ku, Tokyo 106, JAPAN

Contact: monteiro@isye.gatech.edu