Globally solving non-convex quadratic programs via linear integer programming techniques

Wei Xia, J. C. Vera, Luis F. Zuluaga

Research output: Contribution to journalArticleScientificpeer-review

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.
Original languageEnglish
Number of pages22
JournalINFORMS Journal on Computing
Early online dateJul 2019
DOIs
Publication statusE-pub ahead of print - Jul 2019

Fingerprint

Integer programming
Linear programming
MATLAB
Linear systems
Integer linear programming
Mixed integer linear programming
Experiments
Optimal solution

Keywords

  • non-convex quadratic programming
  • global optimization
  • mixed-integer linear optimization
  • KKT conditions
  • branch and bound
  • Hoffman bound

Cite this

@article{24cafe9b771e4c1a85fcc9766f52d2e2,
title = "Globally solving non-convex quadratic programs via linear integer programming techniques",
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 optimization, KKT conditions, branch and bound, Hoffman bound",
author = "Wei Xia and Vera, {J. C.} and Zuluaga, {Luis F.}",
year = "2019",
month = "7",
doi = "10.1287/ijoc.2018.0883",
language = "English",
journal = "INFORMS Journal on Computing",
issn = "1091-9856",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",

}

Globally solving non-convex quadratic programs via linear integer programming techniques. / Xia, Wei; Vera, J. C.; Zuluaga, Luis F.

In: INFORMS Journal on Computing, 07.2019.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Globally solving non-convex quadratic programs via linear integer programming techniques

AU - Xia, Wei

AU - Vera, J. C.

AU - Zuluaga, Luis F.

PY - 2019/7

Y1 - 2019/7

N2 - 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.

AB - 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.

KW - non-convex quadratic programming

KW - global optimization

KW - mixed-integer linear optimization

KW - KKT conditions

KW - branch and bound

KW - Hoffman bound

U2 - 10.1287/ijoc.2018.0883

DO - 10.1287/ijoc.2018.0883

M3 - Article

JO - INFORMS Journal on Computing

JF - INFORMS Journal on Computing

SN - 1091-9856

ER -