Polynomial complexity of an interior point algorithm with a second order corrector step for symmetric cone programming

In this paper, we propose a second order interior point algorithm for symmetric cone programming using a wide neighborhood of the central path. The convergence is shown for commutative class of search directions. The complexity bound is $${O(r^{3/2}\,\log\epsilon^{-1})}$$ for the NT methods, and $${O(r^{2}\,\log\epsilon^{-1})}$$ for the XS and SX methods, where r is the rank of the associated Euclidean Jordan algebra and $${\epsilon\,{ > }\,0}$$ is a given tolerance. If the staring point is strictly feasible, then the corresponding bounds can be reduced by a factor of r 3/4 . The theory of Euclidean Jordan algebras is a basic tool in our analysis. Copyright Springer-Verlag 2011