首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Polynomial convergence of primal-dual algorithms for the second-order cone program based on the MZ-family of directions
Authors:Renato DC Monteiro  Takashi Tsuchiya
Institution:(1) School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332, USA, e-mail: monteiro@isye.gatech.edu, US;(2) The Institute of Statistical Mathematics, 4-6-7 Minami-Azabu, Minato-Ku, Tokyo, 106-8569, Japan, e-mail: tsuchiya@sun312.ism.ac.jp, JP
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. Received: June 5, 1998 / Accepted: September 8, 1999?Published online April 20, 2000
Keywords:: second-order cone programming –  ice-cream cone –  interior-point methods –  polynomial complexity –  path-following          methods –  primal-dual methods –  Newton method
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号