{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T03:38:51Z","timestamp":1777088331343,"version":"3.51.4"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T00:00:00Z","timestamp":1773100800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T00:00:00Z","timestamp":1773100800000},"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":[[2026,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>We consider the problem of minimizing a (possibly nonconvex) quadratic function over a (possibly unbounded) polyhedron, referred to as a quadratic program. By incorporating the first-order optimality conditions, a quadratic program can be formulated as an optimization problem with complementarity constraints. We investigate the effect of incorporating optimality conditions on the strength of linear and semidefinite programming (SDP) relaxations based on the reformulation-linearization technique (RLT relaxation), and the Shor relaxation combined with the RLT relaxation (SDP-RLT relaxation). We establish that the RLT and SDP-RLT bounds arising from the complementarity formulation do not strengthen finite RLT and SDP-RLT bounds arising from the original formulation. On the other hand, the complementarity formulation may yield strictly tighter lower bounds for quadratic programs with a finite optimal value, but unbounded RLT and SDP-RLT relaxations. We present several classes of instances of quadratic programs to illustrate the behavior of the relaxations arising from the complementarity formulation. In particular, our examples reveal that the complementarity formulation should be used with some caution as it may even fail to yield a valid lower bound for unbounded quadratic programs.<\/jats:p>","DOI":"10.1007\/s10898-026-01602-z","type":"journal-article","created":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T01:53:59Z","timestamp":1773107639000},"page":"891-918","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Relaxations of KKT conditions do not strengthen finite RLT and SDP-RLT bounds for nonconvex quadratic programs"],"prefix":"10.1007","volume":"94","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":[[2026,3,10]]},"reference":[{"issue":"2","key":"1602_CR1","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.M., Gould, N., Liberti, L., Lodi, A., Misener, R., Mittelmann, H.D., Sahinidis, N.V., Vigerske, S., Wiegele, A.: QPLIB: A library of quadratic programming instances. Math. Program. Comput. 11(2), 237\u2013265 (2019). https:\/\/doi.org\/10.1007\/s12532-018-0147-4","journal-title":"Math. Program. Comput."},{"issue":"4","key":"1602_CR2","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1137\/0203021","volume":"3","author":"S Sahni","year":"1974","unstructured":"Sahni, S.: Computationally related problems. SIAM J. Comput. 3(4), 262\u2013279 (1974). https:\/\/doi.org\/10.1137\/0203021","journal-title":"SIAM J. Comput."},{"key":"1602_CR3","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/BF00120662","volume":"1","author":"PM Pardalos","year":"1991","unstructured":"Pardalos, P.M., Vavasis, S.A.: Quadratic programming with one negative eigenvalue is NP-hard. J. Global Optim. 1, 15\u201322 (1991). https:\/\/doi.org\/10.1007\/BF00120662","journal-title":"J. Global Optim."},{"key":"1602_CR4","doi-asserted-by":"publisher","unstructured":"Locatelli, M., Schoen, F.: Global Optimization - Theory, Algorithms, and Applications. MOS-SIAM Series on Optimization, vol. 15. SIAM, Philadelphia, PA (2013). https:\/\/doi.org\/10.1137\/1.9781611972672","DOI":"10.1137\/1.9781611972672"},{"key":"1602_CR5","doi-asserted-by":"publisher","unstructured":"Sherali, H.D., Adams, W.P.: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems, pp. 297\u2013367. Springer, Boston, MA (1999). https:\/\/doi.org\/10.1007\/978-1-4757-4388-3","DOI":"10.1007\/978-1-4757-4388-3"},{"issue":"5","key":"1602_CR6","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1007\/BF01074929","volume":"23","author":"NZ Shor","year":"1987","unstructured":"Shor, N.Z.: An approach to obtaining global extremums in polynomial mathematical programming problems. Cybernetics 23(5), 695\u2013700 (1987)","journal-title":"Cybernetics"},{"key":"1602_CR7","doi-asserted-by":"publisher","unstructured":"Giannessi, F., Tomasin, E.: Nonconvex quadratic programs, linear complementarity problems, and integer linear programs. In: Conti, R., Ruberti, A. (eds.) 5th Conference on Optimization Techniques Part I, pp. 437\u2013449. Springer, Berlin, Heidelberg (1973). https:\/\/doi.org\/10.1007\/3-540-06583-0_43","DOI":"10.1007\/3-540-06583-0_43"},{"issue":"3","key":"1602_CR8","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1007\/S10107-004-0549-0","volume":"102","author":"D Vandenbussche","year":"2005","unstructured":"Vandenbussche, D., Nemhauser, G.L.: A polyhedral study of nonconvex quadratic programs with box constraints. Math. Program. 102(3), 531\u2013557 (2005). https:\/\/doi.org\/10.1007\/S10107-004-0549-0","journal-title":"Math. Program."},{"issue":"2","key":"1602_CR9","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/S10107-006-0080-6","volume":"113","author":"S Burer","year":"2008","unstructured":"Burer, S., Vandenbussche, D.: A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Math. Program. 113(2), 259\u2013282 (2008). https:\/\/doi.org\/10.1007\/S10107-006-0080-6","journal-title":"Math. Program."},{"issue":"2","key":"1602_CR10","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/S10589-007-9137-6","volume":"43","author":"S Burer","year":"2009","unstructured":"Burer, S., Vandenbussche, D.: Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound. Comput. Optim. Appl. 43(2), 181\u2013195 (2009). https:\/\/doi.org\/10.1007\/S10589-007-9137-6","journal-title":"Comput. Optim. Appl."},{"issue":"3","key":"1602_CR11","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1007\/S10589-009-9273-2","volume":"48","author":"S Burer","year":"2011","unstructured":"Burer, S., Chen, J.: Relaxing the optimality conditions of box QP. Comput. Optim. Appl. 48(3), 653\u2013673 (2011). https:\/\/doi.org\/10.1007\/S10589-009-9273-2","journal-title":"Comput. Optim. Appl."},{"issue":"1","key":"1602_CR12","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/s10107-011-0462-2","volume":"129","author":"X Bao","year":"2011","unstructured":"Bao, X., Sahinidis, N.V., Tawarmalani, M.: Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons. Math. Program. 129(1), 129\u2013157 (2011). https:\/\/doi.org\/10.1007\/s10107-011-0462-2","journal-title":"Math. Program."},{"issue":"1","key":"1602_CR13","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/S12532-011-0033-9","volume":"4","author":"J Chen","year":"2012","unstructured":"Chen, J., Burer, S.: Globally solving nonconvex quadratic programming problems via completely positive programming. Math. Program. Comput. 4(1), 33\u201352 (2012). https:\/\/doi.org\/10.1007\/S12532-011-0033-9","journal-title":"Math. Program. Comput."},{"key":"1602_CR14","doi-asserted-by":"publisher","unstructured":"Qiu, Y., Y\u0131ld\u0131r\u0131m, E.A.: Polyhedral properties of RLT relaxations of nonconvex quadratic programs and their implications on exact relaxations. Math. Program. 209, 397\u2013433 (2025). https:\/\/doi.org\/10.1007\/s10107-024-02070-7","DOI":"10.1007\/s10107-024-02070-7"},{"issue":"1\u20132","key":"1602_CR15","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/S10107-010-0426-Y","volume":"133","author":"J Hu","year":"2012","unstructured":"Hu, J., Mitchell, J.E., Pang, J.: An LPCC approach to nonconvex quadratic programs. Math. Program. 133(1\u20132), 243\u2013277 (2012). https:\/\/doi.org\/10.1007\/S10107-010-0426-Y","journal-title":"Math. Program."},{"issue":"1","key":"1602_CR16","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1287\/IJOC.2018.0883","volume":"32","author":"W Xia","year":"2020","unstructured":"Xia, W., Vera, J., Zuluaga, L.F.: Globally solving nonconvex quadratic programs via linear integer programming techniques. INFORMS J. Comput. 32(1), 40\u201356 (2020). https:\/\/doi.org\/10.1287\/IJOC.2018.0883","journal-title":"INFORMS J. Comput."},{"key":"1602_CR17","doi-asserted-by":"publisher","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. 81(2), 293\u2013321 (2021). https:\/\/doi.org\/10.1007\/S10898-021-01017-Y","DOI":"10.1007\/S10898-021-01017-Y"},{"key":"1602_CR18","doi-asserted-by":"crossref","unstructured":"Hansen, P., Jaumard, B., Ruiz, M., Xiong, J.: Global minimization of indefinite quadratic functions subject to box constraints. Naval Research Logistics (NRL) 40(3), 373\u2013392 (1993). https:\/\/doi.org\/10.1002\/1520-6750(199304)40:3<373::AID-NAV3220400307>3.0.CO;2-A","DOI":"10.1002\/1520-6750(199304)40:3<373::AID-NAV3220400307>3.0.CO;2-A"},{"issue":"3","key":"1602_CR19","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1007\/S101070050072","volume":"85","author":"C Audet","year":"1999","unstructured":"Audet, C., Hansen, P., Jaumard, B., Savard, G.: A symmetrical linear maxmin approach to disjoint bilinear programming. Math. Program. 85(3), 573\u2013592 (1999). https:\/\/doi.org\/10.1007\/S101070050072","journal-title":"Math. Program."},{"issue":"3","key":"1602_CR20","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1007\/S10107-004-0550-7","volume":"102","author":"D Vandenbussche","year":"2005","unstructured":"Vandenbussche, D., Nemhauser, G.L.: A branch-and-cut algorithm for nonconvex quadratic programs with box constraints. Math. Program. 102(3), 559\u2013575 (2005). https:\/\/doi.org\/10.1007\/S10107-004-0550-7","journal-title":"Math. Program."},{"issue":"4","key":"1602_CR21","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/122272.122273","volume":"25","author":"C Boor","year":"1990","unstructured":"Boor, C.: An empty exercise. SIGNUM Newsl. 25(4), 2\u20136 (1990). https:\/\/doi.org\/10.1145\/122272.122273","journal-title":"An empty exercise. SIGNUM Newsl."},{"issue":"1","key":"1602_CR22","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1137\/0802004","volume":"2","author":"Z Luo","year":"1992","unstructured":"Luo, Z., Tseng, P.: Error bound and convergence analysis of matrix splitting algorithms for the affine variational inequality problem. SIAM J. Optim. 2(1), 43\u201354 (1992). https:\/\/doi.org\/10.1137\/0802004","journal-title":"SIAM J. Optim."},{"issue":"1\u20132","key":"1602_CR23","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 Research Logistics Quarterly"},{"issue":"1","key":"1602_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01100203","volume":"7","author":"HD Sherali","year":"1995","unstructured":"Sherali, H.D., Tun\u00e7bilek, C.H.: A reformulation-convexification approach for solving nonconvex quadratic programming problems. J. Global Optim. 7(1), 1\u201331 (1995). https:\/\/doi.org\/10.1007\/BF01100203","journal-title":"J. Global Optim."},{"key":"1602_CR25","doi-asserted-by":"publisher","unstructured":"Boyd, S.P., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge, Massachusetts, USA (2004). https:\/\/doi.org\/10.1017\/CBO9780511804441","DOI":"10.1017\/CBO9780511804441"},{"issue":"2","key":"1602_CR26","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). https:\/\/doi.org\/10.1007\/s10107-008-0223-z","journal-title":"Math. Program."},{"key":"1602_CR27","unstructured":"Parrilo, P.A.: Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. PhD thesis, California Institute of Technology, Pasadena, California, USA (2000)"},{"issue":"4","key":"1602_CR28","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1137\/S1052623401383248","volume":"12","author":"E Klerk","year":"2002","unstructured":"Klerk, E., Pasechnik, D.V.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12(4), 875\u2013892 (2002). https:\/\/doi.org\/10.1137\/S1052623401383248","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1602_CR29","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1137\/05064401X","volume":"18","author":"J Pe\u00f1a","year":"2007","unstructured":"Pe\u00f1a, J., Vera, J.C., Zuluaga, L.F.: Computing the stability number of a graph via linear and semidefinite programming. SIAM J. Optim. 18(1), 87\u2013105 (2007). https:\/\/doi.org\/10.1137\/05064401X","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1602_CR30","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). https:\/\/doi.org\/10.1080\/10556788.2010.540014","journal-title":"Optim. Methods Softw."},{"issue":"1\u20132","key":"1602_CR31","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). https:\/\/doi.org\/10.1007\/S10107-013-0632-5","journal-title":"Math. Program."},{"issue":"6","key":"1602_CR32","doi-asserted-by":"publisher","first-page":"1163","DOI":"10.1080\/10556788.2016.1245732","volume":"32","author":"EA Y\u0131ld\u0131r\u0131m","year":"2017","unstructured":"Y\u0131ld\u0131r\u0131m, E.A.: Inner approximations of completely positive reformulations of mixed binary quadratic programs: a unified analysis. Optimization Methods and Software 32(6), 1163\u20131186 (2017). https:\/\/doi.org\/10.1080\/10556788.2016.1245732","journal-title":"Optimization Methods and Software"},{"issue":"2","key":"1602_CR33","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(2), 383\u2013405 (2020). https:\/\/doi.org\/10.1007\/S10898-019-00861-3","journal-title":"J. Glob. Optim."},{"issue":"1","key":"1602_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10898-021-01066-3","volume":"82","author":"EA Y\u0131ld\u0131r\u0131m","year":"2022","unstructured":"Y\u0131ld\u0131r\u0131m, E.A.: An alternative perspective on copositive and convex relaxations of nonconvex quadratic programs. J. Glob. Optim. 82(1), 1\u201320 (2022). https:\/\/doi.org\/10.1007\/s10898-021-01066-3","journal-title":"J. Glob. Optim."},{"issue":"3","key":"1602_CR35","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1017\/S1446788700017250","volume":"30","author":"JM Borwein","year":"1981","unstructured":"Borwein, J.M., Wolkowicz, H.: Facial reduction for a cone-convex programming problem. Journal of the Australian Mathematical Society. Series A. Pure Mathematics and Statistics 30(3), 369\u2013380 (1981). https:\/\/doi.org\/10.1017\/S1446788700017250","journal-title":"Journal of the Australian Mathematical Society. Series A. Pure Mathematics and Statistics"},{"issue":"2","key":"1602_CR36","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1016\/0022-247X(81)90138-4","volume":"83","author":"J Borwein","year":"1981","unstructured":"Borwein, J., Wolkowicz, H.: Regularizing the abstract convex program. J. Math. Anal. Appl. 83(2), 495\u2013530 (1981). https:\/\/doi.org\/10.1016\/0022-247X(81)90138-4","journal-title":"J. Math. Anal. Appl."},{"key":"1602_CR37","doi-asserted-by":"publisher","unstructured":"Pataki, G.: Strong duality in conic linear programming: Facial reduction and extended duals. In: Bailey, D.H., Bauschke, H.H., Borwein, P., Garvan, F., Th\u00e9ra, M., Vanderwerff, J.D., Wolkowicz, H. (eds.) Computational and Analytical Mathematics, pp. 613\u2013634. Springer, New York, NY (2013). https:\/\/doi.org\/10.1007\/978-1-4614-7621-4_28","DOI":"10.1007\/978-1-4614-7621-4_28"},{"issue":"1","key":"1602_CR38","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/S10957-012-0219-Y","volume":"158","author":"H Waki","year":"2013","unstructured":"Waki, H., Muramatsu, M.: Facial reduction algorithms for conic optimization problems. J. Optim. Theory Appl. 158(1), 188\u2013215 (2013). https:\/\/doi.org\/10.1007\/S10957-012-0219-Y","journal-title":"J. Optim. Theory Appl."},{"key":"1602_CR39","unstructured":"Rockafellar, R.T.: Convex Analysis. Princeton Landmarks in Mathematics and Physics. Princeton University Press, Princeton, NJ"},{"key":"1602_CR40","doi-asserted-by":"publisher","unstructured":"Permenter, F., Parrilo, P.A.: Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone. Math. Program. 171(1\u20132), 1\u201354 (2018). https:\/\/doi.org\/10.1007\/S10107-017-1169-9","DOI":"10.1007\/S10107-017-1169-9"},{"issue":"2","key":"1602_CR41","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1561\/2400000011","volume":"3","author":"D Drusvyatskiy","year":"2017","unstructured":"Drusvyatskiy, D., Wolkowicz, H.: The many faces of degeneracy in conic optimization. Found. Trends Optim. 3(2), 77\u2013170 (2017). https:\/\/doi.org\/10.1561\/2400000011","journal-title":"Found. Trends Optim."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-026-01602-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-026-01602-z","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-026-01602-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T02:56:54Z","timestamp":1777085814000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-026-01602-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,10]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2026,4]]}},"alternative-id":["1602"],"URL":"https:\/\/doi.org\/10.1007\/s10898-026-01602-z","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,10]]},"assertion":[{"value":"19 August 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 February 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 March 2026","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"}}]}}