{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:24:00Z","timestamp":1740122640433,"version":"3.37.3"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,12,27]],"date-time":"2022-12-27T00:00:00Z","timestamp":1672099200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,12,27]],"date-time":"2022-12-27T00:00:00Z","timestamp":1672099200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11971177"],"award-info":[{"award-number":["11971177"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2023,4]]},"DOI":"10.1007\/s10589-022-00443-2","type":"journal-article","created":{"date-parts":[[2022,12,27]],"date-time":"2022-12-27T11:03:41Z","timestamp":1672139021000},"page":"875-919","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A matrix nonconvex relaxation approach to unconstrained binary polynomial programs"],"prefix":"10.1007","volume":"84","author":[{"given":"Yitian","family":"Qian","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shaohua","family":"Pan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shujun","family":"Bi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,12,27]]},"reference":[{"key":"443_CR1","doi-asserted-by":"publisher","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. Discret. Appl. Math. 119, 79\u2013106 (2002)","journal-title":"Discret. Appl. Math."},{"key":"443_CR2","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1287\/moor.1100.0449","volume":"35","author":"H Attouch","year":"2010","unstructured":"Attouch, H., Bolte, J., Redont, P., Soubeyran, A.: Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the kurdyka-\u0142ojasiewicz inequality. Math. Oper. Res. 35, 438\u2013457 (2010)","journal-title":"Math. Oper. Res."},{"key":"443_CR3","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1016\/j.orl.2016.03.002","volume":"44","author":"SJ Bi","year":"2016","unstructured":"Bi, S.J., Pan, S.H.: Error bounds for rank constrained optimization problems and applications. Oper. Res. Lett. 44, 336\u2013341 (2016)","journal-title":"Oper. Res. Lett."},{"key":"443_CR4","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, 329\u2013357 (2003)","journal-title":"Math. Program."},{"key":"443_CR5","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1137\/S1052623400382467","volume":"12","author":"S Burer","year":"2001","unstructured":"Burer, S., Monteiro, R.D.C., Zhang, Y.: Rank-two relaxation heuristics for max-cut and other binary quadratic programs. SIAM J. Optim. 12, 503\u2013521 (2001)","journal-title":"SIAM J. Optim."},{"key":"443_CR6","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1287\/mnsc.41.4.704","volume":"41","author":"P Chardaire","year":"1994","unstructured":"Chardaire, P., Sutter, A.: A decomposition method for quadratic zero-one programming. Manage. Sci. 41, 704\u2013712 (1994)","journal-title":"Manage. Sci."},{"key":"443_CR7","doi-asserted-by":"publisher","first-page":"391","DOI":"10.4208\/jcm.1708-m2017-0130","volume":"36","author":"TR Fu","year":"2018","unstructured":"Fu, T.R., Ge, D.D., Ye, Y.Y.: On doubly positive semidefinite programming relaxations. J. Comput. Math. 36, 391\u2013403 (2018)","journal-title":"J. Comput. Math."},{"key":"443_CR8","doi-asserted-by":"crossref","unstructured":"Glover, F., L\u00fc, Z.P., Hao, J.K.: Diversification-driven tabu search for unconstrained binary quadratic problems. 4OR-A Q. J. Oper. Res. 8, 239\u2013253 (2010)","DOI":"10.1007\/s10288-009-0115-y"},{"key":"443_CR9","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. Assoc. Comput. Mach. 42, 1115\u20131145 (1995)","journal-title":"J. Assoc. Comput. Mach."},{"key":"443_CR10","unstructured":"Gurobi: Gurobi 9.5.1, http:\/\/www.gurobi.com\/"},{"key":"443_CR11","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s40305-013-0003-1","volume":"1","author":"SM He","year":"2013","unstructured":"He, S.M., Li, Z.N., Zhang, S.Z.: Approximation algorithms for discrete polynomial optimization. J. Oper. Res. Soc. China 1, 3\u201336 (2013)","journal-title":"J. Oper. Res. Soc. China"},{"key":"443_CR12","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/BF01580072","volume":"82","author":"C Helmberg","year":"1998","unstructured":"Helmberg, C., Rendl, F.: Solving quadratic $$(0,1)$$-problems by semidefinite programs and cutting planes. Math. Program. 82, 291\u2013395 (1998)","journal-title":"Math. Program."},{"key":"443_CR13","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1080\/10556780802699201","volume":"24","author":"D Henrion","year":"2009","unstructured":"Henrion, D., Lasserre, J., Loefberg, J.: Gloptipoly3: moments, optimization and semidefinite programming. Optim. Methods Softw. 24, 761\u2013779 (2009)","journal-title":"Optim. Methods Softw."},{"key":"443_CR14","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s11228-008-0076-x","volume":"16","author":"AD Ioffe","year":"2008","unstructured":"Ioffe, A.D., Outrata, J.V.: On metric and calmness qualification conditions in subdifferential calculus. Set-Valued Anal. 16, 199\u2013227 (2008)","journal-title":"Set-Valued Anal."},{"key":"443_CR15","doi-asserted-by":"crossref","unstructured":"Jiang, Z.X., Zhao, X.Y., Ding, C.: A proximal dc approach for quadratic assignment problem. Comput. Optim. Appl. https:\/\/doi.org\/10.1007\/s10589-020-00252-5 (2021)","DOI":"10.1007\/s10589-020-00252-5"},{"key":"443_CR16","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s10107-015-0874-5","volume":"156","author":"SY Kim","year":"2016","unstructured":"Kim, S.Y., Kojima, M., Toh, K.C.: A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems. Math. Program. 156, 161\u2013187 (2016)","journal-title":"Math. Program."},{"key":"443_CR17","first-page":"58","volume":"28","author":"G Kochenberger","year":"2014","unstructured":"Kochenberger, G., Hao, J.K., Glover, F., Lewis, M., L\u00fc, Z.P., Wang, H.B., Wang, Y.: The unconstrained binary quadratic programming problem: a survey. J. Global Optim. 28, 58\u201381 (2014)","journal-title":"J. Global Optim."},{"key":"443_CR18","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/s10107-012-0594-z","volume":"143","author":"N Krislock","year":"2014","unstructured":"Krislock, N., Malick, J., Roupin, F.: Improved semidefinite bounding procedure for solving max-cut problems to optimality. Math. Program. 143, 61\u201386 (2014)","journal-title":"Math. Program."},{"key":"443_CR19","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. Math. Softw. 43, 1\u201323 (2017)","journal-title":"ACM Trans. Math. Softw."},{"key":"443_CR20","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, 796\u2013817 (2001)","journal-title":"SIAM J. Optim."},{"key":"443_CR21","doi-asserted-by":"crossref","unstructured":"Le\u00a0Thi, H.A., Pham\u00a0Dinh, T.: Dc programming and dca: thirty years of developments, Mathematical Programming B, Special Issue dedicated to: DC Programming-Theory, Algorithms and Applications, 169, pp.\u00a05\u201368 (2018)","DOI":"10.1007\/s10107-018-1235-y"},{"key":"443_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107980004a","volume":"84","author":"AS Lewis","year":"1999","unstructured":"Lewis, A.S.: Nonsmooth analysis of eigenvalues. Math. Program. 84, 1\u201324 (1999)","journal-title":"Math. Program."},{"key":"443_CR23","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1007\/s10898-011-9713-2","volume":"52","author":"D Li","year":"2012","unstructured":"Li, D., Sun, X.L., Liu, C.L.: An exact solution method for unconstrained quadratic 0\u20131 programming: a geometric approach. J. Global Optim. 52, 797\u2013829 (2012)","journal-title":"J. Global Optim."},{"key":"443_CR24","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1093\/imaiai\/iay003","volume":"8","author":"QW Li","year":"2018","unstructured":"Li, Q.W., Zhu, Z.H., Tang, G.G.: The non-convex geometry of low-rank matrix optimization. Inf. Inference: J. IMA 8, 51\u201396 (2018)","journal-title":"Inf. Inference: J. IMA"},{"key":"443_CR25","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1007\/s12532-018-0137-6","volume":"10","author":"XD Li","year":"2018","unstructured":"Li, X.D., Sun, D.F., Toh, K.C.: Qsdpnal: a two-phase augmented Lagrangian method for convex quadratic semidefinite programming. Math. Program. Comput. 10, 703\u2013743 (2018)","journal-title":"Math. Program. Comput."},{"key":"443_CR26","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/s10589-019-00067-z","volume":"73","author":"TX Liu","year":"2019","unstructured":"Liu, T.X., Pong, T.K., Takeda, A.: A refined convergence analysis of pdca$$_{e}$$ with applications to simultatneous sparse recovery and outlier detection. Comput. Optim. Appl. 73, 69\u2013100 (2019)","journal-title":"Comput. Optim. Appl."},{"key":"443_CR27","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/s10107-018-1327-8","volume":"176","author":"TX Liu","year":"2019","unstructured":"Liu, T.X., Pong, T.K., Takeda, A.: A successive difference-of-convex approximation method for a class of nonconvex nonsmooth optimization problems. Math. Program. 176, 339\u2013367 (2019)","journal-title":"Math. Program."},{"key":"443_CR28","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/s10851-012-0406-3","volume":"47","author":"DR Luke","year":"2013","unstructured":"Luke, D.R.: Prox-regularity of rank constraint sets and implications for algorithms. J. Math. Imaging Vis. 47, 231\u2013238 (2013)","journal-title":"J. Math. Imaging Vis."},{"key":"443_CR29","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1109\/4234.951377","volume":"5","author":"J Luo","year":"2001","unstructured":"Luo, J., Pattipati, K., Willett, P., Hasegawa, F.: Near-optimal multiuser detection in synchronous CDMA using probabilistic data association. IEEE Commun. Lett. 5, 361\u2013363 (2001)","journal-title":"IEEE Commun. Lett."},{"key":"443_CR30","first-page":"372","volume":"27","author":"Y Nesterov","year":"1983","unstructured":"Nesterov, Y.: A method of solving a convex programming problem with convergence rate $$o(1\/k^2)$$. Soviet Math. Dokl. 27, 372\u2013376 (1983)","journal-title":"Soviet Math. Dokl."},{"key":"443_CR31","doi-asserted-by":"publisher","unstructured":"Niu, Y.S., Glowinski, R.: Discrete dynamical system approaches for boolean polynomial optimization. J. Sci. Comput. 92. https:\/\/doi.org\/10.1007\/s10915-022-01882-z (2022)","DOI":"10.1007\/s10915-022-01882-z"},{"key":"443_CR32","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1023\/B:ANOR.0000039522.58036.68","volume":"131","author":"G Palubeckis","year":"2004","unstructured":"Palubeckis, G.: Multistart tabu search strategies for the unconstrained binary quadratic optimization problem. Ann. Oper. Res. 131, 259\u2013282 (2004)","journal-title":"Ann. Oper. Res."},{"key":"443_CR33","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1287\/moor.2016.0795","volume":"42","author":"JS Pang","year":"2017","unstructured":"Pang, J.S., Razaviyayn, M., Alvarado, A.: Computing b-stationary points of nonsmooth dc programs. Math. Oper. Res. 42, 95\u2013118 (2017)","journal-title":"Math. Oper. Res."},{"key":"443_CR34","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/0305-0548(92)90067-F","volume":"19","author":"PM Pardalos","year":"1992","unstructured":"Pardalos, P.M., Rodgers, G.R.: A branch and bound algorithm for maximum clique problem. Comput. Oper. Res. 19, 363\u2013375 (1992)","journal-title":"Comput. Oper. Res."},{"key":"443_CR35","unstructured":"Pham Dinh, T., Le Thi, H.A.: Convex analysis approach to dc programming: theory, algorithms and applications. Acta Math. Vietnamica, 22, 289\u2013355 (1997)"},{"key":"443_CR36","doi-asserted-by":"crossref","unstructured":"Pham Dinh, T., Nguyen Canh, N., Le Thi, H.A.: An efficient combined dca and b & b using dc\/sdp relaxation for globally solving binary quadratic programs. J. Glob. Optim. 48, 595\u2013632 (2010)","DOI":"10.1007\/s10898-009-9507-y"},{"key":"443_CR37","doi-asserted-by":"crossref","unstructured":"Pham\u00a0Dinh, T., Le\u00a0Thi, H.A.: Recent advances in dc programming and DCA. Trans. Comput. Intell. XIII, 8342, pp.\u00a01\u201337 (2014)","DOI":"10.1007\/978-3-642-54455-2_1"},{"key":"443_CR38","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/BF01096724","volume":"4","author":"AT Phillips","year":"1994","unstructured":"Phillips, A.T., Rosen, J.B.: A quadratic assignment formulation of the molecular conformation problem. J. Global Optim. 4, 229\u2013241 (1994)","journal-title":"J. Global Optim."},{"key":"443_CR39","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1137\/050624509","volume":"28","author":"HD Qi","year":"2006","unstructured":"Qi, H.D., Sun, D.F.: A quadratically convergent newton method for computing the nearest correlation matrix. SIAM J. Matrix Anal. Appl. 28, 360\u2013385 (2006)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"443_CR40","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1093\/imanum\/drp031","volume":"31","author":"HD Qi","year":"2011","unstructured":"Qi, H.D., Sun, D.F.: An augmented Lagrangian dual approach for the H-weighted nearest correlation matrix problem. IMA J. Numer. Anal. 31, 491\u2013511 (2011)","journal-title":"IMA J. Numer. Anal."},{"key":"443_CR41","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/s10107-008-0235-8","volume":"121","author":"F Rendl","year":"2010","unstructured":"Rendl, F., Rinaldi, G., Wiegele, A.: Solving max-cut to optimality by intersecting semidefinite and polyhedral relaxations. Math. Program. 121, 307\u2013335 (2010)","journal-title":"Math. Program."},{"key":"443_CR42","unstructured":"Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)"},{"key":"443_CR43","doi-asserted-by":"crossref","unstructured":"Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Springer, Berlin (1998)","DOI":"10.1007\/978-3-642-02431-3"},{"key":"443_CR44","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/s10559-015-9692-2","volume":"51","author":"VP Shylo","year":"2015","unstructured":"Shylo, V.P., Glover, F., Sergienko, I.V.: Teams of global equilibrium search algorithms for solving the weighted maximum cut problem in parallel. Cybern. Syst. Anal. 51, 16\u201324 (2015)","journal-title":"Cybern. Syst. Anal."},{"key":"443_CR45","doi-asserted-by":"crossref","unstructured":"Sun, D.F., Toh, K.C., Yuan, Y.C., Zhao, X.Y.: SDPNAL+: A matlab software for semidefinite programming with bound constraints (version 1.0). Optim. Methods Softw. 35,\u00a01\u201329 (2020)","DOI":"10.1080\/10556788.2019.1576176"},{"key":"443_CR46","doi-asserted-by":"publisher","first-page":"6535","DOI":"10.1109\/TIT.2016.2598574","volume":"62","author":"RY Sun","year":"2016","unstructured":"Sun, R.Y., Luo, Z.Q.: Guaranteed matrix completion via non-convex factorization. IEEE Trans. Inf. Theory 62, 6535\u20136579 (2016)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"443_CR47","doi-asserted-by":"crossref","unstructured":"Toh, K.C., Todd, M.J., Tutuncu, R.H.: SDPT3\u2013a matlab software package for semidefinite programming, version 2.1. Optim. Methods Softw. 11 (1999)","DOI":"10.1080\/10556789908805762"},{"key":"443_CR48","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/s10589-017-9954-1","volume":"69","author":"B Wen","year":"2018","unstructured":"Wen, B., Chen, X.J., Pong, T.K.: A proximal difference-of-convex algorithm with extrapolation. Comput. Optim. Appl. 69, 297\u2013324 (2018)","journal-title":"Comput. Optim. Appl."},{"key":"443_CR49","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1007\/s10107-012-0584-1","volume":"142","author":"ZW Wen","year":"2013","unstructured":"Wen, Z.W., Yin, W.T.: A feasible method for optimization with orthogonality constraints. Math. Program. 142, 397\u2013434 (2013)","journal-title":"Math. Program."},{"key":"443_CR50","doi-asserted-by":"publisher","first-page":"827","DOI":"10.1016\/j.asoc.2015.04.033","volume":"34","author":"QH Wu","year":"2015","unstructured":"Wu, Q.H., Wang, Y., L\u00fc, Z.P.: A tabu search based hybrid evolutionary algorithm for the max-cut problem. Appl. Soft Comput. 34, 827\u2013837 (2015)","journal-title":"Appl. Soft Comput."},{"key":"443_CR51","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/s12532-015-0082-6","volume":"7","author":"LQ Yang","year":"2015","unstructured":"Yang, L.Q., Sun, D.F., Toh, K.C.: SDPNAL+: a majorized semismooth newton-cg augmented Lagrangian method for semidefinite programming with nonnegative constraints. Math. Program. Comput. 7, 331\u2013366 (2015)","journal-title":"Math. Program. Comput."}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-022-00443-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-022-00443-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-022-00443-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,22]],"date-time":"2023-03-22T17:13:06Z","timestamp":1679505186000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-022-00443-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,27]]},"references-count":51,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,4]]}},"alternative-id":["443"],"URL":"https:\/\/doi.org\/10.1007\/s10589-022-00443-2","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"type":"print","value":"0926-6003"},{"type":"electronic","value":"1573-2894"}],"subject":[],"published":{"date-parts":[[2022,12,27]]},"assertion":[{"value":"6 August 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 December 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 December 2022","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 authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}