Quadratic programs with box constraints involve minimizing a possibly nonconvex quadratic function subject to lower and upper bounds on each variable. This is a well-known NP-hard problem that frequently arises in various applications. We focus on two convex relaxations, namely the RLT (Reformulation-Linearization Technique) relaxation and the SDP-RLT relaxation obtained by adding semidefinite constraints to the RLT relaxation. Both relaxations yield lower bounds on the optimal value of a quadratic program with box constraints. We present complete algebraic descriptions of the set of instances that admit exact RLT relaxations as well as those that admit exact SDP-RLT relaxations. We show that our
descriptions can be converted into algorithms for efficiently constructing instances with exact or inexact relaxations.
Citation
Technical Report, School of Mathematics, The University of Edinburgh, Edinburgh, Scorland, United Kingdom
Article
View On Exact and Inexact RLT and SDP-RLT Relaxations of Quadratic Programs with Box Constraints