\(\)
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.
Article
View A Slightly Lifted Convex Relaxation for Nonconvex Quadratic Programming with Ball Constraints