Asymptotically Tight MILP Approximations for a Nonconvex QCP

References

• Al-Khayyal FA, Larsen C, Van Voorhis T (1995) A relaxation method for nonconvex quadratically constrained quadratic programs. J. Global Optim. 6(3):215–230.Crossref, Google Scholar
• Audet C, Hansen P, Jaumard B, Savard G (2000) A branch and cut algorithm for nonconvex quadratically constrained quadratic programming. Math. Programming 87(1):131–152.Crossref, Google Scholar
• Bach FR, Lanckriet GR, Jordan MI (2004) Multiple kernel learning, conic duality, and the SMO algorithm. Brodley C, ed. ICML ‘04 Proc. 21st Internat. Conf. Machine Learn. (Association for Computing Machinery, New York), 6.Google Scholar
• Ban G-Y, El Karoui N, Lim AE (2018) Machine learning and portfolio optimization. Management Sci. 64(3):1136–1154.Link, Google Scholar
• Bao X, Sahinidis NV, Tawarmalani M (2009) Multiterm polyhedral relaxations for nonconvex, quadratically constrained quadratic programs. Optim. Methods Software 24(4–5):485–504.Crossref, Google Scholar
• Bao X, Sahinidis NV, Tawarmalani M (2011) Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons. Math. Programming 129(1):129–157.Crossref, Google Scholar
• Belotti P, Lee J, Liberti L, Margot F, Wächter A (2009) Branching and bounds tightening techniques for non-convex MINLP. Optim. Methods Software 24(4–5):597–634.Crossref, Google Scholar
• Ben-Tal A, Nemirovski A (2001) On polyhedral approximations of the second-order cone. Math. Oper. Res. 26(2):193–205.Link, Google Scholar
• Bestuzheva K, Besançon 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.Google Scholar
• Burer S (2009) On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Programming 120(2):479–495.Crossref, Google Scholar
• Burer S, Anstreicher KM (2013) Second-order-cone constraints for extended trust-region subproblems. SIAM J. Optim. 23(1):432–451.Crossref, Google Scholar
• Burer S, Vandenbussche D (2008) A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Math. Programming 113(2):259–282.Crossref, Google Scholar
• Burer S, Yang B (2015) The trust region subproblem with non-intersecting linear constraints. Math. Programming 149(1–2):253–264.Crossref, Google Scholar
• Cain MB, O’Neill RP, Castillo A (2012) History of optimal power flow and formulations. Staff paper, Federal Energy Regulatory Commission, Washington, DC.Google Scholar
• De Maio A, Huang Y, Palomar DP, Zhang S, Farina A (2011) Fractional QCQP with applications in ML steering direction estimation for radar detection. IEEE Trans. Signal Processing 59(1):172–185.Crossref, Google Scholar
• Dong H, Luo Y (2018) Compact disjunctive approximations to nonconvex quadratically constrained programs. Preprint, submitted November 20, https://arxiv.org/abs/1811.08122.Google Scholar
• Gurobi (2024) Gurobi Optimizer reference manual. Accessed April 5, 2024, https://docs.gurobi.com/projects/optimizer/en/current/index.html.Google Scholar
• Huang Y, Palomar DP (2014) Randomized algorithms for optimal solutions of double-sided QCQP with applications in signal processing. IEEE Trans. Signal Processing 62(5):1093–1108.Crossref, Google Scholar
• Jiang R, Li D (2019) Second order cone constrained convex relaxations for nonconvex quadratically constrained quadratic programming. J. Global Optim. 75(2):461–494.Crossref, Google Scholar
• 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.Google Scholar
• 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.Google Scholar
• Kim S, Kojima M (2001) Second order cone programming relaxation of nonconvex quadratic optimization problems. Optim. Methods Software 15(3–4):201–224.Crossref, Google Scholar
• Lin Y, Schrage L (2009) The global solver in the LINDO API. Optim. Methods Software 24(4–5):657–668.Crossref, Google Scholar
• Linderoth J (2005) A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs. Math. Programming 103(2):251–282.Crossref, Google Scholar
• Misener R, Floudas CA (2012) Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations. Math. Programming 136(1):155–182.Crossref, Google Scholar
• Misener R, Floudas CA (2013) GloMIQO: Global mixed-integer quadratic optimizer. J. Global Optim. 57(1):3–50.Crossref, Google Scholar
• Misener R, Floudas CA (2014) Antigone: Algorithms for continuous/integer global optimization of nonlinear equations. J. Global Optim. 59(2–3):503–526.Crossref, Google Scholar
• Poljak S, Rendl F, Wolkowicz H (1995) A recipe for semidefinite relaxation for (0, 1)-quadratic programming: In memory of Svata Poljak. J. Global Optim. 7(1):51–73.Crossref, Google Scholar
• Sahinidis NV (1996) BARON: A general purpose global optimization software package. J. Global Optim. 8(2):201–205.Crossref, Google Scholar
• Sherali HD (2007) RLT: A unified approach for discrete and continuous nonconvex optimization. Ann. Oper. Res. 149(1):185–193.Crossref, Google Scholar
• Sherali HD, Adams WP (2013) A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems, Nonconvex Optimization and Its Applications, vol. 31 (Springer Science & Business Media, New York).Google Scholar
• Shor NZ (1987) Quadratic optimization problems. Soviet J. Comput. Systems Sci. 25(6):1–11.Google Scholar
• Shor NZ (1990) Dual quadratic estimates in polynomial and Boolean programming. Ann. Oper. Res. 25(1):163–168.Crossref, Google Scholar
• Shor NZ (1992) Dual estimates in multiextremal problems. J. Global Optim. 2(4):411–418.Crossref, Google Scholar
• Sturm JF, Zhang S (2003) On cones of nonnegative quadratic functions. Math. Oper. Res. 28(2):246–267.Link, Google Scholar
• Tawarmalani M, Sahinidis NV (2004) Global optimization of mixed-integer nonlinear programs: A theoretical and computational study. Math. Programming 99(3):563–591.Crossref, Google Scholar
• Vielma JP, Dunning I, Huchette J, Lubin M (2017) Extended formulations in mixed integer conic quadratic programming. Math. Programming Comput. 9(3):369–418.Crossref, Google Scholar
• Virtanen P, Gommers R, Oliphant TE, Haberland M, Reddy T, Cournapeau D, Burovski E, et al. (2020) SciPy 1.0: Fundamental algorithms for scientific computing in Python. Nature Methods 17(3):261–272.Crossref, Google Scholar
• Wolkowicz H (2000) Semidefinite and Lagrangian relaxations for hard combinatorial problems. Powell MJD, Scholtes S, eds. System Modelling and Optimization (Springer, New York), 269–309.Google Scholar
• Xia W, Vera JC, Zuluaga LF (2020) Globally solving nonconvex quadratic programs via linear integer programming techniques. INFORMS J. Comput. 32(1):40–56.Link, Google Scholar
• Xiang Z, Tao M (2012) Robust beamforming for wireless information and power transmission. IEEE Wireless Comm. Lett. 1(4):372–375.Crossref, Google Scholar
• Zang Y, Zhu H (2022a) An eigenvalue decomposition method for low-rank and non-convex quadratically constrained quadratic programming. Chen Y, ed. 2022 IEEE 6th Adv. Inform. Tech. Electronic Automation Control Conf. (IAEAC) (IEEE, New York), 558–563.Google Scholar
• Zang Y, Zhu H (2022b) Fast and optimal joint decision and estimation by quantized data via noisy channels of sensor networks. Signal Processing 195:108481.Crossref, Google Scholar
• Zhang YJA, So AM-C (2011) Optimal spectrum sharing in MIMO cognitive radio networks via semidefinite programming. IEEE J. Selected Areas Comm. 29(2):362–373.Crossref, Google Scholar
• Zien A, Ong CS (2007) Multiclass multiple kernel learning. Ghahramani Z, ed. Proc. 24th Internat. Conf. Machine Learn. (Association for Computing Machinery, New York), 1191–1198.Google Scholar