{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,16]],"date-time":"2025-05-16T12:40:10Z","timestamp":1747399210278,"version":"3.40.5"},"reference-count":81,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,3,6]],"date-time":"2025-03-06T00:00:00Z","timestamp":1741219200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,3,6]],"date-time":"2025-03-06T00:00:00Z","timestamp":1741219200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100008047","name":"Carnegie Mellon University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100008047","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Prog. Comp."],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We introduce a generic technique to obtain linear relaxations of semidefinite programs with provable guarantees based on the commutativity of the constraint and the objective matrices. We study conditions under which the optimal value of the SDP and the proposed linear relaxation match, which we then relax to provide a flexible methodology to derive effective linear relaxations. We specialize these results to provide linear programs that approximate well-known semidefinite programs for the max cut problem proposed by Poljak and Rendl, and the Lov\u00e1sz theta number; we prove that the linear program proposed for max cut certifies a known eigenvalue bound for the maximum cut value and is in fact stronger. Our ideas can be used to warm-start algorithms that solve semidefinite programs by iterative polyhedral approximation of the feasible region. We verify this capability through multiple experiments on the max cut semidefinite program, the Lov\u00e1sz theta number and on three families of semidefinite programs obtained as convex relaxations of certain quadratically constrained quadratic problems.<\/jats:p>","DOI":"10.1007\/s12532-025-00275-1","type":"journal-article","created":{"date-parts":[[2025,3,6]],"date-time":"2025-03-06T11:51:42Z","timestamp":1741261902000},"page":"385-435","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Instance-specific linear relaxations of semidefinite optimization problems"],"prefix":"10.1007","volume":"17","author":[{"given":"Daniel","family":"de Roux","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Carr","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Ravi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,3,6]]},"reference":[{"key":"275_CR1","unstructured":"Ahmadi, A.A.: Algebraic relaxations and hardness results in polynomial optimization and lyapunov analysis. arXiv preprint arXiv:1201.2892 (2012)"},{"key":"275_CR2","first-page":"27","volume":"685","author":"AA Ahmadi","year":"2017","unstructured":"Ahmadi, A.A., Hall, G.: Sum of squares basis pursuit with linear and second order cone programming. Algebr. Geom. Methods Discrete Math. 685, 27\u201353 (2017)","journal-title":"Algebr. Geom. Methods Discrete Math."},{"issue":"2","key":"275_CR3","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/18M118935X","volume":"3","author":"AA Ahmadi","year":"2019","unstructured":"Ahmadi, A.A., Majumdar, A.: Dsos and sdsos optimization: more tractable alternatives to sum of squares and semidefinite optimization. SIAM J. Appl. Algebr. Geom. 3(2), 193\u2013230 (2019)","journal-title":"SIAM J. Appl. Algebr. Geom."},{"issue":"1","key":"275_CR4","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1137\/0805002","volume":"5","author":"F Alizadeh","year":"1995","unstructured":"Alizadeh, F.: Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5(1), 13\u201351 (1995)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"275_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S0963548399004071","volume":"9","author":"N Alon","year":"2000","unstructured":"Alon, N., Sudakov, B.: Bipartite subgraphs and the smallest eigenvalue. Comb. Probab. Comput. 9(1), 1\u201312 (2000)","journal-title":"Comb. Probab. Comput."},{"key":"275_CR6","unstructured":"ApS, M.: The MOSEK optimization toolbox for MATLAB manual. Version 10.0. (2022). http:\/\/docs.mosek.com\/9.0\/toolbox\/index.html"},{"key":"275_CR7","unstructured":"Baltean-Lugojan, R., Bonami, P., Misener, R., Tramontani, A.: Scoring positive semidefinite cutting planes for quadratic optimization via trained neural networks. preprint: http:\/\/www.optimization-online.org\/DB_HTML\/2018\/11\/6943. html (2019)"},{"key":"275_CR8","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/s10107-011-0462-2","volume":"129","author":"X Bao","year":"2011","unstructured":"Bao, X., Sahinidis, N.V., Tawarmalani, M.: Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons. Math. Program. 129, 129\u2013157 (2011)","journal-title":"Math. Program."},{"issue":"2","key":"275_CR9","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF02592023","volume":"36","author":"F Barahona","year":"1986","unstructured":"Barahona, F., Mahjoub, A.R.: On the cut polytope. Math. Program. 36(2), 157\u2013173 (1986)","journal-title":"Math. Program."},{"key":"275_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-013-0710-8","volume":"143","author":"A Ben-Tal","year":"2014","unstructured":"Ben-Tal, A., Den Hertog, D.: Hidden conic quadratic representation of some nonconvex quadratic optimization problems. Math. Program. 143, 1\u201329 (2014)","journal-title":"Math. Program."},{"key":"275_CR11","doi-asserted-by":"crossref","unstructured":"Ben-Tal, A., Nemirovski, A.: Lectures on modern convex optimization: analysis, algorithms, and engineering applications. SIAM (2001)","DOI":"10.1137\/1.9780898718829"},{"issue":"1","key":"275_CR12","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/j.orl.2019.12.003","volume":"48","author":"D Bertsimas","year":"2020","unstructured":"Bertsimas, D., Cory-Wright, R.: On polyhedral and second-order cone decompositions of semidefinite optimization problems. Oper. Res. Lett. 48(1), 78\u201385 (2020)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"275_CR13","doi-asserted-by":"publisher","first-page":"1873","DOI":"10.1137\/120904172","volume":"25","author":"A Bhardwaj","year":"2015","unstructured":"Bhardwaj, A., Rostalski, P., Sanyal, R.: Deciding polyhedrality of spectrahedra. SIAM J. Optim. 25(3), 1873\u20131884 (2015)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"275_CR14","doi-asserted-by":"publisher","first-page":"756","DOI":"10.1287\/moor.2014.0694","volume":"40","author":"G Braun","year":"2015","unstructured":"Braun, G., Fiorini, S., Pokutta, S., Steurer, D.: Approximation limits of linear programs (beyond hierarchies). Math. Oper. Res. 40(3), 756\u2013772 (2015)","journal-title":"Math. Oper. Res."},{"key":"275_CR15","doi-asserted-by":"crossref","unstructured":"Brouwer, A.E., Cohen, Neumaier, A.: Distance-Regular Graphs. Springer-Verlag (1989)","DOI":"10.1007\/978-3-642-74341-2"},{"issue":"1","key":"275_CR16","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1137\/070711815","volume":"20","author":"S Bundfuss","year":"2009","unstructured":"Bundfuss, S., D\u00fcr, M.: An adaptive linear approximation algorithm for copositive programs. SIAM J. Optim. 20(1), 30\u201353 (2009)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"275_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2811255","volume":"63","author":"SO Chan","year":"2016","unstructured":"Chan, S.O., Lee, J.R., Raghavendra, P., Steurer, D.: Approximate constraint satisfaction requires large lp relaxations. J. ACM (JACM) 63(4), 1\u201322 (2016)","journal-title":"J. ACM (JACM)"},{"key":"275_CR18","doi-asserted-by":"crossref","unstructured":"Charikar, M., Makarychev, K., Makarychev, Y.: Integrality gaps for sherali-adams relaxations. In: Proceedings of the forty-first annual ACM Symposium on Theory of Computing, pp. 283\u2013292 (2009)","DOI":"10.1145\/1536414.1536455"},{"key":"275_CR19","doi-asserted-by":"crossref","unstructured":"Chung, F., Radcliffe, M.: On the spectra of general random graphs. The Electronic Journal of Combinatorics pp. P215\u2013P215 (2011)","DOI":"10.37236\/702"},{"issue":"2","key":"275_CR20","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/s12532-020-00178-3","volume":"12","author":"C Coey","year":"2020","unstructured":"Coey, C., Lubin, M., Vielma, J.P.: Outer approximation with conic certificates for mixed-integer convex problems. Math. Program. Comput. 12(2), 249\u2013293 (2020)","journal-title":"Math. Program. Comput."},{"key":"275_CR21","unstructured":"Conrad, K.: Simultaneous commutativity of operators. University of Connecticut (1992)"},{"key":"275_CR22","doi-asserted-by":"crossref","unstructured":"d\u2019Aspremont, A., Ghaoui, L., Jordan, M., Lanckriet, G.: A direct formulation for sparse pca using semidefinite programming. Advances in neural information processing systems 17 (2004)","DOI":"10.2139\/ssrn.563524"},{"issue":"1\u20133","key":"275_CR23","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1007\/BF01585184","volume":"62","author":"C Delorme","year":"1993","unstructured":"Delorme, C., Poljak, S.: Laplacian eigenvalues and the maximum cut problem. Math. Program. 62(1\u20133), 557\u2013574 (1993)","journal-title":"Math. Program."},{"key":"275_CR24","unstructured":"Dey, S.S., Kazachkov, A.M., Lodi, A., Munoz, G.: Cutting plane generation through sparse principal component analysis. URL http:\/\/www.optimization-online.org\/DB_HTML\/2021\/02\/8259. html (2021)"},{"key":"275_CR25","volume-title":"Geometry of cuts and metrics","author":"MM Deza","year":"2009","unstructured":"Deza, M.M., Laurent, M.: Geometry of cuts and metrics. Springer, Cham (2009)"},{"issue":"4","key":"275_CR26","doi-asserted-by":"publisher","first-page":"1479","DOI":"10.1287\/moor.2020.1077","volume":"46","author":"H Fawzi","year":"2021","unstructured":"Fawzi, H.: On polyhedral approximations of the positive semidefinite cone. Math. Oper. Res. 46(4), 1479\u20131489 (2021)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"275_CR27","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1002\/rsa.20089","volume":"27","author":"U Feige","year":"2005","unstructured":"Feige, U., Ofek, E.: Spectral techniques applied to sparse random graphs. Random Struct. Algorithms 27(2), 251\u2013275 (2005)","journal-title":"Random Struct. Algorithms"},{"key":"275_CR28","doi-asserted-by":"crossref","unstructured":"Friedman, J., Kahn, J., Szemeredi, E.: On the second eigenvalue of random regular graphs. In: Proceedings of the twenty-first annual ACM Symposium on Theory of Computing, pp. 587\u2013598 (1989)","DOI":"10.1145\/73007.73063"},{"key":"275_CR29","volume-title":"Introduction to Random Graphs","author":"A Frieze","year":"2016","unstructured":"Frieze, A., Karo\u0144ski, M.: Introduction to Random Graphs. Cambridge University Press, Cambridge (2016)"},{"key":"275_CR30","unstructured":"Gally, T., Pfetsch, M.E.: Computing restricted isometry constants via mixed-integer semidefinite programming. preprint, submitted (2016)"},{"issue":"3","key":"275_CR31","doi-asserted-by":"publisher","first-page":"594","DOI":"10.1080\/10556788.2017.1322081","volume":"33","author":"T Gally","year":"2018","unstructured":"Gally, T., Pfetsch, M.E., Ulbrich, S.: A framework for solving mixed-integer semidefinite programs. Optimization Methods and Software 33(3), 594\u2013632 (2018)","journal-title":"Optimization Methods and Software"},{"issue":"3","key":"275_CR32","doi-asserted-by":"publisher","first-page":"779","DOI":"10.1007\/s10957-021-01896-x","volume":"190","author":"M Garstka","year":"2021","unstructured":"Garstka, M., Cannon, M., Goulart, P.: Cosmo: a conic operator splitting method for convex conic problems. J. Optim. Theory Appl. 190(3), 779\u2013810 (2021)","journal-title":"J. Optim. Theory Appl."},{"issue":"6","key":"275_CR33","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM (JACM) 42(6), 1115\u20131145 (1995)","journal-title":"J. ACM (JACM)"},{"key":"275_CR34","doi-asserted-by":"crossref","unstructured":"Golub, G.H., Van\u00a0Loan, C.F.: Matrix computations. JHU press (2013)","DOI":"10.56021\/9781421407944"},{"issue":"3","key":"275_CR35","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1137\/S1052623497328987","volume":"10","author":"C Helmberg","year":"2000","unstructured":"Helmberg, C., Rendl, F.: A spectral bundle method for semidefinite programming. SIAM J. Optim. 10(3), 673\u2013696 (2000)","journal-title":"SIAM J. Optim."},{"key":"275_CR36","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1023\/A:1009898604624","volume":"4","author":"C Helmberg","year":"2000","unstructured":"Helmberg, C., Rendl, F., Weismantel, R.: A semidefinite programming approach to the quadratic knapsack problem. J. Comb. Optim. 4, 197\u2013215 (2000)","journal-title":"J. Comb. Optim."},{"key":"275_CR37","doi-asserted-by":"publisher","DOI":"10.1007\/b96977","volume-title":"Positive polynomials in control","author":"D Henrion","year":"2005","unstructured":"Henrion, D., Garulli, A.: Positive polynomials in control, vol. 312. Springer Science & Business Media, Cham (2005)"},{"key":"275_CR38","doi-asserted-by":"crossref","unstructured":"Hojny, C., Pfetsch, M.E.: Handling symmetries in mixed-integer semidefinite programs. In: International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pp. 69\u201378. Springer (2023)","DOI":"10.1007\/978-3-031-33271-5_5"},{"key":"275_CR39","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139020411","volume-title":"Matrix analysis","author":"RA Horn","year":"2012","unstructured":"Horn, R.A., Johnson, C.R.: Matrix analysis. Cambridge University Press, Cambridge (2012)"},{"issue":"4","key":"275_CR40","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1137\/0108053","volume":"8","author":"JE Kelley Jr","year":"1960","unstructured":"Kelley, J.E., Jr.: The cutting-plane method for solving convex programs. J. Soc. Ind. Appl. Math. 8(4), 703\u2013712 (1960)","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"275_CR41","doi-asserted-by":"crossref","unstructured":"Kothari, P.K., Meka, R., Raghavendra, P.: Approximating rectangles by juntas and weakly exponential lower bounds for lp relaxations of csps. SIAM Journal on Computing 0(0), STOC17\u2013305 (2021)","DOI":"10.1137\/17M1152966"},{"issue":"1","key":"275_CR42","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1080\/10556780500065283","volume":"21","author":"K Krishnan","year":"2006","unstructured":"Krishnan, K., Mitchell, J.E.: A unifying framework for several cutting plane methods for semidefinite programming. Optimization Methods Softw. 21(1), 57\u201374 (2006)","journal-title":"Optimization Methods Softw."},{"key":"275_CR43","first-page":"27","volume":"5","author":"GR Lanckriet","year":"2004","unstructured":"Lanckriet, G.R., Cristianini, N., Bartlett, P., Ghaoui, L.E., Jordan, M.I.: Learning the kernel matrix with semidefinite programming. J. Mach. Learn. Res. 5, 27\u201372 (2004)","journal-title":"J. Mach. Learn. Res."},{"issue":"3","key":"275_CR44","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":"6","key":"275_CR45","doi-asserted-by":"publisher","first-page":"1141","DOI":"10.1007\/s11590-016-1001-0","volume":"10","author":"M Locatelli","year":"2016","unstructured":"Locatelli, M.: Exactness conditions for an sdp relaxation of the extended trust region problem. Optim. Lett. 10(6), 1141\u20131151 (2016)","journal-title":"Optim. Lett."},{"issue":"1","key":"275_CR46","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz, L.: On the shannon capacity of a graph. IEEE Trans. Inf. Theory 25(1), 1\u20137 (1979)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"275_CR47","doi-asserted-by":"crossref","unstructured":"Lubin, M., Yamangil, E., Bent, R., Vielma, J.P.: Extended formulations in mixed-integer convex programming. In: Integer Programming and Combinatorial Optimization: 18th International Conference, IPCO 2016, Li\u00e8ge, Belgium, June 1-3, 2016, Proceedings 18, pp. 102\u2013113. Springer (2016)","DOI":"10.1007\/978-3-319-33461-5_9"},{"issue":"3","key":"275_CR48","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/BF02126799","volume":"8","author":"A Lubotzky","year":"1988","unstructured":"Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica 8(3), 261\u2013277 (1988)","journal-title":"Combinatorica"},{"key":"275_CR49","doi-asserted-by":"crossref","unstructured":"Majumdar, A., Hall, G., Ahmadi, A.A.: A survey of recent scalability improvements for semidefinite programming with applications in machine learning, control, and robotics. arXiv preprint arXiv:1908.05209 (2019)","DOI":"10.1146\/annurev-control-091819-074326"},{"key":"275_CR50","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1146\/annurev-control-091819-074326","volume":"3","author":"A Majumdar","year":"2020","unstructured":"Majumdar, A., Hall, G., Ahmadi, A.A.: Recent scalability improvements for semidefinite programming with applications in machine learning, control, and robotics. Ann. Rev. Control Robot. Auton. Syst. 3, 331\u2013360 (2020)","journal-title":"Ann. Rev. Control Robot. Auton. Syst."},{"key":"275_CR51","unstructured":"Mirka, R., Williamson, D.P.: An experimental evaluation of semidefinite programming and spectral algorithms for max cut. In: 20th International Symposium on Experimental Algorithms (SEA 2022). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2022)"},{"issue":"2","key":"275_CR52","doi-asserted-by":"publisher","first-page":"343","DOI":"10.21136\/CMJ.1990.102386","volume":"40","author":"B Mohar","year":"1990","unstructured":"Mohar, B., Poljak, S.: Eigenvalues and the max-cut problem. Czechoslov. Math. J. 40(2), 343\u2013352 (1990)","journal-title":"Czechoslov. Math. J."},{"key":"275_CR53","unstructured":"Nemirovski, A.: Interior point polynomial time methods in convex programming. Lecture notes pp. 3215\u20133224 (2004)"},{"key":"275_CR54","unstructured":"Nesterov, Y., et al.: Semidefinite relaxation and nonconvex quadratic optimization. Universit\u00e9 catholique de Louvain, Center for Operations Research and Econometrics, Tech. rep. (1997)"},{"key":"275_CR55","unstructured":"O\u2019Donnell, R., Schramm, T.: Sherali\u2013adams strikes back. arXiv preprint arXiv:1812.09967 (2018)"},{"key":"275_CR56","doi-asserted-by":"crossref","unstructured":"O\u2019donoghue, B., Chu, E., Parikh, N., Boyd, S.: Conic optimization via operator splitting and homogeneous self-dual embedding. J. Optim. Theory Appl. 169, 1042\u20131068 (2016)","DOI":"10.1007\/s10957-016-0892-3"},{"key":"275_CR57","unstructured":"Parrilo, P.A.: Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. California Institute of Technology (2000)"},{"issue":"2","key":"275_CR58","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s10107-003-0387-5","volume":"96","author":"PA Parrilo","year":"2003","unstructured":"Parrilo, P.A.: Semidefinite programming relaxations for semialgebraic problems. Math. Program. 96(2), 293\u2013320 (2003)","journal-title":"Math. Program."},{"issue":"5","key":"275_CR59","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1016\/j.dam.2006.08.007","volume":"155","author":"D Pisinger","year":"2007","unstructured":"Pisinger, D.: The quadratic knapsack problem-a survey. Discret. Appl. Math. 155(5), 623\u2013648 (2007)","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"275_CR60","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1137\/0805024","volume":"5","author":"S Poljak","year":"1995","unstructured":"Poljak, S., Rendl, F.: Nonpolyhedral relaxations of graph-bisection problems. SIAM J. Optim. 5(3), 467\u2013487 (1995)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"275_CR61","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0167-6377(94)90068-X","volume":"16","author":"S Poljak","year":"1994","unstructured":"Poljak, S., Tuza, Z.: The expected relative error of the polyhedral approximation of the max-cut problem. Oper. Res. Lett. 16(4), 191\u2013198 (1994)","journal-title":"Oper. Res. Lett."},{"key":"275_CR62","doi-asserted-by":"crossref","unstructured":"Qualizza, A., Belotti, P., Margot, F.: Linear programming relaxations of quadratically constrained quadratic programs. In: Mixed Integer Nonlinear Programming, pp. 407\u2013426. Springer (2012)","DOI":"10.1007\/978-1-4614-1927-3_14"},{"key":"275_CR63","doi-asserted-by":"crossref","unstructured":"Ramana, M.V.: Polyhedra, spectrahedra, and semidefinite programming. Topics in semidefinite and interior-point methods, Fields Institute Communications 18, 27\u201338 (1997)","DOI":"10.1090\/fic\/018\/03"},{"issue":"4","key":"275_CR64","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","volume":"3","author":"G Reinelt","year":"1991","unstructured":"Reinelt, G.: Tsplib-a traveling salesman problem library. ORSA J. Comput. 3(4), 376\u2013384 (1991)","journal-title":"ORSA J. Comput."},{"key":"275_CR65","doi-asserted-by":"crossref","unstructured":"Rossi, R.A., Ahmed, N.K.: The network data repository with interactive graph analytics and visualization. In: AAAI (2015). http:\/\/networkrepository.com","DOI":"10.1609\/aaai.v29i1.9277"},{"issue":"1","key":"275_CR66","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1023\/A:1013819515732","volume":"22","author":"HD Sherali","year":"2002","unstructured":"Sherali, H.D., Fraticelli, B.M.: Enhancing rlt relaxations via a new class of semidefinite cuts. J. Global Optim. 22(1), 233\u2013261 (2002)","journal-title":"J. Global Optim."},{"issue":"1","key":"275_CR67","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/BF02283692","volume":"25","author":"NZ Shor","year":"1990","unstructured":"Shor, N.Z.: Dual quadratic estimates in polynomial and boolean programming. Ann. Oper. Res. 25(1), 163\u2013168 (1990)","journal-title":"Ann. Oper. Res."},{"key":"275_CR68","doi-asserted-by":"crossref","unstructured":"Sivaramakrishnan, K.K.: Linear programming approaches to semidefinite programming problems. Rensselaer Polytechnic Institute (2002)","DOI":"10.1090\/fic\/037\/08"},{"key":"275_CR69","doi-asserted-by":"crossref","unstructured":"Spielman, D.: Spectral graph theory. Combinatorial scientific computing 18 (2012)","DOI":"10.1201\/b11644-19"},{"issue":"1","key":"275_CR70","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1214\/18-AOP1263","volume":"47","author":"K Tikhomirov","year":"2019","unstructured":"Tikhomirov, K., Youssef, P.: The spectral gap of dense random regular graphs. Ann. Probab. 47(1), 362\u2013419 (2019)","journal-title":"Ann. Probab."},{"issue":"1","key":"275_CR71","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1137\/1038003","volume":"38","author":"L Vandenberghe","year":"1996","unstructured":"Vandenberghe, L., Boyd, S.: Semidefinite programming. SIAM review 38(1), 49\u201395 (1996)","journal-title":"SIAM review"},{"key":"275_CR72","unstructured":"de\u00a0la Vega, W.F., Kenyon-Mathieu, C.: Linear programming relaxations of maxcut. In: Proceedings of the eighteenth annual ACM-SIAM Symposium on Discrete Algorithms, pp. 53\u201361 (2007)"},{"issue":"5","key":"275_CR73","doi-asserted-by":"publisher","first-page":"492","DOI":"10.1090\/noti1116","volume":"61","author":"C Vinzant","year":"2014","unstructured":"Vinzant, C.: What is a spectrahedron. Notices Amer. Math. Soc 61(5), 492\u2013494 (2014)","journal-title":"Notices Amer. Math. Soc"},{"issue":"1","key":"275_CR74","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s10107-020-01589-9","volume":"193","author":"AL Wang","year":"2022","unstructured":"Wang, A.L., K\u0131l\u0131n\u00e7-Karzan, F.: On the tightness of sdp relaxations of qcqps. Math. Program. 193(1), 33\u201373 (2022)","journal-title":"Math. Program."},{"issue":"3","key":"275_CR75","doi-asserted-by":"publisher","first-page":"1361","DOI":"10.1137\/22M1474539","volume":"33","author":"Y Wang","year":"2023","unstructured":"Wang, Y., Deng, K., Liu, H., Wen, Z.: A decomposition augmented lagrangian method for low-rank semidefinite programming. SIAM J. Optim. 33(3), 1361\u20131390 (2023)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"275_CR76","doi-asserted-by":"publisher","first-page":"893","DOI":"10.1007\/s10589-020-00255-2","volume":"78","author":"Y Wang","year":"2021","unstructured":"Wang, Y., Tanaka, A., Yoshise, A.: Polyhedral approximations of the semidefinite cone and their application. Comput. Optim. Appl. 78(3), 893\u2013913 (2021)","journal-title":"Comput. Optim. Appl."},{"issue":"1\u20132","key":"275_CR77","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1007\/s10107-012-0584-1","volume":"142","author":"Z Wen","year":"2013","unstructured":"Wen, Z., Yin, W.: A feasible method for optimization with orthogonality constraints. Math. Program. 142(1\u20132), 397\u2013434 (2013)","journal-title":"Math. Program."},{"issue":"1\u20132","key":"275_CR78","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/s10107-022-01912-6","volume":"201","author":"H Yang","year":"2023","unstructured":"Yang, H., Liang, L., Carlone, L., Toh, K.C.: An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization. Math. Program. 201(1\u20132), 409\u2013472 (2023)","journal-title":"Math. Program."},{"key":"275_CR79","doi-asserted-by":"crossref","unstructured":"Yang, L., Sun, D., Toh, K.C.: Sdpnal+: a majorized semismooth newton-cg augmented lagrangian method for semidefinite programming with nonnegative constraints. Math. Program. Comput. 7(3), 331\u2013366 (2015)","DOI":"10.1007\/s12532-015-0082-6"},{"key":"275_CR80","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/s11081-010-9107-1","volume":"11","author":"K Yonekura","year":"2010","unstructured":"Yonekura, K., Kanno, Y.: Global optimization of robust truss topology via mixed integer semidefinite programming. Optim. Eng. 11, 355\u2013379 (2010)","journal-title":"Optim. Eng."},{"issue":"4","key":"275_CR81","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":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-025-00275-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12532-025-00275-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-025-00275-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,16]],"date-time":"2025-05-16T12:03:39Z","timestamp":1747397019000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12532-025-00275-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,6]]},"references-count":81,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["275"],"URL":"https:\/\/doi.org\/10.1007\/s12532-025-00275-1","relation":{},"ISSN":["1867-2949","1867-2957"],"issn-type":[{"type":"print","value":"1867-2949"},{"type":"electronic","value":"1867-2957"}],"subject":[],"published":{"date-parts":[[2025,3,6]]},"assertion":[{"value":"31 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 November 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 March 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 May 2025","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"In this article, the ESM file was missing. This has been uploaded now.","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}