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

Citation
Rdc. Monteiro et T. Tsuchiya, Polynomial convergence of primal-dual algorithms for the second-order coneprogram based on the MZ-family of directions, MATH PROGR, 88(1), 2000, pp. 61-83
Citations number
28
Categorie Soggetti
Mathematics
Journal title
MATHEMATICAL PROGRAMMING
ISSN journal
00255610 → ACNP
Volume
88
Issue
1
Year of publication
2000
Pages
61 - 83
Database
ISI
SICI code
0025-5610(200006)88:1<61:PCOPAF>2.0.ZU;2-6
Abstract
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.