##
Polynomial Convergence of Primal-Dual Algorithms for
the Second-Order Cone Program Based on the MZ-Family
of Directions

### Renato D.C. Monteiro and Takashi Tsuchiya

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 natural extension of the Monteiro-Zhang (MZ) family for
semidefinite programming. We show that the 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, carry over to the context of SOCP, that is they have an
$O(\sqrt{n} \log \varepsilon^{-1})$ iteration-complexity to reduce the
duality gap by a factor of $\varepsilon$, where $n$ is the number of
second-order cones. Since the MZ-type family studied in this paper
includes an analogue of the Alizadeh, Haeberly and Overton pure Newton
direction, we establish for the first time the polynomial convergence
of primal-dual algorithms for SOCP based on this search direction.
manuscript, May 1998, School of ISyE, Georgia Tech, Atlanta, GA,
30338

Contact: monteiro@isye.gatech.edu