Globally Solving Nonconvex Quadratic Programs via Linear Integer Programming Techniques

Wei Xia (), Juan C. Vera () and Luis F. Zuluaga ()
Additional contact information
Wei Xia: Industrial and Systems Engineering Department, Lehigh University, Bethlehem, Pennsylvania 18015;
Juan C. Vera: Tilburg School of Economics and Management, Econometrics and Operations Research, Tilburg University, 5037 AB Tilburg, Netherlands
Luis F. Zuluaga: Industrial and Systems Engineering Department, Lehigh University, Bethlehem, Pennsylvania 18015;

INFORMS Journal on Computing, 2020, vol. 32, issue 1, 40-56

Abstract: We reformulate a (indefinite) quadratic program (QP) as a mixed-integer linear programming (MILP) problem by first reformulating a QP as a linear complementary problem, and then using binary variables and big-M constraints to model its complementary constraints. To obtain such reformulation, we use fundamental results on the solution of perturbed linear systems to impose bounds on the QP’s dual variables without eliminating any of its (globally) optimal primal solutions. Reformulating a nonconvex QP as a MILP problem allows the use of current state-of-the-art MILP solvers to find its global optimal solution. To illustrate this, we compare the performance of this MILP-based solution approach, labeled quadprogIP, with quadprogBB, BARON, and CPLEX. In practice, quadprogIP is shown to typically outperform by orders of magnitude quadprogBB, BARON, and CPLEX on standard QPs. Also, unlike quadprogBB, quadprogIP is able to solve QP instances in which the dual feasible set is unbounded. The MATLAB code quadprogIP and the instances used to perform the reported numerical experiments are publicly available at https://github.com/xiawei918/quadprogIP .

Keywords: non-convex quadratic programming; global optimization; mixed-integer linear programming; KKT conditions; branch and bound; Hoffman bound (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0883 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:32:y:2020:i:1:p:40-56

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().