Extended Triangle Inequalities for Nonconvex Box-Constrained Quadratic Programming

Let Box_n = {x in R^n : 0<= x <= e }, and let QPB_n denote the convex hull of {(1, x’)'(1, x’) : x  in Box_n}. The quadratic programming problem min{x’Q x + q’x : x in Box_n} where Q is not positive semidefinite (PSD), is equivalent to a linear optimization problem over QPB_n and could be efficiently solved if a tractable characterization of  QPB_n was available. It is known that QPB_2 can be represented using a PSD constraint combined with constraints generated using the reformulation-linearization technique (RLT). The triangle (TRI) inequalities are also valid for QPB_3, but the PSD, RLT and TRI constraints together do not fully characterize QPB_3. In this paper we describe new valid linear inequalities for QPB_n, n >= 3 based on strengthening the approximation of QPB_3 given by the PSD, RLT and TRI constraints. These new inequalities are generated in a systematic way using a known disjunctive characterization for QPB_3. We also describe a conic strengthening of the linear inequalities that incorporates second-order cone constraints. We show computationally that the new inequalities and their conic strengthenings obtain exact solutions for some nonconvex box-constrained instances that are not solved exactly using the PSD, RLT and TRI constraints.

Article

Download

View PDF