SDP-quality bounds via convex quadratic relaxations for global optimization of mixed-integer quadratic programs

Carlos Nohra(nohramerl.com)
Arvind Raghunathan(raghunathanmerl.com)
Nikolaos Sahinidis(nikosgatech.edu)

Abstract: We consider the global optimization of nonconvex mixed-integer quadratic programs with linear equality constraints. In particular, we present a new class of convex quadratic relaxations which are derived via quadratic cuts. To construct these quadratic cuts, we solve a separation problem involving a linear matrix inequality with a special structure that allows the use of specialized solution algorithms. Our quadratic cuts are nonconvex, but define a convex feasible set when intersected with the equality constraints. We show that our relaxations are an outer-approximation of a semi-infinite convex program which under certain conditions is equivalent to a well-known semidefinite program relaxation. The new relaxations are implemented in the global optimization solver BARON, and tested by conducting numerical experiments on a large collection of problems. Results demonstrate that, for our test problems, these relaxations lead to a significant improvement in the performance of BARON.

Keywords: Global optimization, Mixed-integer quadratic programs, Semidefinite programming relaxations, Convex quadratic relaxations, Quadratic cuts

Category 1: Global Optimization

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Citation: arXiv:2106.13721 (2021)

Download: [PDF]

Entry Submitted: 06/27/2021
Entry Accepted: 06/28/2021
Entry Last Modified: 06/27/2021

Modify/Update this entry