zbMATH — the first resource for mathematics

Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions. (English) Zbl 0967.65077
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. R. D. C. Monteiro and 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 M. Kojima, S. Mizuno and A. Yoshise [Math. Program. Ser. A 44, No. 1, 1-26 (1989; Zbl 0676.90087)] and of R. D. C. Monteiro and 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 S. Mizuno, M. J. Todd and 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 F. Alizadeh, J.-P. Haeberly and M. L. Overton’s pure Newton search direction [SIAM J. Optim. 8, No. 3, 764-768 (1998; Zbl 0911.65047)].

65K05 Numerical mathematical programming methods
90C22 Semidefinite programming
90C25 Convex programming
90C51 Interior-point methods
90C30 Nonlinear programming
Full Text: DOI