Primal-dual path-following algorithms for semidefinite programming

This paper deals with a class of primal-dual interior-point algorithms for semidefinite programming (SDP) which was recently introduced by Kojima, Shindoh, and Kara [SIAM J. Optim., 7 (1997), pp. 86-125]. These authors proposed a family of primal-dual search directions that generalizes the one used in algorithms for linear programming based on the scaling matrix (XS-1/2)-S-1/2. They study three primal-dual algorithms based on this family of search directions: a short-step path-following method, a feasible potential-reduction method, and an infeasible potential-reduction method. However, they were not able to provide an algorithm which generalizes the long-step path-following algorithm introduced by Kojima, Mizuno, and Yoshise [Progress in Mathematical Programming: Interior Point and Related Methods, N. Megiddor, ed., Springer-Verlag, Berlin, New York, 1989, pp. 29-47]. In this paper, we characterize two search directions within their family as being (unique) solutions of systems of linear equations in symmetric variables. Based on this characterization, we present a simplified polynomial convergence proof for one of their short-step path-following algorithms and, for the first time, a polynomially convergent long-step path-following algorithm for SDP which requires an extra root n factor in its iteration-complexity order as compared to its linear programming counterpart, where n is the number of rows (or columns) of the matrices involved.