Polynomial convergence of primal-dual algorithms for the second-order coneprogram based on the MZ-family of directions

In this paper we study primal-dual path-following algorithms for the second -order cone programming (SOCP) based on a family of directions that is a na tural extension of the Monteiro-Zhang (MZ) family for semidefinite programm ing. We show that the polynomial iteration-complexity bounds of two well-kn own algorithms for linear programming, namely the short-step path-following algorithm of Kojima et al. and Monteiro and Adler, and the predictor-corre ctor algorithm of Mizuno et al., carry over to the context of SOCP, that is they have an O(root n log epsilon(-1)) iteration-complexity to reduce the duality gap by a factor of epsilon, where n is the number of second-order c ones. Since the MZ-type family studied in this paper includes an analogue o f the Alizadeh, Haeberly and Overton pure Newton direction, we establish fo r the first time the polynomial convergence of primal-dual algorithms for S OCP based on this search direction.