{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T19:56:47Z","timestamp":1775591807751,"version":"3.50.1"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,7,1]],"date-time":"2019-07-01T00:00:00Z","timestamp":1561939200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,7,1]],"date-time":"2019-07-01T00:00:00Z","timestamp":1561939200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Prog. Comp."],"published-print":{"date-parts":[[2019,9]]},"DOI":"10.1007\/s12532-019-00164-4","type":"journal-article","created":{"date-parts":[[2019,7,1]],"date-time":"2019-07-01T12:02:50Z","timestamp":1561982570000},"page":"503-586","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs"],"prefix":"10.1007","volume":"11","author":[{"given":"Yuzixuan","family":"Zhu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G\u00e1bor","family":"Pataki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Quoc","family":"Tran-Dinh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,7,1]]},"reference":[{"key":"164_CR1","unstructured":"MOSEK ApS. Mosek optimization toolbox for MATLAB 8.0.0.94 (2017)"},{"issue":"3","key":"164_CR2","doi-asserted-by":"publisher","first-page":"319","DOI":"10.4064\/aa-15-3-319-327","volume":"15","author":"V Baston","year":"1969","unstructured":"Baston, V.: Extreme copositive quadratic forms. Acta Arith. 15(3), 319\u2013327 (1969)","journal-title":"Acta Arith."},{"key":"164_CR3","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1017\/S1446788700017250","volume":"30","author":"JM Borwein","year":"1981","unstructured":"Borwein, J.M., Wolkowicz, H.: Facial reduction for a cone\u2013convex programming problem. J. Aust. Math. Soc. 30, 369\u2013380 (1981)","journal-title":"J. Aust. Math. Soc."},{"key":"164_CR4","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1016\/0022-247X(81)90138-4","volume":"83","author":"JM Borwein","year":"1981","unstructured":"Borwein, J.M., Wolkowicz, H.: Regularizing the abstract convex program. J. Math. Anal. Appl. 83, 495\u2013530 (1981)","journal-title":"J. Math. Anal. Appl."},{"issue":"1","key":"164_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/2400000001","volume":"1","author":"S Boyd","year":"2014","unstructured":"Boyd, S., Mueller, M.T., O\u2019Donoghue, B., Wang, Y.: Performance bounds and suboptimal policies for multi-period investment. Found. Trends\u00ae Optim. 1(1), 1\u201372 (2014)","journal-title":"Found. Trends\u00ae Optim."},{"issue":"2","key":"164_CR6","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/s10107-002-0352-8","volume":"95","author":"S Burer","year":"2003","unstructured":"Burer, S., Monteiro, R.D.C.: A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program. 95(2), 329\u2013357 (2003)","journal-title":"Math. Program."},{"issue":"1","key":"164_CR7","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s101070100279","volume":"93","author":"S Burer","year":"2002","unstructured":"Burer, S., Monteiro, R.D.C., Zhang, Y.: Solving a class of semidefinite programs via nonlinear programming. Math. Program. 93(1), 97\u2013122 (2002)","journal-title":"Math. Program."},{"key":"164_CR8","unstructured":"Burton, S., Vinzant, C., Youm, Y.: A real stable extension of the Vamos matroid polynomial. arXiv preprint \n                    arXiv:1411.2038\n                    \n                   (2014)"},{"key":"164_CR9","volume-title":"Proceedings of Jonfest: A Conference in Honour of the 60th Birthday of J. Borwein","author":"V Cheung","year":"2013","unstructured":"Cheung, V., Wolkowicz, H., Schurr, S.: Preprocessing and regularization for degenerate semidefinite programs. In: Bailey, D., Bauschke, H.H., Garvan, F., Th\u00e9ra, M., Vanderwerff, J.D., Wolkowicz, H. (eds.) Proceedings of Jonfest: A Conference in Honour of the 60th Birthday of J. Borwein. Springer, Berlin (2013)"},{"key":"164_CR10","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1017\/S0305004100036185","volume":"58","author":"PH Diananda","year":"1962","unstructured":"Diananda, P.H.: On non-negative forms in real variables some or all of which are non-negative. Proc. Camb. Philos. Soc. 58, 17\u201325 (1962)","journal-title":"Proc. Camb. Philos. Soc."},{"key":"164_CR11","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/j.jsc.2018.06.018","volume":"91","author":"M Dressler","year":"2019","unstructured":"Dressler, M., Iliman, S., de Wolff, T.: An approach to constrained polynomial optimization via nonnegative circuit polynomials and geometric programming. J. Symb. Comput. 91, 149\u2013172 (2019)","journal-title":"J. Symb. Comput."},{"issue":"4","key":"164_CR12","doi-asserted-by":"publisher","first-page":"2301","DOI":"10.1137\/15M103710X","volume":"27","author":"D Drusviyatskiy","year":"2017","unstructured":"Drusviyatskiy, D., Krislock, N., Voronin, Y.L., Wolkowicz, H.: Noisy Euclidean distance realization: robust facial reduction and the Pareto frontier. SIAM J. Optim. 27(4), 2301\u20132331 (2017)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"164_CR13","doi-asserted-by":"publisher","first-page":"1160","DOI":"10.1137\/140968318","volume":"25","author":"D Drusviyatsky","year":"2015","unstructured":"Drusviyatsky, D., Pataki, G., Wolkowicz, H.: Coordinate shadows of semi-definite and Euclidean distance matrices. SIAM J. Optim. 25(2), 1160\u20131178 (2015)","journal-title":"SIAM J. Optim."},{"issue":"1\u20132","key":"164_CR14","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/s10107-015-0937-7","volume":"158","author":"H Fawzi","year":"2016","unstructured":"Fawzi, H., Parrilo, P.A.: Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and CP-rank. Math. Program. 158(1\u20132), 417\u2013465 (2016)","journal-title":"Math. Program."},{"key":"164_CR15","unstructured":"Friberg, H.: Facial reduction heuristics and the motivational example of mixed integer conic optimization. Technical report, Optimization Online (2016)"},{"key":"164_CR16","unstructured":"Fujisawa, K., Fukuda, M., Kobayashi, K., Kojima, M., Nakata, K., Nakata, M., Yamashita, M.: SDPA (semidefinite programming algorithm) and SDPA-GMP User\u2019s Manual\u2014Version 7.1.0. Department of Mathematical and Computing Sciences, Institute of Technology, Tokyo. Research Reports on Mathematical and Computing Sciences Series B-448 (2008)"},{"key":"164_CR17","unstructured":"Fujisawa, K., Kojima, M., Nakata, K., Yamashita, M.: SDPA (semidefinite programming algorithm) User\u2019s Manual Version 6.2. 0. Department of Mathematical and Computing Sciences, Institute of Technology, Tokyo. Research Reports on Mathematical and Computing Sciences Series B: Operations Research (2002)"},{"key":"164_CR18","doi-asserted-by":"crossref","unstructured":"Henrion, D., Lasserre, J.-B.: Detecting global optimality and extracting solutions in GloptiPoly. In: Positive Polynomials in Control, pp. 293\u2013310. Springer, Berlin (2005)","DOI":"10.1007\/10997703_15"},{"issue":"4\u20135","key":"164_CR19","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1080\/10556780802699201","volume":"24","author":"D Henrion","year":"2009","unstructured":"Henrion, D., Lasserre, J.-B., L\u00f6fberg, J.: GloptiPoly 3: moments, optimization and semidefinite programming. Optim. Methods Softw. 24(4\u20135), 761\u2013779 (2009)","journal-title":"Optim. Methods Softw."},{"issue":"4","key":"164_CR20","doi-asserted-by":"publisher","first-page":"2512","DOI":"10.1137\/15M1036543","volume":"26","author":"D Henrion","year":"2016","unstructured":"Henrion, D., Naldi, S., ed Din, M.S.: Exact algorithms for linear matrix inequalities. SIAM J. Optim. 26(4), 2512\u20132539 (2016)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"164_CR21","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1080\/1055678031000098773","volume":"18","author":"M Ko\u010dvara","year":"2003","unstructured":"Ko\u010dvara, M., Stingl, M.: Pennon: a code for convex nonlinear and semidefinite programming. Optim. Methods Softw. 18(3), 317\u2013333 (2003)","journal-title":"Optim. Methods Softw."},{"key":"164_CR22","doi-asserted-by":"publisher","first-page":"2679","DOI":"10.1137\/090759392","volume":"20","author":"N Krislock","year":"2010","unstructured":"Krislock, N., Wolkowicz, H.: Explicit sensor network localization using semidefinite representations and facial reductions. SIAM J. Optim. 20, 2679\u20132708 (2010)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"164_CR23","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1137\/S1052623400366802","volume":"11","author":"JB Lasserre","year":"2001","unstructured":"Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11(3), 796\u2013817 (2001)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"164_CR24","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/s10107-017-1136-5","volume":"167","author":"M Liu","year":"2018","unstructured":"Liu, M., Pataki, G.: Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming. Math. Program. 167(2), 435\u2013480 (2018)","journal-title":"Math. Program."},{"key":"164_CR25","doi-asserted-by":"crossref","unstructured":"Liu, Y., Ryu, E.K., Yin, W.: A new use of Douglas\u2013Rachford splitting for identifying infeasible, unbounded, and pathological conic programs. Math. Program. 1\u201329 (2018)","DOI":"10.1007\/s10107-018-1265-5"},{"key":"164_CR26","doi-asserted-by":"crossref","unstructured":"Lasserre, J.B., Magron, V.: In SDP relaxations, inaccurate solvers do robust optimization. arXiv preprint \n                    arXiv:1811.02879\n                    \n                   (2018)","DOI":"10.1137\/18M1225677"},{"issue":"2","key":"164_CR27","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/s10107-002-0355-5","volume":"95","author":"HD Mittelmann","year":"2003","unstructured":"Mittelmann, H.D.: An independent benchmarking of SDP and SOCP solvers. Math. Program. 95(2), 407\u2013430 (2003)","journal-title":"Math. Program."},{"issue":"2","key":"164_CR28","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s10107-003-0387-5","volume":"96","author":"P Parrilo","year":"2003","unstructured":"Parrilo, P.: Semidefinite programming relaxations for semialgebraic problems. Math. Program. 96(2), 293\u2013320 (2003)","journal-title":"Math. Program."},{"key":"164_CR29","volume-title":"Handbook of Semidefinite Programming","author":"G Pataki","year":"2000","unstructured":"Pataki, G.: The geometry of semidefinite programming. In: Saigal, R., Vandenberghe, L., Wolkowicz, H. (eds.) Handbook of Semidefinite Programming. Kluwer Academic Publishers, Canterbury (2000)"},{"key":"164_CR30","unstructured":"Pataki, G.: A simple derivation of a facial reduction algorithm and extended dual systems. Technical Report, Columbia University (2000)"},{"key":"164_CR31","volume-title":"Proceedings of Jonfest: A Conference in Honor of the 60th Birthday of Jon Borwein","author":"G Pataki","year":"2013","unstructured":"Pataki, G.: Strong duality in conic linear programming: facial reduction and extended duals. In: Bailey, D., Bauschke, H.H., Garvan, F., Th\u00e9ra, M., Vanderwerff, J.D., Wolkowicz, H. (eds.) Proceedings of Jonfest: A Conference in Honor of the 60th Birthday of Jon Borwein. Springer, Berlin (2013)"},{"issue":"1","key":"164_CR32","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/15M1041924","volume":"27","author":"G Pataki","year":"2017","unstructured":"Pataki, G.: Bad semidefinite programs: they all look the same. SIAM J. Optim. 27(1), 146\u2013172 (2017)","journal-title":"SIAM J. Optim."},{"key":"164_CR33","unstructured":"Pataki, G., Schmieta, S.: The DIMACS library of mixed semidefinite-quadratic-linear programs. \n                    http:\/\/dimacs.rutgers.edu\/Challenges\/Seventh\/Instances\/"},{"issue":"1\u20132","key":"164_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-017-1169-9","volume":"171","author":"F Permenter","year":"2018","unstructured":"Permenter, F., Parrilo, P.: Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone. Math. Program. 171(1\u20132), 1\u201354 (2018)","journal-title":"Math. Program."},{"issue":"3","key":"164_CR35","doi-asserted-by":"publisher","first-page":"1257","DOI":"10.1137\/15M1049415","volume":"27","author":"F Permenter","year":"2017","unstructured":"Permenter, F., Friberg, H.A., Andersen, E.D.: Solving conic optimization problems via self-dual embedding and facial reduction: a unified approach. SIAM J. Optim. 27(3), 1257\u20131282 (2017)","journal-title":"SIAM J. Optim."},{"key":"164_CR36","doi-asserted-by":"crossref","unstructured":"Posa, M., Tobenkin, M., Tedrake, R.: Lyapunov analysis of rigid body systems with impacts and friction via sums-of-squares. In: Proceedings of the 16th International Conference on Hybrid Systems: Computation and Control, pp. 63\u201372. ACM, New York (2013)","DOI":"10.1145\/2461328.2461340"},{"issue":"1\u20133","key":"164_CR37","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1080\/10556789808805692","volume":"9","author":"AJ Quist","year":"1998","unstructured":"Quist, A.J., de Klerk, E., Roos, C., Terlaky, T.: Copositive relaxation for general quadratic programming. Optim. Methods Softw. 9(1\u20133), 185\u2013208 (1998)","journal-title":"Optim. Methods Softw."},{"key":"164_CR38","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718812","volume-title":"A Mathematical View of Interior-Point Methods in Convex Optimization","author":"J Renegar","year":"2001","unstructured":"Renegar, J.: A Mathematical View of Interior-Point Methods in Convex Optimization, vol. 3. SIAM, Philadelphia (2001)"},{"issue":"1\u20134","key":"164_CR39","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1080\/10556789908805766","volume":"11","author":"J Sturm","year":"1999","unstructured":"Sturm, J.: Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones. Optim. Methods Softw. 11(1\u20134), 625\u2013653 (1999)","journal-title":"Optim. Methods Softw."},{"issue":"2","key":"164_CR40","doi-asserted-by":"publisher","first-page":"882","DOI":"10.1137\/140964357","volume":"25","author":"D Sun","year":"2015","unstructured":"Sun, D., Toh, K.-C., Yang, L.: A convergent 3-block semi-proximal alternating direction method of multipliers for conic programming with 4-type constraints. SIAM J. Optim. 25(2), 882\u2013915 (2015)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"164_CR41","doi-asserted-by":"publisher","first-page":"986","DOI":"10.1137\/16M1069262","volume":"27","author":"S Tanigawa","year":"2017","unstructured":"Tanigawa, S.: Singularity degree of the positive semidefinite matrix completion problem. SIAM J. Optim. 27(2), 986\u20131009 (2017)","journal-title":"SIAM J. Optim."},{"key":"164_CR42","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719574","volume-title":"Numerical Linear Algebra","author":"LN Trefethen","year":"1997","unstructured":"Trefethen, L.N., Bau III, D.: Numerical Linear Algebra, vol. 50. SIAM, Philadelphia (1997)"},{"key":"164_CR43","volume-title":"Polyhedral and Semidefinite Programming Methods in Combinatorial Optimization. Fields Institute Monographs","author":"L Tun\u00e7el","year":"2011","unstructured":"Tun\u00e7el, L.: Polyhedral and Semidefinite Programming Methods in Combinatorial Optimization. Fields Institute Monographs. American Mathematical Society, Providence (2011)"},{"key":"164_CR44","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s10107-002-0347-5","volume":"95","author":"RH Tutuncu","year":"2003","unstructured":"Tutuncu, R.H., Toh, K.-C., Todd, M.J.: Solving semidefinite-quadratic-linear programming using SDPT3. Math. Program. 95, 189\u2013217 (2003)","journal-title":"Math. Program."},{"issue":"6","key":"164_CR45","doi-asserted-by":"publisher","first-page":"1385","DOI":"10.1016\/j.disc.2008.02.005","volume":"309","author":"DG Wagner","year":"2009","unstructured":"Wagner, D.G., Wei, Y.: A criterion for the half-plane property. Discrete Math. 309(6), 1385\u20131390 (2009)","journal-title":"Discrete Math."},{"issue":"8","key":"164_CR46","doi-asserted-by":"publisher","first-page":"1883","DOI":"10.1007\/s11590-011-0384-1","volume":"6","author":"H Waki","year":"2012","unstructured":"Waki, H.: How to generate weakly infeasible semidefinite programs via Lasserre\u2019s relaxations for polynomial optimization. Optim. Lett. 6(8), 1883\u20131896 (2012)","journal-title":"Optim. Lett."},{"issue":"1","key":"164_CR47","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/s10957-012-0219-y","volume":"158","author":"H Waki","year":"2013","unstructured":"Waki, H., Muramatsu, M.: Facial reduction algorithms for conic optimization problems. J. Optim. Theory Appl. 158(1), 188\u2013215 (2013)","journal-title":"J. Optim. Theory Appl."},{"issue":"3","key":"164_CR48","doi-asserted-by":"publisher","first-page":"823","DOI":"10.1007\/s10589-011-9437-8","volume":"53","author":"H Waki","year":"2012","unstructured":"Waki, H., Nakata, M., Muramatsu, M.: Strange behaviors of interior-point methods for solving semidefinite programming problems in polynomial optimization. Comput. Optim. Appl. 53(3), 823\u2013844 (2012)","journal-title":"Comput. Optim. Appl."},{"issue":"3","key":"164_CR49","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/s12532-015-0082-6","volume":"7","author":"L Yang","year":"2015","unstructured":"Yang, L., Sun, D., Toh, K.-C.: SDPNAL$$+$$: a majorized semi-smooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints. Math. Program. Comput. 7(3), 331\u2013366 (2015)","journal-title":"Math. Program. Comput."},{"issue":"4","key":"164_CR50","doi-asserted-by":"publisher","first-page":"1737","DOI":"10.1137\/080718206","volume":"20","author":"XY Zhao","year":"2010","unstructured":"Zhao, X.Y., Sun, D., Toh, K.-C.: A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Optim. 20(4), 1737\u20131765 (2010)","journal-title":"SIAM J. Optim."}],"container-title":["Mathematical Programming Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-019-00164-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s12532-019-00164-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-019-00164-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,29]],"date-time":"2020-06-29T23:25:29Z","timestamp":1593473129000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s12532-019-00164-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,1]]},"references-count":50,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["164"],"URL":"https:\/\/doi.org\/10.1007\/s12532-019-00164-4","relation":{},"ISSN":["1867-2949","1867-2957"],"issn-type":[{"value":"1867-2949","type":"print"},{"value":"1867-2957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,1]]},"assertion":[{"value":"20 September 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 July 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}