{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T18:44:21Z","timestamp":1776105861186,"version":"3.50.1"},"reference-count":45,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["INFORMS Journal on Computing"],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:p>Nonconvex quadratically constrained programs (QCPs) are generally NP-hard and challenging problems. In this paper, we propose two novel mixed-integer linear programming (MILP) approximations for a nonconvex QCP. Our method begins by utilizing an eigenvalue-based decomposition to express the nonconvex quadratic function as the difference of two convex functions. We then introduce an additional variable to partition each nonconvex constraint into a second-order cone (SOC) constraint and the complement of an SOC constraint. We employ two polyhedral approximation approaches to approximate the SOC constraint. The complement of an SOC constraint is approximated using a combination of linear and complementarity constraints. As a result, we approximate the nonconvex QCP with two linear programs with complementarity constraints (LPCCs). More importantly, we prove that the optimal values of the LPCCs asymptotically converge to that of the original nonconvex QCP. By proving the boundedness of the LPCCs, we further reformulate the LPCCs as MILPs. We demonstrate the effectiveness of our approaches via numerical experiments by applying our proposed approximations to randomly generated instances and two application problems: the joint decision and estimation problem and the two-trust-region subproblem. The numerical results show significant advantages of our approaches in terms of solution quality and computational time compared with existing benchmark approaches.<\/jats:p>\n                  <jats:p>History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods &amp; Analysis.<\/jats:p>\n                  <jats:p>Funding: K. Pan was supported in part by the Research Grants Council of Hong Kong [Grant 15503723]. J. Cheng and B. Yang were supported in part by the Office of Naval Research [Grant N00014-20-1-2154]. J. Cheng was supported in part by the National Science Foundation [Grant ECCS-2404412]. B. Yang was supported in part by the Air Force Office of Scientific Research [Grant FA9550-23-1-0508].<\/jats:p>\n                  <jats:p>Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https:\/\/pubsonline.informs.org\/doi\/suppl\/10.1287\/ijoc.2024.0719 ) as well as from the IJOC GitHub software repository ( https:\/\/github.com\/INFORMSJoC\/2024.0719 ). The complete IJOC Software and Data Repository is available at https:\/\/informsjoc.github.io\/ .<\/jats:p>","DOI":"10.1287\/ijoc.2024.0719","type":"journal-article","created":{"date-parts":[[2025,5,12]],"date-time":"2025-05-12T12:30:07Z","timestamp":1747053007000},"page":"568-589","source":"Crossref","is-referenced-by-count":1,"title":["Asymptotically Tight MILP Approximations for a Nonconvex QCP"],"prefix":"10.1287","volume":"38","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9766-3518","authenticated-orcid":false,"given":"Shiyi","family":"Jiang","sequence":"first","affiliation":[{"name":"Faculty of Business, The Hong Kong Polytechnic University, Kowloon, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3358-9176","authenticated-orcid":false,"given":"Jianqiang","family":"Cheng","sequence":"additional","affiliation":[{"name":"College of Engineering, University of Arizona, Tucson, Arizona 85721"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2127-5348","authenticated-orcid":false,"given":"Kai","family":"Pan","sequence":"additional","affiliation":[{"name":"Faculty of Business, The Hong Kong Polytechnic University, Kowloon, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6760-9054","authenticated-orcid":false,"given":"Boshi","family":"Yang","sequence":"additional","affiliation":[{"name":"School of Mathematical and Statistical Sciences, Clemson University, Clemson, South Carolina 29634"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01099462"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1007\/s101079900106"},{"key":"B3","doi-asserted-by":"crossref","unstructured":"Bach FR, Lanckriet GR, Jordan MI (2004) Multiple kernel learning, conic duality, and the SMO algorithm. Brodley C, ed.\n                      ICML \u201804 Proc. 21st Internat. Conf. Machine Learn.\n                      (Association for Computing Machinery, New York), 6.","DOI":"10.1145\/1015330.1015424"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.2016.2644"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1080\/10556780902883184"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0462-2"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1080\/10556780903087124"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1287\/moor.26.2.193.10561"},{"key":"B9","unstructured":"Bestuzheva K, Besan\u00e7on M, Chen W-K, Chmiela A, Donkiewicz T, van Doornmalen J, Eifler L, et al. (2021) The SCIP optimization suite 8.0. Preprint, submitted December 16, https:\/\/arxiv.org\/abs\/2112.08872."},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-008-0223-z"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1137\/110826862"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0080-6"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0749-1"},{"key":"B14","unstructured":"Cain MB, O\u2019Neill RP, Castillo A (2012) History of optimal power flow and formulations. Staff paper, Federal Energy Regulatory Commission, Washington, DC."},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2010.2087327"},{"key":"B16","unstructured":"Dong H, Luo Y (2018) Compact disjunctive approximations to nonconvex quadratically constrained programs. Preprint, submitted November 20, https:\/\/arxiv.org\/abs\/1811.08122."},{"key":"B17","unstructured":"Gurobi (2024) Gurobi Optimizer reference manual. Accessed April 5, 2024, https:\/\/docs.gurobi.com\/projects\/optimizer\/en\/current\/index.html."},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2013.2297683"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-019-00793-y"},{"key":"B20","doi-asserted-by":"crossref","unstructured":"Jiang S, Cheng J, Pan K, Yang B (2025) Asymptotically tight MILP approximations for a nonconvex QCP. https:\/\/doi.org\/10.1287\/ijoc\/2024.0719.cd, https:\/\/github.com\/INFORMSJoC\/2024.0719.","DOI":"10.1287\/ijoc.2024.0719"},{"key":"B21","unstructured":"Kannan R, Nagarajan H, Deka D (2022) Learning to accelerate the global optimization of quadratically-constrained quadratic programs. Preprint, submitted December 31, https:\/\/arxiv.org\/abs\/2301.00306."},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1080\/10556780108805819"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1080\/10556780902753221"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0582-7"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-012-0555-6"},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-012-9874-7"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-014-0166-2"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1007\/BF01100205"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1007\/BF00138693"},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-006-0107-7"},{"key":"B31","volume-title":"A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems,","volume":"31","author":"Sherali HD","year":"2013"},{"key":"B32","first-page":"1","volume":"25","author":"Shor NZ","year":"1987","journal-title":"Soviet J. Comput. Systems Sci."},{"key":"B33","doi-asserted-by":"publisher","DOI":"10.1007\/BF02283692"},{"key":"B34","doi-asserted-by":"publisher","DOI":"10.1007\/BF00122430"},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1287\/moor.28.2.246.14485"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0467-6"},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-016-0113-y"},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.1038\/s41592-019-0686-2"},{"key":"B39","doi-asserted-by":"crossref","unstructured":"Wolkowicz H (2000) Semidefinite and Lagrangian relaxations for hard combinatorial problems. Powell MJD, Scholtes S, eds.\n                      System Modelling and Optimization\n                      (Springer, New York), 269\u2013309.","DOI":"10.1007\/978-0-387-35514-6_13"},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2018.0883"},{"key":"B41","doi-asserted-by":"publisher","DOI":"10.1109\/WCL.2012.053112.120212"},{"key":"B42","doi-asserted-by":"crossref","unstructured":"Zang Y, Zhu H (2022a) An eigenvalue decomposition method for low-rank and non-convex quadratically constrained quadratic programming. Chen Y, ed.\n                      2022 IEEE 6th Adv. Inform. Tech. Electronic Automation Control Conf. (IAEAC)\n                      (IEEE, New York), 558\u2013563.","DOI":"10.1109\/IAEAC54830.2022.9929567"},{"key":"B43","doi-asserted-by":"publisher","DOI":"10.1016\/j.sigpro.2022.108481"},{"key":"B44","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2011.110209"},{"key":"B45","doi-asserted-by":"crossref","unstructured":"Zien A, Ong CS (2007) Multiclass multiple kernel learning. Ghahramani Z, ed.\n                      Proc. 24th Internat. Conf. Machine Learn.\n                      (Association for Computing Machinery, New York), 1191\u20131198.","DOI":"10.1145\/1273496.1273646"}],"container-title":["INFORMS Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/ijoc.2024.0719","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T08:23:23Z","timestamp":1776068603000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/ijoc.2024.0719"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["10.1287\/ijoc.2024.0719"],"URL":"https:\/\/doi.org\/10.1287\/ijoc.2024.0719","relation":{},"ISSN":["1091-9856","1526-5528"],"issn-type":[{"value":"1091-9856","type":"print"},{"value":"1526-5528","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3]]}}}