{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T12:03:43Z","timestamp":1773144223432,"version":"3.50.1"},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2017,6,28]],"date-time":"2017-06-28T00:00:00Z","timestamp":1498608000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2018,9]]},"DOI":"10.1007\/s10107-017-1169-9","type":"journal-article","created":{"date-parts":[[2017,6,28]],"date-time":"2017-06-28T08:44:08Z","timestamp":1498639448000},"page":"1-54","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":32,"title":["Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone"],"prefix":"10.1007","volume":"171","author":[{"given":"Frank","family":"Permenter","sequence":"first","affiliation":[]},{"given":"Pablo","family":"Parrilo","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,6,28]]},"reference":[{"key":"1169_CR1","doi-asserted-by":"crossref","unstructured":"Ahmadi, A.A., Majumdar, A.: $$DSOS$$ D S O S and $$SDSOS$$ S D S O S optimization: LP and SOCP-based alternatives to sum of squares optimization. In: Proceedings of the 48th Annual Conference on Information Sciences and Systems, pp. 1\u20135 (2014)","DOI":"10.1109\/CISS.2014.6814141"},{"key":"1169_CR2","doi-asserted-by":"crossref","unstructured":"Alipanahi, B., Krislock, N., Ghodsi, A., Wolkowicz, H., Donaldson, L., Li, M.: Protein structure by semidefinite facial reduction. In: Research in Computational Molecular Biology, pp. 1\u201311. Springer (2012)","DOI":"10.1007\/978-3-642-29627-7_1"},{"issue":"2","key":"1169_CR3","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/BF01586000","volume":"71","author":"ED Andersen","year":"1995","unstructured":"Andersen, E.D., Andersen, K.D.: Presolving in linear programming. Math. Program. 71(2), 221\u2013245 (1995)","journal-title":"Math. Program."},{"issue":"1","key":"1169_CR4","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/S0166-218X(01)00266-9","volume":"119","author":"MF Anjos","year":"2002","unstructured":"Anjos, M.F., Wolkowicz, H.: Strengthened semidefinite relaxations via a second lifting for the max-cut problem. Discrete Appl. Math. 119(1), 79\u2013106 (2002)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"1169_CR5","doi-asserted-by":"crossref","first-page":"15","DOI":"10.2140\/pjm.1975.57.15","volume":"57","author":"GP Barker","year":"1975","unstructured":"Barker, G.P., Carlson, D.: Cones of diagonally dominant matrices. Pac. J. Math. 57(1), 15\u201332 (1975)","journal-title":"Pac. J. Math."},{"issue":"3","key":"1169_CR6","doi-asserted-by":"crossref","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":"1169_CR7","doi-asserted-by":"crossref","unstructured":"Berman, A., Shaked-Monderer, N.: Completely positive matrices. World Scientific, Singapore (2003). ISBN 981-238-368-9. http:\/\/opac.inria.fr\/record=b1130077","DOI":"10.1142\/5273"},{"key":"1169_CR8","volume-title":"Semidefinite Optimization and Convex Algebraic Geometry","author":"G Blekherman","year":"2013","unstructured":"Blekherman, G., Parrilo, P.A., Thomas, R.R.: Semidefinite Optimization and Convex Algebraic Geometry. SIAM, Philadelphia (2013)"},{"key":"1169_CR9","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/j.laa.2005.03.029","volume":"405","author":"EG Boman","year":"2005","unstructured":"Boman, E.G., Chen, D., Parekh, O., Toledo, S.: On factor width and symmetric $$H$$ H -matrices. Linear Algebra Appl. 405, 239\u2013248 (2005)","journal-title":"Linear Algebra Appl."},{"issue":"2","key":"1169_CR10","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1016\/0022-247X(81)90138-4","volume":"83","author":"J Borwein","year":"1981","unstructured":"Borwein, J., Wolkowicz, H.: Regularizing the abstract convex program. J. Math. Anal. Appl. 83(2), 495\u2013530 (1981)","journal-title":"J. Math. Anal. Appl."},{"key":"1169_CR11","volume-title":"Convex Optimization","author":"S Boyd","year":"2009","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2009)"},{"key":"1169_CR12","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970777","volume-title":"Linear Matrix Inequalities in System and Control Theory","author":"S Boyd","year":"1994","unstructured":"Boyd, S., El Ghaoui, L., Feron, E., Balakrishnan, V.: Linear Matrix Inequalities in System and Control Theory, vol. 15. SIAM, Philadelphia (1994)"},{"issue":"1","key":"1169_CR13","first-page":"1","volume":"1","author":"S Boyd","year":"2013","unstructured":"Boyd, S., Mueller, M., O\u2019Donoghue, B., Wang, Y.: Performance bounds and suboptimal policies for multi-period investment. Found. Trends Optim. 1(1), 1\u201369 (2013)","journal-title":"Found. Trends Optim."},{"issue":"1","key":"1169_CR14","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1016\/j.aim.2007.05.011","volume":"216","author":"P Br\u00e4nd\u00e9n","year":"2007","unstructured":"Br\u00e4nd\u00e9n, P.: Polynomials with the half-plane property and matroid theory. Adv. Math. 216(1), 302\u2013320 (2007)","journal-title":"Adv. Math."},{"key":"1169_CR15","unstructured":"Burkowski, F., Cheung, Y.-L., Wolkowicz, H.: Efficient use of semidefinite programming for selection of rotamers in protein conformations. Technical report, CORR: in progress, p. 2011. University of Waterloo, Waterloo, Ontario (2011)"},{"key":"1169_CR16","unstructured":"Burton, S., Youm, Y., Vinzant, C.: A real stable extension of the V\u00e1mos matroid polynomial. arXiv:1411.2038"},{"key":"1169_CR17","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/j.laa.2004.05.016","volume":"392","author":"D Chen","year":"2004","unstructured":"Chen, D., Toledo, S.: Combinatorial characterization of the null spaces of symmetric h-matrices. Linear Algebra Appl. 392, 71\u201390 (2004)","journal-title":"Linear Algebra Appl."},{"key":"1169_CR18","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/978-1-4614-7621-4_12","volume-title":"Computational and Analytical Mathematics","author":"Y-L Cheung","year":"2013","unstructured":"Cheung, Y.-L., Schurr, S., Wolkowicz, H.: Preprocessing and regularization for degenerate semidefinite programs. In: Bailey, D.H., Bauschke, H.H., Borwein, P., Garvan, F., Th\u00e9ra, M., Vanderwerff, J., Wolkowicz, H. (eds.) Computational and Analytical Mathematics, pp. 251\u2013303. Springer, Berlin (2013)"},{"issue":"1","key":"1169_CR19","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/S0196-8858(03)00078-2","volume":"32","author":"Y-B Choe","year":"2004","unstructured":"Choe, Y.-B., Oxley, J.G., Sokal, A.D., Wagner, D.G.: Homogeneous multivariate polynomials with the half-plane property. Adv. Appl. Math. 32(1), 88\u2013187 (2004)","journal-title":"Adv. Appl. Math."},{"issue":"5","key":"1169_CR20","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/S0167-6377(97)00011-4","volume":"20","author":"E Klerk de","year":"1997","unstructured":"de Klerk, E., Roos, C., Terlaky, T.: Initialization in semidefinite programming via a self-dual skew-symmetric embedding. Oper. Res. Lett. 20(5), 213\u2013221 (1997)","journal-title":"Oper. Res. Lett."},{"key":"1169_CR21","doi-asserted-by":"crossref","unstructured":"Diananda, P.H.: On non-negative forms in real variables some or all of which are non-negative. In: Mathematical Proceedings of the Cambridge Philosophical Society, vol. 58, pp. 17\u201325. Cambridge Univ Press (1962)","DOI":"10.1017\/S0305004100036185"},{"key":"1169_CR22","doi-asserted-by":"crossref","unstructured":"Fawzi, H., Parrilo, P.A.: Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank. arXiv preprint arXiv:1404.3240 (2014)","DOI":"10.1007\/s10107-015-0937-7"},{"key":"1169_CR23","unstructured":"Grant, M., Boyd, S.: CVX: MATLAB software for disciplined convex programming (web page and software). http:\/\/cvxr.com\/"},{"key":"1169_CR24","unstructured":"Gruber, G., Kruk, S., Rendl, F., Wolkowicz, H.: Presolving for semidefinite programs without constraint qualifications. https:\/\/pdfs.semanticscholar.org\/61ca\/fc993c23c6b94a1115292bcab45fb48bbc52.pdf (1998)"},{"issue":"5","key":"1169_CR25","doi-asserted-by":"crossref","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(5), 2679\u20132708 (2010)","journal-title":"SIAM J. Optim."},{"key":"1169_CR26","unstructured":"L\u00f6fberg, J.: YALMIP : a toolbox for modeling and optimization in MATLAB. In: Proceedings of the CACSD Conference, Taipei, Taiwan, 2004. http:\/\/users.isy.liu.se\/johanl\/yalmip"},{"issue":"5","key":"1169_CR27","doi-asserted-by":"crossref","first-page":"1007","DOI":"10.1109\/TAC.2009.2017144","volume":"54","author":"J L\u00f6fberg","year":"2009","unstructured":"L\u00f6fberg, J.: Pre-and post-processing sum-of-squares programs in practice. IEEE Trans. Autom. Control 54(5), 1007\u20131011 (2009)","journal-title":"IEEE Trans. Autom. Control"},{"key":"1169_CR28","unstructured":"Louren\u00e7o, B.F., Muramatsu, M., Tsuchiya, T.: Solving SDP completely with an interior point oracle (2015). arXiv preprint arXiv:1507.08065"},{"key":"1169_CR29","unstructured":"Luo, Z.-Q., Sturm, J.F., Zhang, S.: Duality results for conic convex programming. Technical report, Econometric Institute Research Papers (1997)"},{"issue":"2","key":"1169_CR30","doi-asserted-by":"crossref","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."},{"key":"1169_CR31","unstructured":"Papachristodoulou, A., Anderson, J., Valmorbida, G., Prajna, S., Seiler, P., Parrilo, P.: SOSTOOLS version 3.00 sum of squares optimization toolbox for MATLAB. arXiv preprint arXiv:1310.4716 (2013)"},{"key":"1169_CR32","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/978-1-4615-4381-7_3","volume-title":"The Geometry of Semidefinite Programming","author":"G Pataki","year":"2000","unstructured":"Pataki, G.: Handbook of semidefinite programming. In: Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds.) The Geometry of Semidefinite Programming, pp. 29\u201365. Springer, Berlin (2000)"},{"key":"1169_CR33","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1007\/978-1-4614-7621-4_28","volume-title":"Computational and Analytical Mathematics","author":"G Pataki","year":"2013","unstructured":"Pataki, G.: Strong duality in conic linear programming: facial reduction and extended duals. In: Bailey, D.H., Bauschke, H.H., Borwein, P., Garvan, F., Th\u00e9ra, M., Vanderwerff, J., Wolkowicz, H. (eds.) Computational and Analytical Mathematics, pp. 613\u2013634. Springer, Berlin (2013)"},{"key":"1169_CR34","doi-asserted-by":"crossref","unstructured":"Pataki, G.: Bad semidefinite programs: they all look the same. arXiv preprint arXiv:1112.1436 (2016)","DOI":"10.1137\/15M1041924"},{"key":"1169_CR35","unstructured":"Pataki, G., Schmieta, S.: The DIMACS library of semidefinite-quadratic-linear programs. http:\/\/dimacs.rutgers.edu\/Challenges\/Seventh\/Instances (1999)"},{"key":"1169_CR36","doi-asserted-by":"crossref","unstructured":"Permenter, F., Parrilo, P.A.: Basis selection for SOS programs via facial reduction and polyhedral approximations. In: Proceedings of the IEEE Conference on Decision and Control (2014)","DOI":"10.1109\/CDC.2014.7040427"},{"key":"1169_CR37","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 (2013)","DOI":"10.1145\/2461328.2461340"},{"issue":"1\u20133","key":"1169_CR38","doi-asserted-by":"crossref","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."},{"issue":"1","key":"1169_CR39","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/BF02614433","volume":"77","author":"MV Ramana","year":"1997","unstructured":"Ramana, M.V.: An exact duality theory for semidefinite programming and its complexity implications. Math. Program. 77(1), 129\u2013162 (1997)","journal-title":"Math. Program."},{"issue":"3","key":"1169_CR40","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1137\/S1052623495288350","volume":"7","author":"MV Ramana","year":"1997","unstructured":"Ramana, M.V., Tun\u00e7el, L., Wolkowicz, H.: Strong duality for semidefinite programming. SIAM J. Optim. 7(3), 641\u2013662 (1997)","journal-title":"SIAM J. Optim."},{"key":"1169_CR41","volume-title":"Convex Analysis","author":"R\u00a0T Rockafellar","year":"1997","unstructured":"Rockafellar, R\u00a0.T.: Convex Analysis, vol. 28. Princeton University Press, Princeton (1997)"},{"issue":"1\u20134","key":"1169_CR42","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1080\/10556789908805766","volume":"11","author":"JF Sturm","year":"1999","unstructured":"Sturm, J.F.: 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":"4","key":"1169_CR43","doi-asserted-by":"crossref","first-page":"1228","DOI":"10.1137\/S1052623498338606","volume":"10","author":"JF Sturm","year":"2000","unstructured":"Sturm, J.F.: Error bounds for linear matrix inequalities. SIAM J. Optim. 10(4), 1228\u20131248 (2000)","journal-title":"SIAM J. Optim."},{"issue":"1\u20134","key":"1169_CR44","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1080\/10556789908805762","volume":"11","author":"K-C Toh","year":"1999","unstructured":"Toh, K.-C., Todd, M.J., T\u00fct\u00fcnc\u00fc, R.H.: SDPT3\u2014a matlab software package for semidefinite programming, version 1.3. Optim. Methods Softw. 11(1\u20134), 545\u2013581 (1999)","journal-title":"Optim. Methods Softw."},{"issue":"2","key":"1169_CR45","doi-asserted-by":"crossref","first-page":"619","DOI":"10.1007\/s10589-012-9480-0","volume":"53","author":"L Tun\u00e7el","year":"2012","unstructured":"Tun\u00e7el, L., Wolkowicz, H.: Strong duality and minimal representations for cone optimization. Comput. Optim. Appl. 53(2), 619\u2013648 (2012)","journal-title":"Comput. Optim. Appl."},{"issue":"6","key":"1169_CR46","doi-asserted-by":"crossref","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":"1169_CR47","doi-asserted-by":"crossref","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":"1169_CR48","doi-asserted-by":"crossref","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":"5","key":"1169_CR49","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1016\/j.orl.2010.05.011","volume":"38","author":"H Waki","year":"2010","unstructured":"Waki, H., Muramatsu, M.: A facial reduction algorithm for finding sparse sos representations. Oper. Res. Lett. 38(5), 361\u2013365 (2010)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"1169_CR50","doi-asserted-by":"crossref","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."},{"key":"1169_CR51","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1016\/S0166-218X(99)00102-X","volume":"96","author":"H Wolkowicz","year":"1999","unstructured":"Wolkowicz, H., Zhao, Q.: Semidefinite programming relaxations for the graph partitioning problem. Discrete Appl. Math. 96, 461\u2013479 (1999)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"1169_CR52","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1287\/moor.19.1.53","volume":"19","author":"Y Ye","year":"1994","unstructured":"Ye, Y., Todd, M.J., Mizuno, S.: An $$\\cal{O} (\\sqrt{nL})$$ O ( nL ) -iteration homogeneous and self-dual linear programming algorithm. Math. Oper. Res. 19(1), 53\u201367 (1994)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"1169_CR53","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1023\/A:1009795911987","volume":"2","author":"Q Zhao","year":"1998","unstructured":"Zhao, Q., Karisch, S.E., Rendl, F., Wolkowicz, H.: Semidefinite programming relaxations for the quadratic assignment problem. J. Comb. Optim. 2(1), 71\u2013109 (1998)","journal-title":"J. Comb. Optim."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-017-1169-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-017-1169-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-017-1169-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,11]],"date-time":"2020-10-11T01:33:21Z","timestamp":1602380001000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-017-1169-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,28]]},"references-count":53,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2018,9]]}},"alternative-id":["1169"],"URL":"https:\/\/doi.org\/10.1007\/s10107-017-1169-9","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,6,28]]}}}