$LDL^T$ Direction Interior Point Method for Semidefinite Programming
提出一种半定规划的内点法，利用LDL^T分解将半定约束转化为非负约束，并推导了高效稳定的导数公式，在79个测试实例上验证了性能。
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),\ldots,d_{[n]}(X)$ obtained from the $LDL^T$ factorization $X = L{\rm Diag}(d_{[1]}(X),\ldots,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 $LDL^T$ 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.