English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Globally optimizing a nonconvex quadratic over the intersection of $m$ ballsin $\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 constructedusing a disjunctive semidefinite formulation based essentially on two copies ofthe $m=1$ case. However, there is no known explicit, tractable, exact convexrepresentation for $m \ge 3$. In this paper, we construct a new, polynomiallysized semidefinite relaxation for all $m$, which does not employ a disjunctiveapproach. 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 existingrelaxations. The key idea of the relaxation is a simple lifting of the originalproblem into dimension $n+1$. Extending this construction: (i) we show thatnonconvex quadratic programming over $\|x\| \le \min \{ 1, g + h^T x \}$ has anexact semidefinite representation; and (ii) we construct a new relaxation forquadratic programming over the intersection of two ellipsoids, which globallysolves all instances of a benchmark collection from the literature.

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