##
A convergence analysis of the scaling-invariant primal-dual
path-following algorithms for second-order cone programming

###
Takashi Tsuchiya

This paper is a continuation of our previous paper in which we studied
a polynomial primal-dual path-following algorithm for SOCP using an
analogue of the HRVW/KSH/M direction for SDP. We develop an improved
and simplified complexity analysis which can be also applied to the
algorithm using the NT direction. Specifically, we show that the
long-step algorithm using the NT direction has
$O(n\log\varepsilon^{-1})$ iteration-complexity to reduce the duality
gap by a factor of $\varepsilon$, where $n$ is the number of the
second-order cones. The complexity for the same algorithm using the
HRVW/KSH/M direction is improved to $O(n^{1.5}\log\varepsilon^{-1})$
from $O(n^3\log\varepsilon^{-1})$ of the previous analysis. We also
show that the short and semilong-step algorithms using the NT
direction (and the HRVW/KSH/M direction) have
$O(\sqrt{n}\log\varepsilon^{-1})$ and $O(n\log\varepsilon^{-1})$
iteration-complexities, respectively.
Research Memorandum No. 664, The Institute of Statistical Mathematics,
Tokyo, Japan

Contact: tsuchiya@sun312.ism.ac.jp