# A Slightly Lifted Convex Relaxation for Nonconvex Quadratic Programming with Ball Constraints



Globally optimizing a nonconvex quadratic over the intersection of $$m$$ balls in $$\mathbb{R}^n$$ is known to be polynomial-time solvable for fixed $$m$$. Moreover, when $$m=1$$, the standard semidefinite relaxation is exact, and when $$m=2$$, it has recently been shown that an exact relaxation can be constructed via a disjunctive semidefinite formulation based on essentially two copies of the $$m=1$$ case. However, there is no known explicit, tractable, exact convex representation for $$m \ge 3$$. In this paper, we construct a new, polynomially sized semidefinite relaxation for all $$m$$, and we demonstrate empirically that it is quite strong compared to existing relaxations, although still not exact for all objectives. The key idea is a simple lifting of the original problem into dimension $$n+1$$. Related to this construction, we also show that nonconvex quadratic programming over $$\|x\| \le \min \{ 1, g + h^T x \}$$, which arises for example as a substructure in the alternating current optimal power flow problem, has an exact semidefinite representation.