{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T13:06:41Z","timestamp":1780924001118,"version":"3.54.1"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,1,30]],"date-time":"2020-01-30T00:00:00Z","timestamp":1580342400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,30]],"date-time":"2020-01-30T00:00:00Z","timestamp":1580342400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001866","name":"National Research Fund","doi-asserted-by":"crossref","award":["2017-R1A2B2005119"],"award-info":[{"award-number":["2017-R1A2B2005119"]}],"id":[{"id":"10.13039\/501100001866","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Grant-in-Aid for Scientific Research","award":["(A) 26242027"],"award-info":[{"award-number":["(A) 26242027"]}]},{"name":"The Ministry of Education, Singapore, Academic Research Fund","award":["R-146-000-257-112"],"award-info":[{"award-number":["R-146-000-257-112"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2020,7]]},"DOI":"10.1007\/s10898-020-00879-y","type":"journal-article","created":{"date-parts":[[2020,1,30]],"date-time":"2020-01-30T06:03:28Z","timestamp":1580364208000},"page":"513-541","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Doubly nonnegative relaxations are equivalent to completely positive reformulations of quadratic optimization problems with block-clique graph structures"],"prefix":"10.1007","volume":"77","author":[{"given":"Sunyoung","family":"Kim","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Masakazu","family":"Kojima","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kim-Chuan","family":"Toh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,1,30]]},"reference":[{"key":"879_CR1","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0024-3795(88)90240-6","volume":"107","author":"J Agler","year":"1988","unstructured":"Agler, J., Helton, J\u00a0.W., McCullough, S., Rodman, L.: Positive semidefinite matrices with a given sparsity pattern. Linear Algebr. Appl. 107, 101\u2013149 (1988)","journal-title":"Linear Algebr. Appl."},{"key":"879_CR2","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, 2320\u20132340 (2013)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"879_CR3","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. of Optim. 14(1), 161\u2013192 (2018)","journal-title":"Pac. J. of Optim."},{"key":"879_CR4","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, 453\u2013479 (2017)","journal-title":"Comput. Optim. Appl."},{"key":"879_CR5","doi-asserted-by":"publisher","DOI":"10.1142\/5273","volume-title":"Compoletely Positive Matrices","author":"A Berman","year":"2003","unstructured":"Berman, A., Shaked-Monderer, N.: Compoletely Positive Matrices. World Scientific, Singapore (2003)"},{"key":"879_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, New York (1993)"},{"key":"879_CR7","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/s10107-017-1109-8","volume":"166","author":"IM Bomze","year":"2017","unstructured":"Bomze, I.M., Cheng, J., Dickinson, P.J.C., Lisser, A.: A fresh CP look at mixed-binary QPs: new formulations and relaxations. Math. Program. 166, 159\u2013184 (2017)","journal-title":"Math. Program."},{"key":"879_CR8","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1007\/s10107-008-0223-z","volume":"120","author":"S Burer","year":"2009","unstructured":"Burer, S.: On the copositive representation of binary and continuous non-convex quadratic programs. Math. Program. 120, 479\u2013495 (2009)","journal-title":"Math. Program."},{"key":"879_CR9","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1080\/03081089808818550","volume":"44","author":"JH Drew","year":"1998","unstructured":"Drew, J.H., Johnson, C.R.: The completely positive and doubly nonnegative completion problems. Linear Multilinear Algebr. 44, 85\u201392 (1998)","journal-title":"Linear Multilinear Algebr."},{"key":"879_CR10","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1023\/A:1008282830093","volume":"10","author":"T Fujie","year":"1997","unstructured":"Fujie, T., Kojima, M.: Semidefinite programming relaxation for nonconvex quadratic programs. J. Global Optim. 10, 367\u2013368 (1997)","journal-title":"J. Global Optim."},{"key":"879_CR11","unstructured":"Fujisawa, K., Kim, S., Kojima, M., Okamoto, Y., Yamashita, M.: User\u2019s Manual for SparseCoLO: Conversion Methods for SPARSE Conic-form Linear Optimization Problems. Technical Report B-453. Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, Tokyo 152-8852 (2009)"},{"issue":"3","key":"879_CR12","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1137\/S1052623400366218","volume":"11","author":"Mituhiro Fukuda","year":"2001","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 Journal on Optimization"},{"key":"879_CR13","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0024-3795(84)90207-6","volume":"58","author":"R Gron","year":"1984","unstructured":"Gron, R., Johnson, C.R., S\u00e1, E.M., Wolkowicz, H.: Positive definite completions of partial Hermitian matrices. Linear Algebr. Appl. 58, 109\u2013124 (1984)","journal-title":"Linear Algebr. Appl."},{"issue":"3","key":"879_CR14","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1145\/3309988","volume":"45","author":"N Ito","year":"2019","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(3), 34 (2019)","journal-title":"ACM Trans. Math. Softw."},{"key":"879_CR15","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1016\/0024-3795(95)00429-7","volume":"241\u2013243","author":"CR Johnson","year":"1996","unstructured":"Johnson, C.R., Smith, R.I.: The completion problem for M-matrices and inverse M-matrices. Linear Algebr. Appl. 241\u2013243, 655\u2013667 (1996)","journal-title":"Linear Algebr. Appl."},{"key":"879_CR16","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1023\/A:1025794313696","volume":"26","author":"S Kim","year":"2003","unstructured":"Kim, S., Kojima, M.: Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxations. Comput. Optim. Appl. 26, 143\u2013154 (2003)","journal-title":"Comput. Optim. Appl."},{"key":"879_CR17","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":"879_CR18","unstructured":"Kim, S., Kojima, M., Toh, K.C.: A geometrical analysis of a class of nonconvex conic programsfor convex conic reformulations of quadratic and polynomial optimization problems. SIAM J. Optim. (to appear)"},{"key":"879_CR19","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/s00245-007-9030-9","volume":"58","author":"M Kobayashi","year":"2008","unstructured":"Kobayashi, M., Kim, S., Kojima, M.: Correlative sparsity in primal-dual interior-point methods for LP, SDP, and SOCP. Appl. Math. Optim. 58, 69\u201388 (2008)","journal-title":"Appl. Math. Optim."},{"key":"879_CR20","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1109\/TCNS.2014.2309732","volume":"1","author":"SH Low","year":"2014","unstructured":"Low, S.H.: Convex relaxation of optimal power flow\u2014part I: formulations and equivalence. IEEE Control Netw. Syst. 1, 15\u201327 (2014)","journal-title":"IEEE Control Netw. Syst."},{"key":"879_CR21","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1080\/10556789908805762","volume":"11","author":"KC Toh","year":"1999","unstructured":"Toh, K.C., Todd, M.J., Tutuncu, R.H.: SDPT3\u2014a Matlab software package for semidefinite programming. Optim. Methods Softw. 11, 545\u2013581 (1999)","journal-title":"Optim. Methods Softw."},{"key":"879_CR22","series-title":"Foundations and Trend in Optimization","volume-title":"Chordal Graphs and Semidefinite Optimization","author":"L Vandenbergh","year":"2014","unstructured":"Vandenbergh, L., Andersen, M.S.: Chordal Graphs and Semidefinite Optimization. Foundations and Trend in Optimization, vol. 1. Now Publishers Inc., Hanover (2014)"},{"key":"879_CR23","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."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-020-00879-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10898-020-00879-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-020-00879-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,29]],"date-time":"2021-01-29T00:28:39Z","timestamp":1611880119000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10898-020-00879-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,30]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["879"],"URL":"https:\/\/doi.org\/10.1007\/s10898-020-00879-y","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1,30]]},"assertion":[{"value":"18 March 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 January 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 January 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}