Relaxing the optimality conditions of box QP

We present semidefinite relaxations of nonconvex, box‐constrained quadratic programming, which incorporate the first‐ and second‐order necessary optimality conditions, and establish theoretical relationships between the new relaxations and a basic semidefinite relaxation due to Shor. We compare these relaxations in the context of branch‐and‐bound to determine a global optimal solution, where it is shown empirically that the new relaxations are significantly stronger than Shor’s. An effective branching strategy is also developed.