{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,17]],"date-time":"2026-09-17T12:06:38Z","timestamp":1789646798658,"version":"4.0.0"},"reference-count":48,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1137\/16m1105888","type":"journal-article","created":{"date-parts":[[2018,3,13]],"date-time":"2018-03-13T10:45:50Z","timestamp":1520937950000},"page":"693-734","source":"Crossref","is-referenced-by-count":1,"title":["$LDL^T$ Direction Interior Point Method for Semidefinite Programming"],"prefix":"10.1137","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3173-3875","authenticated-orcid":true,"given":"Arvind U.","family":"Raghunathan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lorenz T.","family":"Biegler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,3,13]]},"reference":[{"key":"atypb1","unstructured":"F. Alizadeh,\n                      Combinatorial Optimization with Interior Point Methods and Semidefinite Matrices\n                      , Ph.D. thesis, University of Minnesota, Minneapolis, 1991."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623496304700"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614432"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"M. F. Anjos and J. B. Lasserre, eds.\n                      Handbook of Semidefinite, Conic and Polynomial Optimization: Theory, Algorithms, Software and Applications\n                      , Internat. Ser. Oper. Res. Management Sci. 166, Springer, New York, 2012.","DOI":"10.1007\/978-1-4614-0769-0_1"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1070\/RM1971v026n02ABEH003827"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0350-x"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"B. Borchers,\n                      SDPLIB1.2, a library of semidefinite programming test problems\n                      , Optim. Methods Softw., 11 (1999), pp. 683-690.","DOI":"10.1080\/10556789908805769"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/S105262340240851X"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1023\/A:1014834318702"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100279"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0555-2"},{"key":"atypb12","first-page":"23","author":"Dahl J.","year":"2008","journal-title":"Optim. Methods Softw."},{"key":"atypb13","first-page":"215","volume":"18","author":"de Klerk E.","year":"1998","journal-title":"Fields Inst. Commun."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100263"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/0323032"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614319"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366218"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/S105262349630009X"},{"key":"atypb19","unstructured":"G. Golub and C. Van Loan,\n                      Matrix Computations\n                      , Johns Hopkins Stud. Math. Sci., Johns Hopkins University Press, Baltimore, 1996."},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1145\/2950048"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(02)00276-X"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1080\/10556780410001727718"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/0806020"},{"key":"atypb24","unstructured":"N. J. Higham,\n                      Accuracy and Stability of Numerical Algorithms\n                      , SIAM, Philadelphia, 1996."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623494269035"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623403430828"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1080\/10556780701374633"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623496299187"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1145\/321386.321394"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623495293056"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0451-1"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623496312836"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1287\/moor.25.3.381.12216"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0351-9"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"Y. E. Nesterov and A. S. Nemirovskii,\n                      Interior Point Polynomial Methods in Convex Programming: Theory and Applications\n                      , Stud. Appl. Numer. Math., SIAM, Philadelphia, 1994.","DOI":"10.1137\/1.9781611970791"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1287\/moor.22.1.1"},{"key":"atypb37","doi-asserted-by":"crossref","unstructured":"J. Renegar,\n                      A Mathematical View of Interior-Point Methods in Convex Optimization\n                      , MPS-SIAM Ser. Optim., SIAM, philadelphia, 2001.","DOI":"10.1137\/1.9780898718812"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614439"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1137\/0805028"},{"key":"atypb40","unstructured":"G. Srijuntongsiri and S. A. Vavasis,\n                      A Fully Sparse Implementation of a Primal-Dual Interior-Point Potential Reduction Method for Semidefinite Programming\n                      ,arXiv:cs\/0412009v1, 2004."},{"key":"atypb41","doi-asserted-by":"crossref","unstructured":"J. F. Sturm,\n                      Using SeDuMi1.02, a MATLAB toolbox for optimization over symmetric cones\n                      , Optim. Methods Softw., 11 (1999), pp. 625-653.","DOI":"10.1080\/10556789908805766"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1080\/10556789908805745"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1137\/S105262349630060X"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623402419819"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0347-5"},{"key":"atypb46","doi-asserted-by":"crossref","unstructured":"H. Wolkowicz, R. Saigal, and L. Vandenberghe, eds.\n                      Handbook of Semidefinite Programming Theory, Algorithms, and Applications\n                      , Internat. Ser. Oper. Res. Management Sci. 27, Springer, New York, 2000.","DOI":"10.1007\/978-1-4615-4381-7"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2015.1014554"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623495296115"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1105888","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:15:47Z","timestamp":1787336147000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1105888"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":48,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M1105888"],"URL":"https:\/\/doi.org\/10.1137\/16m1105888","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}