Paper Info
Title
LDLT Direction Interior Point Method for Semidefinite Programming.
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))L-T. The approach was first proposed by Fletcher [SIAM J. Control Optim., 23 (1985), pp. 493-513], 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 [Math. Program. Ser. B, 95 (2003), pp. 279-302]. 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 (SDPs) 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.
Year
DOI
Venue
2018
10.1137/16M1105888
SIAM JOURNAL ON OPTIMIZATION
Keywords
DocType
Volume
semidefinite programming,LDLT factorization,interior point method,central path,conditioning of Schur complement
Journal
28
Issue
ISSN
Citations 
1
1052-6234
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Arvind U. Raghunathan116320.63
Lorenz T. Biegler22271185.43