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: [email protected]