Extended Triangle Inequalities for Nonconvex Box-Constrained Quadratic Programming

Abstract

Let ${\mathrm{Box}}_{\mathrm{n}}=\{\mathrm{x}\in {\mathbb{R}}^{\mathrm{n}}:0\le \mathrm{x}\le \mathrm{e}\}$, and let ${\mathrm{QPB}}_{\mathrm{n}}$ denote the convex hull of $\{(1,x^{\prime }{)}^{\prime }(1,x^{\prime }):x\in {\mathrm{Box}}_{\mathrm{n}}\}$. The quadratic programming problem $\min \{x^{\prime }Qx+q^{\prime }x:x\in {\mathrm{Box}}_{\mathrm{n}}\}$ where $Q$ is not positive semidefinite (PSD), is equivalent to a linear optimization problem over ${\mathrm{QPB}}_{\mathrm{n}}$ and could be efficiently solved if a tractable characterization of ${\mathrm{QPB}}_{\mathrm{n}}$ was available. It is known that ${\mathrm{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 ${\mathrm{QPB}}_3$, but the PSD, RLT and TRI constraints together do not fully characterize ${\mathrm{QPB}}_3$. In this paper we describe new valid linear inequalities for ${\mathrm{QPB}}_{\mathrm{n}}$, $n\ge 3$ based on strengthening the approximation of ${\mathrm{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 ${\mathrm{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.