This paper presents the new concept of second-order cone approximations for convex conic programming. Given any open convex cone $K$, a logarithmically homogeneous self-concordant barrier for $K$ and any positive real number $r \le 1$, we associate, with each direction $x \in K$, a second-order cone $\hat K_r(x)$ containing $K$. We show that $K$ is the intersection of the second-order cones $\hat K_r(x)$, as $x$ ranges through all directions in $K$. Using these second-order cones as approximations to cones of symmetric positive definite matrices, we develop a new polynomial-time primal-dual interior-point algorithm for semi-definite programming. The algorithm is extended to symmetric cone programming via the relation between symmetric cones and Euclidean Jordan algebras.
Citation
Foundation of Computational Mathematics, 7 (2007), 271-302