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