Polynomiality of primal-dual algorithms for semidefinite linear complementarity problems based on the Kojima-Shindoh-Hara family of directions

Citation
Rdc. Monteiro et T. Tsuchiya, Polynomiality of primal-dual algorithms for semidefinite linear complementarity problems based on the Kojima-Shindoh-Hara family of directions, MATH PROGR, 84(1), 1999, pp. 39-53
Citations number
33
Categorie Soggetti
Mathematics
Journal title
MATHEMATICAL PROGRAMMING
ISSN journal
00255610 → ACNP
Volume
84
Issue
1
Year of publication
1999
Pages
39 - 53
Database
ISI
SICI code
0025-5610(199901)84:1<39:POPAFS>2.0.ZU;2-K
Abstract
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.