\(\)

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. When $m=2$, it has been shown recently that an

exact relaxation can be constructed using a disjunctive semidefinite

formulation based essentially on 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$, which does not employ a disjunctive

approach. We show that our relaxation is exact for $m=2$. Then, for

$m \ge 3$, we demonstrate empirically that it is fast and strong

compared to existing relaxations. The key idea of the relaxation is a

simple lifting of the original problem into dimension $n+1$. Extending

this construction: (i) we show that nonconvex quadratic programming

over $\|x\| \le \min \{ 1, g + h^T x \}$ has an exact semidefinite

representation; and (ii) we construct a new relaxation for quadratic

programming over the intersection of two ellipsoids, which globally

solves all instances of a benchmark collection from the literature.

## Article

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