Polynomial Convergence of Primal-Dual Algorithms for
Semidefinite Programming Based on Monteiro and Zhang
Family of Directions.
Renato D.C. Monteiro
This paper establishes the polynomial convergence of the
class of primal-dual feasible interior-point algorithms for
semidefinite programming (SDP) based on Monteiro and Zhang
family of search directions. In contrast to Monteiro and
Zhang's work, no condition is imposed on the scaling matrix
that determines the search direction. 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 te al., carry over to the context of SDP.
Since Monteiro and Zhang family of directions includes the
Alizadeh, Haeberly and Overton direction, we establish for the
first time the polynomial convergence of algorithms based on
this search direction.
School of ISyE, Georgia Tech, GA 30332 USA.