{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:58Z","timestamp":1740122458697,"version":"3.37.3"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","license":[{"start":{"date-parts":[[2024,8,12]],"date-time":"2024-08-12T00:00:00Z","timestamp":1723420800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,8,12]],"date-time":"2024-08-12T00:00:00Z","timestamp":1723420800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100007493","name":"Fondation Math\u00e9matique Jacques Hadamard","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100007493","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005856","name":"Faculdade de Ci\u00eancias e Tecnologia, Universidade Nova de Lisboa","doi-asserted-by":"publisher","award":["UID\/EEA\/50008\/2019"],"award-info":[{"award-number":["UID\/EEA\/50008\/2019"]}],"id":[{"id":"10.13039\/501100005856","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We introduce a new sequential algorithm for the Standard Quadratic Programming Problem (StQP), which exploits a formulation of StQP as a Linear Program with Linear Complementarity Constraints (LPLCC). The algorithm is finite and guarantees at least in theory a <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\delta $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                <mml:mi>\u03b4<\/mml:mi>\n              <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximate global minimum for an arbitrary small <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\delta $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                <mml:mi>\u03b4<\/mml:mi>\n              <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, which is a global minimum in practice. The sequential algorithm has two phases. In Phase\u00a01, Stationary Points (SP) with strictly decreasing objective function values are computed. Phase\u00a02 is designed for giving a certificate of global optimality for the last SP computed in Phase\u00a01. Two different Nonlinear Programming Formulations for LPLCC are proposed for each one of these phases, which are solved by efficient enumerative algorithms. New procedures for computing a lower bound for StQP are also proposed, which are easy to implement and give tight bounds in general. Computational experiments with a number of test problems from known sources indicate that the two-phase sequential algorithm is, in general, efficient in practice. Furthermore, the algorithm seems to be an efficient way to study the copositivity of a matrix by exploiting an StQP with this matrix.<\/jats:p>","DOI":"10.1007\/s10898-024-01423-y","type":"journal-article","created":{"date-parts":[[2024,8,12]],"date-time":"2024-08-12T02:02:22Z","timestamp":1723428142000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A two-phase sequential algorithm for global optimization of the standard quadratic programming problem"],"prefix":"10.1007","author":[{"given":"Joaquim","family":"J\u00fadice","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0083-2515","authenticated-orcid":false,"given":"Valentina","family":"Sessa","sequence":"additional","affiliation":[]},{"given":"Masao","family":"Fukushima","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,8,12]]},"reference":[{"key":"1423_CR1","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/j.laa.2020.09.002","volume":"609","author":"K Anstreicher","year":"2021","unstructured":"Anstreicher, K.: Testing copositivity via mixed-integer linear programming. Linear Algebra Appl. 609, 218\u2013230 (2021)","journal-title":"Linear Algebra Appl."},{"issue":"1","key":"1423_CR2","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1023\/A:1008278114178","volume":"10","author":"MJ Best","year":"1997","unstructured":"Best, M.J., Ding, B.: Global and local quadratic minimization. J. Glob. Optim. 10(1), 77\u201390 (1997). https:\/\/doi.org\/10.1023\/A:1008278114178","journal-title":"J. Glob. Optim."},{"issue":"1","key":"1423_CR3","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1137\/141000671","volume":"59","author":"J Bezanson","year":"2017","unstructured":"Bezanson, J., Edelman, A., Karpinski, S., Shah, V.B.: Julia: A fresh approach to numerical computing. SIAM Rev. 59(1), 65\u201398 (2017). https:\/\/doi.org\/10.1137\/141000671","journal-title":"SIAM Rev."},{"issue":"4","key":"1423_CR4","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. Glob. Optim. 13(4), 369\u2013387 (1998). https:\/\/doi.org\/10.1023\/A:1008369322970","journal-title":"J. Glob. Optim."},{"issue":"1\/4","key":"1423_CR5","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1023\/A:1013886408463","volume":"22","author":"IM Bomze","year":"2002","unstructured":"Bomze, I.M.: Branch-and-bound approaches to standard quadratic optimization problems. J. Glob. Optim. 22(1\/4), 17\u201337 (2002). https:\/\/doi.org\/10.1023\/A:1013886408463","journal-title":"J. Glob. Optim."},{"issue":"2","key":"1423_CR6","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). https:\/\/doi.org\/10.1023\/A:1020209017701","journal-title":"J. Glob. Optim."},{"issue":"4","key":"1423_CR7","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1023\/A:1026583532263","volume":"18","author":"IM Bomze","year":"2000","unstructured":"Bomze, I.M., Dur, 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\u20132","key":"1423_CR8","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/s10107-012-0543-x","volume":"138","author":"IM Bomze","year":"2013","unstructured":"Bomze, I.M., Eichfelder, G.: Copositivity detection by difference-of-convex decomposition and $$\\omega $$-subdivision. Math. Program. 138(1\u20132), 365\u2013400 (2013). https:\/\/doi.org\/10.1007\/s10107-012-0543-x","journal-title":"Math. Program."},{"issue":"1","key":"1423_CR9","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/s11590-006-0018-1","volume":"1","author":"IM Bomze","year":"2006","unstructured":"Bomze, I.M., Frommlet, F., Rubey, M.: Improved SDP bounds for minimizing quadratic functions over the $$\\ell ^{1}$$ -ball. Opt. Lett. 1(1), 49\u201359 (2006). https:\/\/doi.org\/10.1007\/s11590-006-0018-1","journal-title":"Opt. Lett."},{"issue":"1","key":"1423_CR10","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/s10107-007-0138-0","volume":"115","author":"IM Bomze","year":"2008","unstructured":"Bomze, I.M., Locatelli, M., Tardella, F.: New and old bounds for standard quadratic optimization: Dominance, equivalence and incomparability. Math. Prog. 115(1), 31\u201364 (2008). https:\/\/doi.org\/10.1007\/s10107-007-0138-0","journal-title":"Math. Prog."},{"issue":"2","key":"1423_CR11","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s10898-004-2701-z","volume":"32","author":"IM Bomze","year":"2005","unstructured":"Bomze, I.M., Palagi, L.: Quartic formulation of standard quadratic optimization problems. J. Glob. Optim. 32(2), 181\u2013205 (2005). https:\/\/doi.org\/10.1007\/s10898-004-2701-z","journal-title":"J. Glob. Optim."},{"issue":"2","key":"1423_CR12","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1287\/moor.2017.0877","volume":"43","author":"IM Bomze","year":"2018","unstructured":"Bomze, I.M., Schachinger, W., Ullrich, R.: The complexity of simple models\u2014A study of worst and typical hard cases for the standard quadratic optimization problem. Math. Oper. Res. 43(2), 651\u2013674 (2018). https:\/\/doi.org\/10.1287\/moor.2017.0877","journal-title":"Math. Oper. Res."},{"issue":"2","key":"1423_CR13","doi-asserted-by":"publisher","first-page":"1076","DOI":"10.1137\/16M107428X","volume":"29","author":"P Bonami","year":"2019","unstructured":"Bonami, P., Lodi, A., Schweiger, J., Tramontani, A.: Solving quadratic programming by cutting planes. SIAM J. Optim. 29(2), 1076\u20131105 (2019). https:\/\/doi.org\/10.1137\/16M107428X","journal-title":"SIAM J. Optim."},{"issue":"2","key":"1423_CR14","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s10589-015-9772-2","volume":"63","author":"C Br\u00e1s","year":"2016","unstructured":"Br\u00e1s, C., Eichfelder, G., J\u00fadice, J.: Copositivity tests based on the linear complementarity problem. Comput. Optim. Appl. 63(2), 461\u2013493 (2016). https:\/\/doi.org\/10.1007\/s10589-015-9772-2","journal-title":"Comput. Optim. Appl."},{"key":"1423_CR15","doi-asserted-by":"crossref","unstructured":"Cottle, R., Pang, J., Stone, R.: The Linear Complementarity Problem. Society for Industrial and Applied Mathematics (2009)","DOI":"10.1137\/1.9780898719000"},{"key":"1423_CR16","unstructured":"Currie, J., Wilson, D.I.: OPTI: Lowering the barrier between open source optimizers and the industrial MATLAB user. In: Found. Comput.-Aided Process Oper. Georgia, USA (2012)"},{"key":"1423_CR17","unstructured":"DIMACS: Second DIMACS Challenge. Test instances available at http:\/\/dimacs.rutgers.edu\/challenges"},{"issue":"2","key":"1423_CR18","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/s101070100244","volume":"91","author":"R Fletcher","year":"2002","unstructured":"Fletcher, R., Leyffer, S.: Nonlinear programming without a penalty function. Math. Prog. 91(2), 239\u2013269 (2002). https:\/\/doi.org\/10.1007\/s101070100244","journal-title":"Math. Prog."},{"issue":"2","key":"1423_CR19","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/s12532-018-0147-4","volume":"11","author":"F Furini","year":"2019","unstructured":"Furini, F., Traversi, E., Belotti, P., Frangioni, A., Gleixner, A., Gould, N., Liberti, L., Lodi, A., Misener, R., Mittelmann, H., Sahinidis, N.V., Vigerske, S., Wiegele, A.: QPLIB: A library of quadratic programming instances. Math. Prog. Comp. 11(2), 237\u2013265 (2019). https:\/\/doi.org\/10.1007\/s12532-018-0147-4","journal-title":"Math. Prog. Comp."},{"key":"1423_CR20","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-021-01017-y","author":"J Gondzio","year":"2021","unstructured":"Gondzio, J., Y\u0131ld\u0131r\u0131m, E.A.: Global solutions of nonconvex standard quadratic programs via mixed integer linear programming reformulations. J. Glob. Optim. (2021). https:\/\/doi.org\/10.1007\/s10898-021-01017-y","journal-title":"J. Glob. Optim."},{"key":"1423_CR21","unstructured":"Gurobi\u00a0Optimization, L.: Gurobi optimizer reference manual. http:\/\/www.gurobi.com"},{"issue":"2","key":"1423_CR22","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. Camb. Phil. Soc. 59(2), 329\u2013339 (1963). https:\/\/doi.org\/10.1017\/S0305004100036951","journal-title":"Math. Proc. Camb. Phil. Soc."},{"issue":"3","key":"1423_CR23","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1016\/0097-3165(73)90006-X","volume":"14","author":"AJ Hoffman","year":"1973","unstructured":"Hoffman, A.J., Pereira, F.: On copositive matrices with -1, 0, 1 entries. J. Comb. Theory Ser. A. 14(3), 302\u2013309 (1973). https:\/\/doi.org\/10.1016\/0097-3165(73)90006-X","journal-title":"J. Comb. Theory Ser. A."},{"key":"1423_CR24","doi-asserted-by":"crossref","unstructured":"Horst, R., Pardalos, P.M., Thoai, N.V.: Introduction to Global Optimization, 2nd ed edn. No. v. 48 in Nonconvex Optimization and Its Applications. Kluwer Academic Publishers, Dordrecht ; Boston (2000)","DOI":"10.1007\/978-1-4615-0015-5"},{"issue":"2\u20133","key":"1423_CR25","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1080\/10556788.2020.1734804","volume":"36","author":"JJ J\u00fadice","year":"2021","unstructured":"J\u00fadice, J.J., Fukushima, M., Iusem, A., Martinez, J.M., Sessa, V.: An alternating direction method of multipliers for the eigenvalue complementarity problem. Optim. Methods Softw. 36(2\u20133), 337\u2013370 (2021). https:\/\/doi.org\/10.1080\/10556788.2020.1734804","journal-title":"Optim. Methods Softw."},{"issue":"1\u20133","key":"1423_CR26","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/S0024-3795(01)00351-2","volume":"337","author":"W Kaplan","year":"2001","unstructured":"Kaplan, W.: A copositivity probe. Linear Algebra Appl. 337(1\u20133), 237\u2013251 (2001). https:\/\/doi.org\/10.1016\/S0024-3795(01)00351-2","journal-title":"Linear Algebra Appl."},{"issue":"1","key":"1423_CR27","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.: A new branch-and-bound algorithm for standard quadratic programming problems. Optim. Methods Softw. 34(1), 79\u201397 (2019). https:\/\/doi.org\/10.1080\/10556788.2017.1341504","journal-title":"Optim. Methods Softw."},{"key":"1423_CR28","unstructured":"MatrixMarket: Math.nist.gov\/MatrixMarket\/index.html. math.nist.gov\/MatrixMarket\/index.html"},{"key":"1423_CR29","unstructured":"Meurant, G.A.: Computer Solution of Large Linear Systems, 1. ed edn. No.\u00a028 in Studies in Mathematics and Its Applications. Elsevier, Amsterdam (1999)"},{"key":"1423_CR30","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). https:\/\/doi.org\/10.4153\/CJM-1965-053-6","journal-title":"Can. J. Math."},{"key":"1423_CR31","doi-asserted-by":"publisher","unstructured":"Nowak, I.: A Global Optimality Criterion for Nonconvex Quadratic Programming over a Simplex. Humboldt-Universit\u00e4t zu Berlin, Mathematisch-Naturwissenschaftliche Fakult\u00e4t II, Institut f\u00fcr Mathematik (2005). https:\/\/doi.org\/10.18452\/2684","DOI":"10.18452\/2684"},{"key":"1423_CR32","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejco.2022.100037","volume":"10","author":"B Peng","year":"2022","unstructured":"Peng, B.: Performance comparison of two recently proposed copositivity tests. EURO J. Comput. Optim. 10, 100037 (2022). https:\/\/doi.org\/10.1016\/j.ejco.2022.100037","journal-title":"EURO J. Comput. Optim."},{"issue":"13","key":"1423_CR33","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.: A clique algorithm for standard quadratic programming. Discret. Appl. Math. 156(13), 2439\u20132448 (2008). https:\/\/doi.org\/10.1016\/j.dam.2007.09.020","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"1423_CR34","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/BF00121304","volume":"2","author":"HD Sherali","year":"1992","unstructured":"Sherali, H.D., Tuncbilek, C.H.: A global optimization algorithm for polynomial programming problems using a Reformulation-Linearization Technique. J. Glob. Optim. 2(1), 101\u2013112 (1992). https:\/\/doi.org\/10.1007\/BF00121304","journal-title":"J. Glob. Optim."},{"issue":"3","key":"1423_CR35","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1007\/s10898-011-9766-2","volume":"52","author":"J Sponsel","year":"2012","unstructured":"Sponsel, J., Bundfuss, S., D\u00fcr, M.: An improved algorithm to test copositivity. J. Glob. Optim. 52(3), 537\u2013551 (2012). https:\/\/doi.org\/10.1007\/s10898-011-9766-2","journal-title":"J. Glob. Optim."},{"issue":"3","key":"1423_CR36","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1023\/A:1023245011830","volume":"26","author":"V Stix","year":"2003","unstructured":"Stix, V.: Target-oriented branch and bound method for global optimization. J. Glob. Optim. 26(3), 261\u2013277 (2003). https:\/\/doi.org\/10.1023\/A:1023245011830","journal-title":"J. Glob. Optim."},{"key":"1423_CR37","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0024-3795(89)90076-1","volume":"119","author":"H V\u00e4liaho","year":"1989","unstructured":"V\u00e4liaho, H.: Quadratic-programming criteria for copositive matrices. Linear Algebra Appl. 119, 163\u2013182 (1989). https:\/\/doi.org\/10.1016\/0024-3795(89)90076-1","journal-title":"Linear Algebra Appl."},{"key":"1423_CR38","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/s10107-004-0559-y","volume":"106","author":"A W\u00e4chter","year":"2006","unstructured":"W\u00e4chter, A., Biegler, L.: On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming. Math. Prog. 106, 25\u201357 (2006)","journal-title":"Math. Prog."},{"issue":"3","key":"1423_CR39","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.: Depth-first simplicial partition for copositivity detection, with an application to MaxClique. Optim. Methods Softw. 26(3), 499\u2013510 (2011). https:\/\/doi.org\/10.1080\/10556788.2010.544310","journal-title":"Optim. Methods Softw."},{"key":"1423_CR40","doi-asserted-by":"crossref","unstructured":"Fernandes, L., J\u00fadice,, J., Sherali, H., Fukushima, M.: On the computation of all eigenvalues for the eigenvalue complementarity problems. J Glob Optim 59, 307\u2013326 (2014)","DOI":"10.1007\/s10898-014-0165-3"}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-024-01423-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-024-01423-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-024-01423-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,12]],"date-time":"2024-08-12T02:04:11Z","timestamp":1723428251000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-024-01423-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,12]]},"references-count":40,"alternative-id":["1423"],"URL":"https:\/\/doi.org\/10.1007\/s10898-024-01423-y","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"type":"print","value":"0925-5001"},{"type":"electronic","value":"1573-2916"}],"subject":[],"published":{"date-parts":[[2024,8,12]]},"assertion":[{"value":"12 June 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 July 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 August 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}