Globally Solving Nonconvex Quadratic Programs via Linear Integer Programming Techniques

References

• Belotti P (2010) Couenne: A user’s manual. Technical report, Clemson University, Clemson, SC. Available at https://www.coin-or.org/Couenne/couenne-user-manual.pdf.Google Scholar
• Belotti P, Lee J, Liberti L, Margot F, Wachter 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) Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, MOS-SIAM Series on Optimization, vol. 2 (SIAM, Philadelphia).Crossref, Google Scholar
• Bertsekas D (1999) Nonlinear Programming (Athena Scientific, Belmont, MA).Google Scholar
• Bomze IM (1998) On standard quadratic optimization problems. J. Global Optim. 13(4):369–387.Crossref, Google Scholar
• Bomze IM, Frommlet F, Locatelli M (2010) Copositivity cuts for improving SDP bounds on the clique number. Math. Programming 124(1–2):13–32.Crossref, Google Scholar
• Bonami P, Günlük O, Linderoth J (2016a) Solving box-constrained nonconvex quadratic programs. Technical report, IBM, Armonk, NY.Google Scholar
• Bonami P, Lodi A, Schweiger J, Tramontani A (2016b) Solving standard quadratic programming by cutting planes. Technical Report DS4DM-2016-001, Polytechnique Montréal, Montréal.Google Scholar
• Boyd S, Vandenberghe L (2004) Convex Optimization (Cambridge University Press, Cambridge, UK).Google Scholar
• Bundfuss S, Dür M (2009) An adaptive linear approximation algorithm for copositive programs. SIAM J. Optim. 20(1):30–53.Crossref, 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 (2010) Optimizing a polyhedral-semidefinite relaxation of completely positive programs. Math. Programming Comput. 2(1):1–19.Crossref, Google Scholar
• Burer S, Vandenbussche D (2009) Globally solving box-constrained non-convex quadratic programs with semidefinite-based finite branch-and-bound. Comput. Optim. Appl. 43(2):181–195.Crossref, Google Scholar
• Chen J, Burer S (2012) Globally solving nonconvex quadratic programming problems via completely positive programming. Math. Programming Comput. 4(1):33–52.Crossref, Google Scholar
• Dobre C, Vera JC (2015) Exploiting symmetry in copositive programs via semidefinite hierarchies. Math. Programming 151(2):659–680.Crossref, Google Scholar
• Dong HB, Anstreicher K (2013) Separating doubly nonnegative and completely positive matrices. Math. Programming 137(1/2):131–153.Crossref, Google Scholar
• Dür M (2010) Copositive programming—A survey. Diehl M, Glineur F, Jarlebring E, Michiels W, eds. Recent Advances in Optimization and its Applications in Engineering (Springer, Berlin), 3–20.Crossref, Google Scholar
• Eustaquio RG, Elizabeth KW, Ademir RA (2008) Constraint qualifications for nonlinear programming. Technical report, Federal University of Parana, Curitiba, Brazil.Google Scholar
• Floudas CA, Visweswaran V (1990) A global optimization algorithm (GOP) for certain classes of nonconvex NLPs—I. Theory. Comput. Chemical Engrg. 14(12):1397–1417.Crossref, Google Scholar
• Gao DY (2004) Canonical duality theory and solutions to constrained nonconvex quadratic programming. J. Global Optim. 29(4):377–399.Crossref, Google Scholar
• Giannessi F, Tomasin E (1973) Nonconvex quadratic programs, linear complementarity problems, and integer linear programs. Conti R, Ruberti A, eds. Fifth Conference on Optimization Techniques Part 1, Lecture Notes in Computer Science, vol. 3 (Springer, Berlin), 437–449.Crossref, Google Scholar
• Gould NIM, Orban D, Toint PL (2003) CUTEr and SifDec: A constrained and unconstrained testing environment, revisited. ACM Trans. Math. Software 29(4):373–394.Crossref, Google Scholar
• Güler O, Hoffman AJ, Rothblum UG (1995) Approximations to solutions to systems of linear inequalities. SIAM J. Matrix Anal. Appl. 16(2):688–696.Crossref, Google Scholar
• Hansen P, Jaumard B, Ruiz M, Xiong J (1993) Global minimization of indefinite quadratic functions subject to box constraints. Naval Res. Logist. 40(3):373–392.Crossref, Google Scholar
• Hoffman AJ (2003) On approximate solutions of systems of linear inequalities. Micchelli CA, ed. Selected Papers of Alan J Hoffman: With Commentary (World Scientific Publishing, Singapore), 174–176.Crossref, Google Scholar
• Horst R, Pardalos PM Thoai NV (2000) Introduction to Global Optimization, 2nd ed. (Kluwer, Dortrecht, Netherlands).Crossref, Google Scholar
• Hu J, Mitchell JE, Pang JS, Yu B (2012) On linear programs with linear complementarity constraints. J. Global Optim. 53(1):29–51.Crossref, Google Scholar
• IBM (2010) IBM ILOG CPLEX Optimization Studio CPLEX user's manual, version 12, release 6. Accessed February 12, 2019, https://www.ibm.com/support/knowledgecenter/SSSA5P_12.6.2/ilog.odms.studio.help/pdf/usrcplex.pdf.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
• Kim S, Kojima M (2003) Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxations. Comput. Optim. Appl. 26(2):143–154.Crossref, Google Scholar
• Mangasarian OL (1981) A condition number for linear inequalities and linear programs. Technical Report 2231, Mathematics Research Center, University of Wisconsin–Madison, Madison.Google Scholar
• Misener R, Floudas CA (2013) GloMIQO: Global mixed-integer quadratic optimizer. J. Global Optim. 57(1):3–50.Crossref, Google Scholar
• Motzkin TS, Straus EG (1965) Maxima for graphs and a new proof of a theorem of Turán. Canadian J. Math. 17(4):533–540.Crossref, Google Scholar
• Nesterov Y (1998) Semidefinite relaxation and nonconvex quadratic optimization. Optim. Methods Software 9(1–3):141–160.Crossref, Google Scholar
• Pardalos PM, Vavasis SA (1991) Quadratic programming with one negative eigenvalue is NP-hard. J. Global Optim. 1(1):15–22.Crossref, Google Scholar
• Peña J, Vera J, Zuluaga LF (2018) An algorithm to compute the Hoffman constant of a system of linear constraints. Working paper, Tillburg University, Tillburg, Netherlands.Google Scholar
• Renegar J (2001) A Mathematical View of Interior-Point Methods in Convex Optimization, MOS-SIAM Series on Optimization, vol. 3 (SIAM, Philadelphia).Crossref, Google Scholar
• Sahinidis NV (1996) BARON: A general purpose global optimization software package. J. Global Optim. 8(2):201–205.Crossref, Google Scholar
• Scozzari A, Tardella F (2008) A clique algorithm for standard quadratic programming. Discrete Appl. Math. 156(13):2439–2448.Crossref, Google Scholar
• Sherali H, Adams W (1994) A hierarchy of relaxations for mixed-integer zero-one programming problems. Discrete Appl. Math. 52(1):83–106.Crossref, 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
• Vanderbei RJ, Shanno DF (1999) An interior-point algorithm for nonconvex nonlinear programming. Comput. Optim. Appl. 13(1–3):231–252.Crossref, Google Scholar
• Zheng XY, Ng KF (2004) Hoffman’s least error bounds for systems of linear inequalities. J. Global Optim. 30(4):391–403.Crossref, Google Scholar