{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T13:06:40Z","timestamp":1780924000509,"version":"3.54.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,1,18]],"date-time":"2021-01-18T00:00:00Z","timestamp":1610928000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,1,18]],"date-time":"2021-01-18T00:00:00Z","timestamp":1610928000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004410","name":"T\u00fcrkiye Bilimsel ve Teknolojik Arastirma Kurumu","doi-asserted-by":"publisher","award":["PhD Scholarship Program BIDEB 2211-A"],"award-info":[{"award-number":["PhD Scholarship Program BIDEB 2211-A"]}],"id":[{"id":"10.13039\/501100004410","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,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The problem of minimizing a (nonconvex) quadratic form over the unit simplex, referred to as a standard quadratic program, admits an exact convex conic formulation over the computationally intractable cone of completely positive matrices. Replacing the intractable cone in this formulation by the larger but tractable cone of doubly nonnegative matrices, i.e., the cone of positive semidefinite and componentwise nonnegative matrices, one obtains the so-called doubly nonnegative relaxation, whose optimal value yields a lower bound on that of the original problem. We present a full algebraic characterization of the set of instances of standard quadratic programs that admit an exact doubly nonnegative relaxation. This characterization yields an algorithmic recipe for constructing such an instance. In addition, we explicitly identify three families of instances for which the doubly nonnegative relaxation is exact. We establish several relations between the so-called convexity graph of an instance and the tightness of the doubly nonnegative relaxation. We also provide an algebraic characterization of the set of instances for which the doubly nonnegative relaxation has a positive gap and show how to construct such an instance using this characterization.\n<\/jats:p>","DOI":"10.1007\/s10107-020-01611-0","type":"journal-article","created":{"date-parts":[[2021,1,18]],"date-time":"2021-01-18T16:03:24Z","timestamp":1610985804000},"page":"365-403","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["On standard quadratic programs with exact and inexact doubly nonnegative relaxations"],"prefix":"10.1007","volume":"193","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0722-2629","authenticated-orcid":false,"given":"Y. G\u00f6rkem","family":"G\u00f6kmen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4141-3189","authenticated-orcid":false,"given":"E. Alper","family":"Y\u0131ld\u0131r\u0131m","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,1,18]]},"reference":[{"key":"1611_CR1","doi-asserted-by":"publisher","unstructured":"Afonin, A., Hildebrand, R., Dickinson, P.J.C.: The extreme rays of the $$6 \\times 6$$ copositive cone. J. Glob. Optim. (2020). https:\/\/doi.org\/10.1007\/s10898-020-00930-y. (To appear)","DOI":"10.1007\/s10898-020-00930-y"},{"issue":"2","key":"1611_CR2","doi-asserted-by":"publisher","first-page":"197","DOI":"10.2140\/pjm.1966.19.197","volume":"19","author":"L Baumert","year":"1966","unstructured":"Baumert, L.: Extreme copositive quadratic forms. Pac. J. Math. 19(2), 197\u2013204 (1966)","journal-title":"Pac. J. Math."},{"issue":"4","key":"1611_CR3","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1023\/A:1008369322970","volume":"13","author":"IM Bomze","year":"1998","unstructured":"Bomze, I.M.: On standard quadratic optimization problems. J. Global Optim. 13(4), 369\u2013387 (1998). https:\/\/doi.org\/10.1023\/A:1008369322970","journal-title":"J. Global Optim."},{"key":"1611_CR4","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1137\/S00361445003756","volume":"44","author":"IM Bomze","year":"2002","unstructured":"Bomze, I.M.: Regularity versus degeneracy in dynamics, games, and optimization: a unified approach to different aspects. SIAM Rev. 44, 394\u2013414 (2002)","journal-title":"SIAM Rev."},{"issue":"2","key":"1611_CR5","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1023\/A:1020209017701","volume":"24","author":"IM Bomze","year":"2002","unstructured":"Bomze, I.M., De Klerk, E.: Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J. Glob. Optim. 24(2), 163\u2013185 (2002)","journal-title":"J. Glob. Optim."},{"issue":"4","key":"1611_CR6","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1023\/A:1026583532263","volume":"18","author":"IM Bomze","year":"2000","unstructured":"Bomze, I.M., D\u00fcr, M., de Klerk, E., Roos, C., Quist, A.J., Terlaky, T.: On copositive programming and standard quadratic optimization problems. J. Glob. Optim. 18(4), 301\u2013320 (2000). https:\/\/doi.org\/10.1023\/A:1026583532263","journal-title":"J. Glob. Optim."},{"issue":"1","key":"1611_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 J. Optim. 20(1), 30\u201353 (2009)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"1611_CR8","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s00493-005-0012-8","volume":"25","author":"M Chudnovsky","year":"2005","unstructured":"Chudnovsky, M., Cornu\u00e9jols, G., Liu, X., Seymour, P.D., Vuskovic, K.: Recognizing Berge graphs. Combinatorica 25(2), 143\u2013186 (2005). https:\/\/doi.org\/10.1007\/s00493-005-0012-8","journal-title":"Combinatorica"},{"key":"1611_CR9","doi-asserted-by":"publisher","first-page":"51","DOI":"10.4007\/annals.2006.164.51","volume":"164","author":"M Chudnovsky","year":"2006","unstructured":"Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math. 164, 51\u2013229 (2006)","journal-title":"Ann. Math."},{"issue":"4","key":"1611_CR10","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 J. Optim. 12(4), 875\u2013892 (2002)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1611_CR11","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. Math. Proc. Cambridge Philos. Soc. 58(1), 17\u201325 (1962). https:\/\/doi.org\/10.1017\/S0305004100036185","journal-title":"Math. Proc. Cambridge Philos. Soc."},{"issue":"6","key":"1611_CR12","doi-asserted-by":"publisher","first-page":"1605","DOI":"10.1016\/j.laa.2012.10.014","volume":"439","author":"PJ Dickinson","year":"2013","unstructured":"Dickinson, P.J., D\u00fcr, M., Gijben, L., Hildebrand, R.: Irreducible elements of the copositive cone. Linear Algebra Appl. 439(6), 1605\u20131626 (2013)","journal-title":"Linear Algebra Appl."},{"issue":"2","key":"1611_CR13","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/s10589-013-9594-z","volume":"57","author":"PJC Dickinson","year":"2014","unstructured":"Dickinson, P.J.C., Gijben, L.: On the computational complexity of membership problems for the completely positive cone and its dual. Comput. Optim. Appl. 57(2), 403\u2013415 (2014). https:\/\/doi.org\/10.1007\/s10589-013-9594-z","journal-title":"Comput. Optim. Appl."},{"issue":"3","key":"1611_CR14","doi-asserted-by":"publisher","first-page":"754","DOI":"10.1287\/moor.22.3.754","volume":"22","author":"LE Gibbons","year":"1997","unstructured":"Gibbons, L.E., Hearn, D.W., Pardalos, P.M., Ramana, M.V.: Continuous characterizations of the maximum clique problem. Math. Oper. Res. 22(3), 754\u2013768 (1997). https:\/\/doi.org\/10.1287\/moor.22.3.754","journal-title":"Math. Oper. Res."},{"key":"1611_CR15","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. J. Glob. Optim. 76, 383\u2013405 (2020)","journal-title":"J. Glob. Optim."},{"issue":"2","key":"1611_CR16","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2), 169\u2013197 (1981). https:\/\/doi.org\/10.1007\/BF02579273","journal-title":"Combinatorica"},{"issue":"2","key":"1611_CR17","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. Math. Proc. Cambridge Philos. Soc. 59(2), 329\u2013339 (1963)","journal-title":"Math. Proc. Cambridge Philos. Soc."},{"issue":"7","key":"1611_CR18","doi-asserted-by":"publisher","first-page":"1538","DOI":"10.1016\/j.laa.2012.04.017","volume":"437","author":"R Hildebrand","year":"2012","unstructured":"Hildebrand, R.: The extreme rays of the $$5 \\times 5$$ copositive cone. Linear Algebra Appl. 437(7), 1538\u20131547 (2012)","journal-title":"Linear Algebra Appl."},{"issue":"5","key":"1611_CR19","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. Chin. Ann. Math. Ser. B 3(5), 625\u2013630 (1982)","journal-title":"Chin. Ann. Math. Ser. B"},{"key":"1611_CR20","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":"3","key":"1611_CR21","doi-asserted-by":"publisher","first-page":"574","DOI":"10.1017\/S0305004100035635","volume":"57","author":"JFC Kingman","year":"1961","unstructured":"Kingman, J.F.C.: A mathematical problem in population genetics. Proc. Cambridge Philos. Soc. 57(3), 574 (1961). https:\/\/doi.org\/10.1017\/S0305004100035635","journal-title":"Proc. Cambridge Philos. Soc."},{"issue":"1\u20132","key":"1611_CR22","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. Math. Program. 144(1\u20132), 265\u2013276 (2014)","journal-title":"Math. Program."},{"issue":"1","key":"1611_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","volume":"25","author":"L Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz, L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory 25(1), 1\u20137 (1979)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"1611_CR24","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. Math. Program. 1(1), 359\u2013365 (1971)","journal-title":"Math. Program."},{"issue":"1","key":"1611_CR25","first-page":"77","volume":"7","author":"H Markowitz","year":"1952","unstructured":"Markowitz, H.: Portfolio selection. J. Financ. 7(1), 77\u201391 (1952)","journal-title":"J. Financ."},{"issue":"1","key":"1611_CR26","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF02760024","volume":"3","author":"JW Moon","year":"1965","unstructured":"Moon, J.W., Moser, L.: On cliques in graphs. Isr. J. Math. 3(1), 23\u201328 (1965)","journal-title":"Isr. J. Math."},{"key":"1611_CR27","doi-asserted-by":"publisher","first-page":"533","DOI":"10.4153\/CJM-1965-053-6","volume":"17","author":"TS Motzkin","year":"1965","unstructured":"Motzkin, T.S., Straus, E.G.: Maxima for graphs and a new proof of a theorem of Tur\u00e1n. Can. J. Math. 17, 533\u2013540 (1965)","journal-title":"Can. J. Math."},{"issue":"2","key":"1611_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. Math. Program. 39(2), 117\u2013129 (1987). https:\/\/doi.org\/10.1007\/BF02592948","journal-title":"Math. Program."},{"key":"1611_CR29","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":"1611_CR30","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 J. Optim. 18(1), 87\u2013105 (2007)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1611_CR31","first-page":"1","volume":"9","author":"B Rosgen","year":"2007","unstructured":"Rosgen, B., Stewart, L.: Complexity results on graphs with few cliques. Discret. Math. Theor. Comput. Sci. 9(1), 1 (2007)","journal-title":"Discret. Math. Theor. Comput. Sci."},{"issue":"1","key":"1611_CR32","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/s10898-015-0269-4","volume":"63","author":"G Sa\u011fol","year":"2015","unstructured":"Sa\u011fol, G., Y\u0131ld\u0131r\u0131m, E.A.: Analysis of copositive optimization based linear programming bounds on standard quadratic optimization. J. Glob. Optim. 63(1), 37\u201359 (2015)","journal-title":"J. Glob. Optim."},{"issue":"4","key":"1611_CR33","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1109\/TIT.1979.1056072","volume":"25","author":"A Schrijver","year":"1979","unstructured":"Schrijver, A.: A comparison of the Delsarte and Lov\u00e1sz bounds. IEEE Trans. Inf. Theory 25(4), 425\u2013429 (1979)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1611_CR34","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1016\/j.laa.2016.07.018","volume":"509","author":"N Shaked-Monderer","year":"2016","unstructured":"Shaked-Monderer, N.: SPN graphs: when copositive = SPN. Linear Algebra Appl. 509, 82\u2013113 (2016)","journal-title":"Linear Algebra Appl."},{"key":"1611_CR35","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1016\/j.laa.2014.10.021","volume":"498","author":"N Shaked-Monderer","year":"2016","unstructured":"Shaked-Monderer, N., Berman, A., D\u00fcr, M., Kannan, M.R.: SPN completable graphs. Linear Algebra Appl. 498, 58\u201373 (2016)","journal-title":"Linear Algebra Appl."},{"issue":"1","key":"1611_CR36","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. Optim. Methods Softw. 27(1), 155\u2013173 (2012)","journal-title":"Optim. Methods Softw."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01611-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01611-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01611-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,25]],"date-time":"2022-04-25T18:11:56Z","timestamp":1650910316000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01611-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,18]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["1611"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01611-0","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,18]]},"assertion":[{"value":"17 February 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 December 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 January 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}