{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T06:03:10Z","timestamp":1774332190247,"version":"3.50.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,7,29]],"date-time":"2021-07-29T00:00:00Z","timestamp":1627516800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,7,29]],"date-time":"2021-07-29T00:00:00Z","timestamp":1627516800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2022,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study convex relaxations of nonconvex quadratic programs. We identify a family of so-called feasibility preserving convex relaxations, which includes the well-known copositive and doubly nonnegative relaxations, with the property that the convex relaxation is feasible if and only if the nonconvex quadratic program is feasible. We observe that each convex relaxation in this family implicitly induces a convex underestimator of the objective function on the feasible region of the quadratic program. This alternative perspective on convex relaxations enables us to establish several useful properties of the corresponding convex underestimators. In particular, if the recession cone of the feasible region of the quadratic program does not contain any directions of negative curvature, we show that the convex underestimator arising from the copositive relaxation is precisely the convex envelope of the objective function of the quadratic program, strengthening Burer\u2019s well-known result on the exactness of the copositive relaxation in the case of nonconvex quadratic programs. We also present an algorithmic recipe for constructing instances of quadratic programs with a finite optimal value but an unbounded relaxation for a rather large family of convex relaxations including the doubly nonnegative relaxation.<\/jats:p>","DOI":"10.1007\/s10898-021-01066-3","type":"journal-article","created":{"date-parts":[[2021,7,29]],"date-time":"2021-07-29T03:25:39Z","timestamp":1627529139000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["An alternative perspective on copositive and convex relaxations of nonconvex quadratic programs"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4141-3189","authenticated-orcid":false,"given":"E. Alper","family":"Y\u0131ld\u0131r\u0131m","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,7,29]]},"reference":[{"issue":"2","key":"1066_CR1","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s10107-012-0602-3","volume":"136","author":"KM Anstreicher","year":"2012","unstructured":"Anstreicher, K.M.: On convex relaxations for quadratically constrained quadratic programming. Math. Program. 136(2), 233\u2013251 (2012). DOI: 10.1007\/s10107-012-0602-3","journal-title":"Math. Program."},{"issue":"4","key":"1066_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(4), 2320\u20132340 (2013). https:\/\/doi.org\/10.1137\/120890636","journal-title":"SIAM J. Optim."},{"issue":"3","key":"1066_CR3","doi-asserted-by":"publisher","first-page":"884","DOI":"10.1007\/s10957-015-0794-9","volume":"168","author":"N Arima","year":"2016","unstructured":"Arima, N., Kim, S., Kojima, M.: Extension of completely positive cone relaxation to moment cone relaxation for polynomial optimization. J. Optim. Theory Appl. 168(3), 884\u2013900 (2016). DOI: 10.1007\/s10957-015-0794-9","journal-title":"J. Optim. Theory Appl."},{"issue":"1\u20132","key":"1066_CR4","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/s10107-015-0951-9","volume":"159","author":"L Bai","year":"2016","unstructured":"Bai, L., Mitchell, J.E., Pang, J.: On conic QPCCs, conic QCQPs and completely positive programs. Math. Program. 159(1\u20132), 109\u2013136 (2016). DOI: 10.1007\/s10107-015-0951-9","journal-title":"Math. Program."},{"key":"1066_CR5","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)"},{"issue":"1\u20132","key":"1066_CR6","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(1\u20132), 159\u2013184 (2017). DOI: 10.1007\/s10107-017-1109-8","journal-title":"Math. Program."},{"issue":"1","key":"1066_CR7","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1137\/070711815","volume":"20","author":"S Bundfuss","year":"2009","unstructured":"Bundfuss, S., D\u00fcr, M.: An adaptive linear approximation algorithm for copositive programs. SIAM Journal on Optimization 20(1), 30\u201353 (2009)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"1066_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 nonconvex quadratic programs. Math. Program. 120(2), 479\u2013495 (2009). DOI: 10.1007\/s10107-008-0223-z","journal-title":"Math. Program."},{"key":"1066_CR9","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":"9","key":"1066_CR10","doi-asserted-by":"publisher","first-page":"1539","DOI":"10.1016\/j.laa.2009.05.021","volume":"431","author":"S Burer","year":"2009","unstructured":"Burer, S., Anstreicher, K.M., D\u00fcr, M.: The difference between 5$$\\times $$ 5 doubly nonnegative and completely positive matrices. Linear Algebra and its Applications 431(9), 1539\u20131552 (2009)","journal-title":"Linear Algebra Appl."},{"issue":"3","key":"1066_CR11","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/j.orl.2012.02.001","volume":"40","author":"S Burer","year":"2012","unstructured":"Burer, S., Dong, H.: Representing quadratically constrained quadratic programs as generalized copositive programs. Oper. Res. Lett. 40(3), 203\u2013206 (2012). DOI: 10.1016\/j.orl.2012.02.001","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"1066_CR12","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1137\/S1052623401383248","volume":"12","author":"E De Klerk","year":"2002","unstructured":"De Klerk, E., Pasechnik, D.V.: Approximation of the stability number of a graph via copositive programming. SIAM Journal on Optimization 12(4), 875\u2013892 (2002)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1066_CR13","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1017\/S0305004100036185","volume":"58","author":"PH Diananda","year":"1962","unstructured":"Diananda, P.H.: On non-negative forms in real variables some or all of which are non-negative. Mathematical Proceedings of the Cambridge Philosophical Society 58(1), 17\u201325 (1962). DOI: https:\/\/doi.org\/10.1017\/S0305004100036185","journal-title":"Math. Proc. Cambr. Philos. Soc."},{"issue":"6","key":"1066_CR14","doi-asserted-by":"publisher","first-page":"1387","DOI":"10.1007\/s11590-013-0645-2","volume":"7","author":"PJC Dickinson","year":"2013","unstructured":"Dickinson, P.J.C., Eichfelder, G., Povh, J.: Erratum to: On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets. Optimization Letters 7(6), 1387\u20131397 (2013). DOI: https:\/\/doi.org\/10.1007\/s11590-013-0645-2","journal-title":"Optim. Lett."},{"issue":"11","key":"1066_CR15","doi-asserted-by":"publisher","first-page":"698","DOI":"10.1287\/mnsc.17.11.698","volume":"17","author":"BC Eaves","year":"1971","unstructured":"Eaves, B.C.: On quadratic programming. Management Science 17(11), 698\u2013711 (1971). DOI: https:\/\/doi.org\/10.1287\/mnsc.17.11.698","journal-title":"Manag. Sci."},{"issue":"6","key":"1066_CR16","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. Optimization Letters 7(6), 1373\u20131386 (2013). DOI: https:\/\/doi.org\/10.1007\/s11590-012-0450-3","journal-title":"Optim. Lett."},{"issue":"1\u20132","key":"1066_CR17","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1002\/nav.3800030109","volume":"3","author":"M Frank","year":"1956","unstructured":"Frank, M., Wolfe, P.: An algorithm for quadratic programming. Naval Research Logistics Quarterly 3(1\u20132), 95\u2013110 (1956). https:\/\/doi.org\/10.1002\/nav.3800030109","journal-title":"Naval Res. Logist. Quart."},{"key":"1066_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-020-01611-0","author":"YG G\u00f6kmen","year":"2021","unstructured":"G\u00f6kmen, Y.G., Y\u0131ld\u0131r\u0131m, E.A.: On standard quadratic programs with exact and inexact doubly nonnegative relaxations. Mathematical Programming (2021). https:\/\/doi.org\/10.1007\/s10107-020-01611-0","journal-title":"Math. Program."},{"key":"1066_CR19","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/s10898-019-00861-3","volume":"76","author":"J Gouveia","year":"2020","unstructured":"Gouveia, J., Pong, T.K., Saee, M.: Inner approximating the completely positive cone via the cone of scaled diagonally dominant matrices. Journal of Global Optimization 76, 383\u2013405 (2020)","journal-title":"J. Global Optim."},{"issue":"2","key":"1066_CR20","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1017\/S0305004100036951","volume":"59","author":"M Hall","year":"1963","unstructured":"Hall, M., Newman, M.: Copositive and completely positive quadratic forms. Mathematical Proceedings of the Cambridge Philosophical Society 59(2), 329\u2013339 (1963)","journal-title":"Math. Proc. Cambr. Philos. Soc."},{"issue":"5","key":"1066_CR21","first-page":"625","volume":"3","author":"L Jiaquan","year":"1982","unstructured":"Jiaquan, L., Tiantai, S., Dingzhu, D.: On the necessary and sufficient condition of the local optimal solution of quadratic programming. Chinese Annals of Mathematics, Series B 3(5), 625\u2013630 (1982)","journal-title":"Chinese Ann. Math., Series B"},{"issue":"1\u20132","key":"1066_CR22","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.: A Lagrangian-DNN relaxation: A fast method for computing tight lower bounds for a class of quadratic optimization problems. Math. Program. 156(1\u20132), 161\u2013187 (2016). DOI: https:\/\/doi.org\/10.1007\/s10107-015-0874-5","journal-title":"Math. Program."},{"issue":"3","key":"1066_CR23","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. Journal of Global Optimization 77(3), 513\u2013541 (2020)","journal-title":"J. Global Optim."},{"issue":"2","key":"1066_CR24","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 Journal on Optimization 30(2), 1251\u20131273 (2020)","journal-title":"SIAM J. Optim."},{"issue":"1\u20132","key":"1066_CR25","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/s10107-013-0632-5","volume":"144","author":"JB Lasserre","year":"2014","unstructured":"Lasserre, J.B.: New approximations for the cone of copositive matrices and its dual. Mathematical Programming 144(1\u20132), 265\u2013276 (2014)","journal-title":"Math. Program."},{"issue":"4","key":"1066_CR26","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1016\/j.orl.2013.04.004","volume":"41","author":"M Locatelli","year":"2013","unstructured":"Locatelli, M.: Computing the value of the convex envelope of quadratic forms over polytopes through a semidefinite program. Operations Research Letters 41(4), 370\u2013372 (2013). https:\/\/doi.org\/10.1016\/j.orl.2013.04.004","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"1066_CR27","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/BF01584097","volume":"1","author":"A Majthay","year":"1971","unstructured":"Majthay, A.: Optimality conditions for quadratic programming. Mathematical Programming 1(1), 359\u2013365 (1971)","journal-title":"Math. Program."},{"issue":"2","key":"1066_CR28","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/BF02592948","volume":"39","author":"KG Murty","year":"1987","unstructured":"Murty, K.G., Kabadi, S.N.: Some NP-complete problems in quadratic and nonlinear programming. Mathematical Programming 39(2), 117\u2013129 (1987). DOI: https:\/\/doi.org\/10.1007\/BF02592948","journal-title":"Math. Program."},{"key":"1066_CR29","volume-title":"Numerical Optimization","author":"J Nocedal","year":"2006","unstructured":"Nocedal, J., Wright, S.J.: Numerical Optimization, second edn. Springer, New York, NY, USA (2006)","edition":"2"},{"key":"1066_CR30","unstructured":"Parrilo, P.A.: Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph.D. thesis, California Institute of Technology (2000)"},{"issue":"1","key":"1066_CR31","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1137\/05064401X","volume":"18","author":"J Pena","year":"2007","unstructured":"Pena, J., Vera, J., Zuluaga, L.F.: Computing the stability number of a graph via linear and semidefinite programming. SIAM Journal on Optimization 18(1), 87\u2013105 (2007)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"1066_CR32","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/s10107-014-0822-9","volume":"151","author":"J Pe\u00f1a","year":"2015","unstructured":"Pe\u00f1a, J., Vera, J.C., Zuluaga, L.F.: Completely positive reformulations for polynomial optimization. Math. Program. 151(2), 405\u2013431 (2015). DOI: https:\/\/doi.org\/10.1007\/s10107-014-0822-9","journal-title":"Math. Program."},{"key":"1066_CR33","volume-title":"Convex Analysis (Princeton Landmarks in Mathematics and Physics)","author":"RT Rockafellar","year":"1970","unstructured":"Rockafellar, R.T.: Convex Analysis. Princeton Landmarks in Mathematics and Physics. Princeton University Press, Princeton (1970)"},{"issue":"6","key":"1066_CR34","first-page":"1","volume":"25","author":"NZ Shor","year":"1987","unstructured":"Shor, N.Z.: Quadratic optimization problems. Soviet Journal of Computer and Systems Sciences 25(6), 1\u201311 (1987)","journal-title":"Soviet J. Comput. Syst. Sci."},{"issue":"1","key":"1066_CR35","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1080\/10556788.2010.540014","volume":"27","author":"EA Y\u0131ld\u0131r\u0131m","year":"2012","unstructured":"Y\u0131ld\u0131r\u0131m, E.A.: On the accuracy of uniform polyhedral approximations of the copositive cone. Optimization Methods and Software 27(1), 155\u2013173 (2012)","journal-title":"Optim. Methods Softw."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-021-01066-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-021-01066-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-021-01066-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,7]],"date-time":"2022-01-07T06:11:25Z","timestamp":1641535885000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-021-01066-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,29]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["1066"],"URL":"https:\/\/doi.org\/10.1007\/s10898-021-01066-3","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,29]]},"assertion":[{"value":"29 May 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 July 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 July 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}