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