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

Samuel Burer Department of Business Analytics, University of Iowa, Iowa City,
IA, 52242–1994, USA. Email<EMAIL_ADDRESS>
(February 28, 2023)

###### 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\geq 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\|\leq\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.

##  1 Introduction

We study the nonconvex optimization problem

$\min_{x\in\mathbb{R}^{n}}\left\\{x^{T}Qx+2\,q^{T}x:\begin{array}[]{l}\|x-c_{i}\|\leq\rho_{i}\quad\forall\
i=1,\ldots,m\end{array}\right\\},$ (QP)

where the data are the $n\times n$ symmetric matrix $Q$, column vectors
$q,c_{1},\ldots,c_{m}\in\mathbb{R}^{n}$, and positive scalars
$\rho_{1},\ldots,\rho_{m}\in\mathbb{R}$. In words, (QP) is nonconvex quadratic
programming over the intersection of $m$ balls in $n$-dimensional space.
Without loss of generality, we assume $c_{1}=0$ and $\rho_{1}=1$, i.e., the
first constraint is the unit ball. Note that, while the feasible set of (QP)
is convex, the objective function is generally nonconvex since $Q$ may not be
positive semidefinite. We assume that (QP) is feasible and hence has an
optimal solution, and we are specifically interested in strong convex
relaxations of (QP).

Although (QP) is polynomial-time solvable to within $\epsilon$-accuracy for
fixed $m$ [6], there is no known exact convex relaxation for all $m$. By
exact, we mean a relaxation with optimal value equal to that of (QP). When
$m=1$, the standard semidefinite (SDP) relaxation is exact [21]. This
relaxation is often called the Shor relaxation and involves a single
$(n+1)\times(n+1)$ positive semidefinite variable. For $m=2$, Kelly et al.
[18] have recently shown that a particular disjunctive semidefinite relaxation
is exact. Their construction is based on essentially two copies of the $m=1$
case, and as a result, it utilizes two $(n+1)\times(n+1)$ positive
semidefinite variables. These and other SDP relaxations will be detailed in
Section 2. Our goals in this paper are: (i) to construct a new, stronger, non-
disjunctive SDP relaxation, which is polynomially sized in $n$ and $m$; and
(ii) to demonstrate its effectiveness empirically. In particular, by non-
disjunctive, we mean that the SDP optimizes over just one semidefinite
variable like the Shor relaxation but with additional constraints on that
matrix variable.

Another line of research examines conditions on the data of (QP) under which
the Shor relaxation is exact. Note that, without loss of generality, by an
orthogonal rotation in the $x$ space, $Q$ may be assumed to be diagonal. In
this case, (QP) is a special case of a diagonal quadratically constrained
quadratic program (diagonal QCQP), that is, a QCQP in which every quadratic
function has a diagonal Hessian. Diagonal QCQPs are well studied in the
literature [12, 13, 19, 25, 4], where it is known, for example, that the Shor
relaxation of (QP) is exact if
$\text{sign}(q_{j})=-\text{sign}(c_{1j})=\cdots=-\text{sign}(c_{mj})$ for all
$j=1,\ldots,n$ [23]. In this paper, however, we seek a relaxation that is
strong irrespective of the data.

(QP) can also be solved globally using any of the high-quality global-
optimization algorithms and software packages available today. We are also
aware of several papers studying global approaches for (QP) that take into
account the problem’s specific structure [7, 5, 1]. Each of these papers uses
some combination of enumeration and lower bounding to find a global optimal
solution and verify its optimality. In contrast, we are interested in
computing a single strong bound, and we will show that our relaxation is
frequently strong enough to deliver a global optimal solution via a rank-1 SDP
optimal solution. Moreover, in future research, our relaxation could certainly
be used as the lower-bounding technique within an enumerative scheme to solve
(QP) globally, but we leave this for future research.

As we began this project, we were motivated by the idea of constructing an
exact relaxation for (QP). Given that (QP) is only known to be polynomial-time
for fixed $m$—not as a function of $m$—it was unclear whether a given
relaxation, which is polynomial in $m$, could possibly be exact for all $m$.
Nevertheless, we still had hope for the case $m=2$. Ultimately, we will show
by experimentation that our construction is not exact for $m=2$ and hence for
all $m$; see Section 4. Even still, we believe that our new relaxation makes
significant progress towards approximating (QP) as we demonstrate empirically.

Our approach is based on two simple transformations of the feasible set of
(QP). First, we write the feasible set in the equivalent form

$\left\\{x\in\mathbb{R}^{n}:\|x\|\leq\sqrt{\rho_{i}^{2}-c_{i}^{T}c_{i}+2c_{i}^{T}x}\quad\forall\
i=1,\ldots,m\right\\}.$

Note that the $i$-th constraint here is equivalent to the rotated second-order
cone condition $x^{T}x\leq\rho_{i}^{2}-c_{i}^{T}c_{i}+2c_{i}^{T}x$. Second, we
introduce an auxiliary variable $\beta\in\mathbb{R}$, which is inserted within
each constraint:

$\left\\{{x\choose\beta}\in\mathbb{R}^{n+1}:\begin{array}[]{l}\|x\|\leq\beta\\\
\beta\leq\sqrt{\rho_{i}^{2}-c_{i}^{T}c_{i}+2c_{i}^{T}x}\quad\forall\
i=1,\ldots,m\end{array}\right\\}.$

Here, $\beta\leq\sqrt{\rho_{i}^{2}-c_{i}^{T}c_{i}+2c_{i}^{T}x}$ can be modeled
using a rotated second-order cone of size $3$. We can then equivalently
minimize $x^{T}Qx+2q^{T}x$ over ${x\choose\beta}\in\mathbb{R}^{n+1}$ in this
new feasible set. The intuition for these transformations comes from the fact
that we are exchanging $m-1$ cone constraints in the original problem, each of
size $n+1$, with $m$ cone constraints of size 3. In this sense, we have
greatly simplified the structure of the feasible set.

The paper is organized as follows. In Section 2, we introduce the required
background necessary to build and evaluate SDP relaxations of (QP). We also
discuss the literature on relaxations specifically for (QP), including the
exact relaxations mentioned above when $m=1$ and $m=2$. Then, in Section 3, we
take a slight detour to study the related problem of nonconvex quadratic
programming over

$\left\\{x\in\mathbb{R}^{n}:\begin{array}[]{l}\|x\|\leq g_{1}+h_{1}^{T}x\\\
\|x\|\leq g_{2}+h_{2}^{T}x\end{array}\right\\},$

i.e., when the functions bounding $\|x\|$ are linear. We continue to assume
the first constraint is the unit ball, i.e., $g_{1}=1$ and $h_{1}=0$. This is
an interesting case in its own right, arising for example as a substructure in
the optimal power flow problem [14, 16] and also studied by Kelly et al. [18].
By examining this case, we build intuition for the case (QP), which we then
consider fully in Section 4. Both Sections 3–4 contain empirical results
demonstrating the strength of our relaxations. Finally, in Section 5, we
return to the linear case of Section 3 and prove that our relaxation is exact,
thus providing theoretical justification for the techniques and relaxations
introduced in this paper.

We briefly mention a problem closely related to (QP), specifically nonconvex
quadratic programming over the intersection of $m$ general ellipsoids. When
$m=2$, this problem is known as the Celis-Dennis-Tapia problem or the two
trust-region subproblem (TTRS). See [15] and references therein for recent
work on (TTRS). As with balls, many researchers have studied ways to build
tight semidefinite relaxations for (TTRS), but an exact relaxation is unknown,
even for the case of concentric ellipsoids. We also tried to apply the ideas
of this paper to (TTRS) by introducing multiple artificial variables
$\beta,\gamma\in\mathbb{R}$ within the trust-region constraints, say,
$\|x\|\leq\beta\leq 1$ and $\|Hx\|\leq\gamma\leq 1$ when the ellipsoids are
concentric. However, the resulting relaxations were no tighter empirically
than those already in the literature, and we were unable to make further
progress specifically on (TTRS). We hypothesize that the shared geometry of
balls, as represented by the reappearance of the norm $\|x\|$, is critical for
the approach of this paper.

We also remark that all computational results in the paper were coded in
Python using the Fusion API of MOSEK 10.0.37 [3] and run on a M2 MacBook Air
with 24 GB of RAM.

###  1.1 Notation and terminology

Our notation and terminology is mostly standard. $\mathbb{R}^{d}$ is the space
of $d$-dimensional real column vectors, and $\mathbb{S}^{d}$ is the space of
$d\times d$ real symmetric matrices. The identity matrix in $\mathbb{S}^{d}$
is denoted $I_{d}$, and the trace inner produce on $\mathbb{S}^{d}$ is defined
as $M\bullet N:=\text{trace}(MN)$ for any two matrices $M,N\in\mathbb{S}^{d}$.
Define

$\displaystyle\mathcal{SOC}^{d}$
$\displaystyle:=\left\\{v\in\mathbb{R}^{d}:\|(v_{2},\ldots,v_{d})\|\leq
v_{1}\right\\},$ $\displaystyle\mathcal{PSD}^{d}$
$\displaystyle:=\left\\{M\in\mathbb{S}^{d}:M\text{ is positive
semidefinite}\right\\}$

to be the $d$-dimensional second-order cone and the $d\times d$ positive
semidefinite cone, respectively. We use SOC and PSD as abbreviations for
second-order cone and positive semidefinite. For any cone $S$, its conic hull
is defined as all finite sums of members in $S$, i.e.,
$\operatorname{conic.hull}(K):=\\{\sum_{k=1}^{K}s_{k}:K\in\mathbb{N},s_{k}\in
S\\}$.

##  2 Background on Semidefinite Relaxations

In this section, we recount techniques and constructions from the literature,
which we will use for building convex relaxations in Sections 3–4. We also
discuss prior research for relaxations of (QP) specifically. Finally, we
discuss standard ways to measure the quality of a given relaxation on a
particular problem instance, which will be employed in Sections 3–4.

We caution the reader that we will reuse (or “overload”) some notation in this
section. For example, the variable $x$ and dimension $n$ in this section are
not strictly speaking the same as defined in the Introduction.

###  2.1 Techniques for building an SDP relaxation

For this subsection as well as Section 2.3, we introduce the generic nonconvex
quadratic programming problem

$\min\left\\{x^{T}Qx:x\in\mathcal{F},\ x_{1}=1\right\\},$ (1)

where

$\mathcal{F}:=\left\\{x\in\mathbb{R}^{n}:\begin{array}[]{l}\ell_{1}^{T}x\geq
0,\ \ell_{2}^{T}x\geq 0\\\ L_{3}^{T}x\in\mathcal{SOC}^{d_{3}},\
L_{4}^{T}x\in\mathcal{SOC}^{d_{4}}\end{array}\right\\}$

is a closed, convex cone with polyhedral and second-order-cone constraints
defined by the data vectors $\ell_{1},\ell_{2}\in\mathbb{R}^{n}$ and data
matrices $L_{3}\in\mathbb{R}^{n\times d_{3}},L_{4}\in\mathbb{R}^{n\times
d_{4}}$. Specifially, $\mathcal{F}$ is defined by two linear constraints and
two second-order cone (SOC) constraints of different sizes. We assume that
$\mathcal{F}$ is nonempty and bounded in which case (1) has an optimal
solution. We also assume that the constraints of $\mathcal{F}$ imply
$x_{1}\geq 0$ .

It is well known that (1) is equivalent to

$\min\left\\{Q\bullet X:X\in\mathcal{G},\ X_{11}=1\right\\},$ (2)

where

$\mathcal{G}:=\operatorname{conic.hull}\left\\{X=xx^{T}:x\in\mathcal{F}\right\\}\subseteq\mathbb{S}^{n}.$

Equivalent means that both have the same optimal value and there exists a
rank-1 optimal solution $X^{*}=x^{*}(x^{*})^{T}$ of (2), where $x^{*}$ is
optimal for (1). Hence, a common approach to solve or approximate (1) is to
build strong convex—typically semidefinite—relaxations for $\mathcal{G}$.

One standard option is the Shor relaxation of $\mathcal{G}$:

$\text{\text{\sc
Shor}}:=\left\\{X\in\mathcal{PSD}^{n}:\begin{array}[]{l}\ell_{1}^{T}Xe_{1}\geq
0,\ \ell_{2}^{T}Xe_{1}\geq 0\\\ J_{d_{3}}\bullet L_{3}^{T}XL_{3}\geq 0\\\
J_{d_{4}}\bullet L_{4}^{T}XL_{4}\geq 0\end{array}\right\\},$

where $e_{1}\in\mathbb{R}^{n}$ is the first unit vector and, for any dimension
$d$,

$J_{d}:=\begin{pmatrix}1&0\\\ 0&-I_{d-1}\end{pmatrix}\in\mathbb{S}^{d}.$

Here, $\ell_{i}^{T}Xe_{1}\geq 0$ reflects the constraint $\ell_{i}^{T}x\geq 0$
of (1) and is derived from the implication

$\ell_{i}^{T}x,\ e_{1}^{T}x\geq
0\quad\Longrightarrow\quad\ell_{i}^{T}xx^{T}e_{1}\geq
0\quad\Longrightarrow\quad\ell_{i}^{T}Xe_{1}\geq 0.$

Morevover, the linear constraint $J_{d_{k}}\bullet L_{k}^{T}XL_{k}\geq 0$ is
derived from the quadratic function defining
$L_{k}^{T}x\in\mathcal{SOC}^{d_{k}}$. The Shor relaxation has two important
properties. First, one can show that $Xe_{1}\in\mathcal{F}$, so that a
feasible solution is always embedded in $X$. Second, when the objective matrix
$Q$ is positive semidefinite, Shor is already strong enough to solve the
quadratic problem, i.e., the optimal value of (2) equals the optimal value of
(1), and the embedded solution is optimal.

Next, we introduce an RLT constraint [22] using the implication

$\ell_{1}^{T}x\geq 0,\ \ell_{2}^{T}x\geq
0\quad\Longrightarrow\quad\ell_{1}^{T}xx^{T}\ell_{2}\geq
0\quad\Longrightarrow\quad\ell_{1}^{T}X\ell_{2}\geq 0,$

and SOCRLT constraints [24, 9] using the implication

$\ell_{i}^{T}x\geq 0,\
L_{k}^{T}x\in\mathcal{SOC}^{d_{k}}\quad\Longrightarrow\quad
L_{k}^{T}xx^{T}\ell_{i}\in\mathcal{SOC}^{d_{k}}\quad\Longrightarrow\quad
L_{k}^{T}X\ell_{i}\in\mathcal{SOC}^{d_{k}}.$

Then defining

RLT $\displaystyle:=\left\\{X\in\mathbb{S}^{n}:\ell_{1}^{T}X\ell_{2}\geq
0\right\\},$ SOCRLT
$\displaystyle:=\left\\{X\in\mathbb{S}^{n}:L_{k}^{T}X\ell_{i}\in\mathcal{SOC}^{d_{k}}\
\ \forall\ i=1,2,\ k=3,4\right\\},$

we arrive at the strengthened relaxation

$\text{\sc Shor}\cap\text{\sc RLT}\cap\text{\sc SOCRLT}.$

Another valid constraint can be derived from the fact that
$L_{k}^{T}x\in\mathcal{SOC}^{d_{k}}$ is equivalent to a positive semidefinite
constraint (or linear matrix inequality) [2]. To explain, we first write
$y:=L_{3}^{T}x$ and $z:=L_{4}^{T}x$, so that the SOC constraints in (1) are
$y\in\mathcal{SOC}^{d_{3}}$ and $z\in\mathcal{SOC}^{d_{4}}$. Then it is well-
known that

$y\in\mathcal{SOC}^{d_{3}}\quad\Longleftrightarrow\quad\operatorname{Arr}_{d_{3}}(y):=\begin{pmatrix}y_{1}&y_{2}&\cdots&y_{d_{3}}\\\
y_{2}&y_{1}&&\\\ \vdots&&\ddots&\\\
y_{d_{3}}&&&y_{1}\end{pmatrix}\in\mathcal{PSD}^{d_{3}}.$

For any dimension $d$,
$\operatorname{Arr}_{d}:\mathbb{R}^{d}\to\mathbb{S}^{d}$ is called the arrow
operator. Likewise $z\in\mathcal{SOC}^{d_{4}}$ if and only if
$\operatorname{Arr}_{d_{4}}(z)\in\mathcal{PSD}^{d_{4}}.$ Then, using the fact
that the Kronecker product of PSD matrices is PSD, we have
$\operatorname{Arr}_{d_{3}}(y)\otimes\operatorname{Arr}_{d_{4}}(z)\in\mathcal{PSD}^{d_{3}d_{4}}$.
Because the left-hand side of this expression is quadratic in $y$ and $z$, we
can equivalently write

$\operatorname{Arr}_{d_{3}}(y)\otimes\operatorname{Arr}_{d_{4}}(z)=(\operatorname{Arr}_{d_{3}}\boxtimes\operatorname{Arr}_{d_{4}})(zy^{T})$

where
$\operatorname{Arr}_{d_{3}}\boxtimes\operatorname{Arr}_{d_{4}}:\mathbb{R}^{d_{4}\times
d_{3}}\to\mathbb{S}^{d_{3}d_{4}}$ is an operator that is linear in $zy^{T}$
and defined by

$(\operatorname{Arr}_{d_{3}}\boxtimes\operatorname{Arr}_{d_{4}})(zy^{T}):=\begin{pmatrix}\operatorname{Arr}_{d_{3}}(y_{1}z)&\operatorname{Arr}_{d_{3}}(y_{2}z)&\cdots&\operatorname{Arr}_{d_{3}}(y_{d_{3}}z)\\\
\operatorname{Arr}_{d_{3}}(y_{2}z)&\operatorname{Arr}_{d_{3}}(y_{1}z)&&\\\
\vdots&&\ddots&\\\
\operatorname{Arr}_{d_{3}}(y_{d_{3}}z)&&&\operatorname{Arr}_{d_{3}}(y_{1}z)\end{pmatrix}.$

Substituting back $y=L_{3}^{T}x$ and $z=L_{4}^{T}x$, we arrive at the
implication

$(\operatorname{Arr}_{d_{3}}\boxtimes\operatorname{Arr}_{d_{4}})(L_{4}^{T}xx^{T}L_{3})\in\mathcal{PSD}^{d_{3}d_{4}}\quad\Longrightarrow\quad(\operatorname{Arr}_{d_{3}}\boxtimes\operatorname{Arr}_{d_{4}})(L_{4}^{T}XL_{3})\in\mathcal{PSD}^{d_{3}d_{4}}.$

Then defining

$\text{\sc
Kron}:=\left\\{X\in\mathbb{S}^{n}:(\operatorname{Arr}_{d_{3}}\boxtimes\operatorname{Arr}_{d_{4}})(L_{4}^{T}XL_{3})\in\mathcal{PSD}^{d_{3}d_{4}}\right\\},$

we have the strongest relaxation thus far:

$\text{\sc Shor}\cap\text{\sc RLT}\cap\text{\sc SOCRLT}\cap\text{\sc Kron}.$

In Sections 3–4, we will derive SDP relaxations using the building blocks just
introduced, i.e., Shor combined with RLT, SOCRLT, and Kron. In a sense, each
of RLT, SOCRLT, and Kron have the same goal—to combine information from pairs
of constraints in (1)—but they differ due to the structure of the underlying
cones, i.e., the nonnegative orthant, the second-order cone, and the PSD cone.
Similar ideas can be derived for other cones, e.g., the rotated second-order
cone, or for other linear operators, whose image is constrained to be positive
semidefinite. Such variations will be introduced in Section 4.

###  2.2 Results from the literature

The relaxations Shor, RLT, SOCRLT, and Kron just introduced are known to be
quite strong in a number of contexts closely related to (QP). Specifically,
Shor is exact for the case of (QP) for $m=1$ [21], and when a single linear
constraint is added to the ball constraint $\|x\|\leq 1$, then $\text{\sc
Shor}\cap\text{\sc SOCRLT}$ is exact [24]. In addition, for the more general
case

$\left\\{x:\begin{array}[]{l}\|x\|\leq 1\\\ 0\leq g_{i}+h_{i}^{T}x\ \ \forall\
i=2,\ldots,m\end{array}\right\\}$

in which multiple linear constraints are added, $\text{\sc Shor}\cap\text{\sc
RLT}\cap\text{\sc SOCRLT}$ is exact as long as none of the hyperplanes
$0=g_{i}+h_{i}^{T}x$ intersect inside the ball [11]. Kron has also been used
to strengthen relaxations of (QP) when there is a second ellipsoidal
constraint [2], not necessarily a ball. As a footnote, we are unaware of any
case in which enforcing Kron specifically makes a relaxation exact for all
objectives, but Kron has proven to be a valuable tool for building strong
relaxations.

We are aware of two papers [17, 16], which have studied techniques for further
strengthening $\text{\sc Shor}\cap\text{\sc RLT}\cap\text{\sc
SOCRLT}\cap\text{\sc Kron}$. Among these, [16] is more similar to the current
paper. In [16], the authors introduce a class of linear cuts for SDP
relaxations of

$\\{x:\|x\|\leq 1,\ \|x-c_{2}\|\leq g_{2}+h_{2}^{T}x\\},$

and they show how to separate the cuts in polynomial time. Through a series of
computational experiments, the authors also show that their cuts are effective
particularly in lower dimensions, say, for $n\leq 10$.

As mentioned in the Introduction, an exact convex relaxation of (QP) via a
disjunctive formulation was recently given by Kelly et al. [18]. They showed
that the feasible region of (QP) can be written as the union of two special
sets:

$\\{x:\|x\|\leq 1,\ 0\leq
g_{1}+h_{1}^{T}x\\}\quad\quad\text{and}\quad\quad\\{x:\|x-c_{2}\|\leq\rho_{2},\
0\leq g_{2}+h_{2}^{T}x\\}.$

Explicit formulas for $g_{i}$ and $h_{i}$ are given in their paper. Since
optimizing over each of these can separately be accomplished with $\text{\sc
Shor}\cap\text{\sc SOCRLT}$ as mentioned above, the authors then use a
disjunctive formulation with two copies of $\text{\sc Shor}\cap\text{\sc
SOCRLT}$ to derive an exact formulation of (QP); see proposition 5 in their
paper. The authors also used similar ideas to derive an exact, disjunctive
formulation for the case $\|x\|\leq\min\\{1,g_{2}+h_{2}^{T}x\\}$; we will
derive an exact, non-disjunctive formulation for this case in Section 3.

Zhen et al. [27] have recently suggested another technique for combining
information from two SOC constraints; see appendix B of [27]. We illustrate
their idea using the two constraints $\|x\|\leq 1$ and
$\|x-c_{2}\|\leq\rho_{2}$ of (QP). The fact that $\|uv^{T}\|_{2}=\|u\|\|v\|$,
where $\|\cdot\|_{2}$ denotes the matrix 2-norm, implies

$\|xx^{T}-xc^{T}\|_{2}=\|x(x-c)^{T}\|_{2}=\|x\|\|x-c_{2}\|\leq
1\cdot\rho_{2}=\rho_{2},$

which can be linearized

$\|X-xc^{T}\|_{2}\leq\rho_{2}\quad\quad\Longleftrightarrow\quad\quad\begin{pmatrix}\rho_{2}I_{n}&X-xc^{T}\\\
X-cx^{T}&I_{n}\end{pmatrix}\in\mathcal{PSD}^{2n}.$

In our experiments in Sections 3–4, we added this constraint to $\text{\sc
Shor}\cap\text{\sc RLT}\cap\text{\sc SOCRLT}\cap\text{\sc Kron}$, but it did
not provide added strength on our test instances. Although we do not consider
this valid constraint further in this paper, investigating its precise
relationship with existing constraints remains an interesting avenue for
research.

###  2.3 Measuring the quality of a relaxation

Following the notation of Section 2.1, let $\mathcal{R}$ be a given
semidefinite relaxation of $\mathcal{G}$, which is at least as strong as Shor,
i.e., $\mathcal{R}\subseteq\text{\sc Shor}$. The SDP relaxation corresponding
to $\mathcal{R}$ is

$r^{*}:=\min\left\\{Q\bullet X:X\in\mathcal{R},\ X_{11}=1\right\\},$

and we let $X^{*}$ denote an optimal solution.

We can assess the quality of the relaxation by comparing $r^{*}$ to any
readily available feasible value $v=x^{T}Qx$, where $x\in\mathcal{F}$ is some
feasible point. In particular, as mentioned in Section 2.1, $X^{*}$ has an
embedded feasible solution, but there are often multiple methods for obtaining
a good feasible value $v$ in practice, e.g., using a rounding procedure from
$X^{*}$ or some other type of heuristic. Our primary measure of relaxation
quality will be the relative gap between $r^{*}$ and $v$ defined as follows:

$\text{relative gap}:=\frac{v-r^{*}}{\max\\{1,\tfrac{1}{2}|v+r^{*}|\\}}.$ (3)

A secondary measure of relaxation quality is the so-called eigenvalue ratio of
$X^{*}$. By construction, if the rank of $X^{*}$ is 1, then
$X^{*}=x^{*}(x^{*})^{T}$ for some optimal solution $x^{*}$ of (1). Of course,
in practice $X^{*}$ will most likely not be exactly rank-1, but it may be
numerically close to rank-1. The eigenvalue ratio tries to capture how close
$X^{*}$ is to being rank-1. Specifically,

$\text{eigenvalue ratio}:=\frac{\lambda_{1}[X^{*}]}{\lambda_{2}[X^{*}]},$

where $\lambda_{1}[X^{*}]$ and $\lambda_{2}[X^{*}]$ are the largest and
second-largest eigenvalues of $X^{*}$. Generally speaking, the higher the
eigenvalue ratio, the closer $X^{*}$ is to being rank-1.

In the computational results of Sections 3–4, we will say that an instance is
solved by a relaxation if both of the following two conditions are satisfied:

  * •

the relative gap between $r^{*}$ and the feasible value $v$, which comes from
the solution $x$ embedded in $X^{*}$, is less than $10^{-4}$;

  * •

the eigenvalue ratio of $X^{*}$ is greater than $10^{4}$.

Similar definitions of the term solved have been used in [9, 1, 16, 15].
Strictly speaking, a small relative gap is enough to verify approximate
optimality, but we will also require a large eigenvalue ratio in order to
bolster our confidence in the numerical results. It should also be noted that,
for randomly generated instances such as those investigated in Sections 3–4,
small relative gaps and large eigenvalue ratios are typically highly
positively correlated.

##  3 The Case $\|x\|\leq\min\\{1,g_{2}+h_{2}^{T}x\\}$

In this section, we examine the case of nonconvex quadratic programming over
the set

$\left\\{x\in\mathbb{R}^{n}:\|x\|\leq g_{i}+h_{i}^{T}x\ \ \forall\
i=1,2\right\\}$ (4)

with $g_{1}=1$ and $h_{1}=0$ such that the first constraint is $\|x\|\leq 1$.
We assume (4) is nonempty, but otherwise no particular assumptions are made on
$g_{2}$ and $h_{2}$. We have two goals in this section. First, we wish to
develop intuition for building a strong relaxation for (QP) in Section 4.
Second, this case is interesting in its own right as a substructure of the
optimal power flow problem [14, 16]. Moreover, Kelly et al. [18] have also
recently studied this case; see Section 2.2.

###  3.1 Semidefinite relaxations

As discussed in Section 2, there are several ways to build relaxations of
nonconvex QPs over the set (4). We first homogenize (4) using an auxiliary
variable $\alpha\in\mathbb{R}$:

$\widetilde{\mathcal{F}}:=\left\\{{\alpha\choose
x}\in\mathbb{R}^{n+1}:\begin{array}[]{l}\|x\|\leq g_{i}\alpha+h_{i}^{T}x\ \
\forall\ i=1,2\end{array}\right\\},$

Note that $\alpha\geq 0$ is implied by the first constraint and that (4) is
recovered by projecting $\widetilde{\mathcal{F}}\cap\\{{\alpha\choose
x}:\alpha=1\\}$ back to $\mathbb{R}^{n}$. Then setting

$\widetilde{w}:={\alpha\choose x}\in\mathbb{R}^{n+1},$ (5)

we investigate relaxations of
$\widetilde{\mathcal{G}}:=\operatorname{conic.hull}\\{\widetilde{w}\widetilde{w}^{T}:\widetilde{w}\in\widetilde{\mathcal{F}}\\}$.
Defining

$\widetilde{L}_{i}:=\begin{pmatrix}g_{i}&0\\\
h_{i}&I_{n}\end{pmatrix}\in\mathbb{R}^{(n+1)\times(n+1)}\ \ \forall\ i=1,2,$

we rewrite

$\widetilde{\mathcal{F}}=\left\\{\widetilde{w}\in\mathbb{R}^{n+1}:\widetilde{L}_{i}^{T}w\in\mathcal{SOC}^{n+1}\quad\forall\
i=1,2\right\\}.$

Then, in accordance with Section 2, we define the following relaxation of
$\widetilde{\mathcal{G}}$:

$\displaystyle\widetilde{\mathcal{R}}$ $\displaystyle:=\text{\sc
Shor}\cap\text{\sc Kron}$
$\displaystyle:=\left\\{\widetilde{W}\in\mathcal{PSD}^{n+1}:\begin{array}[]{l}J_{n+1}\bullet\widetilde{L}_{i}^{T}\widetilde{W}\widetilde{L}_{i}\geq
0\quad\forall\ i=1,2\\\
(\operatorname{Arr}_{n+1}\boxtimes\operatorname{Arr}_{n+1})(\widetilde{L}_{2}^{T}\widetilde{W}\widetilde{L}_{1})\in\mathcal{PSD}^{(n+1)^{2}}\end{array}\right\\}.$

Note that RLT and SOCRLT are not applicable here because
$\widetilde{\mathcal{F}}$ contains no explicit linear constraints.

In hopes of improving upon $\widetilde{\mathcal{R}}$, as discussed in the
Introduction, we introduce the auxiliary variable $\beta\in\mathbb{R}$ into
(4):

$\left\\{{x\choose\beta}\in\mathbb{R}^{n+1}:\begin{array}[]{l}\|x\|\leq\beta\\\
\beta\leq g_{i}+h_{i}^{T}x\ \ \forall\ i=1,2\end{array}\right\\}.$ (6)

This swaps one SOC constraint in (4) for two linear constraints, hence
simplifying the structure of the feasible set, but it does not affect
optimization over (4) since $\beta$ is an artificial variable not impacting
the objective $x^{T}Qx+2q^{T}x$. We then proceed as above by homogenizing:

$\mathcal{F}:=\left\\{w\in\mathbb{R}^{n+2}:\begin{array}[]{l}\|x\|\leq\beta\\\
\beta\leq g_{i}\alpha+h_{i}^{T}x\ \ \forall\ i=1,2\end{array}\right\\},$

where

$w:=\begin{pmatrix}\alpha\\\ x\\\ \beta\end{pmatrix}\in\mathbb{R}^{n+2},$ (7)

Note that the first linear constraint, with $g_{1}=1$ and $h_{1}=0$, ensures
$\alpha\geq 0$.

We next define

$P:=\begin{pmatrix}0&0\\\ 0&I_{n}\\\
1&0\end{pmatrix}\in\mathbb{R}^{(n+2)\times(n+1)}$ (8)

and

$\ell_{i}:=\begin{pmatrix}g_{i}\\\ h_{i}\\\
-1\end{pmatrix}\in\mathbb{R}^{n+2}\ \ \forall\ i=1,2$

so that

$\mathcal{F}=\left\\{w\in\mathbb{R}^{n+2}:P^{T}w\in\mathcal{SOC}^{n+1},\
\ell_{i}^{T}w\geq 0\ \forall\ i=1,2\right\\}.$

Then Section 2 provides the following relaxation of
$\mathcal{G}:=\operatorname{conic.hull}\\{ww^{T}\in\mathbb{S}^{n+1}:w\in\mathcal{F}\\}$:

$\displaystyle\mathcal{R}$ $\displaystyle:=\text{\sc Shor}\cap\text{\sc
RLT}\cap\text{\sc SOCRLT}$
$\displaystyle:=\left\\{W\in\mathcal{PSD}^{n+2}:\begin{array}[]{l}J_{n+1}\bullet
P^{T}WP\geq 0\\\ \ell_{1}^{T}W\ell_{2}\geq 0\\\
P^{T}W\ell_{i}\in\mathcal{SOC}^{n+1}\ \ \forall\ i=1,2\end{array}\right\\}.$

In this case, Kron is not relevant because $\mathcal{F}$ only contains one SOC
constraint. Compared to $\widetilde{\mathcal{R}}$, the relaxation
$\mathcal{R}$ has only one PSD constraint but contains one extra linear
constraint and two SOC constraints.

###  3.2 Computational results, an exactness result, and a conjecture

From the previous subsection, to approximate the problem

$\min\left\\{x^{T}Qx+2q^{T}x:\|x\|\leq 1,\ \|x\|\leq
g_{2}+h_{2}^{T}x\right\\},$ (9)

we have the semidefinite relaxations

$\displaystyle\min\left\\{\widetilde{Q}\bullet\widetilde{W}:\widetilde{W}\in\widetilde{\mathcal{R}},\
\widetilde{W}_{11}=1\right\\}$ (Kron)
$\displaystyle\min\left\\{\widehat{Q}\bullet W:W\in\mathcal{R},\
W_{11}=1\right\\}$ (Beta)

where

$\widetilde{Q}:=\begin{pmatrix}0&q^{T}\\\
q&Q\end{pmatrix}\quad\quad\text{and}\quad\quad\widehat{Q}:=\begin{pmatrix}0&q^{T}&0\\\
q&Q&0\\\ 0&0&0\end{pmatrix}.$ (10)

We use the name “Kron” to remind the reader that $\widetilde{\mathcal{R}}$ is
equivalent to $\text{\sc Shor}\cap\text{\sc Kron}$ and “Beta” to denote our
relaxation, which is based on the artificial variable $\beta$.

We first provide a small example showing that Beta does indeed impove upon
Kron. Recall from Section 2.3, that we say a relaxation solves an instance if
both the relative gap is less than $10^{-4}$ and the eigenvalue ratio is more
than $10^{4}$.

######  Example 1.

Consider an instance of (9) with $n=2$ and

$Q=\begin{pmatrix}-0.67&0.95\\\ 0.95&-1.59\end{pmatrix},\quad
q=\begin{pmatrix}-0.89\\\ -0.89\end{pmatrix},\quad g_{2}=1.52,\quad
h_{2}=\begin{pmatrix}0.19\\\ -0.91\end{pmatrix}.$

Kron returns the lower bound $-2.6363$, the method of [16] returns $-2.5543$,
and Beta solves the instance with an optimal value of $-2.4672$ and optimal
solution

$x^{*}\approx\begin{pmatrix}0.978358\\\ -0.206920\end{pmatrix}.$

Next we generated 1,000 feasible instances of (9) for each of the dimensions
$n\in\\{2,4,6\\}$, and we specifically did not include instances that were
already solved by Shor in this test set. For example, this guaranteed that no
test instance was convex due to $Q$ being positive semidefinite. Note also
that the number of constraints here is always $m=2$. In particular, to
generate each instance, we first sampled a random point $x^{0}$ in the unit
ball, and then generated $h_{2}$ with entries i.i.d. according to the standard
normal distribution $N(0,1)$. Then $g_{2}$ was generated according to the
formula $U(0,1)+h_{2}^{T}x^{0}-\|x^{0}\|$, where $U(0,1)$ is the uniform
distribution between 0 and 1, so that $x^{0}$ was interior feasible. Then $Q$
and $q$ were generated with all entries i.i.d. in $N(0,1)$. Finally, Shor was
solved, and if Shor did not solve the instance, it was included in our test
set.

$n$ | $m$ | # Instances | # Solved | Total Time (s)
---|---|---|---|---
|  |  | Kron | Beta | Shor | Kron | Beta
2 | 2 | 1,000 | 979 | 1,000 | 0.4 | 1.9 | 0.8
4 | 2 | 1,000 | 987 | 1,000 | 0.7 | 11.7 | 1.1
6 | 2 | 1,000 | 990 | 1,000 | 0.9 | 151.9 | 1.5
Table 1: Number of instances of (9) solved by Kron and Beta over 3,000
randomly generated instances, which were not already solved by Shor. Instances
are grouped by dimensions $(n,m)$. Also shown are the total time (in seconds)
to solve all instances for each method in each grouping. Times for Shor are
also shown for reference.

Table 1 shows the results of our experiments. We see clearly that, while Kron
solves many instances, Beta solves all instances in much less time. In fact,
Beta takes about the same time as Shor.

Upon further examination of the details of the results depicted in Table 1, we
noticed that the RLT constraint $\ell_{1}^{T}W\ell_{2}\geq 0$ in $\mathcal{R}$
was active at all optimal solutions. This led us to investigate the condition
$\ell_{1}^{T}W\ell_{2}=0$ more carefully. Recall that $\beta$ was inserted
between $\|x\|$ and $\min\\{1,g_{2}+h_{2}^{T}x\\}$. When $\|x\|$ is strictly
less than $\min\\{1,g_{2}+h_{2}^{T}x\\}$, there are multiple values of
$\beta$, which are feasible for the same value of $x$. To remove this
ambiguity, we can actually force $\beta=\min\\{1,g_{2}+h_{2}^{T}x\\}$ by
adding the quadratic complementarity equation

$(1-\beta)(g_{2}+h_{2}^{T}x-\beta)=(\ell_{1}^{T}w)(\ell_{2}^{T}w)=0$

to the definition of $\mathcal{F}$. Formally, we define

$\displaystyle\mathcal{F}^{0}$
$\displaystyle:=\left\\{w\in\mathcal{F}:(\ell_{1}^{T}w)(\ell_{2}^{T}w)=0\right\\},$
$\displaystyle\mathcal{G}^{0}$
$\displaystyle:=\operatorname{conic.hull}\\{W=ww^{T}:w\in\mathcal{F}^{0}\\},$
$\displaystyle\mathcal{R}^{0}$
$\displaystyle:=\\{W\in\mathcal{R}:\ell_{1}^{T}W\ell_{2}=0\\}.$

Note that optimizing $x^{T}Qx+2q^{T}x$ over
$\mathcal{F}^{0}\cap\\{x:\alpha=1\\}$ is equivalent to (9) because $\beta$ is
artificial. In Section 5, we will prove the following theorem:

######  Theorem 1.

$\mathcal{G}^{0}=\mathcal{R}^{0}$.

This ensures that (9) is equivalent to

$\min\left\\{\widehat{Q}\bullet W:W\in\mathcal{R},\ W_{11}=1,\
\ell_{1}^{T}W\ell_{2}=0\right\\}=\min\left\\{\widehat{Q}\bullet
W:W\in\mathcal{R}^{0},\ W_{11}=1\right\\},$

that is, equivalent to Beta with the strengthened constraint
$\ell_{1}^{T}W\ell_{2}=0$. Hence, the fact that $\ell_{1}^{T}W\ell_{2}\geq 0$
is active at optimality for all instances in Table 1 is actually another
verification that Beta solves these instances.

This begs the question: why should the constraint $\ell_{1}^{T}W\ell_{2}\geq
0$ be active at optimality for the instances tested? Indeed, after extensive
experimentation, this appears to always be the case, and accordingly, we offer
the following conjecture:

######  Conjecture 1.

There exists an optimal solution $W^{*}$ of Beta with
$\ell_{1}^{T}W^{*}\ell_{2}=0$.

If this conjecture is true, then it must rely on the fact that the the
variable $\beta$ does not appear in the objective of (9). Indeed, in Section
5, we will give an example inside the proof of Proposition 1 showing that,
when $\beta$ is involved in the objective, $\ell_{1}^{T}W\ell_{2}=0$ may not
hold at optimality.

##  4 The Case of (QP)

Following the path laid in Sections 2–3, we now return to our primary case of
interest, problem (QP). We first construct two semidefinite relaxations, one
which already exists in the literature and our new construction based on the
variable $\beta$ discussed in the Introduction. Then we conduct computational
experiments showing the strength of our relaxation.

As in previous sections, we will overload some of our notation. For example,
$\widetilde{\mathcal{R}}$ and $\mathcal{R}$ will be used similarly in this
section as in Section 3, but their technical definitions will be different.

###  4.1 Semidefinite relaxations

We first homogenize the feasible set of (QP) by introducing
$\alpha\in\mathbb{R}$:

$\widetilde{\mathcal{F}}:=\left\\{{\alpha\choose
x}\in\mathbb{R}^{n+1}:\begin{array}[]{l}\|x-\alpha c_{i}\|\leq
g_{i}\alpha+h_{i}^{T}x\ \ \forall\ i=1,\ldots,m\end{array}\right\\},$ (11)

Then, defining $\widetilde{w}$ by (5) and

$\widetilde{L}_{i}:=\begin{pmatrix}g_{i}&-c_{i}^{T}\\\
h_{i}&I_{n}\end{pmatrix}\in\mathbb{R}^{(n+1)\times(n+1)}\ \ \forall\
i=1,\ldots,m$

we rewrite

$\widetilde{\mathcal{F}}=\left\\{\widetilde{w}\in\mathbb{R}^{n+1}:\widetilde{L}_{i}^{T}w\in\mathcal{SOC}^{n+1}\quad\forall\
i=1,\ldots,m\right\\}.$

Then, in accordance with Section 2, we define the following relaxation of
$\widetilde{\mathcal{G}}:=\operatorname{conic.hull}\\{\widetilde{w}\widetilde{w}^{T}\in\mathbb{S}^{n+1}:\widetilde{w}\in\widetilde{\mathcal{F}}\\}$:

$\displaystyle\widetilde{\mathcal{R}}$ $\displaystyle:=\text{\sc
Shor}\cap\text{\sc Kron}$
$\displaystyle:=\left\\{\widetilde{W}\in\mathcal{PSD}^{n+1}:\begin{array}[]{ll}J_{n+1}\bullet\widetilde{L}_{i}^{T}\widetilde{W}\widetilde{L}_{i}\geq
0&\forall\ i=1,\ldots,m\\\
(\operatorname{Arr}_{n+1}\boxtimes\operatorname{Arr}_{n+1})(\widetilde{L}_{k}^{T}\widetilde{W}\widetilde{L}_{i})\in\mathcal{PSD}^{(n+1)^{2}}&\forall\
1\leq i<k\leq m\end{array}\right\\},$

Note that RLT and SOCRLT are not applicable here because
$\widetilde{\mathcal{F}}$ contains no explicit linear constraints.

In hopes of improving upon $\widetilde{\mathcal{R}}$, we introduce the
auxiliary variable $\beta\in\mathbb{R}$ into (QP):

$\left\\{{x\choose\beta}\in\mathbb{R}^{n+1}:\begin{array}[]{l}\|x\|\leq\beta,\
\beta\leq 1\\\ \beta\leq\sqrt{g_{i}+h_{i}^{T}x}\ \ \forall\
i=2,\ldots,m\end{array}\right\\},$

where $g_{i}:=\rho_{i}^{2}-c_{i}^{T}c_{i}$ and $h_{i}:=2c_{i}$ for all
$i=2,\ldots,m$. This swaps $m-1$ SOC constraints in (QP) for one linear
constraint and $m-1$ low-dimensional rotated SOC constraints, hence
simplifying the structure of the feasible set. In particular, defining

$\mathcal{RSOC}^{3}:=\\{v\in\mathbb{R}^{3}:v_{1},v_{2}\geq 0,\ v_{3}^{2}\leq
v_{1}v_{2}\\}$

to be the 3-dimensional rotated SOC, we have

$\beta\leq\sqrt{g_{i}+h_{i}^{T}x}\quad\Longleftrightarrow\quad\begin{pmatrix}1\\\
g_{i}+h_{i}^{T}x\\\ \beta\end{pmatrix}\in\mathcal{RSOC}^{3}.$

Then we homogenize:

$\mathcal{F}:=\left\\{w\in\mathbb{R}^{n+2}:\|x\|\leq\beta,\ \beta\leq\alpha,\
\begin{pmatrix}\alpha\\\ g_{i}\alpha+h_{i}^{T}x\\\
\beta\end{pmatrix}\in\mathcal{RSOC}^{3}\quad\forall\ i=2,\ldots,m\right\\},$

where $w$ is defined by (7). Note that this feasible set ensures $\alpha\geq
0$. We next define $P$ by (8) and

$\ell_{1}:=\begin{pmatrix}1\\\ 0\\\ -1\end{pmatrix}\in\mathbb{R}^{n+2},\quad
L_{i}:=\begin{pmatrix}1&g_{i}&0\\\ 0&h_{i}&0\\\
0&0&1\end{pmatrix}\in\mathbb{R}^{(n+2)\times 3}\ \ \forall\ i=2,\ldots,m$

so that we may rewrite

$\mathcal{F}=\left\\{w\in\mathbb{R}^{n+2}:\begin{array}[]{l}P^{T}w\in\mathcal{SOC}^{n+1},\
\ell_{1}^{T}w\geq 0,\\\ L_{i}^{T}w\in\mathcal{RSOC}^{3}\ \forall\
i=2,\ldots,m\end{array}\right\\}$

To build a relaxation of
$\mathcal{G}:=\operatorname{conic.hull}\left\\{ww^{T}\in\mathbb{S}^{n+1}:w\in\mathcal{F}\right\\}$,
we define the matrix

$K:=\begin{pmatrix}0&1/2&0\\\ 1/2&0&0\\\ 0&0&-1\end{pmatrix}\in\mathbb{S}^{3}$

and the linear operator

$\operatorname{sMat_{2}}:\mathbb{R}^{3}\to\mathbb{S}^{2}\quad\quad\quad\text{by}\quad\quad\quad\operatorname{sMat_{2}}(v):=\begin{pmatrix}v_{1}&v_{3}\\\
v_{3}&v_{2}\end{pmatrix}$

so that

$v\in\mathcal{RSOC}^{3}\quad\Longleftrightarrow\quad v_{1},v_{2}\geq 0,\
v^{T}Kv\geq
0\quad\Longleftrightarrow\quad\operatorname{sMat_{2}}(v)\in\mathcal{PSD}^{2}.$

Then our relaxation is

$\displaystyle\mathcal{R}$ $\displaystyle:=\text{\sc Shor}\cap\text{\sc
SOCRLT}\cap\text{\sc Kron}$
$\displaystyle:=\left\\{W\in\mathcal{PSD}^{n+2}:\begin{array}[]{ll}J_{n+1}\bullet
P^{T}WP\geq 0&\\\ P^{T}W\ell_{1}\in\mathcal{SOC}^{n+1}&\\\ K\bullet
L_{i}^{T}WL_{i}\geq 0&\forall\ i=2,\ldots,m\\\
L_{i}^{T}W\ell_{1}\in\mathcal{RSOC}^{3}&\forall\ i=2,\ldots,m\\\
(\operatorname{Arr}_{n+1}\boxtimes\operatorname{sMat_{2}})(L_{i}^{T}WP)\in\mathcal{PSD}^{2(n+1)}&\forall\
i=2,\ldots,m\\\
(\operatorname{sMat_{2}}\boxtimes\operatorname{sMat_{2}})(L_{k}^{T}WL_{i})\in\mathcal{PSD}^{4}&\forall\
2\leq i<k\leq m\end{array}\right\\}.$

Note that, compared to $\widetilde{\mathcal{R}}$, the relaxation $\mathcal{R}$
utilizes more, but smaller, cones. Specifically, $\widetilde{\mathcal{R}}$ has
two PSD conditions, one of size roughly $n\times n$ and one of size
$n^{2}\times n^{2}$. In contrast, $\mathcal{R}$ has roughly $m$ PSD conditions
of size $n\times n$, $m$ linear constraints, $m$ 3-dimensional rotated SOC
constraints, and $m^{2}$ PSD conditions of size $4\times 4$.

###  4.2 Computational results for $m=2$

From the previous subsection, to approximate (QP), we have the semidefinite
relaxations

$\displaystyle\min\left\\{\widetilde{Q}\bullet\widetilde{W}:\widetilde{W}\in\widetilde{\mathcal{R}},\
\widetilde{W}_{11}=1\right\\}$ (Kron)
$\displaystyle\min\left\\{\widehat{Q}\bullet W:W\in\mathcal{R},\
W_{11}=1\right\\}$ (Beta)

where $\widetilde{Q}$ and $\widehat{Q}$ are given by (10). We first provide a
small example showing that Beta can significantly impove Kron.

######  Example 2.

Consider an instance of (QP) with $(n,m)=(2,2)$ and

$Q=\begin{pmatrix}-0.12&0.66\\\ 0.66&-1.58\end{pmatrix},\quad
q=\begin{pmatrix}1.04\\\ 0.10\end{pmatrix},\quad c_{2}=\begin{pmatrix}0.09\\\
-0.34\end{pmatrix},\quad\rho_{2}=0.98.$

Kron returns the lower bound $-1.9206$, the method of [16] returns $-1.9076$,
and Beta solves the instance with an optimal value of $-1.8856$ and optimal
solution

$x^{*}\approx\begin{pmatrix}-0.303464\\\ -0.952843\end{pmatrix}.$

Next we generated 1,000 feasible instances of (QP) for each of the dimension
pairs $(n,m)\in\\{(2,2),(4,2),(8,2)\\}$, and we specifically excluded
instances that were already solved by Shor. Note that, for this set of
experiments, the number of constraints is kept constant at $m=2$. In
particular, to generate each instance, we followed the method of [9]; see
section 5.3 of that paper and the discussion therein. The idea is to first
generate and solve globally an instance of (QP) with $m=1$ and then to add a
second ball constraint, which cuts off the optimal solution just calculated.
The resulting problem is likely to possess multiple good candidates for
optimal solutions, thus ostensibly making it a more challenging instance of
(QP). We call these the Martinez instances following the terminology
introduced in [9].

$n$ | $m$ | # Instances | # Solved | Total Time (s)
---|---|---|---|---
|  |  | Kron | Beta | Shor | Kron | Beta
2 | 2 | 1,000 | 949 | 997 | 0.4 | 3.7 | 1.9
4 | 2 | 1,000 | 885 | 997 | 0.7 | 25.5 | 3.5
6 | 2 | 1,000 | 886 | 1,000 | 1.0 | 353.4 | 5.5
Table 2: Number of instances of (QP) solved by Kron and Beta over 3,000
randomly generated Martinez instances, which were not already solved by Shor.
Instances are grouped by dimensions $(n,m)$. Also shown are the total time (in
seconds) to solve all instances for each method in each grouping. Times for
Shor are also shown for reference.

Table 2 shows the results of our experiments. We see that, while Kron solves
many instances, Beta solves nearly all instances in much less time. In fact,
Beta takes just a bit more time than Shor.

We also examined the so-called gap closure for each relaxation. For a given
instance, let $s^{*}$ be the optimal value of Shor, and let $v$ be the best
(i.e., minimum) feasible value from the solutions embedded within the three
relaxations Shor, Kron, and Beta at optimality. Then

gap closure for Kron $\displaystyle:=\left(\frac{\text{[optimal value for
\text{\sc Kron}]}-s^{*}}{v-s^{*}}\right)\times 100\%$ gap closure for Beta
$\displaystyle:=\left(\frac{\text{[optimal value for \text{\sc
Beta}]}-s^{*}}{v-s^{*}}\right)\times 100\%$

A gap closure of 0% means that the relaxation did not improve upon Shor, and a
gap closure of 100% means that the relaxation was exact.

Solution Status | # Instances | Avg Gap Closed
---|---|---
Kron | Beta |  | Kron | Beta
unsolved | unsolved | 6 | 57% | 66%
unsolved | solved | 274 | 87% | 100%
solved | unsolved | 0 | - | -
solved | solved | 2720 | 100% | 100%
Table 3: Average gap closures for Table 2. Instances are grouped by solution
status for Kron and Beta.

Table 3 shows that the average gap closures for Kron were around 10% less than
for Beta on those instances unsolved by Kron. We also see that there were no
instances that were solved by Kron and yet unsolved by Beta. This suggests
empirically that Beta is always at least as strong as Kron, although we do not
have a formal proof establishing this.

Eltved and Burer [16] also solved instances of (QP) with $m=2$, and in their
paper, they reported that their method, which is at least as strong as Kron,
was unable to solve 267 randomly generated instances with $n$ ranging from 2
to 10; see table 6 therein. We ran Beta on these instances and solved 262 of
them. We also ran the method of [16] on the six instances in Table 2, which
were unsolved by Beta, and their method generated worse lower bounds in all
six cases.

###  4.3 Computational results for $m>2$

Continuing the prevous subsection, we now investigate the use of Kron and Beta
to approximate instances of (QP) with $m>2$. To this end, we generated random
instances of the following geometric problem, which we call max-norm:

> In $\mathbb{R}^{n}$, given a point $p$ and $m$ balls containing the origin,
> find a point in the intersection of the balls with maximum distance to $p$.

This is an instance of (QP) with $Q=-I$ and $q=p$. Specifically, the first
ball is the unit ball, and then remaining $m-1$ balls are generated with
random centers $c_{i}$ in the unit ball and random radii $\rho_{i}$, each in
$\|c_{i}\|+U(0,1.5)$, where $U(0,1.5)$ is continuous uniform between 0 and
1.5. In particular, this guarantees that $x=0$ is feasible. Finally, $p$ is
generated uniformly in the ball of radius 4 centered at the origin. As in
previous experiments, we exclude instances that are solved by Shor.

Similar to Tables 2–3 in the previous subsection, Tables 4 and 5 show the
results of Kron and Beta on 1,000 max-norm instances for four pairs of
dimensions $(n,m)$. These results show clearly that Beta significantly
outperforms Kron in terms of both number of instances solved and the average
gap closed. In terms of timings, we see that Beta can take significantly
longer than Kron for larger values of $m$.

$n$ | $m$ | # Instances | # Solved | Total Time (s)
---|---|---|---|---
|  |  | Kron | Beta | Shor | Kron | Beta
2 | 5 | 1,000 | 91 | 951 | 0.3 | 6.3 | 7.3
2 | 9 | 1,000 | 103 | 948 | 0.4 | 11.6 | 28.3
4 | 9 | 1,000 | 0 | 861 | 0.7 | 115.0 | 61.8
4 | 17 | 1,000 | 1 | 830 | 0.9 | 432.5 | 632.7
Table 4: Number of max-norm instances solved by Kron and Beta on 4,000 instances unsolved by Shor. Instances are grouped by dimensions $(n,m)$. Also included are the total time (in seconds) to solve all instances for each method in each grouping. Solution Status | # Instances | Avg Gap Closed
---|---|---
Kron | Beta |  | Kron | Beta
unsolved | unsolved | 410 | 2% | 30%
unsolved | solved | 3395 | 11% | 100%
solved | unsolved | 0 | - | -
solved | solved | 195 | 100% | 100%
Table 5: Average gap closures for Table 4. Instances are grouped by solution
status for Kron and Beta.

##  5 Proof of Theorem 1

In this section, we prove Theorem 1 from Section 3, which states that

$\mathcal{G}^{0}:=\operatorname{conic.hull}\left\\{ww^{T}\in\mathbb{S}^{n+2}:\begin{array}[]{l}P^{T}w\in\mathcal{SOC}^{n+1}\\\
\ell_{i}^{T}w\geq 0\ \ \forall\ i=1,2\\\
(\ell_{1}^{T}w)(\ell_{2}^{T}w)=0\end{array}\right\\}$

equals

$\mathcal{R}^{0}:=\left\\{W\in\mathcal{PSD}^{n+2}:\begin{array}[]{l}J_{n+1}\bullet
P^{T}WP\geq 0\\\ P^{T}W\ell_{i}\in\mathcal{SOC}^{n+1}\ \ \forall\ i=1,2\\\
\ell_{1}^{T}W\ell_{2}=0\end{array}\right\\}.$

A closely related result is theorem 2.7 in [26]. Theorem 1 is slightly
different, however, because the second-order cone is expressed in a smaller
dimension ($n+1$) than the ambient dimension ($n+2$). So we prove Theorem 1
rigorously here, and in particular, we adapt a proof technique from [8].

We first prove some lemmas. To simplify notation a bit, let $J:=J_{n+1}$
throughout the rest of this section. Our first lemma states some
straightforward properties of $J$.

######  Lemma 1.

Regarding $J$, it holds that:

  1. (i)

If $v\in\mathcal{SOC}^{n+1}$, then $Jv\in\mathcal{SOC}^{n+1}$, and hence
$w^{T}Jv\geq 0$ for all $w\in\mathcal{SOC}^{n+1}$.

  2. (ii)

If $v\in\operatorname{bd}(\mathcal{SOC}^{n+1})$, then $v^{T}Jv=0$.

The next two lemmas are analagous to the exactness results of Shor and
$\text{\sc Shor}\cap\text{\sc SOCRLT}$ discussed in Section 2.2.

######  Lemma 2.

$\operatorname{conic.hull}\\{ww^{T}:P^{T}w\in\mathcal{SOC}^{n+1}\\}=\\{W\in\mathcal{PSD}^{n+2}:J\bullet
P^{T}WP\geq 0\\}.$

###### Proof.

This can be proven, for example, by showing that all extreme rays of the
right-hand-side set have rank-1, which can in turn be shown via Pataki’s bound
on the rank of extreme matrices of SDP-representable sets [20]. ∎

######  Lemma 3.

Fix $i=1$ or $i=2$. It holds that

$\operatorname{conic.hull}\left\\{ww^{T}:\begin{array}[]{l}P^{T}w\in\mathcal{SOC}^{n+1}\\\
\ell_{i}^{T}w\geq
0\end{array}\right\\}=\left\\{W\in\mathcal{PSD}^{n+2}:\begin{array}[]{l}J\bullet
P^{T}WP\geq 0\\\ P^{T}W\ell_{i}\in\mathcal{SOC}^{n+1}\end{array}\right\\}.$

###### Proof.

In the statement of the proposition, let $\mathcal{G}[i]$ be the left-hand-
side set, and let $\mathcal{R}[i]$ be the right-hand side. Clearly
$\mathcal{G}[i]\subseteq\mathcal{R}[i]$. We show the reverse inclusion by
proving $\mathcal{R}[i]$ has rank-1 extreme rays. Indeed, let $W\neq 0$ be an
arbitrary extreme ray in $\mathcal{R}[i]$. We will show
$\operatorname{rank}(W)=1$ by considering three cases

First consider when
$P^{T}W\ell_{i}\in\operatorname{int}(\mathcal{SOC}^{n+1})$, in which case $W$
must also be extreme in $\\{W\in\mathcal{PSD}^{n+2}:J\bullet P^{T}WP\geq
0\\}$. Then $\operatorname{rank}(W)=1$ by Lemma 2.

Next consider when $P^{T}W\ell_{i}\in\operatorname{bd}(\mathcal{SOC}^{n+1})$
with $W\ell_{i}=0$. Using Lemma 2, we write $W=\sum_{k}w^{k}(w^{k})^{T}$ for
$w^{k}$ satisfying $P^{T}w^{k}\in\mathcal{SOC}^{n+1}$. We then have

$W\ell_{i}=0\quad\Rightarrow\quad\ell_{i}^{T}W\ell_{i}=0\quad\Rightarrow\quad\sum_{k}(\ell_{i}^{T}w^{k})^{2}=0\quad\Rightarrow\quad\ell_{i}^{T}w^{k}=0\
\ \forall\ k,$

which proves $W\in\mathcal{G}[i]$ and hence $W$ is extreme in
$\mathcal{G}[i]$. Thus, $\operatorname{rank}(W)=1$, as desired.

Finally, consider when
$P^{T}W\ell_{i}\in\operatorname{bd}(\mathcal{SOC}^{n+1})$ with $W\ell_{i}\neq
0$. Define $v:=W\ell_{i}\neq 0$ so that
$P^{T}v\in\operatorname{bd}(\mathcal{SOC}^{n+1})$. In addition,
$W\in\mathcal{PSD}^{n+2}$ implies $\ell_{i}^{T}v=\ell_{i}^{T}W\ell_{i}\geq 0$.
Hence, we conclude that $vv^{T}$ is a nonzero member of
$\mathcal{G}[i]\subseteq\mathcal{R}[i]$. Next, for small $\epsilon>0$, define
$W_{\epsilon}:=W-\epsilon\,vv^{T}$; we claim $W_{\epsilon}\in\mathcal{R}[i]$.
Indeed, $W_{\epsilon}\in\mathcal{PSD}^{n+2}$ because it is a rank-1
perturbation of $W\in\mathcal{PSD}^{n+2}$ with $v\in\operatorname{Range}(W)$
[10, lemma 2]. Moreover, $P^{T}v\in\operatorname{bd}(\mathcal{SOC}^{n+1})$
implies by Lemma 1(ii) that

$J\bullet P^{T}W_{\epsilon}P=J\bullet
P^{T}WP-\epsilon(P^{T}v)^{T}J(P^{T}v)=J\bullet P^{T}WP-\epsilon\cdot 0\geq 0.$

We also have

$P^{T}W_{\epsilon}\ell_{i}=P^{T}W\ell_{i}-\epsilon(\ell_{i}^{T}v)P^{T}v=(1-\epsilon\cdot\ell_{i}^{T}v)P^{T}v\in\operatorname{bd}(\mathcal{SOC}^{n+1}).$

Thus, when $\epsilon>0$ is small, $W_{\epsilon}\in\mathcal{R}[i]$ as claimed.
Then the equation $W=W_{\epsilon}+\epsilon\,vv^{T}$ and the fact that $W$ is
extreme in $\mathcal{R}[i]$ imply $W$ must be a positive multiple of $vv^{T}$,
i.e., $\operatorname{rank}(W)=1$, as desired. ∎

Our next lemma is a technical result about extreme rays in the intersection of
two closed convex cones.

######  Lemma 4.

Let $\mathcal{P}$ be a closed convex cone, and let $\mathcal{Q}$ be a half-
space containing the origin. Every extreme ray of $\mathcal{P}\cap\mathcal{Q}$
is either an extreme ray of $\mathcal{P}$ or can be expressed as the sum of
two extreme rays of $\mathcal{P}$.

###### Proof.

See [8, Lemma 5]. ∎

We are now ready to prove Theorem 1.

###### Proof.

Since $\mathcal{G}^{0}\subseteq\mathcal{R}^{0}$ by construction, we show the
reverse inclusion by proving that every extreme ray $W$ of $\mathcal{R}^{0}$
has rank 1 and hence is an element of $\mathcal{G}^{0}$. We define
$v_{i}:=W\ell_{i}$ for $i=1,2$. Note that $v_{1}v_{1}^{T}\in\mathcal{G}^{0}$
because $\ell_{1}^{T}v_{1}=\ell_{1}^{T}W\ell_{1}\geq 0$,
$\ell_{2}^{T}v_{1}=\ell_{2}^{T}W\ell_{1}=0$, and
$P^{T}v_{1}=P^{T}W\ell_{1}\in\mathcal{SOC}^{n+1}$. A similar argument shows
$v_{2}v_{2}^{T}\in\mathcal{G}^{0}$.

We first consider the case when $v_{1}=0$. Applying Lemma 3 for the case
$i=2$, we express $W$ as

$W=\sum_{k}w^{k}(w^{k})^{T},\quad P^{T}w^{k}\in\mathcal{SOC}^{n+1}\text{ and
}\ell_{2}^{T}w^{k}\geq 0\quad\forall\ k.$

As in the proof of Lemma 3, $v_{1}=0$ then implies $\ell_{1}^{T}w^{k}=0$ for
all $k$. So $W\in\mathcal{G}^{0}$, and because $W$ is extreme in
$\mathcal{R}^{0}\supseteq\mathcal{G}^{0}$, it must have rank 1. A similar
argument shows $\operatorname{rank}(W)=1$ for the case $v_{2}=0$.

So we assume from this point forward that $v_{i}:=W\ell_{i}\neq 0$ for both
$i=1,2$. Since $W\in\mathcal{PSD}^{n+2}$ ensures
$W\ell_{i}=0\Leftrightarrow\ell_{i}^{T}W\ell_{i}=0$, we have
$\ell_{i}^{T}v_{i}=\ell_{i}^{T}W\ell_{i}>0$ for both $i$.

The second case we consider assumes $J\bullet P^{T}WP=0$ and
$P^{T}v_{i}=P^{T}W\ell_{i}\in\operatorname{int}(\mathcal{SOC}^{n+1})$ for both
$i=1,2$. Then $W$ is extreme for the equality-constrained cone
$\\{W\in\mathcal{PSD}^{n+2}:J\bullet P^{T}WP=0,\ell_{1}^{T}W\ell_{2}=0\\}$,
which in turn implies that $W$ is extreme for the inequality-constrained cone
$\mathcal{P}\cap\mathcal{Q}$, where

$\mathcal{P}:=\left\\{W\in\mathcal{PSD}^{n+2}:J\bullet P^{T}WP\geq
0\right\\},\ \ \ \
\mathcal{Q}:=\\{W\in\mathbb{S}^{n+2}:\ell_{1}^{T}W\ell_{2}\geq 0\\},$

Applying Lemma 2 with $\mathcal{P}$ and Lemma 4 with
$\mathcal{P}\cap\mathcal{Q}$, we conclude that $\operatorname{rank}(W)\leq 2$.
If its rank equals 1, we are done. So assume $\operatorname{rank}(Y)=2$. We
derive a contradiction to the assumption that $W$ is extreme in
$\mathcal{R}^{0}$. Consider the equation

$U:=\begin{pmatrix}\ell_{1}^{T}\\\ \ell_{2}^{T}\\\
I\end{pmatrix}W\begin{pmatrix}\ell_{1}&\ell_{2}&I\end{pmatrix}=\begin{pmatrix}\ell_{1}^{T}W\ell_{1}&\ell_{1}^{T}W\ell_{2}&\ell_{1}^{T}W\\\
\ell_{2}^{T}W\ell_{1}&\ell_{2}W\ell_{2}&\ell_{2}^{T}W\\\
W\ell_{1}&W\ell_{2}&W\end{pmatrix}=\begin{pmatrix}\ell_{1}^{T}v_{1}&0&v_{1}^{T}\\\
0&\ell_{2}^{T}v_{2}&v_{2}^{T}\\\ v_{1}&v_{2}&W\end{pmatrix},$

and recall that $\ell_{1}^{T}v_{1}>0$ and $\ell_{2}^{T}v_{2}>0$. It holds that
$U$ is PSD with $\operatorname{rank}(U)\leq\operatorname{rank}(W)=2$, and the
Schur complement theorem implies

$M:=W-(\ell_{1}^{T}v_{1})^{-1}v_{1}v_{1}^{T}-(\ell_{2}^{T}v_{2})^{-1}v_{2}v_{2}^{T}\in\mathcal{PSD}^{n+2},$

with $\operatorname{rank}(M)=\operatorname{rank}(W)-2$. So
$\operatorname{rank}(M)\leq 0$ and hence $M=0$, that is,

$W=(\ell_{1}^{T}v_{1})^{-1}v_{1}v_{1}^{T}+(\ell_{2}^{T}v_{2})^{-1}v_{2}v_{2}^{T},$

contradicting the assumption that $W$ is extreme in $\mathcal{R}^{0}$ due to
the fact that both $v_{1}v_{1}^{T}$ and $v_{2}v_{2}^{T}$ are elements of
$\mathcal{G}^{0}\subseteq\mathcal{R}^{0}$.

For our third and final case, we assume $J\bullet P^{T}WP>0$,
$P^{T}v_{1}\in\operatorname{bd}(\mathcal{SOC}^{n+1})$, or
$P^{T}v_{2}\in\operatorname{bd}(\mathcal{SOC}^{n+1})$. Let us consider two
perturbations of $W$:

$W_{\epsilon_{i}}:=W-\epsilon_{i}\,v_{i}v_{i}^{T}\quad\forall\ i=1,2$

for two parameters $\epsilon_{i}>0$. We claim that
$W_{\epsilon_{i}}\in\mathcal{R}^{0}$ for at least one $i$, in which case $W$
must be rank-1 as argued in the proof of Lemma 3.

Using $W\in\mathcal{R}^{0}$, we first argue that each $W_{\epsilon_{i}}$
satisfies all constraints of $\mathcal{R}^{0}$, except possibly $J\bullet
P^{T}W_{\epsilon_{i}}P\geq 0$. Fix $i=1$; the proof for $i=2$ is similar. We
know $W_{\epsilon_{1}}\in\mathcal{PSD}^{n+2}$ since
$v_{1}\in\operatorname{Range}(W)$ [10, Lemma 2]. We also have

$P^{T}W_{\epsilon_{1}}\ell_{1}=P^{T}v_{1}-\epsilon_{1}P^{T}v_{1}(v_{1}^{T}\ell_{1})=(1-\epsilon_{1}(v_{1}^{T}\ell_{1}))P^{T}v_{1}\in\mathcal{SOC}^{n+1}$

for small $\epsilon_{1}>0$. Furthermore, noting that
$v_{1}^{T}\ell_{2}=\ell_{1}^{T}W\ell_{2}=0$, we see

$P^{T}W_{\epsilon_{1}}\ell_{2}=P^{T}v_{2}-\epsilon_{1}P^{T}v_{1}(\ell_{1}^{T}W\ell_{2})=P^{T}v_{2}-\epsilon_{1}P^{T}v_{1}\cdot
0=P^{T}v_{2}\in\mathcal{SOC}^{n+1}.$

Finally,

$\ell_{1}^{T}W_{\epsilon_{1}}\ell_{2}=\ell_{1}^{T}W\ell_{2}-\epsilon_{1}(\ell_{1}^{T}v_{1})(v_{1}^{T}\ell_{2})=\ell_{1}^{T}W\ell_{2}-\epsilon_{1}(\ell_{1}^{T}v_{1})(\ell_{1}^{T}W\ell_{2})=0-\epsilon_{1}\cdot\ell_{1}^{T}v_{1}\cdot
0=0,$

as desired.

We now claim that at least one $W_{\epsilon_{i}}$ satisfies the remaining
constraint

$J\bullet P^{T}W_{\epsilon_{i}}P=J\bullet
P^{T}WP-\epsilon_{i}J\bullet(P^{T}v_{i})(P^{T}v_{i})^{T}\geq 0$

for small $\epsilon_{i}>0$, thus completing the proof as discussed above. If
$J\bullet P^{T}WP>0$, then both $W_{\epsilon_{i}}$ satisfy the inequality. If
$P^{T}v_{1}\in\operatorname{bd}(\mathcal{SOC}^{n+1})$, then $W_{\epsilon_{1}}$
satisfies the inequality because $J\bullet(P^{T}v_{i})(P^{T}v_{i})^{T}=0$ by
Lemma 1(ii). Similarly if
$P^{T}v_{2}\in\operatorname{bd}(\mathcal{SOC}^{n+1})$, then $W_{\epsilon_{2}}$
satisfies the inequality. ∎

As just proven, Theorem 1 establishes $\mathcal{G}^{0}=\mathcal{R}^{0}$. A
natural question is whether the analagous sets $\mathcal{G}$ and $\mathcal{R}$
as defined in Section 3 are also equal, i.e., without the complementarity
conditions $(\ell_{1}^{T}w)(\ell_{2}^{T}w)=0$ and $\ell_{1}^{T}W\ell_{2}=0$.
We show in the following proposition that this is not true.

######  Proposition 1.

Let $\mathcal{F}$, $\mathcal{G}$, and $\mathcal{R}$ be defined as in Section 2
with respect to the set (4). Then $\mathcal{G}\subsetneq\mathcal{R}$.

###### Proof.

For $n=3$, $g_{1}=1$, $h_{1}=0$, $g_{2}=0$, and $h_{2}=e$, where $e$ is the
vector of all ones, define

$\hat{U}:=\frac{1}{3}\begin{pmatrix}2&\sqrt{2}&\sqrt{3}\\\ 1&1&-1\\\ 1&1&-1\\\
1&0&-1\\\ \sqrt{3}&\sqrt{2}&\sqrt{3}\end{pmatrix}$

and

$\hat{W}:=\hat{U}\hat{U}^{T}.$

It is straightforward to verify $\hat{W}\in\\{W\in\mathcal{R}:W_{11}=1\\}$
with $P^{T}W\ell_{i}\in\operatorname{bd}(\mathcal{SOC}^{n+1})$ for both
$i=1,2$. As $\operatorname{rank}(\hat{W})=3$, let

$\hat{N}=\begin{pmatrix}[r]0&-2\sqrt{3}\\\ -1&\sqrt{2}(\sqrt{3}-2)\\\ 1&0\\\
0&2(\sqrt{2}+\sqrt{3})-\sqrt{6}-3\\\
0&\sqrt{3}+2\end{pmatrix}\approx\begin{pmatrix}[r]0&-3.4641\\\ -1&-0.3789\\\
1&0.0000\\\ 0&0.8430\\\ 0&3.7321\end{pmatrix}$

be a matrix whose columns span $\text{Null}(\hat{W})$. Also define

$\displaystyle\hat{M}$
$\displaystyle:=e_{1}e_{1}^{T}+\text{symm}\left((PJP^{T}\hat{W})(\ell_{1}\ell_{1}^{T}+\ell_{2}\ell_{2}^{T})\right)+\hat{N}\hat{N}^{T}$
$\displaystyle\approx\begin{pmatrix}[r]13.0000&1.2682&-0.0445&-2.9649&-12.8511\\\
1.2682&-0.4830&-1.6266&-0.8488&-0.5634\\\
-0.0445&-1.6266&-0.6266&-0.5293&0.8508\\\
-2.9649&-0.8488&-0.5293&-0.7213&3.8998\\\
-12.8511&-0.5634&0.8508&3.8998&13.7881\end{pmatrix},$

where $e_{1}$ is the first unit vector and, for any square matrix $H$, we
define $\text{symm}(H):=\tfrac{1}{2}(H+H^{T})$.

Next, we consider the two optimization problems

$\displaystyle v^{*}$
$\displaystyle:=\min\\{w^{T}\hat{M}w:w\in\mathcal{F},\alpha=1\\}=\min\\{\hat{M}\bullet
W:W\in\mathcal{G},W_{11}=1\\},$ $\displaystyle r^{*}$
$\displaystyle:=\min\\{\hat{M}\bullet W:W\in\mathcal{R},W_{11}=1\\}.$

By construction, the first problem is relaxed by the second via the inclusion
$\mathcal{G}\subseteq\mathcal{R}$. In particular, $v^{*}\geq r^{*}$. In fact,
we claim $v^{*}>1=r^{*}$, which will demonstrate that
$\mathcal{G}\subsetneq\mathcal{R}$.

We first argue $r^{*}=1$. Let $W\in\mathcal{R}$ with $W_{11}=1$ be any
feasible point. We have

$\displaystyle\hat{M}\bullet W$
$\displaystyle=\left(e_{1}e_{1}^{T}+\text{symm}\left((PJP^{T}\hat{W})(\ell_{1}\ell_{1}^{T}+\ell_{2}\ell_{2}^{T})\right)+\hat{N}\hat{N}^{T}\right)\bullet
W$ $\displaystyle=e_{1}e_{1}^{T}\bullet
W+(PJP^{T}\hat{W})(\ell_{1}\ell_{1}^{T}+\ell_{2}\ell_{2}^{T})\bullet
W+\hat{N}\hat{N}^{T}\bullet W$
$\displaystyle=W_{11}+(P^{T}\hat{W}\ell_{1})^{T}J(P^{T}W\ell_{1})+(P^{T}\hat{W}\ell_{2})^{T}J(P^{T}W\ell_{2})+\hat{N}\hat{N}^{T}\bullet
W$
$\displaystyle=1+(P^{T}\hat{W}\ell_{1})^{T}J(P^{T}W\ell_{1})+(P^{T}\hat{W}\ell_{2})^{T}J(P^{T}W\ell_{2})+0$
$\displaystyle\geq 1+0+0+0$ $\displaystyle=1,$

where the inequality follows from Lemma 1(i). Moreover, by evaluating
$\hat{M}\bullet W$ at $\hat{W}$, we have

$\displaystyle\hat{M}\bullet\hat{W}$
$\displaystyle=1+(P^{T}\hat{W}\ell_{1})^{T}J(P^{T}\hat{W}\ell_{1})+(P^{T}\hat{W}\ell_{2})^{T}J(P^{T}\hat{W}\ell_{2})+0$
$\displaystyle=1+0+0+0$ $\displaystyle=1,$

where the second equality comes from Lemma 1(ii) and the fact that
$P^{T}W\ell_{i}\in\operatorname{bd}(\mathcal{SOC}^{n+1})$ for both $i$. It
follows that $r^{*}=1$.

To establish $v^{*}>1$, we used the global nonconvex quadratic programming
solver of Gurobi 9.5 to calculate $v^{*}$. Gurobi returned the optimal
solution

$w^{*}=\begin{pmatrix}\alpha^{*}\\\ x^{*}\\\
\beta^{*}\end{pmatrix}\approx\begin{pmatrix}[r]1.0000\\\ 0.5690\\\ 0.5689\\\
0.3957\\\ 0.8966\end{pmatrix},$

satisfying

$\displaystyle\ell_{1}^{T}w^{*}=\beta^{*}-\alpha^{*}g_{0}+h_{0}^{T}x^{*}$
$\displaystyle\approx 0.1034>0,$
$\displaystyle\ell_{2}^{T}w^{*}=\beta^{*}-\alpha^{*}g_{1}+h_{1}^{T}x^{*}$
$\displaystyle\approx 0.6369>0,$ $\displaystyle\beta^{*}-\|x^{*}\|$
$\displaystyle\approx 0.0000,$ $\displaystyle v^{*}=(w^{*})^{T}\hat{M}w^{*}$
$\displaystyle\approx 1.0002>1.$

Moreover, Gurobi reported a best lower bound of approximately $1.0002$ with an
optimality gap of $1.2\times 10^{-8}$. ∎

Related to Conjecture 1, we note that this proof is based on the relaxation
$\min\\{\hat{M}\bullet W:W\in\mathcal{R},W_{11}=1\\}$ for which the RLT
constraint $\ell_{1}^{T}W\ell_{2}\geq 0$ is not active at optimality. However,
note that this specific objective matrix $\hat{M}$ involves the artificial
variable $\beta$, whereas the conjecture applies only to objectives not
involving $\beta$. See also the discussion after Conjecture 1 in Section 3.

##  6 Conclusions

In this paper, we have constructed stronger relaxations for (QP) by
transforming its feasible set, lifting to one higher dimension, and employing
standard relaxation techniques from the literature. Our computational results
demonstrate the strength of our relaxation. In addition, the time required for
solving our relaxation is modest for small values of $m$. We have also
examined an important variant of (QP) based on the feasible set
$\|x\|\leq\min\\{1,g_{2}+h_{2}^{T}x\\}$ and shown that it has an exact, non-
disjunctive semidefinite representation.

There are many open questions related to this research, e.g., Conjecture 1. In
addition, is it possible to prove that our relaxation Beta is always at least
as tight as Kron, which is supported by the computational evidence?
Furthermore, is Beta provably as strong as the method of [16]? Is it possible
to extend Theorem 1 to the case of more constraints of the form $\|x\|\leq
g_{i}+h_{i}^{T}x$? Finally, could our relaxation be used as the basis for an
effective global optimization algorithm of (QP)?

## Statements and Declarations

The author declares that he has no competing interests.

## References

  * [1] T. A. Almaadeed, S. Ansary Karbasy, M. Salahi, and A. Hamdi.  On indefinite quadratic optimization over the intersection of balls and linear constraints.  J. Optim. Theory Appl., 194(1):246–264, 2022.
  * [2] K. M. Anstreicher.  Kronecker product constraints with an application to the two-trust-region subproblem.  SIAM Journal on Optimization, 27(1):368–378, 2017.
  * [3] M. ApS.  The MOSEK Fusion API for Python Manual. Version 10.0.37., 2023.
  * [4] G. Azuma, M. Fukuda, S. Kim, and M. Yamashita.  Exact sdp relaxations for quadratic programs with bipartite graph structures, 2022.
  * [5] A. Beck and D. Pan.  A branch and bound algorithm for nonconvex quadratic optimization with ball and linear constraints.  J. Global Optim., 69(2):309–342, 2017.
  * [6] D. Bienstock.  A note on polynomial solvability of the CDT problem.  SIAM Journal on Optimization, 26(1):488–498, 2016.
  * [7] D. Bienstock and A. Michalka.  Polynomial solvability of variants of the trust-region subproblem.  In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 380–390. ACM, New York, 2014.
  * [8] S. Burer.  A gentle, geometric introduction to copositive optimization.  Math. Program., 151(1, Ser. B):89–116, 2015.
  * [9] S. Burer and K. M. Anstreicher.  Second-order-cone constraints for extended trust-region subproblems.  SIAM Journal on Optimization, 23(1):432–451, 2013.
  * [10] S. Burer, K. M. Anstreicher, and M. Dür.  The difference between $5\times 5$ doubly nonnegative and completely positive matrices.  Linear Algebra Appl., 431(9):1539–1552, 2009.
  * [11] S. Burer and B. Yang.  The trust region subproblem with non-intersecting linear constraints.  Mathematical Programming, 149(1-2, Ser. A):253–264, 2015.
  * [12] S. Burer and Y. Ye.  Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs.  Math. Program., 181(1, Ser. A):1–17, 2020.
  * [13] S. Burer and Y. Ye.  Correction to: Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs.  Math. Program., 190(1-2, Ser. A):845–848, 2021.
  * [14] C. Chen, A. Atamtürk, and S. S. Oren.  A spatial branch-and-cut method for nonconvex QCQP with bounded complex variables.  Mathematical Programming, 165(2, Ser. A):549–577, 2017.
  * [15] L. Consolini and M. Locatelli.  Sharp and fast bounds for the celis-dennis-tapia problem, 2021.
  * [16] A. Eltved and S. Burer.  Strengthened SDP relaxation for an extended trust region subproblem with an application to optimal power flow.  Math. Program., 197(1, Ser. A):281–306, 2023.
  * [17] R. Jiang and D. Li.  Second order cone constrained convex relaxations for nonconvex quadratically constrained quadratic programming.  Journal of Global Optimization, 75(2):461–494, June 2019.
  * [18] S. Kelly, Y. Ouyang, and B. Yang.  A note on semidefinite representable reformulations for two variants of the trust-region subproblem.  Manuscript, School of Mathematical and Statistical Sciences, Clemson University, Clemson, South Carolina, USA, 2022.
  * [19] M. Locatelli.  Kkt-based primal-dual exactness conditions for the shor relaxation.  Journal of Global Optimization, 2022.  Published online: 29 November 2022.
  * [20] G. Pataki.  On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues.  Math. Oper. Res., 23:339–358, 1998.
  * [21] F. Rendl and H. Wolkowicz.  A semidefinite framework for trust region subproblems with applications to large scale minimization.  Math. Programming, 77(2, Ser. B):273–299, 1997.
  * [22] H. D. Sherali and W. P. Adams.  A reformulation-linearization technique for solving discrete and continuous nonconvex problems, volume 31 of Nonconvex Optimization and its Applications.  Kluwer Academic Publishers, Dordrecht, 1999.
  * [23] S. Sojoudi and J. Lavaei.  Exactness of semidefinite relaxations for nonlinear optimization problems with underlying graph structure.  SIAM J. Optim., 24(4):1746–1778, 2014.
  * [24] J. F. Sturm and S. Zhang.  On cones of nonnegative quadratic functions.  Math. Oper. Res., 28(2):246–267, 2003.
  * [25] A. L. Wang and F. Kılı nç Karzan.  On the tightness of SDP relaxations of QCQPs.  Math. Program., 193(1, Ser. A):33–73, 2022.
  * [26] Y. Ye and S. Zhang.  New results on quadratic minimization.  SIAM J. Optim., 14(1):245–267 (electronic), 2003.
  * [27] J. Zhen, D. de Moor, and D. den Hertog.  An extension of the reformulation-linearization technique to nonlinear optimization.  Manuscript, ETH Zürich, , Zürich, Switzerland, 2022.