Plynomial Convergence of Primal-Dual Algorithms for SDLCP Based on the Monteiro-Zhang Family of Directions

摘要

The paper establishes the polynomial converge-nce of a new class of path-following methods for semide- finite linear complementarity problems (SDLCP) whos-se search directions belong to the class of directions introduced by Monteiro [7]. Namely, we show that the polynomial iteration complexity bounds of the well known algori-thm for linear programming, namely the short-step path-following algorithm of Kojima et al. and Monteiro and Alder, carry over to the context of SDLCP