Preprint
A Slightly Lifted Convex Relaxation for Nonconvex Quadratic Programming with Ball Constraints
03/02/2023
DOI: 10.48550/arxiv.2303.01624
Abstract
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.
Details
- Title: Subtitle
- A Slightly Lifted Convex Relaxation for Nonconvex Quadratic Programming with Ball Constraints
- Creators
- Samuel Burer
- Resource Type
- Preprint
- DOI
- 10.48550/arxiv.2303.01624
- Language
- English
- Date posted
- 03/02/2023
- Academic Unit
- Business Analytics
- Record Identifier
- 9984380606702771
Metrics
18 Record Views