Implementation Issues in CSDP

Brian Borchers (borchersnmt.edu)

Abstract: CSDP is a software package that implements the XZ primal--dual interior point method for semidefinite programming. In this method there are a number of computationally intensive steps including the construction of the Schur complement matrix $O$, the factorization of $O$, multiplications of matrices of size $n$ and Cholesky factorizations of matrices of size $n$. Profiling shows that for different problems, each of these types of operations can dominate the CPU time used by \mbox{CSDP}. We discuss ways in which the performance of these operations has been optimized in CSDP. We also discuss techniques for improving the accuracy of the solutions by scaling and ignoring small pivots in the factorization of the Schur complement matrix. As with linear programming, we have found that in practice this improves the accuracy of the solutions that are obtained.

Keywords: Semidefinite Programming, XZ Method

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: New Mexico Tech, February 28, 2001.

Download: [Postscript]

Entry Submitted: 03/30/2001
Entry Accepted: 03/30/2001
Entry Last Modified: 03/30/2001

Modify/Update this entry