A primal-dual second order cone approximations algorithm for symmetric cone programming

Chek Beng Chua (cbchuamath.uwaterloo.ca)

Abstract: 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.

Keywords: semi-definite programming, symmetric cone, interior-point methods, second-order cones

Category 1: Linear, Cone and Semidefinite Programming (Other )

Citation: Foundation of Computational Mathematics, 7 (2007), 271-302

Download:

Entry Submitted: 03/03/2003
Entry Accepted: 03/03/2003
Entry Last Modified: 09/10/2008

Modify/Update this entry