{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:42:12Z","timestamp":1740145332159,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,3,6]],"date-time":"2021-03-06T00:00:00Z","timestamp":1614988800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,6]],"date-time":"2021-03-06T00:00:00Z","timestamp":1614988800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Spanish Ministry","award":["RTI2018-095993-B-100"],"award-info":[{"award-number":["RTI2018-095993-B-100"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cent Eur J Oper Res"],"published-print":{"date-parts":[[2022,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Over the last decades, algorithms have been developed for checking copositivity of a matrix. Methods are based on several principles, such as spatial branch and bound, transformation to Mixed Integer Programming, implicit enumeration of KKT points or face-based search. Our research question focuses on exploiting the mathematical properties of the relative interior minima of the standard quadratic program (StQP) and monotonicity. We derive several theoretical properties related to convexity and monotonicity of the standard quadratic function over faces of the standard simplex. We illustrate with numerical instances up to 28 dimensions the use of monotonicity in face-based algorithms. The question is what traversal through the face graph of the standard simplex is more appropriate for which matrix instance; top down or bottom up approaches. This depends on the level of the face graph where the minimum of StQP can be found, which is related to the density of the so-called convexity graph.<\/jats:p>","DOI":"10.1007\/s10100-021-00737-6","type":"journal-article","created":{"date-parts":[[2021,3,6]],"date-time":"2021-03-06T06:02:46Z","timestamp":1615010566000},"page":"1071-1092","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["On monotonicity and search strategies in face-based copositivity detection algorithms"],"prefix":"10.1007","volume":"30","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0927-111X","authenticated-orcid":false,"given":"B.","family":"G.-T\u00f3th","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1572-1436","authenticated-orcid":false,"given":"E. M. T.","family":"Hendrix","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8459-4982","authenticated-orcid":false,"given":"L. G.","family":"Casado","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,3,6]]},"reference":[{"issue":"2","key":"737_CR1","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1023\/A:1020209017701","volume":"24","author":"IM Bomze","year":"2002","unstructured":"Bomze IM, De Klerk E (2002) Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J Glob Optim 24(2):163\u2013185","journal-title":"J Glob Optim"},{"issue":"7","key":"737_CR2","doi-asserted-by":"publisher","first-page":"1511","DOI":"10.1016\/j.laa.2007.09.035","volume":"428","author":"S Bundfuss","year":"2008","unstructured":"Bundfuss S, D\u00fcr M (2008) Algorithmic copositivity detection by simplicial partition. Linear Algebra Appl 428(7):1511\u20131523","journal-title":"Linear Algebra Appl"},{"issue":"2","key":"737_CR3","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1007\/s10107-008-0223-z","volume":"120","author":"S Burer","year":"2009","unstructured":"Burer S (2009) On the copositive representation of binary and continuous nonconvex quadratic programs. Math Program 120(2):479\u2013495","journal-title":"Math Program"},{"key":"737_CR4","unstructured":"Challenge problems: independent sets in graphs. https:\/\/oeis.org\/A265032\/a265032.html"},{"key":"737_CR5","unstructured":"Gondzio J, Yildirim EA (2018) Global solutions of nonconvex standard quadratic programs via mixed integer linear programming reformulations. Technical Report ERGO-18-022, School of Mathematics, The University of Edinburgh"},{"issue":"2","key":"737_CR6","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1017\/S0305004100036951","volume":"59","author":"M Hall","year":"1963","unstructured":"Hall M, Newman M (1963) Copositive and completely positive quadratic forms. Math Proc Camb Philos Soc 59(2):329\u2013339","journal-title":"Math Proc Camb Philos Soc"},{"issue":"1","key":"737_CR7","doi-asserted-by":"publisher","first-page":"020007","DOI":"10.1063\/1.5089974","volume":"2070","author":"EMT Hendrix","year":"2019","unstructured":"Hendrix EMT, Salmer\u00f3n JMG, Casado LG (2019) On function monotonicity in simplicial branch and bound. AIP Conf Proc 2070(1):020007","journal-title":"AIP Conf Proc"},{"issue":"1\u20133","key":"737_CR8","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/S0024-3795(00)00138-5","volume":"313","author":"W Kaplan","year":"2000","unstructured":"Kaplan W (2000) A test for copositive matrices. Linear Algebra Appl 313(1\u20133):203\u2013206","journal-title":"Linear Algebra Appl"},{"issue":"1","key":"737_CR9","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1080\/10556788.2017.1341504","volume":"34","author":"G Liuzzi","year":"2019","unstructured":"Liuzzi G, Locatelli M, Piccialli V (2019) A new branch-and-bound algorithm for standard quadratic programming problems. Optim Methods Softw 34(1):79\u201397","journal-title":"Optim Methods Softw"},{"issue":"2","key":"737_CR10","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/BF02592948","volume":"39","author":"KG Murty","year":"1987","unstructured":"Murty KG, Kabadi SN (1987) Some NP-complete problems in quadratic and nonlinear programming. Math Program 39(2):117\u2013129","journal-title":"Math Program"},{"issue":"4","key":"737_CR11","doi-asserted-by":"publisher","first-page":"2902","DOI":"10.1137\/17M115308X","volume":"28","author":"J Nie","year":"2018","unstructured":"Nie J, Yang Z, Zhang X (2018) A complete semidefinite algorithm for detecting copositive matrices and tensors. SIAM J Optim 28(4):2902\u20132921","journal-title":"SIAM J Optim"},{"issue":"4","key":"737_CR12","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1023\/A:1008315627883","volume":"14","author":"I Nowak","year":"1999","unstructured":"Nowak I (1999) A new semidefinite programming bound for indefinite quadratic forms over a simplex. J Glob Optim 14(4):357\u2013364","journal-title":"J Glob Optim"},{"issue":"1","key":"737_CR13","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1137\/050637467","volume":"18","author":"J Povh","year":"2007","unstructured":"Povh J, Rendl F (2007) A copositive programming approach to graph partitioning. SIAM J Optim 18(1):223\u2013241","journal-title":"SIAM J Optim"},{"key":"737_CR14","unstructured":"Salmer\u00f3n JMG (2019) High performance computing to solve global optimization problems. Ph.D. thesis, Universidad de Almer\u00eda"},{"key":"737_CR15","unstructured":"Salmer\u00f3n JMG, Casado LG, Hendrix EMT (2018) Paralelizaci\u00f3n de la detecci\u00f3n de una matriz copositiva mediante la evaluaci\u00f3n de las facetas de un simplex unidad. In: Libro de Abstracts de las Jornadas SARTECO 2018. Universidad de Zaragoza, pp 77\u201382"},{"issue":"13","key":"737_CR16","doi-asserted-by":"publisher","first-page":"2439","DOI":"10.1016\/j.dam.2007.09.020","volume":"156","author":"A Scozzari","year":"2008","unstructured":"Scozzari A, Tardella F (2008) A clique algorithm for standard quadratic programming. Discrete Appl Math 156(13):2439\u20132448","journal-title":"Discrete Appl Math"},{"key":"737_CR17","unstructured":"Second DIMACS implementation challenge. http:\/\/archive.dimacs.rutgers.edu\/Challenges\/"},{"key":"737_CR18","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0024-3795(86)90246-6","volume":"81","author":"H V\u00e4liaho","year":"1986","unstructured":"V\u00e4liaho H (1986) Criteria for copositive matrices. Linear Algebra Appl 81:19\u201334","journal-title":"Linear Algebra Appl"},{"issue":"2\u20133","key":"737_CR19","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1016\/j.laa.2008.07.028","volume":"430","author":"S Yang","year":"2009","unstructured":"Yang S, Li X (2009) Algorithms for determining the copositivity of a given symmetric matrix. Linear Algebra Appl 430(2\u20133):609\u2013618","journal-title":"Linear Algebra Appl"},{"issue":"3","key":"737_CR20","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1080\/10556788.2010.544310","volume":"26","author":"J \u017dilinskas","year":"2011","unstructured":"\u017dilinskas J, D\u00fcr M (2011) Depth-first simplicial partition for copositivity detection, with an application to maxclique. Optim Methods Softw 26(3):499\u2013510","journal-title":"Optim Methods Softw"}],"container-title":["Central European Journal of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10100-021-00737-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10100-021-00737-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10100-021-00737-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,26]],"date-time":"2022-05-26T17:30:43Z","timestamp":1653586243000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10100-021-00737-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,6]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["737"],"URL":"https:\/\/doi.org\/10.1007\/s10100-021-00737-6","relation":{},"ISSN":["1435-246X","1613-9178"],"issn-type":[{"type":"print","value":"1435-246X"},{"type":"electronic","value":"1613-9178"}],"subject":[],"published":{"date-parts":[[2021,3,6]]},"assertion":[{"value":"22 January 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 March 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}