A unified analysis for a class of long-step primal-dual path-following interior-point algorithms for semidefinite programming

摘要

We present a unified analysis for a class of long-step primal-dual path-following algorithms for semidefinite programming whose search directions are obtained through linearization of the symmetrized equation of the central path H-p(XS) = [PXTP-1 + (PXSP-1)(T)] /2 = mu I introduced by Zhang. At an iterate (X, S), we choose a scaling matrix P from the class of nonsingular matrices P such that PXSP-1 is symmetric. This class of matrices includes the three well-known choices, namely: P = S-1/2 and P = X-1/2 proposed by Monteiro, and the matrix P corresponding to the Nesterov-Todd direction. We show that within the class of algorithms studied in this paper, the one based on the Nesterov-Todd direction has the lowest possible iteration-complexity bound that can provably be derived from our analysis. More specifically, its iteration-complexity bound is of the same order as that of the corresponding long-step primal-dual path-following algorithm for linear programming introduced by Kojima, Mizuno and Yoshise. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V. [References: 27]