{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,21]],"date-time":"2025-10-21T15:39:52Z","timestamp":1761061192089,"version":"build-2065373602"},"reference-count":42,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2021,5,1]],"date-time":"2021-05-01T00:00:00Z","timestamp":1619827200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2021,5,1]],"date-time":"2021-05-01T00:00:00Z","timestamp":1619827200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T00:00:00Z","timestamp":1746057600000},"content-version":"vor","delay-in-days":1461,"URL":"http:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"},{"start":{"date-parts":[[2021,5,1]],"date-time":"2021-05-01T00:00:00Z","timestamp":1619827200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2021,5,1]],"date-time":"2021-05-01T00:00:00Z","timestamp":1619827200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2021,5,1]],"date-time":"2021-05-01T00:00:00Z","timestamp":1619827200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2021,5,1]],"date-time":"2021-05-01T00:00:00Z","timestamp":1619827200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2021,5,1]],"date-time":"2021-05-01T00:00:00Z","timestamp":1619827200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/501100007493","name":"Fondation Math\u00e9matique Jacques Hadamard","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100007493","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Journal of Symbolic Computation"],"published-print":{"date-parts":[[2021,5]]},"DOI":"10.1016\/j.jsc.2020.11.001","type":"journal-article","created":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T21:35:02Z","timestamp":1605821702000},"page":"942-959","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":6,"special_numbering":"C","title":["Exact algorithms for semidefinite programs with degenerate feasible set"],"prefix":"10.1016","volume":"104","author":[{"given":"Didier","family":"Henrion","sequence":"first","affiliation":[]},{"given":"Simone","family":"Naldi","sequence":"additional","affiliation":[]},{"given":"Mohab","family":"Safey El Din","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"issue":"1","key":"10.1016\/j.jsc.2020.11.001_br0010","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1137\/17M1142132","article-title":"Log-barrier interior point methods are not strongly polynomial","volume":"2","author":"Allamigeon","year":"2018","journal-title":"SIAM J. Appl. Algebra Geom."},{"key":"10.1016\/j.jsc.2020.11.001_br0020","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.jsc.2017.07.002","article-title":"Solving generic nonarchimedean semidefinite programs using stochastic game algorithms","volume":"85","author":"Allamigeon","year":"2018","journal-title":"J. Symb. Comput."},{"key":"10.1016\/j.jsc.2020.11.001_br0030","series-title":"High Performance Optimization","first-page":"197","article-title":"The MOSEK interior point optimizer for linear programming: an implementation of the homogeneous algorithm","author":"Andersen","year":"2000"},{"key":"10.1016\/j.jsc.2020.11.001_br0040","series-title":"Handbook on Semidefinite, Conic and Polynomial Optimization","first-page":"1","article-title":"Introduction to semidefinite, conic and polynomial optimization","author":"Anjos","year":"2012"},{"issue":"4","key":"10.1016\/j.jsc.2020.11.001_br0050","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1016\/j.jco.2014.02.005","article-title":"Intrinsic complexity estimates in polynomial optimization","volume":"30","author":"Bank","year":"2014","journal-title":"J. Complex."},{"key":"10.1016\/j.jsc.2020.11.001_br0060","series-title":"Quantifier Elimination and Cylindrical Algebraic Decomposition","article-title":"A new algorithm to find a point in every cell defined by a family of polynomials","author":"Basu","year":"1998"},{"key":"10.1016\/j.jsc.2020.11.001_br0070","article-title":"Algorithms in Real Algebraic Geometry","volume":"vol. 10","author":"Basu","year":"2006"},{"year":"2012","series-title":"Semidefinite Optimization and Convex Algebraic Geometry","author":"Blekherman","key":"10.1016\/j.jsc.2020.11.001_br0080"},{"key":"10.1016\/j.jsc.2020.11.001_br0090","article-title":"Real Algebraic Geometry","volume":"vol. 36","author":"Bochnak","year":"1998"},{"issue":"2","key":"10.1016\/j.jsc.2020.11.001_br0100","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1016\/0022-247X(81)90138-4","article-title":"Regularizing the abstract convex program","volume":"83","author":"Borwein","year":"1981","journal-title":"J. Math. Anal. Appl."},{"year":"1994","series-title":"Linear Matrix Inequalities in System and Control Theory, vol. 15","author":"Boyd","key":"10.1016\/j.jsc.2020.11.001_br0110"},{"year":"2013","series-title":"Bifurcations and Catastrophes: Geometry of Solutions to Nonlinear Problems","author":"Demazure","key":"10.1016\/j.jsc.2020.11.001_br0120"},{"issue":"2","key":"10.1016\/j.jsc.2020.11.001_br0130","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1561\/2400000011","article-title":"The many faces of degeneracy in conic optimization","volume":"3","author":"Drusvyatskiy","year":"2017","journal-title":"Found. Trends Optim."},{"key":"10.1016\/j.jsc.2020.11.001_br0140","series-title":"Third International Congress on Mathematical Software, Proceedings","first-page":"84","article-title":"Mathematical software \u2013 ICMS 2010","author":"Faug\u00e8re","year":"2010"},{"issue":"1","key":"10.1016\/j.jsc.2020.11.001_br0150","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1006\/jcom.2000.0571","article-title":"A Gr\u00f6bner-free alternative for polynomial system solving","volume":"17","author":"Giusti","year":"2001","journal-title":"J. Complex."},{"key":"10.1016\/j.jsc.2020.11.001_br0160","series-title":"ISSAC'13","first-page":"197","article-title":"Computing rational solutions of linear matrix inequalities","author":"Guo","year":"2013"},{"key":"10.1016\/j.jsc.2020.11.001_br0170","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/j.jsc.2015.06.010","article-title":"Real root finding for determinants of linear matrices","volume":"74","author":"Henrion","year":"2015","journal-title":"J. Symb. Comput."},{"issue":"4","key":"10.1016\/j.jsc.2020.11.001_br0180","doi-asserted-by":"crossref","first-page":"2512","DOI":"10.1137\/15M1036543","article-title":"Exact algorithms for linear matrix inequalities","volume":"26","author":"Henrion","year":"2016","journal-title":"SIAM J. Optim."},{"key":"10.1016\/j.jsc.2020.11.001_br0200","series-title":"Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation (ISSAC'18)","first-page":"191","article-title":"Exact algorithms for semidefinite programs with degenerate feasible set","author":"Henrion","year":"2018"},{"issue":"1","key":"10.1016\/j.jsc.2020.11.001_br0190","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1080\/10556788.2017.1341505","article-title":"SPECTRA\u2013a Maple library for solving linear matrix inequalities in exact arithmetic","volume":"34","author":"Henrion","year":"2019","journal-title":"Optim. Methods Softw."},{"key":"10.1016\/j.jsc.2020.11.001_br0210","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.jsc.2017.03.001","article-title":"Improving root separation bounds","volume":"84","author":"Herman","year":"2018","journal-title":"J. Symb. Comput."},{"key":"10.1016\/j.jsc.2020.11.001_br0220","series-title":"ARITH 2017","article-title":"Implementation and performance evaluation of an extended precision floating-point arithmetic library for high-accuracy semidefinite programming","author":"Joldes","year":"2017"},{"issue":"4","key":"10.1016\/j.jsc.2020.11.001_br0230","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1023\/A:1008203903341","article-title":"On the complexity of semidefinite programs","volume":"10","author":"Khachiyan","year":"1997","journal-title":"J. Glob. Optim."},{"issue":"2","key":"10.1016\/j.jsc.2020.11.001_br0240","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/BF01581723","article-title":"Local convergence of predictor\u2014corrector infeasible-interior-point algorithms for SDPs and SDLCPs","volume":"80","author":"Kojima","year":"1998","journal-title":"Math. Program."},{"key":"10.1016\/j.jsc.2020.11.001_br0250","first-page":"1","article-title":"Grundz\u00fcge einer arithmetischen theorie der algebraischen Gr\u00f6ssen","volume":"92","author":"Kronecker","year":"1882","journal-title":"J. Reine Angew. Math."},{"volume":"vol. 1","year":"2010","series-title":"Moments, Positive Polynomials and Their Applications","key":"10.1016\/j.jsc.2020.11.001_br0260"},{"key":"10.1016\/j.jsc.2020.11.001_br0270","series-title":"Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation (ISSAC'16)","first-page":"357","article-title":"Solving rank-constrained semidefinite programs in exact arithmetic","author":"Naldi","year":"2016"},{"key":"10.1016\/j.jsc.2020.11.001_br0280","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1016\/j.jsc.2017.07.009","article-title":"Solving rank-constrained semidefinite programs in exact arithmetic","volume":"85","author":"Naldi","year":"2018","journal-title":"J. Symb. Comput."},{"key":"10.1016\/j.jsc.2020.11.001_br0290","article-title":"Interior-Point Polynomial Algorithms in Convex Programming","volume":"vol. 13","author":"Nesterov","year":"1994"},{"issue":"2","key":"10.1016\/j.jsc.2020.11.001_br0300","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/s10107-008-0253-6","article-title":"The algebraic degree of semidefinite programming","volume":"122","author":"Nie","year":"2010","journal-title":"Math. Program."},{"issue":"1","key":"10.1016\/j.jsc.2020.11.001_br0310","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/BF02614433","article-title":"An exact duality theory for semidefinite programming and its complexity implications","volume":"77","author":"Ramana","year":"1997","journal-title":"Math. Program."},{"issue":"4","key":"10.1016\/j.jsc.2020.11.001_br0320","doi-asserted-by":"crossref","first-page":"716","DOI":"10.1006\/jcom.2000.0563","article-title":"Finding at least one point in each connected component of a real algebraic set defined by a single equation","volume":"16","author":"Rouillier","year":"2000","journal-title":"J. Complex."},{"issue":"1","key":"10.1016\/j.jsc.2020.11.001_br0330","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/s11786-007-0003-9","article-title":"Testing sign conditions on a multivariate polynomial and applications","volume":"1","author":"Safey El Din","year":"2007","journal-title":"Math. Comput. Sci."},{"key":"10.1016\/j.jsc.2020.11.001_br0340","series-title":"ISSAC'03","first-page":"224","article-title":"Polar varieties and computation of one point in each connected component of a smooth real algebraic set","author":"Safey El Din","year":"2003"},{"issue":"6","key":"10.1016\/j.jsc.2020.11.001_br0350","article-title":"A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets","volume":"63","author":"Safey El Din","year":"2017","journal-title":"J. ACM"},{"key":"10.1016\/j.jsc.2020.11.001_br0360","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1016\/j.jsc.2017.08.001","article-title":"Bit complexity for multi-homogeneous polynomial system solving - application to polynomial minimization","volume":"87","author":"Safey El Din","year":"2018","journal-title":"J. Symb. Comput."},{"issue":"6","key":"10.1016\/j.jsc.2020.11.001_br0370","doi-asserted-by":"crossref","first-page":"2876","DOI":"10.1137\/090772459","article-title":"Computing rational points in convex semialgebraic sets and sum of squares decompositions","volume":"20","author":"Safey El Din","year":"2010","journal-title":"SIAM J. Optim."},{"issue":"7","key":"10.1016\/j.jsc.2020.11.001_br0380","doi-asserted-by":"crossref","first-page":"1495","DOI":"10.4171\/jems\/620","article-title":"Sums of squares of polynomials with rational coefficients","volume":"18","author":"Scheiderer","year":"2016","journal-title":"J. Eur. Math. Soc."},{"issue":"5","key":"10.1016\/j.jsc.2020.11.001_br0390","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/s00200-002-0109-x","article-title":"Computing parametric geometric resolutions","volume":"13","author":"Schost","year":"2003","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"issue":"1\u20134","key":"10.1016\/j.jsc.2020.11.001_br0400","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1080\/10556789908805766","article-title":"Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones","volume":"11\/12","author":"Sturm","year":"1999","journal-title":"Optim. Methods Softw."},{"issue":"1\u20134","key":"10.1016\/j.jsc.2020.11.001_br0410","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1080\/10556789908805762","article-title":"SDPT3 \u2013 a MATLAB software package for semidefinite programming, version 1.3","volume":"11","author":"Toh","year":"1999","journal-title":"Optim. Methods Softw."},{"year":"2016","series-title":"Polyhedral and Semidefinite Programming Methods in Combinatorial Optimization, vol. 27","author":"Tun\u00e7el","key":"10.1016\/j.jsc.2020.11.001_br0420"}],"container-title":["Journal of Symbolic Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0747717120301176?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0747717120301176?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:17:33Z","timestamp":1760059053000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0747717120301176"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5]]},"references-count":42,"alternative-id":["S0747717120301176"],"URL":"https:\/\/doi.org\/10.1016\/j.jsc.2020.11.001","relation":{},"ISSN":["0747-7171"],"issn-type":[{"type":"print","value":"0747-7171"}],"subject":[],"published":{"date-parts":[[2021,5]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Exact algorithms for semidefinite programs with degenerate feasible set","name":"articletitle","label":"Article Title"},{"value":"Journal of Symbolic Computation","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.jsc.2020.11.001","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2020 Elsevier Ltd.","name":"copyright","label":"Copyright"}]}}