{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,18]],"date-time":"2025-09-18T10:24:44Z","timestamp":1758191084761,"version":"3.44.0"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T00:00:00Z","timestamp":1751328000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T00:00:00Z","timestamp":1751328000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100007655","name":"Czech Technical University in Prague","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100007655","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2025,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>The aim of this paper is to solve linear semidefinite programs arising from higher-order Lasserre relaxations of unconstrained binary quadratic optimization problems. For this we use an interior point method with a preconditioned conjugate gradient method solving the linear systems. The preconditioner utilizes the low-rank structure of the solution of the relaxations. In order to fully exploit this, we need to re-write the moment relaxations. To treat the arising linear equality constraints we use an <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\ell _1$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>\u2113<\/mml:mi>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:msub>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>-penalty approach within the interior-point solver. The efficiency of this approach is demonstrated by numerical experiments with the MAXCUT and other randomly generated problems and a comparison with a state-of-the-art semidefinite solver and the ADMM method. We further propose a hybrid ADMM-interior-point method that proves to be efficient for certain problem classes. As a by-product, we observe that the second-order relaxation is often high enough to deliver a globally optimal solution of the original problem.<\/jats:p>","DOI":"10.1007\/s10898-025-01523-3","type":"journal-article","created":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T05:20:15Z","timestamp":1751347215000},"page":"63-85","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the numerical solution of Lasserre relaxations of unconstrained binary quadratic optimization problem"],"prefix":"10.1007","volume":"93","author":[{"given":"Soodeh","family":"Habibi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4414-0083","authenticated-orcid":false,"given":"Michal","family":"Ko\u010dvara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Stingl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,7,1]]},"reference":[{"issue":"4","key":"1523_CR1","doi-asserted-by":"publisher","first-page":"1310","DOI":"10.1137\/06066847X","volume":"18","author":"MF Anjos","year":"2008","unstructured":"Anjos, M.F., Burer, S.: On handling free variables in interior-point methods for conic linear optimization. SIAM. J. on Opt. 18(4), 1310\u20131325 (2008)","journal-title":"SIAM. J. on Opt."},{"key":"1523_CR2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718829","volume-title":"Lectures on modern convex optimization: analysis, algorithms, and engineering applications","author":"A Ben-Tal","year":"2001","unstructured":"Ben-Tal, A., Nemirovski, A.: Lectures on modern convex optimization: analysis, algorithms, and engineering applications. SIAM, Philadelphia (2001)"},{"key":"1523_CR3","doi-asserted-by":"crossref","unstructured":"Campos, J.S., Misener, R., Parpas, P.: Partial lasserre relaxation for sparse Max-Cut. Optimization and Engineering, pages 1\u201322, (2022)","DOI":"10.1007\/s11081-022-09763-y"},{"issue":"6","key":"1523_CR4","doi-asserted-by":"publisher","first-page":"1333","DOI":"10.1137\/0327068","volume":"27","author":"G Di Pillo","year":"1989","unstructured":"Di Pillo, G., Grippo, L.: Exact penalty functions in constrained optimization. SIAM. J. on Control and Opt. 27(6), 1333\u20131360 (1989)","journal-title":"SIAM. J. on Control and Opt."},{"issue":"1","key":"1523_CR5","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/s10107-015-0977-z","volume":"160","author":"H Fawzi","year":"2016","unstructured":"Fawzi, H., Saunderson, J., Parrilo, P.A.: Sparse sums of squares on finite abelian groups and improved semidefinite lifts. Math. Progr. 160(1), 149\u2013191 (2016)","journal-title":"Math. Progr."},{"key":"1523_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58582-1","volume-title":"Numerische Verfahren zur L\u00f6sung unrestringierter Optimierungsaufgaben","author":"C Geiger","year":"1999","unstructured":"Geiger, C., Kanzow, C.: Numerische Verfahren zur L\u00f6sung unrestringierter Optimierungsaufgaben. Springer-Verlag, Berlin-Heidelberg (1999)"},{"issue":"1","key":"1523_CR7","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1007\/s10107-015-0870-9","volume":"156","author":"B Ghaddar","year":"2016","unstructured":"Ghaddar, B., Vera, J.C., Anjos, M.F.: A dynamic inequality generation scheme for polynomial programming. Math. Program. 156(1), 21\u201357 (2016)","journal-title":"Math. Program."},{"issue":"6","key":"1523_CR8","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 42(6), 1115\u20131145 (1995)","journal-title":"J. ACM"},{"issue":"2","key":"1523_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3514039","volume":"48","author":"N Gusmeroli","year":"2022","unstructured":"Gusmeroli, N., Hrga, T., Lu\u017ear, B., Povh, J., Siebenhofer, M., Wiegele, A.: BiqBin: a parallel branch-and-bound solver for binary quadratic problems with linear constraints. ACM Trans. on Math. Softwa. (TOMS) 48(2), 1\u201331 (2022)","journal-title":"ACM Trans. on Math. Softwa. (TOMS)"},{"key":"1523_CR10","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2021.100622","volume":"44","author":"N Gusmeroli","year":"2022","unstructured":"Gusmeroli, N., Wiegele, A.: EXPEDIS: An exact penalty method over discrete sets. Discrete Opt 44, 100622 (2022)","journal-title":"Discrete Opt"},{"issue":"2","key":"1523_CR11","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1137\/050648237","volume":"19","author":"N Gvozdenovi\u0107","year":"2008","unstructured":"Gvozdenovi\u0107, N., Laurent, M.: The operator $$\\psi $$ for the chromatic number of a graph. SIAM. J. on Opt. 19(2), 572\u2013591 (2008)","journal-title":"SIAM. J. on Opt."},{"key":"1523_CR12","volume-title":"Loraine\u2013an interior-point solver for low-rank semidefinite programming","author":"S Habibi","year":"2022","unstructured":"Habibi, S., Ko\u010dvara, M., Stingl, M.: Loraine\u2013an interior-point solver for low-rank semidefinite programming. Optimization Methods and Software, Submitted (2022)"},{"key":"1523_CR13","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1016\/j.disopt.2016.08.001","volume":"24","author":"S Kim","year":"2017","unstructured":"Kim, S., Kojima, M.: Binary quadratic optimization problems that are difficult to solve by conic relaxations. Discrete. Opt 24, 170\u2013183 (2017)","journal-title":"Discrete. Opt"},{"issue":"4","key":"1523_CR14","doi-asserted-by":"publisher","first-page":"3177","DOI":"10.1137\/17M1152061","volume":"28","author":"I Klep","year":"2018","unstructured":"Klep, I., Povh, J., Vol\u010di\u010d, J.: Minimizer extraction in polynomial optimization is robust. SIAM. J. on Opt. 28(4), 3177\u20133207 (2018)","journal-title":"SIAM. J. on Opt."},{"issue":"1","key":"1523_CR15","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/s10878-014-9734-0","volume":"28","author":"G Kochenberger","year":"2014","unstructured":"Kochenberger, G., Hao, J.-K., Glover, F., Lewis, M., L\u00fc, Z., Wang, H., Wang, Y.: The unconstrained binary quadratic programming problem: a survey. J. of Comb. Opt. 28(1), 58\u201381 (2014)","journal-title":"J. of Comb. Opt."},{"issue":"4","key":"1523_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3005345","volume":"43","author":"N Krislock","year":"2017","unstructured":"Krislock, N., Malick, J., Roupin, F.: Biqcrunch: A semidefinite branch-and-bound method for solving binary quadratic problems. ACM Trans. on Math. Softw. (TOMS) 43(4), 1\u201323 (2017)","journal-title":"ACM Trans. on Math. Softw. (TOMS)"},{"key":"1523_CR17","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107447226","volume-title":"An introduction to polynomial and semi-algebraic optimization","author":"J-B Lasserre","year":"2015","unstructured":"Lasserre, J.-B.: An introduction to polynomial and semi-algebraic optimization. Cambridge University Press, Cambridge (2015)"},{"issue":"5","key":"1523_CR18","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1016\/j.orl.2016.07.006","volume":"44","author":"JB Lasserre","year":"2016","unstructured":"Lasserre, J.B.: A MAX-CUT formulation of 0\/1 programs. Ops. Res. Lett. 44(5), 625\u2013629 (2016)","journal-title":"Ops. Res. Lett."},{"issue":"4","key":"1523_CR19","doi-asserted-by":"publisher","first-page":"871","DOI":"10.1287\/moor.28.4.871.20508","volume":"28","author":"M Laurent","year":"2003","unstructured":"Laurent, M.: Lower bound for the number of iterations in semidefinite hierarchies for the cut polytope. Math. of Ops. Res. 28(4), 871\u2013883 (2003)","journal-title":"Math. of Ops. Res."},{"key":"1523_CR20","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, 407\u2013430 (2003)","journal-title":"Math. Program."},{"key":"1523_CR21","unstructured":"MOSEK ApS. The MOSEK optimization toolbox for MATLAB manual. Version 10.0., (2022)"},{"key":"1523_CR22","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977608","volume-title":"Moment and Polynomial Opt","author":"J Nie","year":"2023","unstructured":"Nie, J.: Moment and Polynomial Opt. SIAM, Philadelphia (2023)"},{"key":"1523_CR23","doi-asserted-by":"crossref","unstructured":"Rendl, F., Rinaldi, G., Wiegele, A.: A branch and bound algorithm for max-cut based on combining semidefinite and polyhedral relaxations. In International Conference on Integer Programming and Combinatorial Optimization, pages 295\u2013309. Springer, (2007)","DOI":"10.1007\/978-3-540-72792-7_23"},{"key":"1523_CR24","unstructured":"Sakaue, S., Takeda, A., Kim, S., Ito, N.: Exact SDP relaxations with truncated moment matrix for binary polynomial optimization problems. In Proceedings of the 5th International Conference on Continuous Optimization (ICCOPT), (2016)"},{"issue":"2","key":"1523_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1377612.1377619","volume":"35","author":"H Waki","year":"2008","unstructured":"Waki, H., Kim, S., Kojima, M., Muramatsu, M., Sugimoto, H.: Algorithm 883: SparsePOP\u2013a sparse semidefinite programming relaxation of polynomial optimization problems. ACM. Trans. on Math. Softw. (TOMS) 35(2), 1\u201313 (2008)","journal-title":"ACM. Trans. on Math. Softw. (TOMS)"},{"issue":"1","key":"1523_CR26","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1137\/19M1307871","volume":"31","author":"J Wang","year":"2021","unstructured":"Wang, J., Magron, V., Lasserre, J.-B.: TSSOS: A moment-SOS hierarchy that exploits term sparsity. SIAM. J. on Opt. 31(1), 30\u201358 (2021)","journal-title":"SIAM. J. on Opt."},{"issue":"4","key":"1523_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3569709","volume":"48","author":"J Wang","year":"2022","unstructured":"Wang, J., Magron, V., Lasserre, J.B., Mai, N.H.A.: CS-TSSOS: Correlative and term sparsity for large-scale polynomial optimization. ACM. Trans. on Math. Softw. 48(4), 1\u201326 (2022)","journal-title":"ACM. Trans. on Math. Softw."},{"issue":"3","key":"1523_CR28","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/s12532-010-0017-1","volume":"2","author":"Z Wen","year":"2010","unstructured":"Wen, Z., Goldfarb, D., Yin, W.: Alternating direction augmented Lagrangian methods for semidefinite programming. Math. Program. Comput. 2(3), 203\u2013230 (2010)","journal-title":"Math. Program. Comput."},{"key":"1523_CR29","doi-asserted-by":"crossref","unstructured":"Zhang, R.Y., Lavaei, J.: Modified interior-point method for large-and-sparse low-rank semidefinite programs. 2017 IEEE 56th Annual Conference on Decision and Control (CDC), (Dec 2017)","DOI":"10.1109\/CDC.2017.8264510"}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-025-01523-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-025-01523-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-025-01523-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,17]],"date-time":"2025-09-17T11:42:27Z","timestamp":1758109347000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-025-01523-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,1]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["1523"],"URL":"https:\/\/doi.org\/10.1007\/s10898-025-01523-3","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"type":"print","value":"0925-5001"},{"type":"electronic","value":"1573-2916"}],"subject":[],"published":{"date-parts":[[2025,7,1]]},"assertion":[{"value":"26 December 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 June 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 July 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author has no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}