We seek the global minimum of a quadratic function f with box constrained variables. For this goal, we underestimate f by a convex piecewise-quadratic function defined as the maximum of \(p\ge 1\) convex quadratic functions (p underestimators). We show that when \(p\rightarrow \infty \) the optimal solution of this relaxation converges to an optimal solution of the strong “Shor plus RLT” semi-definite relaxation of the initial problem. To compute the new relaxation, we introduce an iterative algorithm that adds convex quadratic cuts (or cutting-quadrics) one by one in a cutting plane fashion. The resulting convexification is tighter than the one produced by previous related methods that use \(p=1\) , i.e., using multiple underestimators leads to a stronger convexification than using a unique one (as in past work). Its integration into a spatial branch-and-bound algorithm brings a second advantage: compared to previous work, we can refine the lower bound at each node of the branching tree. This is because we are able to compute underestimators that act specifically on any particular node of the branching tree. Numerical results show that even a small value of \(p\in \{2, 3\}\) can often be enough to reduce the branching tree size by half compared to sticking to \(p=1\) . The resulting algorithm is also competitive in terms of CPU time compared to well-established solvers that rely on other techniques.
