{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,16]],"date-time":"2026-02-16T20:59:43Z","timestamp":1771275583063,"version":"3.50.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,9,2]],"date-time":"2021-09-02T00:00:00Z","timestamp":1630540800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,9,2]],"date-time":"2021-09-02T00:00:00Z","timestamp":1630540800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100004085","name":"Ministry of Education, Science and Technology","doi-asserted-by":"publisher","award":["NRF 2017-R1A2B2005119"],"award-info":[{"award-number":["NRF 2017-R1A2B2005119"]}],"id":[{"id":"10.13039\/501100004085","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/japan","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["KAKENHI 20H04145"],"award-info":[{"award-number":["KAKENHI 20H04145"]}],"id":[{"id":"10.13039\/japan","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2022,2]]},"DOI":"10.1007\/s10898-021-01071-6","type":"journal-article","created":{"date-parts":[[2021,9,2]],"date-time":"2021-09-02T02:03:37Z","timestamp":1630548217000},"page":"243-262","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Exact SDP relaxations of quadratically constrained quadratic programs with forest structures"],"prefix":"10.1007","volume":"82","author":[{"given":"Godai","family":"Azuma","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mituhiro","family":"Fukuda","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sunyoung","family":"Kim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Makoto","family":"Yamashita","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,9,2]]},"reference":[{"issue":"1","key":"1071_CR1","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s10107-017-1206-8","volume":"173","author":"S Adachi","year":"2019","unstructured":"Adachi, S., Nakatsukasa, Y.: Eigenvalue-based algorithm and analysis for nonconvex qcqp with one constraint. Math. Program. 173(1), 79\u2013116 (2019)","journal-title":"Math. Program."},{"key":"1071_CR2","doi-asserted-by":"crossref","unstructured":"Anjos, M.F., Lasserre, J.B., editors. Handbook on Semidefinite, Conic and Polynomial Optimization, volume 166 of International Series in Operations Research & Management Science. Springer, New York, NY 10013, USA (2012)","DOI":"10.1007\/978-1-4614-0769-0"},{"key":"1071_CR3","unstructured":"Anton, H., Rorres, C.: Elementary Linear Algebra: Applications Version. Wiley, New York, 11th ed. (2014)"},{"issue":"1","key":"1071_CR4","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(1), 129 (2011)","journal-title":"Math. Program."},{"issue":"2","key":"1071_CR5","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1145\/1149283.1149286","volume":"2","author":"P Biswas","year":"2006","unstructured":"Biswas, P., Lian, T.-C., Wang, T.-C., Ye, Y.: Semidefinite programming based algorithms for sensor network localization. ACM Trans. Sens. Netw. 2(2), 188\u2013220 (2006)","journal-title":"ACM Trans. Sens. Netw."},{"issue":"3","key":"1071_CR6","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1109\/TCNS.2015.2401172","volume":"2","author":"S Bose","year":"2015","unstructured":"Bose, S., Gayme, D.F., Chandy, K.M., Low, S.H.: Quadratically constrained quadratic programs on acyclic graphs with application to power flow. IEEE Trans. Netw. Syst. 2(3), 278\u2013287 (2015)","journal-title":"IEEE Trans. Netw. Syst."},{"issue":"1","key":"1071_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-019-01367-2","volume":"181","author":"S Burer","year":"2020","unstructured":"Burer, S., Ye, Y.: Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs. Math. Program. 181(1), 1\u201317 (2020)","journal-title":"Math. Program."},{"issue":"2","key":"1071_CR8","first-page":"503","volume":"139","author":"M El-Mikkawy","year":"2003","unstructured":"El-Mikkawy, M.: A note on a three-term recurrence for a tridiagonal matrix. Appl. Math. Comput. 139(2), 503\u2013511 (2003)","journal-title":"Appl. Math. Comput."},{"issue":"3","key":"1071_CR9","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1137\/S1052623400366218","volume":"11","author":"M 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(3), 647\u2013674 (2001)","journal-title":"SIAM J. Optim."},{"issue":"12","key":"1071_CR10","doi-asserted-by":"publisher","first-page":"1643","DOI":"10.1002\/nme.733","volume":"57","author":"SD Garvey","year":"2003","unstructured":"Garvey, S.D., Tisseur, F., Friswell, M.I., Penny, J.E.T., Prells, U.: Simultaneous tridiagonalization of two symmetric matrices. Int. J. Numer. Meth. Eng. 57(12), 1643\u20131660 (2003)","journal-title":"Int. J. Numer. Meth. Eng."},{"issue":"3","key":"1071_CR11","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.: 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."},{"issue":"1\u20132","key":"1071_CR12","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1080\/03081089908818608","volume":"46","author":"CR Johnson","year":"1999","unstructured":"Johnson, C.R., Leal Duarte, A.: The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree. Linear Multilinear Algebra 46(1\u20132), 139\u2013144 (1999)","journal-title":"Linear Multilinear Algebra"},{"issue":"23","key":"1071_CR13","doi-asserted-by":"publisher","first-page":"3125","DOI":"10.1016\/j.disc.2005.04.025","volume":"306","author":"CR Johnson","year":"2006","unstructured":"Johnson, C.R., Leal-Duarte, A.: Converse to the parter-wiener theorem: the case of non-trees. Discret. Math. 306(23), 3125\u20133129 (2006)","journal-title":"Discret. Math."},{"key":"1071_CR14","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/S0024-3795(01)00589-4","volume":"363","author":"CR Johnson","year":"2003","unstructured":"Johnson, C.R., Leal Duarte, A., Saiago, C.M., Sutton, B.D., Witt, A.J.: On the relative position of multiple eigenvalues in the spectrum of an hermitian matrix with a given graph. Linear Algebra Appl. 363, 147\u2013159 (2003)","journal-title":"Linear Algebra Appl."},{"issue":"2","key":"1071_CR15","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(2), 143\u2013154 (2003)","journal-title":"Comput. Optim. Appl."},{"issue":"1","key":"1071_CR16","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s10107-010-0402-6","volume":"129","author":"S Kim","year":"2011","unstructured":"Kim, S., Kojima, M., Mevissen, M., Yamashita, M.: Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion. Math. Program. 129(1), 33\u201368 (2011)","journal-title":"Math. Program."},{"issue":"1","key":"1071_CR17","doi-asserted-by":"publisher","first-page":"53","DOI":"10.2307\/1907742","volume":"25","author":"TC Koopmans","year":"1957","unstructured":"Koopmans, T.C., Beckmann, M.: Assignment problems and the location of economic activities. Econometrica 25(1), 53\u201376 (1957)","journal-title":"Econometrica"},{"issue":"1","key":"1071_CR18","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/s10107-013-0648-x","volume":"145","author":"M Laurent","year":"2014","unstructured":"Laurent, M., Varvitsiotis, A.: A new graph parameter related to bounded rank positive semidefinite matrix completions. Math. Program. 145(1), 291\u2013325 (2014)","journal-title":"Math. Program."},{"issue":"1","key":"1071_CR19","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1109\/TPWRS.2011.2160974","volume":"27","author":"J Lavaei","year":"2012","unstructured":"Lavaei, J., Low, S.H.: Zero duality gap in optimal power flow problem. IEEE Trans. Power Syst. 27(1), 92\u2013107 (2012)","journal-title":"IEEE Trans. Power Syst."},{"issue":"2","key":"1071_CR20","doi-asserted-by":"publisher","first-page":"725","DOI":"10.1137\/14099379X","volume":"27","author":"R Madani","year":"2017","unstructured":"Madani, R., Sojoudi, S., Fazelnia, G., Lavaei, J.: Finding low-rank solutions of sparse linear matrix inequalities using convex optimization. SIAM J. Optim. 27(2), 725\u2013758 (2017)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"1071_CR21","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/s10107-002-0351-9","volume":"95","author":"K Nakata","year":"2003","unstructured":"Nakata, K., Fujisawa, K., Fukuda, M., Kojima, M., Murota, K.: Exploiting sparsity in semidefinite programming via matrix completion II: Implementation and numerical results. Math. Program. 95(2), 303\u2013327 (2003)","journal-title":"Math. Program."},{"key":"1071_CR22","doi-asserted-by":"crossref","unstructured":"Nesterov,Y., Wolkowicz, H., Ye,Y.: Semidefinite Programming Relaxations of Nonconvex Quadratic Optimization, volume\u00a027 of Handbook of Semidefinite Programming. International Series in Operations Research & Management Science, pp. 361\u2013419. Springer, Boston, MA (2000)","DOI":"10.1007\/978-1-4615-4381-7_13"},{"issue":"2","key":"1071_CR23","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1287\/moor.23.2.339","volume":"23","author":"G Pataki","year":"1998","unstructured":"Pataki, G.: On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues. Math. Oper. Res. 23(2), 339\u2013358 (1998)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"1071_CR24","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1137\/S003614450444614X","volume":"49","author":"I P\u00f3lik","year":"2007","unstructured":"P\u00f3lik, I., Terlaky, T.: A survey of the s-lemma. SIAM Rev. 49(3), 371\u2013418 (2007)","journal-title":"SIAM Rev."},{"issue":"3","key":"1071_CR25","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/j.disopt.2009.01.002","volume":"6","author":"J Povh","year":"2009","unstructured":"Povh, J., Rendl, F.: Copositive and semidefinite relaxations of the quadratic assignment problem. Discret. Optim. 6(3), 231\u2013241 (2009)","journal-title":"Discret. Optim."},{"key":"1071_CR26","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.dam.2019.04.032","volume":"275","author":"S Safarina","year":"2020","unstructured":"Safarina, S., Moriguchi, S., Mullin, T.J., Yamashita, M.: Conic relaxation approaches for equal deployment problems. Discret. Appl. Math. 275, 111\u2013125 (2020)","journal-title":"Discret. Appl. Math."},{"issue":"4","key":"1071_CR27","first-page":"133","volume":"62","author":"S Safarina","year":"2019","unstructured":"Safarina, S., Mullin, T.J., Yamashita, M.: Polyhedral-based methods for mixed-integer socp in tree breeding. J. Oper. Res. Soc. Jpn 62(4), 133\u2013151 (2019)","journal-title":"J. Oper. Res. Soc. Jpn"},{"key":"1071_CR28","doi-asserted-by":"publisher","unstructured":"Sheen, H., Yamashita, M.: Exploiting aggregate sparsity in second order cone relaxations for quadratic constrained quadratic programming problems. To appear in Optim. Methods Softw., https:\/\/doi.org\/10.1080\/10556788.2020.1827256","DOI":"10.1080\/10556788.2020.1827256"},{"issue":"3","key":"1071_CR29","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1007\/s00211-010-0357-9","volume":"118","author":"RB Sidje","year":"2011","unstructured":"Sidje, R.B.: On the simultaneous tridiagonalization of two symmetric matrices. Numer. Math. 118(3), 549\u2013566 (2011)","journal-title":"Numer. Math."},{"issue":"4","key":"1071_CR30","doi-asserted-by":"publisher","first-page":"1746","DOI":"10.1137\/130915261","volume":"24","author":"S Sojoudi","year":"2014","unstructured":"Sojoudi, S., Lavaei, J.: Exactness of semidefinite relaxations for nonlinear optimization problems with underlying graph structure. SIAM J. Optim. 24(4), 1746\u20131778 (2014)","journal-title":"SIAM J. Optim."},{"key":"1071_CR31","doi-asserted-by":"publisher","unstructured":"Wang, A.L., K\u0131l\u0131nc\u0327-Karzan, F.: The generalized trust region subproblem: solution complexity and convex hull results. Math. Program. (2020). https:\/\/doi.org\/10.1007\/s10107-020-01560-8","DOI":"10.1007\/s10107-020-01560-8"},{"key":"1071_CR32","doi-asserted-by":"crossref","unstructured":"Wang, A.L., K\u0131l\u0131nc\u0327-Karzan, F.: On the tightness of sdp relaxations of qcqps. To appear in Math. Program. (2021)","DOI":"10.1007\/s10107-020-01589-9"},{"key":"1071_CR33","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-4381-7","volume-title":"Handbook of Semidefinite Programming: Theory, Algorithms, and Applications","author":"H Wolkowicz","year":"2000","unstructured":"Wolkowicz, H., Saigal, R., Vandenberghe, L.: Handbook of Semidefinite Programming: Theory, Algorithms, and Applications. Springer, New York (2000)"},{"issue":"3","key":"1071_CR34","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(3), 331\u2013366 (2015)","journal-title":"Math. Program. Comput."},{"key":"1071_CR35","doi-asserted-by":"crossref","unstructured":"Zhou, F., Chen,Y., Low, S.H.: Sufficient conditions for exact semidefinite relaxation of optimal power flow in unbalanced multiphase radial networks. In: IEEE 58th Conference on Decision and Control (CDC), vol. 58, pp. 6227\u20136233 (2019)","DOI":"10.1109\/CDC40024.2019.9029827"}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-021-01071-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-021-01071-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-021-01071-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,2]],"date-time":"2022-02-02T17:07:51Z","timestamp":1643821671000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-021-01071-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,2]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["1071"],"URL":"https:\/\/doi.org\/10.1007\/s10898-021-01071-6","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,2]]},"assertion":[{"value":"5 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 August 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 September 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}