Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions (Q1591356): Difference between revisions

The authors 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 [cf. \textit{R. D. C. Monteiro} and \textit{Y. Zhang}, Math. Program. 81A, No. 3, 281-299 (1998; Zbl 0919.90109)]. It is shown that the polynomial iteration-complexity bounds of two well-known algorithms for linear programming, namely, the short-step path-following algorithm of \textit{M. Kojima}, \textit{S. Mizuno} and \textit{A. Yoshise} [Math. Program. Ser. A 44, No. 1, 1-26 (1989; Zbl 0676.90087)] and of \textit{R. D. C. Monteiro} and \textit{I. Adler} [ibid. 44, No. 1, 27-41 and 43-66 (1989; Zbl 0676.90038 and Zbl 0676.90039)] and the predictor-corrector algorithm of \textit{S. Mizuno}, \textit{M. J. Todd} and \textit{Y. Ye} [Math. Oper. Res. 18, No. 4, 964-981 (1993; Zbl 0810.90091)], 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. For the first time the polynomial convergence of primal-dual algorithms for SOCP is based on \textit{F. Alizadeh}, \textit{J.-P. Haeberly} and \textit{M. L. Overton's} pure Newton search direction [SIAM J. Optim. 8, No. 3, 764-768 (1998; Zbl 0911.65047)].