Optimization Online


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

Chek Beng Chua (cbchua***at***math.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


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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society