caa a22 4500 475769511 CHVBK 20180406123615.0 cr unu---uuuuu 170329e20000601xx s 000 0 eng 10.1007/PL00011378 doi (NATIONALLICENCE)springer-10.1007/PL00011378 Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions [Elektronische Daten] [Renato D.C. Monteiro, Takashi Tsuchiya] 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 natural extension of the Monteiro-Zhang (MZ) family for semidefinite programming. We show that the polynomial 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, and the predictor-corrector algorithm of Mizuno et al., carry over to the context of SOCP, that is they have an O(  logε-1) iteration-complexity to reduce the duality gap by a factor of ε, 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. Springer-Verlag Berlin Heidelberg, 2000 Key words: second-order cone programming - ice-cream cone - interior-point methods - polynomial complexity - path-following methods - primal-dual methods - Newton method nationallicence Monteiro Renato D.C. School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332, USA, e-mail: monteiro@isye.gatech.edu, US aut Tsuchiya Takashi The Institute of Statistical Mathematics, 4-6-7 Minami-Azabu, Minato-Ku, Tokyo, 106-8569, Japan, e-mail: tsuchiya@sun312.ism.ac.jp, JP aut https://doi.org/10.1007/PL00011378 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/PL00011378 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Monteiro Renato D.C. School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332, USA, e-mail: monteiro@isye.gatech.edu, US aut NATIONALLICENCE 700 1- Tsuchiya Takashi The Institute of Statistical Mathematics, 4-6-7 Minami-Azabu, Minato-Ku, Tokyo, 106-8569, Japan, e-mail: tsuchiya@sun312.ism.ac.jp, JP aut Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer