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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$${O(r^{3/2}\,\log\epsilon^{-1})}$$</EquationSource> </InlineEquation> for the NT methods, and <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$${O(r^{2}\,\log\epsilon^{-1})}$$</EquationSource> </InlineEquation> for the XS and SX methods, where r is the rank of the associated Euclidean Jordan algebra and <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$${\epsilon\,{ > }\,0}$$</EquationSource> </InlineEquation> is a given tolerance. If the staring point is strictly feasible, then the corresponding bounds can be reduced by a factor of r <Superscript>3/4</Superscript>. The theory of Euclidean Jordan algebras is a basic tool in our analysis. Copyright Springer-Verlag 2011