A polynomial primal-dual path-following algorithm for second-order cone programming

Takashi Tsuchiya

Second order code programming (SOCP) is the problem of minimizing linear objective function over cross-section of second-order cones and an affine space. Recently this problem gets more attention because of its various important applications including quadratically constrained convex quadratic programming. In this paper we deal with a primal-dual path-following algorithm for SOCP to show many of the ideas developed for primal-dual algorithms for LP and SDP carry over to this problem without sacrificing invariance under the automorphism group. We extend neighborhoods of the central trajectory and develop an analogue of HRVW/KSH/M direction, and establish $O(\sqrt{n}\log\varepsilon^{-1})$, $O(n\log\varepsilon^{-1})$ and $O(n^4\log\varepsilon^{-1})$ iteration-complexity bounds for short-step, semilong-step and long-step path following algorithm, respectively, to reduce the duality gap by a factor of $\varepsilon$.

Research Memorandum No. 649, The Institute of Statistical Mathematics, Tokyo 106 JAPAN, October, 1997

Contact: tsuchiya@sun312.ism.ac.jp