{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T17:42:15Z","timestamp":1769017335308,"version":"3.49.0"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T00:00:00Z","timestamp":1683936000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T00:00:00Z","timestamp":1683936000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Karlsruher Institut f\u00fcr Technologie (KIT)"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2023,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Recently, Bomze et\u00a0al. introduced a sparse conic relaxation of the scenario problem of a two stage stochastic version of the standard quadratic optimization problem. When compared numerically to Burer\u2019s classical reformulation, the authors showed that there seems to be almost no difference in terms of solution quality, whereas the solution time can differ by orders of magnitudes. While the authors did find a very limited special case, for which Burer\u2019s reformulation and their relaxation are equivalent, no satisfying explanation for the high quality of their bound was given. This article aims at shedding more light on this phenomenon and give a more thorough theoretical account of its inner workings. We argue that the quality of the outer approximation cannot be explained by traditional results on sparse conic relaxations based on positive semidenifnite or completely positive matrix completion, which require certain sparsity patterns characterized by chordal and block clique graphs respectively, and put certain restrictions on the type of conic constraint they seek to sparsify. In an effort to develop an alternative approach, we will provide a new type of convex reformulation of a large class of stochastic quadratically constrained quadratic optimization problems that is similar to Burer\u2019s reformulation, but lifts the variables into a comparatively lower dimensional space. The reformulation rests on a generalization of the set-completely positive matrix cone. This cone can then be approximated via inner and outer approximations in order to obtain upper and lower bounds, which potentially close the optimality gap, and hence can give a certificate of exactness for these sparse reformulations outside of traditional, known sufficient conditions. Finally, we provide some numerical experiments, where we asses the quality of the inner and outer approximations, thereby showing that the approximations may indeed close the optimality gap in interesting cases.<\/jats:p>","DOI":"10.1007\/s10898-023-01283-y","type":"journal-article","created":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T08:02:21Z","timestamp":1683964941000},"page":"221-254","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Sparse conic reformulation of structured QCQPs based on copositive optimization with applications in stochastic optimization"],"prefix":"10.1007","volume":"87","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9598-0106","authenticated-orcid":false,"given":"Markus","family":"Gabl","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,5,13]]},"reference":[{"key":"1283_CR1","doi-asserted-by":"publisher","DOI":"10.1142\/5273","volume-title":"Completely Positive Matrices","author":"A Berman","year":"2003","unstructured":"Berman, A., Shaked-Monderer, N.: Completely Positive Matrices. World Scientific, Singapore (2003)"},{"key":"1283_CR2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2022.105735","volume":"142","author":"E Bettiol","year":"2022","unstructured":"Bettiol, E., Bomze, I., L\u00e9tocart, L., Rinaldi, F., Traversi, E.: Mining for diamonds-Matrix generation algorithms for binary quadratically constrained quadratic problems. Comput. Oper. Res. 142, 105735 (2022)","journal-title":"Comput. Oper. Res."},{"issue":"1","key":"1283_CR3","first-page":"2","volume":"89","author":"I Bomze","year":"2012","unstructured":"Bomze, I., D\u00fcr, M., Teo, C.-P.: Copositive optimization. Optima Newsl. Math. Optim. Soc. 89(1), 2\u20138 (2012)","journal-title":"Optima Newsl. Math. Optim. Soc."},{"key":"1283_CR4","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s00186-020-00726-6","volume":"93","author":"I Bomze","year":"2021","unstructured":"Bomze, I., Gabl, M.: Interplay of non-convex quadratically constrained problems with adjustable robust optimization. Math. Methods Oper. Res. 93, 115\u2013151 (2021)","journal-title":"Math. Methods Oper. Res."},{"issue":"1","key":"1283_CR5","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/j.ejor.2021.10.056","volume":"299","author":"IM Bomze","year":"2022","unstructured":"Bomze, I.M., Gabl, M., Maggioni, F., Pflug, G.C.: Two-stage stochastic standard quadratic optimization. Eur. J. Oper. Res. 299(1), 21\u201334 (2022)","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"1283_CR6","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 nonconvex quadratic programs. Math. Program. 120(2), 479\u2013495 (2009)","journal-title":"Math. Program."},{"key":"1283_CR7","doi-asserted-by":"crossref","unstructured":"Burer, S.: Copositive programming. In: Handbook on Semidefinite, Conic and Polynomial Optimization, pp. 201\u2013218. Springer (2012)","DOI":"10.1007\/978-1-4614-0769-0_8"},{"issue":"1","key":"1283_CR8","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 Algebra 44(1), 85\u201392 (1998)","journal-title":"Linear Multilinear Algebra"},{"issue":"6","key":"1283_CR9","doi-asserted-by":"publisher","first-page":"1373","DOI":"10.1007\/s11590-012-0450-3","volume":"7","author":"G Eichfelder","year":"2013","unstructured":"Eichfelder, G., Povh, J.: On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets. Optim. Lett. 7(6), 1373\u20131386 (2013)","journal-title":"Optim. Lett."},{"key":"1283_CR10","unstructured":"Fan, L., Aghamolki, H. G., Miao, Z., Zeng, B.: Achieving SDP tightness through SOCP relaxation with cycle-based SDP feasibility constraints for AC OPF. arXiv preprint arXiv:1804.05128, (2018)"},{"issue":"3","key":"1283_CR11","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."},{"key":"1283_CR12","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1007\/s10898-020-00879-y","volume":"77","author":"S Kim","year":"2020","unstructured":"Kim, S., Kojima, M., Toh, K.-C.: Doubly nonnegative relaxations are equivalent to completely positive reformulations of quadratic optimization problems with block-clique graph structures. J. Glob. Optim. 77, 513\u2013541 (2020)","journal-title":"J. Glob. Optim."},{"issue":"2","key":"1283_CR13","doi-asserted-by":"publisher","first-page":"1251","DOI":"10.1137\/19M1237715","volume":"30","author":"S Kim","year":"2020","unstructured":"Kim, S., Kojima, M., Toh, K.-C.: A geometrical analysis on convex conic reformulations of quadratic and polynomial optimization problems. SIAM J. Optim. 30(2), 1251\u20131273 (2020)","journal-title":"SIAM J. Optim."},{"key":"1283_CR14","unstructured":"L\u00f6fberg, J.: Yalmip: a toolbox for modeling and optimization in matlab. In: Proceedings of the CACSD Conference, Taipei, Taiwan (2004)"},{"issue":"1","key":"1283_CR15","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/s10107-016-1019-1","volume":"161","author":"K Natarajan","year":"2017","unstructured":"Natarajan, K., Teo, C.-P.: On reduced semidefinite programs for second order moment bounds with applications. Math. Programm. 161(1), 487\u2013518 (2017)","journal-title":"Math. Programm."},{"issue":"1","key":"1283_CR16","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/s10107-019-01453-5","volume":"186","author":"D Padmanabhan","year":"2021","unstructured":"Padmanabhan, D., Natarajan, K., Murthy, K.: Exploiting partial correlations in distributionally robust optimization. Math. Program. 186(1), 209\u2013255 (2021)","journal-title":"Math. Program."},{"key":"1283_CR17","volume-title":"Convex Analysis","author":"RT Rockafellar","year":"2015","unstructured":"Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (2015)"},{"key":"1283_CR18","unstructured":"Sliwak, J., Anjos, M., L\u00e9tocart, L., Maeght, J., Traversi, E.: Improving clique decompositions of semidefinite relaxations for optimal power flow problems. arXiv preprint arXiv:1912.09232, (2019)"},{"issue":"4","key":"1283_CR19","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1561\/2400000006","volume":"1","author":"L Vandenberghe","year":"2015","unstructured":"Vandenberghe, L., Andersen, M.S.: Chordal graphs and semidefinite optimization. Found. Trends Optim. 1(4), 241\u2013433 (2015)","journal-title":"Found. Trends Optim."},{"issue":"1","key":"1283_CR20","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/s10107-019-01366-3","volume":"180","author":"Y Zheng","year":"2020","unstructured":"Zheng, Y., Fantuzzi, G., Papachristodoulou, A., Goulart, P., Wynn, A.: Chordal decomposition in operator-splitting methods for sparse semidefinite programs. Math. Program. 180(1), 489\u2013532 (2020)","journal-title":"Math. Program."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-023-01283-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-023-01283-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-023-01283-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,29]],"date-time":"2023-07-29T06:07:08Z","timestamp":1690610828000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-023-01283-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,13]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["1283"],"URL":"https:\/\/doi.org\/10.1007\/s10898-023-01283-y","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,13]]},"assertion":[{"value":"9 May 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 April 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 May 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}