Optimization Online


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

Carlos Nohra(nohra***at***merl.com)
Arvind Raghunathan(raghunathan***at***merl.com)
Nikolaos Sahinidis(nikos***at***gatech.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society