Abstract:

We present an interior point method for semidefinite programming where the semidefinite constraints on a matrix X are formulated as nonnegative constraints on d[1](X), . . . , d[n] (X) obtained from the LDLT factorization X = LDiag(d[1](X), . . . , d[n] (X))LT . The approach was first proposed by Fletcher who also provided analytic expressions for the derivatives of the factors in terms of X and the approach was subsequently utilized in an interior point algorithm by Benson and Vanderbei. However, the evaluation of first and second derivatives of d[i] (X) has been a bottleneck in such an algorithm. In this paper, we: (i) derive formulae for the first and second derivatives of d[i] (X) that are efficient and numerically stable to compute, (ii) show that the LDLT based search direction can be viewed in the standard framework of interior point methods for semidefinite programs with comparable computational cost per iteration, (iii) characterize the central path, and (iv) analyze the numerical conditioning of the linear system arising in the algorithm. We provide detailed numerical results on 79 SDP instances from the SDPLIB test set.