{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:29Z","timestamp":1740109289783,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,11,21]],"date-time":"2020-11-21T00:00:00Z","timestamp":1605916800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,11,21]],"date-time":"2020-11-21T00:00:00Z","timestamp":1605916800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["2014-R1A2A1A11049618","2017-R1A2B2005119"],"award-info":[{"award-number":["2014-R1A2A1A11049618","2017-R1A2B2005119"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","award":["R-146-000-257-112"],"award-info":[{"award-number":["R-146-000-257-112"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,6]]},"DOI":"10.1007\/s10107-020-01594-y","type":"journal-article","created":{"date-parts":[[2020,11,21]],"date-time":"2020-11-21T16:02:36Z","timestamp":1605974556000},"page":"761-787","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Doubly nonnegative relaxations for quadratic and polynomial optimization problems with binary and box constraints"],"prefix":"10.1007","volume":"193","author":[{"given":"Sunyoung","family":"Kim","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Masakazu","family":"Kojima","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7204-8933","authenticated-orcid":false,"given":"Kim-Chuan","family":"Toh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,11,21]]},"reference":[{"issue":"4","key":"1594_CR1","doi-asserted-by":"publisher","first-page":"2320","DOI":"10.1137\/120890636","volume":"23","author":"N Arima","year":"2013","unstructured":"Arima, N., Kim, S., Kojima, M.: A quadratically constrained quadratic optimization model for completely positive cone programming. SIAM J. Optim. 23(4), 2320\u20132340 (2013)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1594_CR2","first-page":"161","volume":"14","author":"N Arima","year":"2018","unstructured":"Arima, N., Kim, S., Kojima, M., Toh, K.C.: Lagrangian-conic relaxations, part I: a unified framework and its applications to quadratic optimization problems. Pac. J. Optim. 14(1), 161\u2013192 (2018)","journal-title":"Pac. J. Optim."},{"issue":"3","key":"1594_CR3","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/s10589-016-9879-0","volume":"66","author":"N Arima","year":"2017","unstructured":"Arima, N., Kim, S., Kojima, M., Toh, K.C.: A robust Lagrangian-DNN method for a class of quadratic optimization problems. Comput. Optim. Appl. 66(3), 453\u2013479 (2017)","journal-title":"Comput. Optim. Appl."},{"key":"1594_CR4","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1137\/080716542","volume":"2","author":"A Beck","year":"2009","unstructured":"Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2, 183\u2013202 (2009)","journal-title":"SIAM J. Imaging Sci."},{"key":"1594_CR5","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1007\/BF01580873","volume":"47","author":"MJ Best","year":"1990","unstructured":"Best, M.J., Chakravarti, N.: Active set algorithms for isotonic regression; a unifying framework active set algorithms for isotonic regression; a unifying framework. Math. Prog. 47, 425\u2013439 (1990)","journal-title":"Math. Prog."},{"key":"1594_CR6","volume-title":"Graph Theory and Sparse Matrix Computation","author":"JRS Blair","year":"1993","unstructured":"Blair, J.R.S., Peyton, B.: An introduction to chordal graphs and clique trees. In: Liu, J.W.H., George, A., Gilbert, J.R. (eds.) Graph Theory and Sparse Matrix Computation. Springer-Verlag, New York (1993)"},{"key":"1594_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s12532-010-0010-8","volume":"2","author":"S Burer","year":"2010","unstructured":"Burer, S.: Optimizing a polyhedral-semidefinite relaxation of completely positive programs. Math. Program. Comput. 2, 1\u201319 (2010)","journal-title":"Math. Program. Comput."},{"key":"1594_CR8","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/s10107-011-0485-8","volume":"137","author":"H Dong","year":"2013","unstructured":"Dong, H., Anstreicher, K.: Separating doubly nonnegative and completely positive matrices. Math. Program. 137, 131\u2013153 (2013)","journal-title":"Math. Program."},{"issue":"3","key":"1594_CR9","doi-asserted-by":"publisher","first-page":"391","DOI":"10.4208\/jcm.1708-m2017-0130","volume":"36","author":"T Fu","year":"2018","unstructured":"Fu, T., Ge, D., Ye, Y.: On doubly positive semidefinite programming relaxations. J. Comput. Math. 36(3), 391\u2013403 (2018)","journal-title":"J. Comput. Math."},{"key":"1594_CR10","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1137\/S1052623400366218","volume":"11","author":"M Fukuda","year":"2000","unstructured":"Fukuda, M., Kojima, M., Murota, K., Nakata, K.: Exploiting sparsity in semidefinite programming via matrix completion. I: general framework. SIAM J. Optim. 11, 647\u2013674 (2000)","journal-title":"SIAM J. Optim."},{"key":"1594_CR11","unstructured":"Hahn, P., Anjos, M.: QAPLIB\u2014a quadratic assignment problem library. http:\/\/www.seas.upenn.edu\/qaplib"},{"key":"1594_CR12","unstructured":"Ito, N.: Applications of accelerated proximal gradient methods to binary classification and polynomial optimization. Ph.D. thesis, The University of Tokyo (2018)"},{"key":"1594_CR13","doi-asserted-by":"crossref","unstructured":"Ito, N., Kim, S., Kojima, M., Takeda, A., Toh, K.C.: BBCPOP: a sparse doubly nonnegative relaxation of polynomial optimization problems with binary, box and complementarity constraints. ACM Trans. Math. Softw. 45, Article 34 (2019)","DOI":"10.1145\/3309988"},{"key":"1594_CR14","unstructured":"Kim, S., Kojima, M., Toh, K.C.: Doubly nonnegative relaxations for quadratic and polynomial optimization problems with binary and box constraints. Research Rport B-483, Tokyo Institute of Technology, Department of Mathematical and Computing Sciences, Oh-Okayama, Meguro-ku, Tokyo 152-8552, July 2016"},{"key":"1594_CR15","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s10107-015-0874-5","volume":"156","author":"S Kim","year":"2016","unstructured":"Kim, S., 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":"1594_CR16","doi-asserted-by":"crossref","unstructured":"Lasserre, J.B.: An explicit exact SDP relaxation for nonlinear 0-1 programs. In: Integer Programming and Combinatorial Optimization, pp. 293\u2013303. Springer (2001)","DOI":"10.1007\/3-540-45535-3_23"},{"key":"1594_CR17","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 problems of moments. SIAM J. Optim. 11, 796\u2013817 (2001)","journal-title":"SIAM J. Optim."},{"issue":"1\u20132","key":"1594_CR18","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/s13675-015-0050-y","volume":"5","author":"JB Lasserre","year":"2017","unstructured":"Lasserre, J.B., Toh, K.C., Yang, S.: A bounded degree SOS hierarchy for polynomial optimization. EURO J. Comput. Optim. 5(1\u20132), 87\u2013117 (2017)","journal-title":"EURO J. Comput. Optim."},{"key":"1594_CR19","first-page":"157","volume-title":"Emerging Applications of Algebraic Geometry. The IMA Volumes in Mathematics and Its Applications","author":"M Laurent","year":"2008","unstructured":"Laurent, M.: Sums of squares, moment matrices and optimization over polynomials sums of squares, moment matrices and optimization over polynomials. In: Putinar, M., Sullivant, S. (eds.) Emerging Applications of Algebraic Geometry. The IMA Volumes in Mathematics and Its Applications, vol. 149, pp. 157\u2013270. Springer, New York, NY (2008)"},{"key":"1594_CR20","first-page":"238","volume":"255","author":"JJ Moreau","year":"1962","unstructured":"Moreau, J.J.: D\u00e9composition orthogonale d\u2019un espace hilbertien selon deux cones mutuellement polaires. C. R. Acad. Sci. 255, 238\u2013240 (1962)","journal-title":"C. R. Acad. Sci."},{"issue":"2","key":"1594_CR21","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1137\/110825844","volume":"22","author":"J Nie","year":"2012","unstructured":"Nie, J., Wang, L.: Regularization methods for SDP relaxations in large scale polynomial optimization. SIAM J. Optim. 22(2), 408\u2013428 (2012)","journal-title":"SIAM J. Optim."},{"key":"1594_CR22","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/PL00009258","volume":"23","author":"PM Pardalos","year":"1999","unstructured":"Pardalos, P.M., Xue, G.: Algorithms for a class of isotonic regression problems. Algorithmica 23, 211\u2013222 (1999)","journal-title":"Algorithmica"},{"key":"1594_CR23","unstructured":"Sloane, N.: Challenge problems: independent sets in graphs"},{"key":"1594_CR24","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1137\/050623802","volume":"17","author":"H Waki","year":"2006","unstructured":"Waki, H., Kim, S., Kojima, M., Muramatsu, M.: Sums of squares and semidefinite programming relaxations for polynomial optimization problems with structured sparsity. SIAM J. Optim. 17, 218\u2013242 (2006)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1594_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s12532-017-0121-6","volume":"10","author":"T Weisser","year":"2018","unstructured":"Weisser, T., Lasserre, J.B., Toh, K.C.: Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity. Math. Program. Comput. 10(1), 1\u201332 (2018)","journal-title":"Math. Program. Comput."},{"key":"1594_CR26","unstructured":"Wiegele, A.: Biq Mac library. http:\/\/www.biqmac.uni-klu.ac.at\/biqmaclib.html (2007)"},{"key":"1594_CR27","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."},{"key":"1594_CR28","doi-asserted-by":"crossref","unstructured":"Yoshise, A., Matsukawa, Y.: On optimization over the doubly nonnegative cone. In: IEEE Multi-conference on Systems and Control (2010)","DOI":"10.1109\/CACSD.2010.5612811"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01594-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01594-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01594-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T14:29:01Z","timestamp":1654871341000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01594-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,21]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["1594"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01594-y","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2020,11,21]]},"assertion":[{"value":"13 March 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 November 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 November 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}