remarkRemark hypothesisHypothesis claimClaim assumptionAssumption
exampleExample Exploiting Sign Symmetries in Minimizing SORFF. Guo, J. Wang,
and J. Zheng

# Exploiting Sign Symmetries in Minimizing Sums of Rational Functions††thanks:
Submitted to the editors DATE. This work was funded by National Key R&D
Program of China under grant No. 2023YFA1009401, Natural Science Foundation of
China under grant No. 12201618 and 12171324.

Feng Guo School of Mathematical Sciences, Dalian University of Technology,
Dalian 116024, Liaoning Province, China<EMAIL_ADDRESS>Jie Wang Academy
of Mathematics and Systems Science, Chinese academy of sciences, Beijing
100190, China<EMAIL_ADDRESS>Jianhao Zheng School of Mathematical
Sciences, Dalian University of Technology, Dalian 116024, Liaoning Province,
China.

###### Abstract

This paper is devoted to the problem of minimizing a sum of rational functions
over a basic semialgebraic set. We provide a hierarchy of sum of squares (SOS)
relaxations that is dual to the generalized moment problem approach due to
Bugarin, Henrion, and Lasserre. The investigation of the dual SOS aspect
offers two benefits: 1) it allows us to conduct a convergence rate analysis
for the hierarchy; 2) it leads to a sign symmetry adapted hierarchy consisting
of block-diagonal semidefinite relaxations. When the problem possesses
correlative sparsity as well as sign symmetries, we propose sparse
semidefinite relaxations by exploiting both structures. Various numerical
experiments are performed to demonstrate the efficiency of our approach.
Finally, an application to maximizing sums of generalized Rayleigh quotients
is presented.

###### keywords:

sum of rational functions, sign symmetry, semidefinite relaxation, correlative
sparsity, generalized Rayleigh quotient

90C23, 90C22, 90C26

##  1 Introduction

In this paper, we consider the optimization problem of minimizing a sum of
rational functions:

(SRFO)
$\rho\coloneqq\inf_{x\in\mathbf{K}}\sum_{i=1}^{N}\frac{p_{i}(\mathbf{x})}{q_{i}(\mathbf{x})},$

where

(1) $\mathbf{K}\coloneqq\\{\mathbf{x}\in{\mathbb{R}}^{n}\mid
g_{j}(\mathbf{x})\geq 0,\ j=1,\ldots,m\\},$

and $p_{i},q_{i},g_{j}$ are polynomials in variables
$\mathbf{x}=(x_{1},\ldots,x_{n})$. Throughout the paper, we make the following
assumption on (SRFO): (i) $\mathbf{K}$ is compact; (ii) $q_{i}>0$ on
$\mathbf{K}$ for $i=1,\ldots,N$. The problem (SRFO) has applications in
various fields, including computer vision [7, 9], multi-user MIMO systems
[21], sparse Fisher discriminant analysis in pattern recognition [4, 5, 32].

Given the potentially large number of terms $N$ and the absence of convexity
(resp. concavity) assumptions on $p_{i}$ (resp. $q_{i}$), globally solving
(SRFO) or achieving a close approximation of the optimum $\rho$ presents
significant challenges. In literature, (SRFO) is often called a sum-of-ratios
program which stands as one of the most complex fractional programs
encountered to date. For strategies of tackling sum-of-ratios programs under
specific assumptions regarding concavity and linearity of ratios, the reader
may refer to the survey [24] and [33, Table 1].

In the scenario where $N=1$, by utilizing the polynomial structure in (SRFO)
and Positivstellensätze from real algebraic geometry, some hierarchies of
semidefinite programming (SDP) relaxations were proposed in [8, 18]. The basic
idea is to maximizing a number $\gamma\in{\mathbb{R}}$ subject to the
nonnegativity of $p_{1}-\gamma q_{1}$ on $\mathbf{K}$ which can be ensured by
certain sum of squares (SOS) representations. In [6], the problem of
minimizing a rational function was reformulated as a polynomial optimization
problem and solved by the exact Jacobian SDP relaxation method proposed by Nie
[17].

For the case that $N>1$, one could attempt to reduce all rational functions
$p_{i}/q_{i}$ to the same denominator and apply the hierarchies of SDP
relaxations mentioned above. However, due to the potentially large value of
$N$, the resulting unified denominator may have a significantly high degree,
which makes it impractical to even solve the first order relaxations of the
hierarchies. To overcome this difficulty, Bugarin, Henrion, and Lasserre [3]
reformulated (SRFO) as an equivalent infinite-dimensional linear program which
is a particular instance of the generalized moment problem (GMP) with $N$
unknown measures. The GMP can be relaxed into a hierarchy of SDPs which
provides increasingly tight lower bounds on $\rho$. When a correlative
sparsity pattern is present in the polynomial data of (SRFO), a sparse GMP
reformulation for (SRFO) and a corresponding hierarchy of sparse SDP
relaxations were also proposed in [3]. By employing pushforward measures,
Lasserre et al. [12] gave an approach yielding convergent upper bounds on
$\rho$.

Contributions. Our main contributions are summarized as follows:

  1. 1.

By studying the Lagrange dual problem, we unveil that the core strategy of the
GMP approach is to replace the terms $p_{i}/q_{i}$, $i=2,\ldots,N$ by
polynomial approximations from below on $\mathbf{K}$, leading to a problem
with a single denominator. As a result, we provide a hierarchy of SOS
relaxations that is dual to the GMP approach due to Bugarin, Henrion, and
Lasserre. Moreover, we are able to conduct a convergence rate analysis for the
hierarchy of SDP relaxations for (SRFO).

  2. 2.

We present a sign symmetry adapted hierarchy consisting of block-diagonal SDP
relaxations for (SRFO). Furthermore, when both correlative sparsity and sign
symmetries are present in the polynomial data of (SRFO), we show that the
exploitation of sign symmetries can be naturally incorporated into the sparse
hierarchy of SDP relaxations for (SRFO), thereby further reducing the
computational cost. Various numerical experiments demonstrate the efficiency
of our approach.

The rest of the paper is organized as follows. We first recall some
preliminaries and the GMP approach for (SRFO) in Section 2. In Section 3, we
investigate the dual aspect of the GMP approach and conduct convergence rate
analysis for the SDP hierarchy. In Section 4, we develop sparse SDP
relaxations for (SRFO) by exploiting sign symmetries as well as correlative
sparsity present in the problem data. Numerical experiments are presented in
Section 5 and an application to maximizing sums of generalized Rayleigh
quotients is provided in Section 6.

##  2 Notation and Preliminaries

Let $\mathbb{N}$ denote the set of nonnegative integers. For
$n\in\mathbb{N}\setminus\\{0\\}$, let $[n]\coloneqq\\{1,2,\ldots,n\\}$. For
$k\in\mathbb{N}$, let
$\mathbb{N}^{n}_{k}\coloneqq\\{{\boldsymbol{\alpha}}=(\alpha_{i})\in\mathbb{N}^{n}\mid\sum_{i=1}^{n}\alpha_{i}\leq
k\\}$. We use $|\cdot|$ to denote the cardinality of a set. Let
${\mathbb{R}}[\mathbf{x}]\coloneqq{\mathbb{R}}[x_{1},\ldots,x_{n}]$ be the
ring of multivariate polynomials in $n$ variables $\mathbf{x}$, and
${\mathbb{R}}[\mathbf{x}]_{k}$ denote the subset of polynomials of degree no
greater than $k$. A polynomial $f\in{\mathbb{R}}[\mathbf{x}]$ can be written
as
$f=\sum_{{\boldsymbol{\alpha}}\in\mathbb{N}^{n}}f_{{\boldsymbol{\alpha}}}\mathbf{x}^{{\boldsymbol{\alpha}}}$
with $f_{{\boldsymbol{\alpha}}}\in{\mathbb{R}}$ and
$\mathbf{x}^{{\boldsymbol{\alpha}}}\coloneqq x_{1}^{\alpha_{1}}\cdots
x_{n}^{\alpha_{n}}$. The support of $f$ is defined by
$\mbox{supp}(f)\coloneqq\\{{\boldsymbol{\alpha}}\in\mathbb{N}^{n}\mid
f_{{\boldsymbol{\alpha}}}\neq 0\\}$. For $\mathcal{A}\subseteq\mathbb{N}^{n}$,
${\mathbb{R}}[\mathcal{A}]$ denotes the set of polynomials with supports
contained in $\mathcal{A}$, i.e.,
${\mathbb{R}}[\mathcal{A}]\coloneqq\\{f\in{\mathbb{R}}[\mathbf{x}]\mid\mbox{supp}(f)\subseteq\mathcal{A}\\}$.
For $\mathbf{u}=(u_{1},\ldots,u_{n})\in{\mathbb{R}}^{n}$, $\|\mathbf{u}\|$
denotes the standard Euclidean norm of $\mathbf{u}$. For $t\in\mathbb{R}$, we
use $\lceil t\rceil$ to denote the smallest integer that is not smaller than
$t$. We use $A\succeq 0$ to indicate that the matrix $A$ is positive
semidefinite. For two matrices $A,B$ of the same size, let $A\circ B$ denote
the Hadamard product, defined by $[A\circ B]_{ij}=A_{ij}B_{ij}$.

###  2.1 Sums of squares and moments

We recall some background about SOS polynomials and the dual theory of moment
matrices. A polynomial $f(\mathbf{x})\in{\mathbb{R}}[\mathbf{x}]$ is said to
be a _sum of squares_ if it can be written as
$f(\mathbf{x})=\sum_{i=1}^{t}f_{i}(\mathbf{x})^{2}$ for some
$f_{1}(\mathbf{x}),\ldots,f_{t}(\mathbf{x})\in{\mathbb{R}}[\mathbf{x}]$. Let
$\Sigma[\mathbf{x}]$ denote the set of SOS polynomials in
${\mathbb{R}}[\mathbf{x}]$.

Let $\mathbf{g}\coloneqq\\{g_{1},\ldots,g_{m}\\}$ be the set of polynomials
that defines the semialgebraic set $\mathbf{K}$ in (1). We denote by

$\mathcal{Q}(\mathbf{g})\coloneqq\left\\{\sigma_{0}+\sum_{j=1}^{m}\sigma_{j}g_{j}\
\middle|\ \sigma_{j}\in\Sigma[\mathbf{x}],j\in\\{0\\}\cup[m]\right\\}$

the quadratic module generated by $\mathbf{g}$ and denote by

$\mathcal{Q}_{k}(\mathbf{g})\coloneqq\left\\{\sigma_{0}+\sum_{j=1}^{m}\sigma_{j}g_{j}\
\middle|\
\sigma_{0},\sigma_{j}\in\Sigma[\mathbf{x}],\deg(\sigma_{0}),\deg(\sigma_{j}g_{j})\leq
2k,j\in[m]\right\\}$

the $k$-th truncated quadratic module. It is clear that if
$f\in\mathcal{Q}(\mathbf{g})$, then $f(\mathbf{x})\geq 0$ for any
$\mathbf{x}\in\mathbf{K}$ though the converse is not necessarily true.

Given a (pseudo-moment) sequence of real numbers
$\mathbf{y}\coloneqq(y_{{\boldsymbol{\alpha}}})_{{\boldsymbol{\alpha}}\in\mathbb{N}^{n}}$,
the $k$-th order moment matrix is the matrix $\mathbf{M}_{k}(\mathbf{y})$
indexed by $\mathbb{N}^{n}_{k}$ with the
$({\boldsymbol{\alpha}},{\boldsymbol{\beta}})$-th entry being
$y_{{\boldsymbol{\alpha}}+{\boldsymbol{\beta}}}$. Given a polynomial
$f(\mathbf{x})=\sum_{{\boldsymbol{\alpha}}}f_{{\boldsymbol{\alpha}}}\mathbf{x}^{{\boldsymbol{\alpha}}}$,
the $k$-th order localizing matrix $\mathbf{M}_{k}(f\mathbf{y})$ indexed by
$\mathbb{N}^{n}_{k}$ is defined by
$[\mathbf{M}_{k}(f\mathbf{y})]_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}=\sum_{{\boldsymbol{\alpha}}}f_{{\boldsymbol{\alpha}}}y_{{\boldsymbol{\alpha}}+{\boldsymbol{\beta}}+{\boldsymbol{\gamma}}}$.
The Riesz functional $L_{\mathbf{y}}$ on ${\mathbb{R}}[\mathbf{x}]$ is defined
by
$L_{\mathbf{y}}\left(\sum_{{\boldsymbol{\alpha}}}f_{{\boldsymbol{\alpha}}}\mathbf{x}^{{\boldsymbol{\alpha}}}\right)\coloneqq\sum_{{\boldsymbol{\alpha}}}f_{{\boldsymbol{\alpha}}}y_{{\boldsymbol{\alpha}}}$.

######  Definition 2.1 (Archimedean condition).

We say that $\mathcal{Q}(\mathbf{g})$ is Archimedean if there exists $M>0$
such that $M-x_{1}^{2}-\cdots-x_{n}^{2}\in\mathcal{Q}(\mathbf{g})$.

Note that the Archimedean condition implies that $\mathbf{K}$ is compact and
the converse is not necessarily true. However, for any compact set
$\mathbf{K}$, we could always force the associated quadratic module to be
Archimedean by adding a redundant constraint $M-x_{1}^{2}-\cdots-x_{n}^{2}\geq
0$ in the description of $\mathbf{K}$ for sufficiently large $M$.

######  Theorem 2.2.

[22, Putinar’s Positivstellensatz] Suppose that $\mathcal{Q}(\mathbf{g})$ is
Archimedean. If a polynomial $f\in{\mathbb{R}}[\mathbf{x}]$ is positive on
$\mathbf{K}$, then $f\in\mathcal{Q}_{k}(\mathbf{g})$ for some
$k\in\mathbb{N}$.

###  2.2 The GMP reformulation and SDP relaxations

In [3], Bugarin et al. reformulated (SRFO) as the following GMP:

(P) $\left\\{\begin{aligned} \inf_{\mu_{i}\in\mathcal{M}(\mathbf{K})_{+}}&\
\sum_{i=1}^{N}\int_{\mathbf{K}}p_{i}\mathrm{d}\mu_{i}\\\ \text{s.t.}\quad\,&\
\int_{\mathbf{K}}q_{1}\mathrm{d}\mu_{1}=1,\\\ &\
\int_{\mathbf{K}}\mathbf{x}^{{\boldsymbol{\alpha}}}q_{i}\mathrm{d}\mu_{i}=\int_{\mathbf{K}}\mathbf{x}^{{\boldsymbol{\alpha}}}q_{1}\mathrm{d}\mu_{1},\quad\forall{\boldsymbol{\alpha}}\in\mathbb{N}^{n},i\in[N]\setminus\\{1\\},\end{aligned}\right.$

where $\mathcal{M}(\mathbf{K})_{+}$ denotes the set of finite positive Borel
measures supported on $\mathbf{K}$.

Let

$\displaystyle d_{j}$ $\displaystyle\coloneqq\lceil\deg(g_{j})/2\rceil,\quad
j\in[m],$ $\displaystyle d_{\min}$
$\displaystyle\coloneqq\max\,\\{\lceil\deg(p_{i})/2\rceil,\lceil\deg(q_{i})/2\rceil,i\in[N];\,d_{j},j\in[m]\\}.$

Based on the reformulation (P), Bugarin et al. further proposed the following
hierarchy of SDP relaxations for (SRFO) ($k\geq d_{\min}$):

(P$k$) $\left\\{\begin{aligned} \inf_{\mathbf{y}_{i}}&\
\sum_{i=1}^{N}L_{\mathbf{y}_{i}}(p_{i})\\\ \text{s.t.}&\
\mathbf{M}_{k}(\mathbf{y}_{i})\succeq 0,\quad i\in[N],\\\ &\
\mathbf{M}_{k-d_{j}}(g_{j}\mathbf{y}_{i})\succeq 0,\quad i\in[N],j\in[m],\\\
&\ L_{\mathbf{y}_{1}}(q_{1})=1,\\\ &\
L_{\mathbf{y}_{i}}(\mathbf{x}^{{\boldsymbol{\alpha}}}q_{i})=L_{\mathbf{y}_{1}}(\mathbf{x}^{{\boldsymbol{\alpha}}}q_{1}),\quad\forall{\boldsymbol{\alpha}}\in\mathbb{N}^{n}_{2k-\max\\{\deg(q_{1}),\deg(q_{i})\\}},i\in[N]\setminus\\{1\\}.\end{aligned}\right.$

It was shown in [3] that under Assumption 1 and the Archimedean condition, the
sequence of optima of (P$k$) converges to $\rho$ as $k\to\infty$.

##  3 The dual perspective and convergence rate analysis

In this section, we will unveil the underlying principle of the GMP
reformulation (P) for (SRFO) from the dual perspective, which enables us to
achieve a convergence rate analysis of the hierarchy of SDP relaxations for
(SRFO).

###  3.1 The dual perspective

Let us derive the Lagrange dual problem of the GMP reformulation (P) for
(SRFO). Note that there are infinitely many constraints involved in (P). To
formulate the dual problem, we need to embed these constraints into an
appropriate functional space paired with a dual space [25]. Let $\mathcal{Y}$
be the space of all functions $\omega:\mathbb{N}^{n}\to{\mathbb{R}}$ equipped
with natural algebraic operations of addition and multiplication by a scalar.
We associate this space with the dual space $\mathcal{Y}^{*}$ consisting of
functions $\omega^{*}:\mathbb{N}^{n}\to{\mathbb{R}}$ such that only a finite
number of values
$\omega^{*}({\boldsymbol{\alpha}}),{\boldsymbol{\alpha}}\in\mathbb{N}^{n}$ are
nonzero. For $\omega\in\mathcal{Y}$ and $\omega^{*}\in\mathcal{Y}^{*}$, define
the scalar product

$\langle\omega^{*},\omega\rangle\coloneqq\sum_{{\boldsymbol{\alpha}}\in\mathbb{N}^{n}}\omega^{*}({\boldsymbol{\alpha}})\omega({\boldsymbol{\alpha}}),$

where the summation is performed over ${\boldsymbol{\alpha}}$ in the finite
support set of $\omega^{*}$. Equivalently, we can take $\mathcal{Y}^{*}$ to be
the polynomial ring ${\mathbb{R}}[\mathbf{x}]$. For any
$h(\mathbf{x})=\sum_{{\boldsymbol{\alpha}}\in\mathbb{N}^{n}}h_{{\boldsymbol{\alpha}}}\mathbf{x}^{{\boldsymbol{\alpha}}}\in{\mathbb{R}}[\mathbf{x}]$
and $\omega\in\mathcal{Y}$, define the scalar product

$\langle
h,\omega\rangle\coloneqq\sum_{{\boldsymbol{\alpha}}\in\mathbb{N}^{n}}h_{{\boldsymbol{\alpha}}}\omega({\boldsymbol{\alpha}}).$

Clearly, for each $i\in[N]\setminus\\{1\\}$, the mapping
$\omega_{i}:\mathbb{N}^{n}\to{\mathbb{R}}$ defined by

$\omega_{i}({\boldsymbol{\alpha}})\coloneqq\int_{\mathbf{K}}\mathbf{x}^{{\boldsymbol{\alpha}}}q_{i}\mathrm{d}\mu_{i}-\int_{\mathbf{K}}\mathbf{x}^{{\boldsymbol{\alpha}}}q_{1}\mathrm{d}\mu_{1},\
\ \forall{\boldsymbol{\alpha}}\in\mathbb{N}^{n},$

belongs to the space $\mathcal{Y}$, and then the second part of constraints of
(P) can be expressed as $\omega_{i}=0,i\in[N]\setminus\\{1\\}$. Let
$h_{i}=\sum_{{\boldsymbol{\alpha}}\in\mathbb{N}^{n}}h^{i}_{{\boldsymbol{\alpha}}}\mathbf{x}^{{\boldsymbol{\alpha}}}\in{\mathbb{R}}[\mathbf{x}]$
be the dual variable associated with the constraint
$\omega_{i}=0,i\in[N]\setminus\\{1\\}$, and let $c$ be the dual variable
associated with the constraint $\int_{\mathbf{K}}q_{1}\mathrm{d}\mu_{1}=1$.
The Lagrangian of (P) now can be written as

$\displaystyle\mathcal{L}(\\{\mu_{i}\\},\\{h_{i}\\},c)\coloneqq$
$\displaystyle\sum_{i=1}^{N}\int_{\mathbf{K}}p_{i}\mathrm{d}\mu_{i}-c\left(\int_{\mathbf{K}}q_{1}\mathrm{d}\mu_{1}-1\right)-\sum_{i=2}^{N}\langle
h_{i},\omega_{i}\rangle$ $\displaystyle=$
$\displaystyle\,c+\sum_{i=1}^{N}\int_{\mathbf{K}}p_{i}\mathrm{d}\mu_{i}-\int_{\mathbf{K}}cq_{1}\mathrm{d}\mu_{1}-\sum_{i=2}^{N}\sum_{{\boldsymbol{\alpha}}\in\mathbb{N}^{n}}h^{i}_{{\boldsymbol{\alpha}}}\left(\int_{\mathbf{K}}\mathbf{x}^{{\boldsymbol{\alpha}}}q_{i}\mathrm{d}\mu_{i}-\int_{\mathbf{K}}\mathbf{x}^{{\boldsymbol{\alpha}}}q_{1}\mathrm{d}\mu_{1}\right)$
$\displaystyle=$
$\displaystyle\,c+\int_{\mathbf{K}}\left(p_{1}-cq_{1}+q_{1}\sum_{i=2}^{N}h_{i}\right)\mathrm{d}\mu_{1}+\sum_{i=2}^{N}\int_{\mathbf{K}}\left(p_{i}-q_{i}h_{i}\right)\mathrm{d}\mu_{i}.$

The Lagrange dual function of (P) is

$\inf_{\mu_{i}\in\mathcal{M}(\mathbf{K})_{+}}\mathcal{L}(\\{\mu_{i}\\},\\{h_{i}\\},c)=\left\\{\begin{array}[]{ll}c,&\text{if}\
p_{1}-q_{1}(c-\sum_{i=2}^{N}h_{i})\geq 0,\ p_{i}-q_{i}h_{i}\geq 0\ \text{on}\
\mathbf{K},\\\ -\infty,&\text{otherwise}.\end{array}\right.$

Hence, the Lagrange dual problem of (P) is

(D) $\left\\{\begin{aligned} \sup_{c,h_{i}}&\ c\\\ \text{s.t.}&\
p_{1}(\mathbf{x})+\left(\sum_{i=2}^{N}h_{i}(\mathbf{x})-c\right)q_{1}(\mathbf{x})\geq
0,\quad\forall\mathbf{x}\in\mathbf{K},\\\ &\
p_{i}(\mathbf{x})-h_{i}(\mathbf{x})q_{i}(\mathbf{x})\geq
0,\quad\forall\mathbf{x}\in\mathbf{K},i\in[N]\setminus\\{1\\},\\\ &\
h_{i}\in{\mathbb{R}}[\mathbf{x}],\quad
i\in[N]\setminus\\{1\\}.\end{aligned}\right.$

For each $i\in[N]\setminus\\{1\\}$, define

$\mathcal{H}_{i}\coloneqq\left\\{h\in{\mathbb{R}}[\mathbf{x}]\,\middle|\,\frac{p_{i}(\mathbf{x})}{q_{i}(\mathbf{x})}\geq
h(\mathbf{x}),\ \ \forall\mathbf{x}\in\mathbf{K}\right\\}.$

Since each $q_{i}>0$ on $\mathbf{K}$, the Lagrange dual problem of (P) can be
also expressed as

$\sup_{h_{i}\in\mathcal{H}_{i}}\inf_{\mathbf{x}\in\mathbf{K}}\
\frac{p_{1}(\mathbf{x})}{q_{1}(\mathbf{x})}+\sum_{i=2}^{N}h_{i}(\mathbf{x}).$

Consequently, the underlying principle of the GMP reformulation (P) for
(SRFO), derived from the dual aspect, can be unfolded as follows: 1) replacing
the terms $\frac{p_{i}}{q_{i}}$, $i\in[N]\setminus\\{1\\}$ by polynomial
approximations $h_{i}\in{\mathbb{R}}[\mathbf{x}]$ from below on $\mathbf{K}$;
2) computing the infimum of the resulting function which contains only a
single denominator; 3) letting the approximations $h_{i}$’s vary and taking
the supremum.

######  Theorem 3.1.

Under Assumption 1, the optimum of (D) equals $\rho$.

######  Proof 3.2.

Denote the optimum of (D) by $\tau$. Clearly, we have $\tau\leq\rho$. Fix an
arbitrary $\varepsilon>0$. By the Stone-Weierstrass theorem, for each
$i\in[N]\setminus\\{1\\}$, there exists
$\hat{h}_{i}\in{\mathbb{R}}[\mathbf{x}]$ such that

$\sup_{\mathbf{x}\in\mathbf{K}}\left|\frac{p_{i}(\mathbf{x})}{q_{i}(\mathbf{x})}-\hat{h}_{i}(\mathbf{x})\right|\leq\frac{\varepsilon}{2(N-1)}.$

Letting $h_{i}\coloneqq\hat{h}_{i}-\varepsilon/2(N-1)$, we have

$\frac{p_{i}(\mathbf{x})}{q_{i}(\mathbf{x})}-\frac{\varepsilon}{N-1}\leq
h_{i}(\mathbf{x})\leq\frac{p_{i}(\mathbf{x})}{q_{i}(\mathbf{x})},\quad\forall\mathbf{x}\in\mathbf{K}.$

Hence, $h_{i}\in\mathcal{H}_{i}$ and

$\tau\geq\inf_{\mathbf{x}\in\mathbf{K}}\frac{p_{1}(\mathbf{x})}{q_{1}(\mathbf{x})}+\sum_{i=2}^{N}h_{i}(\mathbf{x})\geq\inf_{\mathbf{x}\in\mathbf{K}}\sum_{i=1}^{N}\frac{p_{i}(\mathbf{x})}{q_{i}(\mathbf{x})}-\varepsilon\geq\rho-\varepsilon.$

Thus, $(\rho-\varepsilon,h_{2},\ldots,h_{N})$ is feasible to (D). As
$\varepsilon$ is arbitrary, we obtain $\tau=\rho$.

######  Remark 3.3.

Theorem 3.1 can also be derived from strong duality between (P) and (D). In
fact, as $\mathbf{K}$ is compact, there exist constant polynomials
$\hat{h}_{i}$’s and $\hat{c}\in{\mathbb{R}}$ such that
$p_{i}/q_{i}>\hat{h}_{i}$, $i\in[N]\setminus\\{1\\}$, and
$p_{1}/q_{1}+\sum_{i=2}^{N}\hat{h}_{i}>\hat{c}$ on $\mathbf{K}$. That is,
$(\hat{c},\hat{h}_{2},\ldots,\hat{h}_{N})$ is a strictly feasible solution of
(D) and hence there is no dual gap between (P) and (D).

By truncating the polynomial degree, we obtain the following hierarchy of dual
SOS relaxations for (SRFO) ($k\geq d_{\min}$):

(D$k$) $\rho_{k}\coloneqq\left\\{\begin{aligned} \sup_{c,h_{i}}&\ c\\\
\text{s.t.}&\
p_{1}(\mathbf{x})+\left(\sum_{i=2}^{N}h_{i}(\mathbf{x})-c\right)q_{1}(\mathbf{x})\in
Q_{k}(\mathbf{g}),\\\ &\
p_{i}(\mathbf{x})-h_{i}(\mathbf{x})q_{i}(\mathbf{x})\in
Q_{k}(\mathbf{g}),\quad i\in[N]\setminus\\{1\\},\\\ &\
h_{i}\in{\mathbb{R}}[\mathbf{x}]_{2k-\max\\{\deg(q_{1}),\deg(q_{i})\\}},\quad
i\in[N]\setminus\\{1\\}.\end{aligned}\right.$

######  Theorem 3.4.

Under Assumption 1 and the Archimedean condition, it holds
$\rho_{k}\nearrow\rho$ as $k\to\infty$.

######  Proof 3.5.

It is obvious that $\rho_{k}\leq\rho_{k+1}\leq\rho$ for all $k\geq d_{\min}$.
Fix an arbitrary $\varepsilon>0$ and we will prove that there exists
$k_{\varepsilon}\in\mathbb{N}$ such that
$\rho_{k_{\bar{\varepsilon}}}\geq\rho-\varepsilon$. For
$\bar{\varepsilon}\coloneqq\varepsilon/3$, let
$(\rho-\bar{\varepsilon},\bar{h}_{2},\ldots,\bar{h}_{N})$ be the feasible
solution to (D) provided in the proof of Theorem 3.1. For each $i=2,\ldots,N$,
let

$h_{i}\coloneqq\bar{h}_{i}-\frac{\bar{\varepsilon}}{N-1}.$

Then, for $\mathbf{x}\in\mathbf{K}$, it holds that

(2)
$p_{i}(\mathbf{x})-h_{i}(\mathbf{x})q_{i}(\mathbf{x})=p_{i}(\mathbf{x})-\bar{h}_{i}(\mathbf{x})q_{i}(\mathbf{x})+\frac{\bar{\varepsilon}}{N-1}q_{i}(\mathbf{x})\geq\frac{\bar{\varepsilon}}{N-1}q_{i}(\mathbf{x})>0.$

By Theorem 2.2, there exists $k_{i}\in\mathbb{N}$ such that
$h_{i}\in{\mathbb{R}}[\mathbf{x}]_{2k_{i}-\deg(q_{i})}$ and
$p_{i}-h_{i}q_{i}\in Q_{k_{i}}(\mathbf{g})$. Moreover, for
$\mathbf{x}\in\mathbf{K}$, we have

$\displaystyle
p_{1}(\mathbf{x})+\left(\sum_{i=2}^{N}h_{i}(\mathbf{x})-(\rho-\varepsilon)\right)q_{1}(\mathbf{x})$
$\displaystyle=$ $\displaystyle
p_{1}(\mathbf{x})+q_{1}(\mathbf{x})\sum_{i=2}^{N}\bar{h}_{i}(\mathbf{x})-\bar{\varepsilon}q_{1}(\mathbf{x})-\rho
q_{1}(\mathbf{x})+3\bar{\varepsilon}q_{1}(\mathbf{x})$ $\displaystyle\geq$
$\displaystyle(\rho-\bar{\varepsilon})q_{1}(\mathbf{x})-\rho
q_{1}(\mathbf{x})+2\bar{\varepsilon}q_{1}(\mathbf{x})\geq\bar{\varepsilon}q_{1}(\mathbf{x})>0.$

By Theorem 2.2 again, there exists $k_{1}\in\mathbb{N}$ such that

$p_{1}(\mathbf{x})+\left(\sum_{i=2}^{N}h_{i}(\mathbf{x})-(\rho-\varepsilon)\right)q_{1}(\mathbf{x})\in
Q_{k_{1}}(\mathbf{g}).$

Let $k_{\varepsilon}\coloneqq\max_{1\leq i\leq N}k_{i}$. Then
$(\rho-\varepsilon,h_{2},\ldots,h_{N})$ is feasible to (D$k$) with
$k=k_{\varepsilon}$, which implies
$\rho_{k_{\varepsilon}}\geq\rho-\varepsilon$.

###  3.2 Convergence rate analysis

The exploration of the dual aspect of the GMP reformulation (P) allows us to
perform a convergence rate analysis for the hierarchy of SDP relaxations for
(SRFO) by utilizing some existing results from the literature.

######  Lemma 3.6.

For each $i\in[N]\setminus\\{1\\}$, there exists a constant $c_{i}$ depending
on $p_{i}$, $q_{i}$ and $\mathbf{K}$ such that for any $k\in\mathbb{N}$, there
exists $h\in{\mathbb{R}}[\mathbf{x}]_{k}$ satisfying

$\sup_{\mathbf{x}\in\mathbf{K}}\left|\frac{p_{i}(\mathbf{x})}{q_{i}(\mathbf{x})}-h(\mathbf{x})\right|\leq\frac{c_{i}}{k}.$

######  Proof 3.7.

Denote by

$\omega_{\mathbf{K}}\left(\frac{p_{i}}{q_{i}},t\right)\coloneqq\sup\left\\{\left|\frac{p_{i}(\mathbf{x})}{q_{i}(\mathbf{x})}-\frac{p_{i}(\mathbf{y})}{q_{i}(\mathbf{y})}\right|\colon\mathbf{x},\mathbf{y}\in\mathbf{K},\
\|\mathbf{x}-\mathbf{y}\|\leq t\right\\}$

the standard modulus of continuity of $p_{i}/q_{i}$ on $\mathbf{K}$. By the
multivariate version of Jackson’s theorem (see [27]), there exists a constant
$\hat{c}_{i}$ depending on $p_{i}$, $q_{i}$ and $\mathbf{K}$ such that for any
$k\in\mathbb{N}$, there exists $h\in{\mathbb{R}}[\mathbf{x}]_{k}$ satisfying

$\sup_{\mathbf{x}\in\mathbf{K}}\left|\frac{p_{i}(\mathbf{x})}{q_{i}(\mathbf{x})}-h(\mathbf{x})\right|\leq\hat{c}_{i}\omega_{\mathbf{K}}\left(\frac{p_{i}}{q_{i}},\frac{1}{k}\right).$

As $q_{i}(\mathbf{x})>0$ on $\mathbf{K}$, $p_{i}/q_{i}$ is Lipschitz on
$\mathbf{K}$. So there is a constant $L_{i}$ such that
$\omega_{\mathbf{K}}(p_{i}/q_{i},t)\leq L_{i}t$. Then, the conclusion follows
by letting $c_{i}\coloneqq\hat{c}_{i}L_{i}$.

The origin belongs to the interior of $\mathbf{K}$.

The following result is a consequence of the fundamental result [19, Theorem
6] and [11, Corollary 1].

######  Theorem 3.8.

[10, Theorem 3] Let the Archimedean condition and Assumption 3.2 hold. If
$\phi(\mathbf{x})\in{\mathbb{R}}[\mathbf{x}]$ is strictly positive on
$\mathbf{K}$, then $\phi\in Q_{k}(\mathbf{g})$ whenever

$k\geq
C_{\mathbf{K}}\exp{\left[\left(3^{\deg(\phi)+1}\kappa^{\deg(\phi)}(\deg(\phi))^{2}n^{\deg{\phi}}\frac{\max_{\mathbf{x}\in\mathbf{K}}\phi(\mathbf{x})}{\min_{\mathbf{x}\in\mathbf{K}}\phi(\mathbf{x})}\right)^{C_{\mathbf{K}}}\right]},$

for some constant $C_{\mathbf{K}}$ depending only on $g_{j}$’s and

(3) $\kappa\coloneqq\frac{1}{\sup\,\\{t>0\colon[-t,\
t]^{n}\subseteq\mathbf{K}\\}}.$

Let

$q^{\max}\coloneqq\max_{2\leq i\leq
N,\mathbf{x}\in\mathbf{K}}q_{i}(\mathbf{x}),\ \ q^{\min}\coloneqq\min_{2\leq
i\leq N,\mathbf{x}\in\mathbf{K}}q_{i}(\mathbf{x}),\ \
\rho^{\max}\coloneqq\max_{\mathbf{x}\in\mathbf{K}}\sum_{i=1}^{N}\frac{p_{i}(\mathbf{x})}{q_{i}(\mathbf{x})}.$

Using Theorem 3.8, we can establish the following convergence rate of the
hierarchy (D$k$).

######  Theorem 3.9.

Let the Archimedean condition and Assumptions 1, 3.2 hold. Then, there exist
constants $C_{1}$ and $C_{2}$ depending on $p_{i}$’s, $q_{i}$’s, $g_{j}$’s and
$\mathbf{K}$, such that for any $\varepsilon>0$, we have
$\rho_{k}\geq\rho-\varepsilon$ whenever

$\displaystyle k$ $\displaystyle\geq C_{2}\exp{\left[\left(3(3\omega
n)^{D(N,\varepsilon)}D(N,\varepsilon)^{2}\frac{(4(\rho^{\max}-\rho)+3\varepsilon)(N-1)}{\varepsilon}\frac{q^{\max}}{q^{\min}}\right)^{C_{2}}\right]}$
$\displaystyle=O\left(\exp\left[\frac{1}{\varepsilon^{3C_{2}}}(3\omega
n)^{\frac{4(N-1)C_{1}C_{2}}{\varepsilon}}\right]\right),$

where $\omega=\max\\{1,\kappa\\}$ and

$D(N,\varepsilon)\coloneqq\max\left\\{\deg(p_{i}),\
\left\lceil\frac{4C_{1}(N-1)}{\varepsilon}\right\rceil+\deg(q_{i}):i\in[N]\right\\}.$

######  Proof 3.10.

Fix an arbitrary $\varepsilon>0$. For each $i\in[N]\setminus\\{1\\}$, let
$c_{i}$ be the constant in Lemma 3.6 and $C_{1}\coloneqq\max_{2\leq i\leq
N}c_{i}$. Then, there exists $h_{i}\in{\mathbb{R}}[\mathbf{x}]$ of degree
$\lceil 4c_{i}(N-1)/\varepsilon\rceil$ satisfying

$\sup_{\mathbf{x}\in\mathbf{K}}\left|\frac{p_{i}(\mathbf{x})}{q_{i}(\mathbf{x})}-h_{i}(\mathbf{x})\right|\leq\frac{c_{i}}{\lceil
4c_{i}(N-1)/\varepsilon\rceil}\leq\frac{\varepsilon}{4(N-1)}.$

For $i\in[N]\setminus\\{1\\}$, let $\hat{h}_{i}\coloneqq
h_{i}-\varepsilon/2(N-1)$. Then, for any $\mathbf{x}\in\mathbf{K}$, it holds
that

$\displaystyle
p_{i}(\mathbf{x})-\hat{h}_{i}(\mathbf{x})q_{i}(\mathbf{x})=q_{i}(\mathbf{x})\left(\frac{p_{i}(\mathbf{x})}{q_{i}(\mathbf{x})}-\hat{h}_{i}(\mathbf{x})\right)=q_{i}(\mathbf{x})\left(\frac{p_{i}(\mathbf{x})}{q_{i}(\mathbf{x})}-h_{i}(\mathbf{x})+\frac{\varepsilon}{2(N-1)}\right),$

and

$p_{1}(\mathbf{x})+\left(\sum_{i=2}^{N}\hat{h}_{i}(\mathbf{x})-(\rho-\varepsilon)\right)q_{1}(\mathbf{x})=q_{1}(\mathbf{x})\left(\frac{p_{1}(\mathbf{x})}{q_{1}(\mathbf{x})}+\sum_{i=2}^{N}h_{i}(\mathbf{x})-\rho+\frac{\varepsilon}{2}\right).$

Therefore, for any $\mathbf{x}\in\mathbf{K}$,

$\displaystyle p_{i}(\mathbf{x})-\hat{h}_{i}(\mathbf{x})q_{i}(\mathbf{x})$
$\displaystyle\geq\frac{\varepsilon}{4(N-1)}q^{\min},$ $\displaystyle
p_{1}(\mathbf{x})+\left(\sum_{i=2}^{N}\hat{h}_{i}(\mathbf{x})-(\rho-\varepsilon)\right)q_{1}(\mathbf{x})$
$\displaystyle\geq
q_{1}(\mathbf{x})\left(\sum_{i=1}^{N}\frac{p_{i}(\mathbf{x})}{q_{i}(\mathbf{x})}-\frac{\varepsilon}{4}-\rho+\frac{\varepsilon}{2}\right)\geq\frac{\varepsilon}{4}q^{\min},$

and

$\displaystyle p_{i}(\mathbf{x})-\hat{h}_{i}(\mathbf{x})q_{i}(\mathbf{x})$
$\displaystyle\leq\frac{3\varepsilon}{4(N-1)}q^{\max},$ $\displaystyle
p_{1}(\mathbf{x})+\left(\sum_{i=2}^{N}\hat{h}_{i}(\mathbf{x})-(\rho-\varepsilon)\right)q_{1}(\mathbf{x})$
$\displaystyle\leq
q_{1}(\mathbf{x})\left(\sum_{i=1}^{N}\frac{p_{i}(\mathbf{x})}{q_{i}(\mathbf{x})}+\frac{\varepsilon}{4}-\rho+\frac{\varepsilon}{2}\right)$
$\displaystyle\leq\left(\rho^{\max}-\rho+\frac{3\varepsilon}{4}\right)q^{\max}.$

Note that

$\displaystyle\frac{\varepsilon}{4(N-1)}q^{\min}\leq\frac{\varepsilon}{4}q^{\min},\quad\frac{3\varepsilon}{4(N-1)}q^{\max}\leq\left(\rho^{\max}-\rho+\frac{3\varepsilon}{4}\right)q^{\max},$
$\displaystyle\deg(p_{i}-\hat{h}_{i}(\mathbf{x})q_{i}),\
\deg\left(p_{1}+\left(\sum_{i=2}^{N}\hat{h}_{i}-(\rho-\varepsilon)\right)q_{1}\right)\leq
D(N,\varepsilon).$

Hence, by Theorem 3.8, there exists a constant $C_{2}$ depending on $g_{j}$’s
such that whenever

$\displaystyle k$ $\displaystyle\geq
C_{2}\exp{\left[\left(3^{D(N,\varepsilon)+1}\omega^{D(N,\varepsilon)}D(N,\varepsilon)^{2}n^{D(N,\varepsilon)}\frac{\left(\rho^{\max}-\rho+\frac{3\varepsilon}{4}\right)q^{\max}}{\frac{\varepsilon}{4(N-1)}q^{\min}}\right)^{C_{2}}\right]}$
$\displaystyle=C_{2}\exp{\left[\left(3(3\omega
n)^{D(N,\varepsilon)}D(N,\varepsilon)^{2}\frac{(4(\rho^{\max}-\rho)+3\varepsilon)(N-1)}{\varepsilon}\frac{q^{\max}}{q^{\min}}\right)^{C_{2}}\right]}$
$\displaystyle=O\left(\exp\left[\frac{1}{\varepsilon^{3C_{2}}}(3\omega
n)^{\frac{4(N-1)C_{1}C_{2}}{\varepsilon}}\right]\right),$

$(\rho-\varepsilon,\hat{h}_{2},\ldots,\hat{h}_{N})$ is feasible to (D$k$) and
thus $\rho_{k}\geq\rho-\varepsilon$.

##  4 Sign symmetry adapted SDP relaxations

In this section, we propose block-diagonal SDP relaxations for (SRFO) by
exploiting sign symmetries as well as correlative sparsity, which would
significantly reduce the computational burden for structured problems.

###  4.1 Sparse SDP relaxations by exploiting sign symmetries

Let us first define the sign symmetries of a subset
$\mathcal{A}\subseteq\mathbb{N}^{n}$.

######  Definition 4.1.

Given a finite set $\mathcal{A}\subseteq\mathbb{N}^{n}$, the sign symmetries
$\mathcal{R}(\mathcal{A})$ of $\mathcal{A}$ consist of all vectors
$\mathbf{r}\in{\mathbb{Z}}^{n}_{2}\coloneqq\\{0,1\\}^{n}$ satisfying
$\mathbf{r}^{\intercal}{\boldsymbol{\alpha}}\equiv 0\,(\rm{mod}\,2)$ for all
${\boldsymbol{\alpha}}\in\mathcal{A}$. Moreover, we define the associated set
$\overline{\mathcal{A}}\coloneqq\\{{\boldsymbol{\alpha}}\in\mathbb{N}^{n}\mid\mathbf{r}^{\intercal}{\boldsymbol{\alpha}}\equiv
0\,(\rm{mod}\,2),\,\forall\mathbf{r}\in\mathcal{R}(\mathcal{A})\\}$.

Note that $\mathcal{R}(\mathcal{A})$ is a linear subspace of
${\mathbb{Z}}^{n}_{2}$ for any $\mathcal{A}\subseteq\mathbb{N}^{n}$. The
notion of sign symmetries stems from the invariance of polynomials under sign
flips on variables [13, 29]. For any $\mathbf{r}\in{\mathbb{Z}}^{n}_{2}$, we
define the map
$\theta_{\mathbf{r}}\colon{\mathbb{R}}[\mathbf{x}]\rightarrow{\mathbb{R}}[\mathbf{x}]$
by
$\theta_{\mathbf{r}}(f)(x_{1},\ldots,x_{n})=f((-1)^{r_{1}}x_{1},\ldots,(-1)^{r_{n}}x_{n})$.
A polynomial $f$ is said to have the sign symmetry $\mathbf{r}$ if
$\theta_{\mathbf{r}}(f)=f$. Note that a polynomial $f$ has the set of sign
symmetries $\mathcal{R}\subseteq{\mathbb{Z}}^{n}_{2}$ if and only if
$\mbox{supp}(f)\subseteq\\{{\boldsymbol{\alpha}}\in\mathbb{N}^{n}\mid\mathbf{r}^{\intercal}{\boldsymbol{\alpha}}\equiv
0\,(\rm{mod}\,2),\,\forall\mathbf{r}\in\mathcal{R}\\}$.

For $i\in[N]\setminus\\{1\\}$, let

(4)
$\mathcal{A}_{i}\coloneqq\mbox{supp}(p_{i})\cup\mbox{supp}(q_{i})\cup\bigcup_{j=1}^{m}\mbox{supp}(g_{j}),$

and let

(5)
$\mathcal{A}_{1}\coloneqq\mbox{supp}(p_{1})\cup\mbox{supp}(q_{1})\cup\bigcup_{i=2}^{N}\mathcal{A}_{i}.$

For the remainder of this section, we denote the set of sign symmetries of
$\mathcal{A}_{i}$ by $\mathcal{R}_{i}$.

Given $\mathbf{r}\in{\mathbb{Z}}_{2}^{n}$, let
$\mathbf{r}(\mathbf{a})\coloneqq((-1)^{r_{1}}a_{1},\ldots,(-1)^{r_{n}}a_{n})$
for $\mathbf{a}\in{\mathbb{R}}^{n}$ and for a set
$S\subseteq{\mathbb{R}}^{n}$, let
$\mathbf{r}(S)\coloneqq\\{\mathbf{r}(\mathbf{a})\in{\mathbb{R}}^{n}\mid\mathbf{a}\in
S\\}$.

######  Lemma 4.2.

One has $\mathbf{r}(\mathbf{K})=\mathbf{K}$,
$\theta_{\mathbf{r}}(p_{i})=p_{i}$, and $\theta_{\mathbf{r}}(q_{i})=q_{i}$ for
all $\mathbf{r}\in\mathcal{R}_{i}$, $i\in[N]$.

######  Proof 4.3.

It is straightforward to verify from the definitions.

In order to take the inherent sign symmetries of (SRFO) into account, let us
consider the following sign symmetry adapted version of (D):

(SD) $\rho^{\rm{s}}\coloneqq\left\\{\begin{aligned} \sup_{c,h_{i}}&\ c\\\
\text{s.t.}&\
\frac{p_{1}(\mathbf{x})}{q_{1}(\mathbf{x})}+\sum_{i=2}^{N}h_{i}(\mathbf{x})\geq
c,\quad\forall\mathbf{x}\in\mathbf{K},\\\ &\
\frac{p_{i}(\mathbf{x})}{q_{i}(\mathbf{x})}\geq
h_{i}(\mathbf{x}),\quad\forall\mathbf{x}\in\mathbf{K},\\\ &\
c\in{\mathbb{R}},\ h_{i}\in{\mathbb{R}}[\overline{\mathcal{A}_{i}}],\quad
i\in[N]\setminus\\{1\\}.\end{aligned}\right.$

######  Theorem 4.4.

Under Assumption 1, it holds $\rho^{\rm{s}}=\rho$.

######  Proof 4.5.

Clearly, we have $\rho^{\rm{s}}\leq\rho$ by Theorem 3.1. To show the converse,
fix an arbitrary $\varepsilon>0$ and let
$(\rho-\varepsilon,h_{2},\ldots,h_{N})$ be the feasible solution to (D)
provided in the proof of Theorem 3.1 so that

(6) $\frac{p_{i}(\mathbf{x})}{q_{i}(\mathbf{x})}-\frac{\varepsilon}{N-1}\leq
h_{i}(\mathbf{x})\leq\frac{p_{i}(\mathbf{x})}{q_{i}(\mathbf{x})},\quad\forall\mathbf{x}\in\mathbf{K}.$

For each $i\in[N]\setminus\\{1\\}$, let
$\tilde{h}_{i}\coloneqq\frac{1}{|\mathcal{R}_{i}|}\sum_{\mathbf{r}\in\mathcal{R}_{i}}\theta_{\mathbf{r}}(h_{i})$.
We have
$\sum_{\mathbf{r}\in\mathcal{R}_{i}}\theta_{\mathbf{r}}(\mathbf{x}^{{\boldsymbol{\alpha}}})=0$
for each
${\boldsymbol{\alpha}}\in\mathbb{N}^{n}\setminus\overline{\mathcal{A}_{i}}$.
In fact, as
${\boldsymbol{\alpha}}\in\mathbb{N}^{n}\setminus\overline{\mathcal{A}_{i}}$,
there exists $\tilde{\mathbf{r}}\in\mathcal{R}_{i}$ such that

$-\sum_{\mathbf{r}\in\mathcal{R}_{i}}\theta_{\mathbf{r}}(\mathbf{x}^{{\boldsymbol{\alpha}}})=\tilde{\mathbf{r}}\left(\sum_{\mathbf{r}\in\mathcal{R}_{i}}\theta_{\mathbf{r}}(\mathbf{x}^{{\boldsymbol{\alpha}}})\right)=\sum_{\mathbf{r}\in\mathcal{R}_{i}}\theta_{\tilde{\mathbf{r}}+\mathbf{r}}(\mathbf{x}^{{\boldsymbol{\alpha}}})=\sum_{\mathbf{r}\in\tilde{\mathbf{r}}+\mathcal{R}_{i}}\theta_{\mathbf{r}}(\mathbf{x}^{{\boldsymbol{\alpha}}})=\sum_{\mathbf{r}\in\mathcal{R}_{i}}\theta_{\mathbf{r}}(\mathbf{x}^{{\boldsymbol{\alpha}}}).$

Therefore, we have $\tilde{h}_{i}\in{\mathbb{R}}[\overline{\mathcal{A}_{i}}]$.
Moreover, it follows from Lemma 4.2 and (6) that

(7)
$\frac{p_{i}(\mathbf{x})}{q_{i}(\mathbf{x})}-\frac{\varepsilon}{N-1}\leq\tilde{h}_{i}(\mathbf{x})\leq\frac{p_{i}(\mathbf{x})}{q_{i}(\mathbf{x})},\quad\forall\mathbf{x}\in\mathbf{K}.$

Thus we have

$\inf_{\mathbf{x}\in\mathbf{K}}\frac{p_{1}(\mathbf{x})}{q_{1}(\mathbf{x})}+\sum_{i=2}^{N}\tilde{h}_{i}(\mathbf{x})\geq\inf_{\mathbf{x}\in\mathbf{K}}\sum_{i=1}^{N}\frac{p_{i}(\mathbf{x})}{q_{i}(\mathbf{x})}-\varepsilon=\rho-\varepsilon.$

Therefore, $(\rho-\varepsilon,\tilde{h}_{2},\ldots,\tilde{h}_{N})$ is feasible
to (SD). As $\varepsilon>0$ is arbitrary, we obtain $\rho^{\rm{s}}\geq\rho$.

Given $\mathbf{r}\in{\mathbb{Z}}_{2}^{n}$ with
$\mathbf{r}(\mathbf{K})=\mathbf{K}$, for a measure
$\mu\in\mathcal{M}(\mathbf{K})_{+}$, we define a new measure
$\mu^{\mathbf{r}}$ by $\mu^{\mathbf{r}}(S)=\mu(\mathbf{r}(S))$ for any Borel
set $S\subseteq\mathbf{K}$. A measure is said to be _invariant_ with respect
to the sign symmetries $\mathcal{R}$ if $\mu^{\mathbf{r}}=\mu$ for all
$\mathbf{r}\in\mathcal{R}$.

######  Lemma 4.6.

Let $\mathbf{r}\in{\mathbb{Z}}_{2}^{n}$, $\mu\in\mathcal{M}(\mathbf{K})_{+}$,
and $f\in{\mathbb{R}}[\mathbf{x}]$.

  1. 1.

For ${\boldsymbol{\alpha}}\in\mathbb{N}^{n}$,
$\int_{\mathbf{K}}\mathbf{x}^{{\boldsymbol{\alpha}}}\mathrm{d}\mu^{\mathbf{r}}=(-1)^{\mathbf{r}^{\intercal}{\boldsymbol{\alpha}}}\int_{\mathbf{K}}\mathbf{x}^{{\boldsymbol{\alpha}}}\mathrm{d}\mu$.

  2. 2.

If $\mathbf{r}\in\mathcal{R}(\mbox{supp}(f))$, then
$\int_{\mathbf{K}}f\mathrm{d}\mu^{\mathbf{r}}=\int_{\mathbf{K}}f\mathrm{d}\mu$.

  3. 3.

If $\mathbf{r}\in\mathcal{R}(\mbox{supp}(f))$, then for
${\boldsymbol{\alpha}}\in\mathbb{N}^{n}$,
$\int_{\mathbf{K}}\mathbf{x}^{{\boldsymbol{\alpha}}}f\mathrm{d}\mu^{\mathbf{r}}=(-1)^{\mathbf{r}^{\intercal}{\boldsymbol{\alpha}}}\int_{\mathbf{K}}\mathbf{x}^{{\boldsymbol{\alpha}}}f\mathrm{d}\mu$.

######  Proof 4.7.

It is straightforward to verify from the definitions.

Let $\mathcal{M}(\mathbf{K})^{\mathcal{R}_{i}}_{+}$ denote the set of finite
positive Borel measures that are invariant with respect to the sign symmetries
$\mathcal{R}_{i}$. Then the dual of (SD) reads as

(SP) $\left\\{\begin{aligned}
\inf_{\mu_{i}\in\mathcal{M}(\mathbf{K})^{\mathcal{R}_{i}}_{+}}&\
\sum_{i=1}^{N}\int_{\mathbf{K}}p_{i}\mathrm{d}\mu_{i}\\\
\text{s.t.}\quad\,\,&\ \int_{\mathbf{K}}q_{1}\mathrm{d}\mu_{1}=1,\\\ &\
\int_{\mathbf{K}}\mathbf{x}^{{\boldsymbol{\alpha}}}q_{i}\mathrm{d}\mu_{i}=\int_{\mathbf{K}}\mathbf{x}^{{\boldsymbol{\alpha}}}q_{1}\mathrm{d}\mu_{1},\quad\forall{\boldsymbol{\alpha}}\in\overline{\mathcal{A}_{i}},i\in[N]\setminus\\{1\\}.\\\
\end{aligned}\right.$

We now point out that (SP) cannot be viewed as a consequence of (P) equipped
with invariant measures. Indeed, the latter would involve additional
constraints

$\int_{\mathbf{K}}\mathbf{x}^{{\boldsymbol{\alpha}}}q_{1}\mathrm{d}\mu_{1}=0,\quad\forall{\boldsymbol{\alpha}}\in\overline{\mathcal{A}_{1}}\setminus\bigcap_{i=2}^{N}\overline{\mathcal{A}_{i}},$

since for any
${\boldsymbol{\alpha}}\in\overline{\mathcal{A}_{1}}\setminus\bigcap_{i=2}^{N}\overline{\mathcal{A}_{i}}$,
there exists $j\in[N]\setminus\\{1\\}$ such that
${\boldsymbol{\alpha}}\notin\overline{\mathcal{A}_{j}}$ which implies
$\int_{\mathbf{K}}\mathbf{x}^{{\boldsymbol{\alpha}}}q_{1}\mathrm{d}\mu_{1}=\int_{\mathbf{K}}\mathbf{x}^{{\boldsymbol{\alpha}}}q_{j}\mathrm{d}\mu_{j}=0$
by Lemma 4.6. This (somewhat surprising) fact particularly highlights the
significance of considering the SOS problem (D) when one exploits sign
symmetries for (SRFO).

The sign symmetry adapted reformulation (SD) allows us to consider block-
diagonal SDP relaxations for (SRFO). For $\mathcal{A}\subseteq\mathbb{N}^{n}$
and $k\in\mathbb{N}$, let us define a binary matrix $B^{\mathcal{A}}_{k}$
indexed by $\mathbb{N}^{n}_{k}$ through

$[B_{k}^{\mathcal{A}}]_{{\boldsymbol{\alpha}},{\boldsymbol{\beta}}}=\left\\{\begin{array}[]{ll}1,&\text{if}\
{\boldsymbol{\alpha}}+{\boldsymbol{\beta}}\in\overline{\mathcal{A}},\\\
0,&\text{otherwise}.\end{array}\right.$

It could be easily seen that $B^{\mathcal{A}}_{k}$ is block-diagonal up to
appropriate row/column permutations [29]. We define the sparse quadratic
module $Q_{k}(\mathbf{g},\mathcal{A})$ associated with $\mathcal{A}$ by

$Q_{k}(\mathbf{g},\mathcal{A})\coloneqq\left\\{\sigma_{0}+\sum_{j=1}^{m}\sigma_{j}g_{j}\middle|\sigma_{j}=[\mathbf{x}]_{k-d_{j}}^{\intercal}G_{j}[\mathbf{x}]_{k-d_{j}},G_{j}\in\mathbb{S}^{+}(B^{\mathcal{A}}_{k-d_{j}}),j\in\\{0\\}\cup[m]\right\\},$

where $d_{0}:=0$, for $s\in\mathbb{N}$,
$[\mathbf{x}]_{s}\coloneqq[1,x_{1},x_{2},\ldots,x_{n}^{s}]$ denotes the
canonical vector of monomials up to degree $s$, and
$\mathbb{S}^{+}(B^{\mathcal{A}}_{s})$ denotes the set of positive semidefinite
matrices with sparsity pattern being specified by $B^{\mathcal{A}}_{s}$. The
sign symmetry adapted version of (D$k$) is given by

(SD$k$) $\rho^{\rm{s}}_{k}\coloneqq\left\\{\begin{aligned} \sup_{c,h_{i}}&\
c\\\ \text{s.t.}&\
p_{1}(\mathbf{x})+\left(\sum_{i=2}^{N}h_{i}(\mathbf{x})-c\right)q_{1}(\mathbf{x})\in
Q_{k}(\mathbf{g},\mathcal{A}_{1}),\\\ &\
p_{i}(\mathbf{x})-h_{i}(\mathbf{x})q_{i}(\mathbf{x})\in
Q_{k}(\mathbf{g},\mathcal{A}_{i}),\quad i\in[N]\setminus\\{1\\},\\\ &\
c\in{\mathbb{R}},\
h_{i}(\mathbf{x})\in{\mathbb{R}}[\overline{\mathcal{A}_{i}}]\cap{\mathbb{R}}[\mathbf{x}]_{2k-\max\\{\deg(q_{1}),\deg(q_{i})\\}},\quad
i\in[N]\setminus\\{1\\}.\end{aligned}\right.$

The following theorem is a sign symmetry adapted version of Theorem 2.2.

######  Theorem 4.8.

[29, Theorem 6.11] Let $f\in{\mathbb{R}}[\mathbf{x}]$ and
$\mathcal{A}=\mbox{supp}(f)\cup\bigcup_{j=1}^{m}\mbox{supp}(g_{j})$. Assume
that the quadratic module $Q(\mathbf{g})$ is Archimedean and $f$ is positive
on $\mathbf{K}$. Then $f\in Q_{k}(\mathbf{g},\mathcal{A})$ for some
$k\in\mathbb{N}$.

######  Remark 4.9.

By a similar argument as for Theorem 4.8 (see [29]), one can actually show
that if $f\in Q_{k}(\mathbf{g})$, then $f\in Q_{k}(\mathbf{g},\mathcal{A})$
with $\mathcal{A}=\mbox{supp}(f)\cup\bigcup_{j=1}^{m}\mbox{supp}(g_{j})$.

######  Theorem 4.10.

The following statements hold true:

  1. (i)

For $k\geq d_{\min}$, $\rho^{\rm{s}}_{k}\leq\rho_{k}$. Moreover, if
$\mathcal{R}_{1}=\mathcal{R}_{2}=\cdots=\mathcal{R}_{N}$, then
$\rho^{\rm{s}}_{k}=\rho_{k}$.

  2. (ii)

Under Assumption 1 and the Archimedean condition,
$\rho^{\rm{s}}_{k}\nearrow\rho$ as $k\to\infty$.

######  Proof 4.11.

(i). It follows from the fact that any feasible solution
$(c,h_{2},\ldots,h_{N})$ to (SD$k$) is also feasible to (D$k$). Now assume
$\mathcal{R}_{1}=\mathcal{R}_{2}=\cdots=\mathcal{R}_{N}$. To show
$\rho^{\rm{s}}_{k}\geq\rho_{k}$, let $(c,h_{2},\ldots,h_{N})$ be any feasible
solution to (D$k$). For each $i\in[N]\setminus\\{1\\}$, let
$\tilde{h}_{i}\coloneqq\frac{1}{|\mathcal{R}_{1}|}\sum_{\mathbf{r}\in\mathcal{R}_{1}}\theta_{\mathbf{r}}(h_{i})\in{\mathbb{R}}[\overline{\mathcal{A}_{1}}]\cap{\mathbb{R}}[\mathbf{x}]_{2k-\max\\{\deg(q_{1}),\deg(q_{i})\\}}$.
From $p_{i}(\mathbf{x})-h_{i}(\mathbf{x})q_{i}(\mathbf{x})\in
Q_{k}(\mathbf{g})$ and Remark 4.9, we deduce that

(8) $p_{i}(\mathbf{x})-\tilde{h}_{i}(\mathbf{x})q_{i}(\mathbf{x})\in
Q_{k}(\mathbf{g},\mathcal{A}_{1}).$

Moreover, from
$p_{1}(\mathbf{x})+\left(\sum_{i=2}^{N}h_{i}(\mathbf{x})-c\right)q_{1}(\mathbf{x})\in
Q_{k}(\mathbf{g})$ and Remark 4.9 it follows that

$p_{1}(\mathbf{x})+\left(\sum_{i=2}^{N}\tilde{h}_{i}(\mathbf{x})-c\right)q_{1}(\mathbf{x})\in
Q_{k}(\mathbf{g},\mathcal{A}_{1}).$

Therefore, $(c,\tilde{h}_{2},\ldots,\tilde{h}_{N})$ is feasible to (SD$k$),
which implies $\rho^{\rm{s}}_{k}\geq\rho_{k}$.

(ii). It is clear that $\rho^{\rm{s}}_{k}\leq\rho^{\rm{s}}_{k+1}$ for any
$k\geq d_{\min}$. To show the convergence, fix an arbitrary $\varepsilon>0$.
For $\bar{\varepsilon}\coloneqq\varepsilon/3$, let
$(\rho-\bar{\varepsilon},\bar{h}_{2},\ldots,\bar{h}_{N})$ be the feasible
solution to (SD) provided in the proof of Theorem 4.4. For each
$i\in[N]\setminus\\{1\\}$, let

$h_{i}\coloneqq\bar{h}_{i}-\frac{\bar{\varepsilon}}{N-1}\in{\mathbb{R}}[\overline{\mathcal{A}_{i}}].$

Then, for $\mathbf{x}\in\mathbf{K}$, it holds that

(9)
$p_{i}(\mathbf{x})-h_{i}(\mathbf{x})q_{i}(\mathbf{x})=p_{i}(\mathbf{x})-\bar{h}_{i}(\mathbf{x})q_{i}(\mathbf{x})+\frac{\bar{\varepsilon}}{N-1}q_{i}(\mathbf{x})\geq\frac{\bar{\varepsilon}}{N-1}q_{i}(\mathbf{x})>0.$

By Theorem 4.8, there exists $k_{i}\in\mathbb{N}$ such that
$h_{i}\in{\mathbb{R}}[\overline{\mathcal{A}_{i}}]\cap{\mathbb{R}}[\mathbf{x}]_{2k_{i}-\deg(q_{i})}$
and $p_{i}-h_{i}q_{i}\in Q_{k_{i}}(\mathbf{g},\mathcal{A}_{i})$. Moreover, for
$\mathbf{x}\in\mathbf{K}$, we have

$\displaystyle
p_{1}(\mathbf{x})+\left(\sum_{i=2}^{N}h_{i}(\mathbf{x})-(\rho-\varepsilon)\right)q_{1}(\mathbf{x})$
$\displaystyle=$ $\displaystyle
p_{1}(\mathbf{x})+q_{1}(\mathbf{x})\sum_{i=2}^{N}\bar{h}_{i}(\mathbf{x})-\bar{\varepsilon}q_{1}(\mathbf{x})-\rho
q_{1}(\mathbf{x})+3\bar{\varepsilon}q_{1}(\mathbf{x})$ $\displaystyle\geq$
$\displaystyle(\rho-\bar{\varepsilon})q_{1}(\mathbf{x})-\rho
q_{1}(\mathbf{x})+2\bar{\varepsilon}q_{1}(\mathbf{x})\geq\bar{\varepsilon}q_{1}(\mathbf{x})>0.$

By Theorem 4.8 again, there exists $k_{1}\in\mathbb{N}$ such that

$p_{1}(\mathbf{x})+\left(\sum_{i=2}^{N}h_{i}(\mathbf{x})-(\rho-\varepsilon)\right)q_{1}(\mathbf{x})\in
Q_{k_{1}}(\mathbf{g},\mathcal{A}_{1}).$

Let $k_{\varepsilon}\coloneqq\max_{1\leq i\leq N}k_{i}$. Then
$(\rho-\varepsilon,h_{2},\ldots,h_{N})$ is feasible to (SD$k$) with
$k=k_{\varepsilon}$, which implies
$\rho^{\rm{s}}_{k_{\varepsilon}}\geq\rho-\varepsilon$. As $\varepsilon$ is
arbitrary, we prove the convergence of $\\{\rho^{\rm{s}}_{k}\\}$ to $\rho$.

Note that the optimum $\rho^{\rm{s}}_{k}$ of (SD$k$) may depend on which ratio
being chosen as $p_{1}/q_{1}$. We give an example to illustrate this
phenomenon.

######  Example 4.12.

Let

$f\coloneqq\frac{x^{2}+y^{2}-yz}{1+2x^{2}+y^{2}+z^{2}}+\frac{y^{2}+x^{2}z}{1+x^{2}+2y^{2}+z^{2}}+\frac{z^{2}-x+y}{1+x^{2}+y^{2}+2z^{2}}.$

Consider the minimization of $f$ over the unit ball
$\\{(x,y,z)\in{\mathbb{R}}^{3}\mid 1-x^{2}-y^{2}-z^{2}\geq 0\\}$. We consider
three cases: (1) $p_{1}=x^{2}+y^{2}-yz,q_{1}=1+2x^{2}+y^{2}+z^{2}$; (2)
$p_{1}=y^{2}+x^{2}z,q_{1}=1+x^{2}+2y^{2}+z^{2}$; (3)
$p_{1}=z^{2}-x+y,q_{1}=1+x^{2}+y^{2}+2z^{2}$. We present the computational
results in Table 1. For this problem, $-0.3465$ can be certified to be
globally optimal.

Table 1: Computational results for Example 4.12. $k$ |  | $\sup$(D$k$) |  |  $\sup$(SD$k$)
---|---|---|---|---
|  | case (1) | case (2) | case (3)
$2$ |  | -0.3563 |  | -0.4275 | -0.4513 | -0.4738
$3$ |  | -0.3465 |  | -0.3469 | -0.3546 | -0.3550
$4$ |  |  |  | -0.3465 | -0.3465 | -0.3465

######  Remark 4.13.

To guarantee $\rho^{\rm{s}}_{k}=\rho_{k}$, one may simply letting
$\mathcal{A}_{1}=\cdots=\mathcal{A}_{N}$ by Theorem 4.10.

Finally, the dual of (SD$k$) reads as

(SP$k$) $\left\\{\begin{aligned} \inf_{\mathbf{y}_{i}}&\
\sum_{i=1}^{N}L_{\mathbf{y}_{i}}(p_{i})\\\ \text{s.t.}&\
B^{\mathcal{A}_{i}}_{k}\circ\mathbf{M}_{k}(\mathbf{y}_{i})\succeq 0,\quad
i\in[N],\\\ &\
B^{\mathcal{A}_{i}}_{k-d_{j}}\circ\mathbf{M}_{k-d_{j}}(g_{j}\mathbf{y}_{i})\succeq
0,\quad i\in[N],j\in[m],\\\ &\ L_{\mathbf{y}_{1}}(q_{1})=1,\\\ &\
L_{\mathbf{y}_{i}}(\mathbf{x}^{{\boldsymbol{\alpha}}}q_{i})=L_{\mathbf{y}_{1}}(\mathbf{x}^{{\boldsymbol{\alpha}}}q_{1}),\quad\forall{\boldsymbol{\alpha}}\in\mathbb{N}^{n}_{2k-\max\\{\deg(q_{1}),\deg(q_{i})\\}}\cap\overline{\mathcal{A}_{i}},i\in[N]\setminus\\{1\\}.\\\
\end{aligned}\right.$

###  4.2 Sparse SDP relaxations by exploiting both correlative sparsity and
sign symmetries

In this subsection, we present sparse SDP relaxations for (SRFO) by exploiting
both correlative sparsity and sign symmetries. Let us begin by recalling a
correlative sparsity adapted GMP reformulation and a corresponding hierarchy
of sparse SDP relaxations for (SRFO) proposed in [3]. We first describe the
correlative sparsity pattern in (SRFO). For $I\subseteq[n]$, $\mathbf{x}(I)$
denotes the set of variables $x_{i}$ with $i\in I$. The index sets $[n]$ and
$[m]$ can be decomposed as $[n]=\cup_{i=1}^{N}I_{i}$ and
$[m]=\cup_{i=1}^{N}J_{i}$ such that

  1. (i)

For every $i\in[N]$, $p_{i},q_{i}\in{\mathbb{R}}[\mathbf{x}(I_{i})]$;

  2. (ii)

For every $j\in J_{i}$, $g_{j}\in{\mathbb{R}}[\mathbf{x}(I_{i})]$;

  3. (iii)

For every $i\in[N]$, there exists $k\in J_{i}$ such that
$g_{k}=M_{i}-\sum_{\ell\in I_{i}}x_{\ell}^{2}$ for some $M_{i}>0$;

  4. (iv)

The subsets $\\{I_{i}\\}_{i=1}^{N}$ satisfy the running intersection property
(RIP), that is, for every $i\in[N]\setminus\\{1\\}$,
$I_{i}\cap(\cup_{j=1}^{i-1}I_{j})\subseteq I_{k}$ for some $k\in[i-1]$.

######  Remark 4.14.

If $\mathbf{K}$ is compact and one knows some $M>0$ such that
$M-x_{1}^{2}-\cdots-x_{n}^{2}\geq 0$ for all $\mathbf{x}\in\mathbf{K}$, then
we can always add redundant constraints $M-\sum_{j\in I_{i}}x_{j}^{2}\geq
0,i\in[N]$ to the description of $\mathbf{K}$ so that Assumption 4.2 (iii) is
satisfied.

For every $i\in[N]$, let

$\mathbf{K}_{i}\coloneqq\left\\{\mathbf{x}(I_{i})\in{\mathbb{R}}^{|I_{i}|}\mid
g_{j}(\mathbf{x}(I_{i}))\geq 0,\ j\in J_{i}\right\\},$

and
$\pi_{i}\colon\mathcal{M}(\mathbf{K})_{+}\rightarrow\mathcal{M}(\mathbf{K}_{i})_{+}$
be the projection on $\mathbf{K}_{i}$, that is, for any
$\mu\in\mathcal{M}(\mathbf{K})_{+}$,

$\pi_{i}(\mu(B))\coloneqq\mu(\\{\mathbf{x}:\mathbf{x}\in\mathbf{K},\mathbf{x}(I_{i})\in
B\\}),\quad\forall B\in\mathcal{B}(\mathbf{K}_{i}),$

where $\mathcal{B}(\mathbf{K}_{i})$ is the usual Borel $\sigma$-algebra
associated with $\mathbf{K}_{i}$. For every pair $(i,j)\in[N]\times[N]$ with
$i\neq j$ and $I_{i}\cap I_{j}\neq\emptyset$, let

$\mathbf{K}_{ij}=\mathbf{K}_{ji}\coloneqq\left\\{\mathbf{x}(I_{i}\cap
I_{j}):\mathbf{x}(I_{i})\in\mathbf{K}_{i},\
\mathbf{x}(I_{j})\in\mathbf{K}_{j}\right\\},$

and the projection
$\pi_{ij}\colon\mathcal{M}(\mathbf{K}_{i})_{+}\rightarrow\mathcal{M}(\mathbf{K}_{ij})_{+}$
is defined in an obvious similar manner. Moreover, let us define the sets

$U_{i}\coloneqq\\{j\in\\{i+1,\ldots,N\\}\mid I_{i}\cap I_{j}\neq\emptyset\\},\
i\in[N-1],\quad U_{N}\coloneqq\emptyset,$

and

$V_{1}\coloneqq\emptyset,\quad V_{i}\coloneqq\\{j\in\\{1,\ldots,i-1\\}\mid
I_{i}\cap I_{j}\neq\emptyset\\},\ i\in[N]\setminus\\{1\\}.$

Then the correlative sparsity adapted GMP reformulation for (SRFO) is given by

(CP) $\rho^{\rm{c}}\coloneqq\left\\{\begin{aligned}
\inf_{\mu_{i}\in\mathcal{M}(\mathbf{K}_{i})_{+}}&\
\sum_{i=1}^{N}\int_{\mathbf{K}_{i}}p_{i}\mathrm{d}\mu_{i}\\\
\text{s.t.}\quad\,\,&\ \int_{\mathbf{K}_{i}}q_{i}\mathrm{d}\mu_{i}=1,\quad
i\in[N],\\\ &\
\pi_{ij}(q_{i}\mathrm{d}\mu_{i})=\pi_{ji}(q_{j}\mathrm{d}\mu_{j}),\quad j\in
U_{i},\ i\in[N-1].\end{aligned}\right.$

For $I\subseteq[n]$ and $f\in\mathbb{R}[\mathbf{x}(I)]$, let
$\mathbf{M}_{k}(\mathbf{y},I)$ (resp. $\mathbf{M}_{k}(f\mathbf{y},I)$) be the
moment (resp. localizing) submatrix obtained by retaining only those rows and
columns of $\mathbf{M}_{k}(\mathbf{y})$ (resp. $\mathbf{M}_{k}(f\mathbf{y})$)
indexed by ${\boldsymbol{\alpha}}\in\mathbb{N}^{n}$ with $\alpha_{i}=0$
whenever $i\notin I$. For $1\leq i<j\leq N$ with $I_{i}\cap
I_{j}\neq\emptyset$, let
$\mathbb{N}^{(ij)}\coloneqq\\{{\boldsymbol{\alpha}}\in\mathbb{N}^{n}\mid\alpha_{k}=0,\,\forall
k\not\in I_{i}\cap I_{j}\\}$. Then, the hierarchy of correlative sparsity
adapted SDP relaxations for (SRFO) is given by

(CP$k$) $\rho_{k}^{\rm{c}}\coloneqq\left\\{\begin{aligned}
\inf_{\mathbf{y}_{i}}&\ \sum_{i=1}^{N}L_{\mathbf{y}_{i}}(p_{i})\\\
\text{s.t.}&\ \mathbf{M}_{k}(\mathbf{y}_{i},I_{i})\succeq 0,\quad i\in[N],\\\
&\ \mathbf{M}_{k-d_{j}}(g_{j}\mathbf{y}_{i},I_{i})\succeq 0,\quad j\in
J_{i},i\in[N],\\\ &\ L_{\mathbf{y}_{i}}(q_{i})=1,\quad i\in[N],\\\ &\
L_{\mathbf{y}_{i}}(\mathbf{x}^{{\boldsymbol{\alpha}}}q_{i})=L_{\mathbf{y}_{j}}(\mathbf{x}^{{\boldsymbol{\alpha}}}q_{j}),\\\
&\
\forall{\boldsymbol{\alpha}}\in\mathbb{N}_{2k-\max\\{\deg(q_{i}),\deg(q_{j})\\}}^{(ij)},j\in
U_{i},i\in[N-1].\\\ \end{aligned}\right.$

######  Theorem 4.15.

[3, Theorems 3.1 and 3.2] Let Assumption 4.2 hold and assume that $q_{i}>0$ on
$\mathbf{K}_{i}$ for $i\in[N]$. It hold $\rho^{\rm{c}}=\rho$ and
$\rho^{\rm{c}}_{k}\nearrow\rho$ as $k\to\infty$.

We can derive the Lagrange dual of (CP$k$) which reads as

(CD$k$) $\left\\{\begin{aligned} \sup_{c_{i},h_{i,j}}&\ \sum_{i=1}^{N}c_{i}\\\
\text{s.t.}\,\,&\ p_{i}-\left(c_{i}+\sum_{j\in U_{i}}h_{i,j}-\sum_{j\in
V_{i}}h_{j,i}\right)q_{i}\in Q_{k}(\\{g_{j}\\}_{j\in J_{i}}),\
c_{i}\in{\mathbb{R}},\ i\in[N],\\\ &\
h_{i,j}\in{\mathbb{R}}[\mathbf{x}(I_{i}\cap
I_{j})]_{2k-\max\\{\deg(q_{i}),\deg(q_{j})\\}},\quad j\in U_{i},\
i\in[N-1].\end{aligned}\right.$

######  Proposition 4.16.

Under Assumption 4.2 (iii), the strong duality holds between (CP$k$) and
(CD$k$) for all $k\geq d_{\min}$.

######  Proof 4.17.

Let $\\{\mu_{i}\\}$ be a feasible solution of (CP) (see the proof of [3,
Theorem 3.1] for the existence). For each $i\in[N]$, let
$\mathbf{y}_{i}=(y_{i{\boldsymbol{\alpha}}})_{{\boldsymbol{\alpha}}\in\mathbb{N}^{|I_{i}|}_{2k}}$
be such that
$y_{i{\boldsymbol{\alpha}}}=\int_{\mathbf{K}_{i}}\mathbf{x}^{{\boldsymbol{\alpha}}}\mathrm{d}\mu_{i}$
for ${\boldsymbol{\alpha}}\in\mathbb{N}^{|I_{i}|}_{2k}$. Then,
$\\{\mathbf{y}_{i}\\}$ is a feasible solution of (CP$k$). As Assumption 4.2
(iii) holds, according to the proof of [3, Theorem 2.2], the feasible set of
(CP$k$) is compact, which implies that the optimal solution set of (CP$k$) is
nonempty and bounded. Therefore, (CD$k$) is strictly feasible [28] and the
strong duality holds [26, Theorem 4.1.3].

Let

(10)
$\mathcal{A}\coloneqq\bigcup_{i=1}^{N}\left(\mbox{supp}(p_{i})\cup\mbox{supp}(q_{i})\right)\cup\bigcup_{j=1}^{m}\mbox{supp}(g_{j}),$

and $\mathcal{R}$ be the set of sign symmetries of $\mathcal{A}$. Now we
consider the following sign symmetry adapted version of (CP):

(CSP) $\rho^{\rm{cs}}\coloneqq\left\\{\begin{aligned}
\inf_{\mu_{i}\in\mathcal{M}(\mathbf{K}_{i})_{+}^{\mathcal{R}}}&\
\sum_{i=1}^{N}\int_{\mathbf{K}_{i}}p_{i}\mathrm{d}\mu_{i}\\\
\text{s.t.}\quad\,\,&\ \int_{\mathbf{K}_{i}}q_{i}\mathrm{d}\mu_{i}=1,\quad
i\in[N],\\\ &\
\pi_{ij}(q_{i}\mathrm{d}\mu_{i})=\pi_{ji}(q_{j}\mathrm{d}\mu_{j}),\quad j\in
U_{i},i\in[N-1].\end{aligned}\right.$

######  Theorem 4.18.

Let Assumption 4.2 hold and assume that $q_{i}>0$ on $\mathbf{K}_{i}$ for
$i\in[N]$. It holds $\rho^{\rm{cs}}=\rho$.

######  Proof 4.19.

Since $\mathcal{M}(\mathbf{K}_{i})^{\mathcal{R}}_{+}$ is a subset of
$\mathcal{M}(\mathbf{K}_{i})_{+}$ for each $i\in[N]$, we immediately have
$\rho^{\rm{cs}}\geq\rho$. For the converse, fix an arbitrary $\varepsilon>0$
and suppose that $\\{\mu_{i}\\}$ is any feasible solution of (CP) with
$\sum_{i=1}^{N}\int_{\mathbf{K}}p_{i}\mathrm{d}\mu_{i}<\rho+\varepsilon$. For
each $i\in[N]$, let us define a new measure
$\tilde{\mu}_{i}\in\mathcal{M}(\mathbf{K}_{i})^{\mathcal{R}}_{+}$ by
$\tilde{\mu}_{i}\coloneqq\frac{1}{|\mathcal{R}|}\sum_{\mathbf{r}\in\mathcal{R}}\mu_{i}^{\mathbf{r}}$.
For any $j\in U_{i},i\in[N-1]$, by Lemma 4.6, one can check that
$\pi_{ij}(q_{i}\mathrm{d}\tilde{\mu_{i}})=\pi_{ji}(q_{j}\mathrm{d}\tilde{\mu}_{j}).$
Moreover, by Lemma 4.6 again,
$\sum_{i=1}^{N}\int_{\mathbf{K}}p_{i}\mathrm{d}\tilde{\mu}_{i}=\sum_{i=1}^{N}\int_{\mathbf{K}}p_{i}\mathrm{d}\mu_{i}<\rho+\varepsilon$.
As $\varepsilon>0$ is arbitrary, $\rho^{\rm{cs}}\leq\rho$.

For each $i\in[N]$ and each $k\in\mathbb{N}$, define a binary matrix
$B^{\mathcal{A}}_{i,k}$ indexed by $\mathbb{N}^{|I_{i}|}_{k}$ (we embed
$\mathbb{N}^{|I_{i}|}_{k}$ into $\mathbb{N}^{n}_{k}$ in the natural way) such
that

$[B^{\mathcal{A}}_{i,k}]_{{\boldsymbol{\alpha}},{\boldsymbol{\beta}}}\coloneqq\left\\{\begin{array}[]{ll}1,&\text{if}\
{\boldsymbol{\alpha}}+{\boldsymbol{\beta}}\in\overline{\mathcal{A}},\\\
0,&\text{otherwise}.\end{array}\right.$

The sign symmetry adapted version of (CP$k$) is given by

(CSP$k$) $\rho^{\rm{cs}}_{k}\coloneqq\left\\{\begin{aligned}
\inf_{\mathbf{y}_{i}}&\ \sum_{i=1}^{N}L_{\mathbf{y}_{i}}(p_{i})\\\
\text{s.t.}&\
B^{\mathcal{A}}_{i,k}\circ\mathbf{M}_{k}(\mathbf{y}_{i},I_{i})\succeq 0,\quad
i\in[N],\\\ &\
B^{\mathcal{A}}_{i,k-d_{j}}\circ\mathbf{M}_{k-d_{j}}(g_{j}\mathbf{y}_{i},I_{i})\succeq
0,\quad j\in J_{i},i\in[N],\\\ &\ L_{\mathbf{y}_{i}}(q_{i})=1,\quad
i\in[N],\\\ &\
L_{\mathbf{y}_{i}}(\mathbf{x}^{{\boldsymbol{\alpha}}}q_{i})=L_{\mathbf{y}_{j}}(\mathbf{x}^{{\boldsymbol{\alpha}}}q_{j}),\\\
&\
\forall{\boldsymbol{\alpha}}\in\mathbb{N}_{2k-\max\\{\deg(q_{i}),\deg(q_{j})\\}}^{(ij)}\cap\overline{\mathcal{A}},j\in
U_{i},i\in[N-1].\end{aligned}\right.$

######  Theorem 4.20.

Let Assumption 4.2 hold and assume that $q_{i}>0$ on $\mathbf{K}_{i}$ for
$i\in[N]$. It holds $\rho^{\rm{cs}}_{k}=\rho^{\rm{c}}_{k}$ for all $k\geq
d_{\min}$. Consequently, $\rho^{\rm{cs}}_{k}\nearrow\rho$ as $k\to\infty$.

######  Proof 4.21.

Let $\\{\mathbf{y}_{i}\\}$ be a feasible solution to (CP$k$). Note that
$B^{\mathcal{A}}_{i,k}\circ\mathbf{M}_{k}(\mathbf{y}_{i},I_{i})$ (resp.
$B^{\mathcal{A}}_{i,k-d_{j}}\circ\mathbf{M}_{k-d_{j}}(g_{j}\mathbf{y}_{i},I_{i})$,
$j\in J_{i}$) consists of diagonal blocks of
$\mathbf{M}_{k}(\mathbf{y}_{i},I_{i})$ (resp.
$\mathbf{M}_{k-d_{j}}(g_{j}\mathbf{y}_{i},I_{i})$, $j\in J_{i}$) for all
$i\in[N]$. Thus, $\\{\mathbf{y}_{i}\\}$ is also feasible to (CSP$k$). So
$\rho^{\rm{cs}}_{k}\leq\rho^{\rm{c}}_{k}$.

On the other hand, let $\\{\mathbf{y}_{i}\\}$ be any feasible solution to
(CSP$k$). For every $i\in[N]$, we define a pseudo-moment sequence
$\mathbf{y}^{\prime}_{i}=(y^{\prime}_{i{{\boldsymbol{\alpha}}}})_{{\boldsymbol{\alpha}}\in\mathbb{N}^{|I_{i}|}_{k}}$
as follows:

$y^{\prime}_{i{{\boldsymbol{\alpha}}}}=\begin{cases}y_{i{\boldsymbol{\alpha}}},&\text{
if }{\boldsymbol{\alpha}}\in\overline{\mathcal{A}},\\\ 0,&\text{
otherwise}.\end{cases}$

By the definition of $\mathcal{A}$, one can easily check that
$\\{\mathbf{y}^{\prime}_{i}\\}$ is a feasible solution to (CP$k$) and
$\sum_{i=1}^{N}L_{\mathbf{y}^{\prime}_{i}}(p_{i})=\sum_{i=1}^{N}L_{\mathbf{y}_{i}}(p_{i})$.
So $\rho^{\rm{cs}}_{k}\geq\rho^{\rm{c}}_{k}$ and it follows
$\rho^{\rm{cs}}_{k}=\rho^{\rm{c}}_{k}$ as desired.

The dual of (CSP$k$) reads as

(CSD$k$) $\left\\{\begin{aligned} \sup_{c_{i},h_{i,j}}&\
\sum_{i=1}^{N}c_{i}\\\ \text{s.t.}\,\,&\ p_{i}-\left(c_{i}+\sum_{j\in
U_{i}}h_{i,j}-\sum_{j\in V_{i}}h_{j,i}\right)q_{i}\in Q_{k}(\\{g_{j}\\}_{j\in
J_{i}},\mathcal{A}),\ c_{i}\in{\mathbb{R}},\ i\in[N],\\\ &\
h_{i,j}\in{\mathbb{R}}[\mathbf{x}(I_{i}\cap
I_{j})]_{2k-\max\\{\deg(q_{i}),\deg(q_{j})\\}}\cap{\mathbb{R}}[\overline{\mathcal{A}}],\quad
j\in U_{i},i\in[N-1].\end{aligned}\right.$

######  Proposition 4.22.

Under Assumption 4.2 (iii), the strong duality holds between (CSP$k$) and
(CSD$k$) for all $k\geq d_{\min}$.

######  Proof 4.23.

Note that for any feasible solution $\\{\mathbf{y}_{i}\\}$ of (CSP$k$), only
the entries
$y_{i{\boldsymbol{\alpha}}},{\boldsymbol{\alpha}}\in\overline{\mathcal{A}}$,
are involved in (CSP$k$). By the proof of Theorem 4.20, the corresponding
point $\\{\mathbf{y}^{\prime}_{i}\\}$ is feasible to (CP$k$). Then, the proof
of Proposition 4.16 indicates that the feasible set of (CSP$k$) is compact.
Hence, the strong duality holds between (CSP$k$) and (CSD$k$) as proved in
Proposition 4.16.

##  5 Numerical experiments

In this section, we conduct numerical experiments to test the performance of
the sign symmetry adapted approaches against the approaches in [3]. We use the
Julia package TSSOS111TSSOS is publically available at
https://github.com/wangjie212/TSSOS. [14] to build the SDP relaxations and
rely on MOSEK [2] to solve them. Throughout this section, $k$ stands for the
relaxation order. All numerical experiments were performed on a desktop
computer with Intel(R) Core(TM) i9-10900<EMAIL_ADDRESS>and 64G RAM.

###  5.1 Comparison of (SD$k$) with (D$k$)

We begin by presenting three examples without correlative sparsity.

######  Example 5.1.

Consider the problem

(11) $\min_{\mathbf{x}\in{\mathbb{R}}^{3}}\
\sum_{a=1/M}^{1-1/M}\frac{p_{a}(\mathbf{x})}{q_{a}(\mathbf{x})}\quad\text{s.t.}\
x_{1}^{2}+x_{2}^{2}+x_{3}^{2}=3,$

where

$\displaystyle p_{a}(\mathbf{x})=$
$\displaystyle\,a^{4}(x_{1}^{6d}+x_{2}^{6d}+x_{3}^{6d})+(x_{1}^{4d}x_{2}^{2d}+x_{2}^{4d}x_{3}^{2d}+x_{3}^{4d}x_{1}^{2d})+$
$\displaystyle\,a^{8}(x_{1}^{2d}x_{2}^{4d}+x_{2}^{2d}x_{3}^{4d}+x_{3}^{2d}x_{1}^{4d}),$
$\displaystyle q_{a}(\mathbf{x})=$
$\displaystyle\,2a^{6}(x_{1}^{4d}x_{2}^{2d}+x_{2}^{4d}x_{3}^{2d}+x_{3}^{4d}x_{1}^{2d})+2a^{2}(x_{1}^{2d}x_{2}^{4d}+x_{2}^{2d}x_{3}^{4d}+x_{3}^{2d}x_{1}^{4d})+$
$\displaystyle\,3(1-2a^{2}+a^{4}-2a^{6}+a^{8})x_{1}^{2d}x_{2}^{2d}x_{3}^{2d},$

and $M,d$ are positive integers. Replacing $x_{i}^{d}$’s by $y_{i}$’s in
$p_{a}(\mathbf{x}),q_{a}(\mathbf{x})$ and denoting the resulting polynomials
by $\tilde{p}_{a}(\mathbf{y}),\tilde{q}_{a}(\mathbf{y})$ with
$\mathbf{y}=(y_{1},y_{2},y_{3})$, one can show that for all $0<a<1$,
$\tilde{p}_{a}(\mathbf{y})-\tilde{q}_{a}(\mathbf{y})\geq 0$ on
${\mathbb{R}}^{3}$ with ten zeros: $\\{(1,\pm 1,\pm 1),(\pm a,1,0),(0,\pm
a,1),(1,0,\pm a)\\}$ [23]. Then, it is obvious that the optimum of (11) is
$M-1$. Moreover, we can rewrite $q_{a}(\mathbf{x})$ as

$\displaystyle q_{a}(\mathbf{x})=$
$\displaystyle\,2a^{6}(x_{1}^{4d}x_{2}^{2d}+x_{2}^{4d}x_{3}^{2d}+x_{3}^{4d}x_{1}^{2d}-3x_{1}^{2d}x_{2}^{2d}x_{3}^{2d})+$
$\displaystyle\,2a^{2}(x_{1}^{2d}x_{2}^{4d}+x_{2}^{2d}x_{3}^{4d}+x_{3}^{2d}x_{1}^{4d}-3x_{1}^{2d}x_{2}^{2d}x_{3}^{2d})+$
$\displaystyle\,3(1+a^{4}+a^{8})x_{1}^{2d}x_{2}^{2d}x_{3}^{2d}.$

Then, by the arithmetic-geometric inequality, we see that
$q_{a}(\mathbf{x})>0$ for all feasible points $\mathbf{x}$. Hence, (11)
satisfies Assumption 1 for all positive integers $M$ and $d$. For
$M\in\\{6,8,10\\}$ and $d\in\\{2,3,4\\}$, we solve (11) using the minimum
relaxation order $k=3d$ and present the computational results in Table 2. From
the table, we see that by exploiting sign symmetries, we gain speedup by
$1\sim 2$ magnitudes.

Table 2: Computational results for (11). $M$ |  |  $\sup$(D$k$)/Time |  |  $\sup$(SD$k$)/Time
---|---|---|---|---
| $d=2$ | $d=3$ | $d=4$ |  | $d=2$ | $d=3$ | $d=4$
$6$ |  | 5.00/0.31s | 5.00/3.85s | 5.00/36.1s |  | 5.00/0.06s | 5.00/0.38s | 5.00/1.17s
$8$ |  | 7.00/0.43s | 7.00/4.25s | 7.00/52.4s |  | 7.00/0.09s | 7.00/0.54s | 7.00/1.84s
$10$ |  | 9.00/0.54s | 9.00/5.34s | 9.00/126s |  | 9.00/0.12s | 9.00/0.71s | 9.00/2.43s

######  Example 5.2.

Consider the following problem adapted from [3]:

(12)
$\min_{\mathbf{x}\in{\mathbb{R}}^{n}}-\sum_{i=1}^{N}\frac{1}{\sum_{j=1}^{n}(x_{j}^{2}-a_{ij})^{2}+c_{i}}\quad\textrm{
s.t. }60-\sum_{i=1}^{n}(x_{i}^{2}-5)^{2}\geq 0.$

The data $\\{a_{ij}\\},\\{c_{i}\\}$ are given in [1, Table 16] with
$N=30,n\in\\{5,10\\}$. For $n=5$, the optimum of (12) is $-10.4056$, and for
$n=10$, the optimum is $-10.2088$. We present the computational results in
Table 3. From the table, we see that 1) the global optimum is achieved at
$k=5$ for $n=5$ and is achieved at $k=4$ for $n=10$; 2) by exploiting sign
symmetries, we gain speedup by $1\sim 3$ magnitudes.

Table 3: Computational results for (12). The symbol ‘-’ indicates that MOSEK
runs out of memory.

$n$ |  |  $\sup$(D$k$)/Time |  |  $\sup$(SD$k$)/Time
---|---|---|---|---
$5$ |  | $k=3$ | $k=4$ | $k=5$ |  | $k=3$ | $k=4$ | $k=5$
| -49.4493/3.53s | -12.4737/27.8s | -10.4056/306s |  | -49.4493/0.19s | -12.4736/1.52s | -10.4056/5.66s
$10$ |  | $k=2$ | $k=3$ | $k=4$ |  | $k=2$ | $k=3$ | $k=4$
| -25.2408/4.68 | -19.2391/1158s | - |  | -25.2408/0.11 | -19.2391/3.12s | -10.2088/46.8s

######  Example 5.3.

Now we carry out randomly generated problems of the form

(13) $\min_{\mathbf{x}\in{\mathbb{R}}^{n}}\
-\sum_{i=1}^{N}\frac{1}{f_{i}^{2}+1}\quad\text{s.t.}\ \
x_{1}^{2}+\cdots+x_{n}^{2}\leq 1,$

which are constructed as follows: 1) randomly choose a subset of nonconstant
monomials $\mathscr{M}$ from $[\mathbf{x}]_{d}$ with prescribed probability
$\xi$; 2) randomly assign $3$ elements in $\mathscr{M}$ to each $f_{i}$
coupled with random coefficients in $[0,1]$. It is clear that the optimal
value of (13) is $-N$. We denote the set of (13) generated in such a way by
RandSRFO$(N,n,d,\xi)$ and construct the following $12$ instances222They are
available at https://wangjie212.github.io/jiewang/code.html.:

$\displaystyle P_{1},P_{2},P_{3}$
$\displaystyle\in\textsc{RandSRFO}(10,6,4,0.05),$ $\displaystyle
P_{4},P_{5},P_{6}$ $\displaystyle\in\textsc{RandSRFO}(8,5,5,0.10),$
$\displaystyle P_{7},P_{8},P_{9}$
$\displaystyle\in\textsc{RandSRFO}(6,8,4,0.03),$ $\displaystyle
P_{10},P_{11},P_{12}$ $\displaystyle\in\textsc{RandSRFO}(12,7,5,0.05).$

We solve those instances using the minimum relaxation order $k=d$ and present
the computational results in Table 4. From the table, we see that by
exploiting sign symmetries, we gain speedup by $1\sim 2$ magnitudes.

Table 4: Computational results for (13). The symbol ‘-’ indicates that MOSEK
runs out of memory.

| $P_{1}$ | $P_{2}$ | $P_{3}$ | $P_{4}$ | $P_{5}$ | $P_{6}$
---|---|---|---|---|---|---
$\sup$(D$k$)/Time | -10.00/24.9s | -10.00/22.7s | -10.00/20.5s | -8.000/19.7s | -8.000/19.3s | -8.000/19.3s
$\sup$(SD$k$)/Time | -10.00/1.97s | -10.00/0.92s | -10.00/0.89s | -8.000/1.57s | -8.000/1.41s | -8.000/1.61s
| $P_{7}$ | $P_{8}$ | $P_{9}$ | $P_{10}$ | $P_{11}$ | $P_{12}$
$\sup$(D$k$)/Time | -6.000/311s | -6.000/331s | -6.000/370s | - | - | -
$\sup$(SD$k$)/Time | -6.000/3.04s | -6.000/2.18s | -6.000/2.79s | -12.00/19.7s | -12.00/19.9s | -12.00/19.8s

###  5.2 Comparison of (CD$k$) with (CSD$k$)

We will proceed with two examples for which both correlative sparsity and sign
symmetries are present.

######  Example 5.4.

Consider

(14) $\displaystyle\min_{\mathbf{x}\in{\mathbb{R}}^{2N+2}}$ $\displaystyle\
\sum_{i=1}^{N}\frac{(x_{2i-1}^{2}+x_{2i}^{2}+x_{2i+1}^{2})x_{2i-1}^{2}x_{2i}^{2}x_{2i+1}^{2}+x_{2i+2}^{8}}{x_{2i-1}^{2}x_{2i}^{2}x_{2i+1}^{2}x_{2i+2}^{2}}$
s.t. $\displaystyle\ x_{2i-1}^{2}+x_{2i}^{2}+x_{2i+1}^{2}+x_{2i+2}^{2}=4,\quad
i\in[N].$

For each $i$, the polynomial

$(x_{2i-1}^{2}+x_{2i}^{2}+x_{2i+1}^{2}-4x_{2i+2}^{2})x_{2i-1}^{2}x_{2i}^{2}x_{2i+1}^{2}+x_{2i+2}^{8}$

is nonnegative with zeros $(\pm 1,\pm 1,\pm 1,\pm 1)$ [15]. Therefore, the
optimum of (14) equals $4N$. It is clear that Assumption 4.2 holds with
$I_{i}=\\{2i-1,2i,2i+1,2i+2\\}$ and $J_{i}=\\{i\\}$, $i\in[N]$. For
$N\in\\{20,40,60\\}$, we solve (14) and present the computational results in
Table 5. It can be seen from the table that by exploiting sign symmetries, we
gain extra speedup by several times.

Table 5: Computational results for (14). The symbol ‘*’ indicates that MOSEK encounters numerical issues. $N$ |  |  $\sup$(CD$k$)/Time |  |  $\sup$(CSD$k$)/Time
---|---|---|---|---
| $k=4$ | $k=5$ |  | $k=4$ | $k=5$
20 |  | 16.65*/1.38s | 80.00/10.6s |  | 19.06*/0.49s | 80.00/0.73s
40 |  | 37.71*/3.25s | 160.0/15.8s |  | 37.71*/0.62s | 160.0/1.79s
60 |  | 52.17*/6.97s | 240.0/28.9s |  | 57.75*/1.51s | 240.0/3.43s

######  Example 5.5.

Consider

(15) $\min_{\mathbf{x}\in{\mathbb{R}}^{2N+1}}\
\sum_{i=1}^{N}\frac{p_{i}(\mathbf{x})}{q_{i}(\mathbf{x})}\quad\text{s.t.}\ \
x_{2i-1}^{2}+x_{2i}^{2}+x_{2i+1}^{2}=3,\ i\in[N],$

where

$\displaystyle p_{i}(\mathbf{x})=$ $\displaystyle
x_{2i-1}^{6d}+x_{2i}^{6d}+x_{2i+1}^{6d}+3x_{2i-1}^{2d}x_{2i}^{2d}x_{2i+1}^{2d},$
$\displaystyle q_{i}(\mathbf{x})=$ $\displaystyle
x_{2i-1}^{4d}x_{2i}^{2d}+x_{2i-1}^{2d}x_{2i}^{4d}+x_{2i-1}^{4d}x_{2i+1}^{2d}+x_{2i-1}^{2d}x_{2i+1}^{4d}+x_{2i}^{4d}x_{2i+1}^{2d}+x_{2i}^{2d}x_{2i+1}^{4d},$

for some $d\geq 1$. From Example 5.1, it is easy to see that the optimum of
(15) equals $N$. Moreover, Assumption 4.2 holds with
$I_{i}=\\{2i-1,2i,2i+1\\}$ and $J_{i}=\\{i\\}$, $i\in[N]$. For
$N\in\\{5,10,20\\}$ and $d\in\\{2,3,4\\}$, we solve (15) using the minimum
relaxation order $k=3d$ and present the computational results in Table 6.
Again, it can be seen from the table that by exploiting sign symmetries, we
gain extra significant speedup.

Table 6: Computational results for (15). $N$ |  |  $\sup$(CD$k$)/Time |  |  $\sup$(CSD$k$)/Time
---|---|---|---|---
| $d=2$ | $d=3$ | $d=4$ |  | $d=2$ | $d=3$ | $d=4$
$5$ |  | 5.000/0.28s | 5.000/2.58s | 5.000/23.1s |  | 5.000/0.06s | 5.000/0.34s | 5.000/1.06s
$10$ |  | 10.00/0.56s | 10.00/4.35s | 10.00/44.1s |  | 10.00/0.12s | 10.00/0.80s | 10.00/2.05s
$20$ |  | 20.00/1.17s | 20.00/9.50s | 20.00/95.8s |  | 20.00/0.25s | 15.00/1.62s | 20.00/4.40s

###  5.3 Comparison of (CD$k$) with (CSD$k$) and the epigraph approach

In this subsection, we further compare (CD$k$) with the epigraph approach
which translates (SRFO) into a polynomial optimization problem:

(SEA) $\left\\{\begin{aligned} \inf_{c_{i},\mathbf{x}}&\
\sum_{i=1}^{N}c_{i}\\\ \text{s.t.}&\
p_{i}(\mathbf{x})-c_{i}q_{i}(\mathbf{x})=0,\quad i\in[N],\\\ &\
g_{j}(\mathbf{x})\geq 0,\quad j\in[m].\end{aligned}\right.$

Note that (SEA) inherits the correlative sparsity and sign symmetries of
(SRFO) which can be exploited to obtain sparse SDP relaxations for (SEA) [30].

######  Example 5.6.

Consider

(16) $\max_{\mathbf{x}\in{\mathbb{R}}^{N+1}}\
\sum_{i=1}^{N}\frac{1}{100(x_{i+1}^{2}-x_{i}^{2})^{2}+(x_{i}^{2}-1)^{2}+1}\quad\text{s.t.}\
\ 16-x_{i}^{2}\geq 0,\ i\in[N+1],$

which is modified from the well-known Rosenbrock problem. Clearly, the optimum
of (16) equals $N$ and Assumption 4.2 holds with $I_{i}=J_{i}=\\{i,i+1\\}$,
$i\in[N]$. We solve (16) for $N\in\\{100,200,400\\}$. It turns out that the
SDP relaxations (CD$k$) and (CSD$k$) attain global optimality at $k=2$ while
the epigraph approach attains global optimality at $k=4$. We present the
computational results in Table 7, from which we can see that the sparse SDP
relaxation (CSD$k$) is the most efficient approach.

Table 7: Computational results for (16). ‘EPI’ indicates the lower bounds obtained by the epigraph approach. $N$ |  | EPI/Time |  |  $\sup$(CD$k$)/Time |  |  $\sup$(CSD$k$)/Time
---|---|---|---|---|---|---
| $k=4$ |  | $k=2$ |  | $k=2$
$100$ |  | 100.0/2.30s |  | 100.0/0.15s |  | 100.0/0.06s
$200$ |  | 200.0/6.94s |  | 200.0/0.58s |  | 200.0/0.21s
$400$ |  | 400.0/20.8s |  | 400.0/1.72s |  | 400.0/0.97s

######  Example 5.7.

Consider

(17)
$\min_{\mathbf{x}\in{\mathbb{R}}^{N+s}}\sum_{i=1}^{N}\frac{\sum_{j=1}^{s}x_{i+j-1}x_{i+j}}{1+\sum_{j=1}^{s+1}jx_{i+j-1}^{2}}\quad\textrm{s.t.
}1-x_{i}^{2}\geq 0,\ i\in[N+s],$

for some $s\geq 1$. It is clear that Assumption 4.2 holds with
$I_{i}=J_{i}=\\{i,i+1,\ldots,i+s\\}$, $i\in[N]$. We solve (17) for
$N\in\\{20,40,60\\}$ using the minimum relaxation order $k=3$ and present the
computational results in Table 8. From the table, we see that the epigraph
approach yields slightly tighter bounds and moreover, the sparse SDP
relaxation (CSD$k$) is the most efficient approach.

Table 8: Computational results for (17). ‘EPI’ indicates the lower bounds obtained by the epigraph approach. $N$ |  | EPI/Time |  |  $\sup$(CD$k$)/Time |  |  $\sup$(CSD$k$)/Time
---|---|---|---|---|---|---
| $k=3$ |  | $k=3$ |  | $k=3$
$20$ |  | -4.5892/23.9s |  | -4.6173/61.6s |  | -4.6173/23.3s
$40$ |  | -8.7429/62.0s |  | -8.8778/105s |  | -8.8778/52.8s
$60$ |  | -12.901/100s |  | -13.138/148s |  | -13.138/70.8s

Finally, we would like to mention that the epigraph approach behaves very
badly on the examples presented in the previous subsections.

##  6 An application to maximizing sums of generalized Rayleigh quotients

In this section, we apply the sparse SDP relaxations to the problem of
maximizing a sum of generalized Rayleigh quotients which arises from signal
processing.

In the downlink of a multi-user MIMO system, the base station can multiplex
signals intended to different users on the same spectral resource. A
challenging problem arising in such a scenario is the joint optimization of
channel assignment (scheduling) and beamforming aimed at maximizing the sum-
rate in each time-slot. Assuming zero-forcing linear beamforming at the base
station, Primolevo et al. [21] addressed this task by investigating a greedy
method to approximately maximize the sum-rate. At each iteration of their
method a spatial channel needs to be determined to allocate a specific user,
which reduces to maximizing a sum of generalized Rayleigh quotients of the
form

(18)
$\max_{\mathbf{z}\in{\mathbb{C}}^{n}}\sum_{i=1}^{N}\frac{\mathbf{z}^{\rm{H}}A_{i}\mathbf{z}}{\mathbf{z}^{\rm{H}}B_{i}\mathbf{z}}\quad\text{s.t.
}\ \|\mathbf{z}\|^{2}=1,$

where $A_{i},B_{i}\in{\mathbb{C}}^{n\times n}$ are positive semidefinite
Hermitian matrices, $\mathbf{z}^{\rm{H}}$ denotes the conjugate transpose of
$\mathbf{z}$, $n$ is the number of assigned spatial channels at the current
iteration, and $N$ is the number of available users in the time-slot.

When $N=2$, the real counterpart of the problem (18) also appears in the
sparse Fisher discriminant analysis in pattern recognition (see [4, 5, 32]).
The single generalized Rayleigh quotient optimization problem corresponds to
the classical eigenvalue problem and can be solved in polynomial time [20].
However, when $N\geq 2$, solving (18) is much more challenging and requires
sophisticated techniques (see [16, 31, 34] for the real case of $N=2$). In
particular, Primolevo et al. [21] restricted $\mathbf{z}$ in (18) to be
columns of an identity matrix to give a suboptimal solution.

Here, we convert (18) into a real problem by specifying the real and imaginary
parts of the complex variables and coefficients appearing in (18). Let
$\mathbf{z}=\mathbf{x}+\mathbf{i}\mathbf{y}$,
$A_{i}=A_{i,1}+\mathbf{i}A_{i,2}$, and $B_{i}=B_{i,1}+\mathbf{i}B_{i,2}$ with
$\mathbf{x},\mathbf{y}\in{\mathbb{R}}^{n}$ and
$A_{i,1},A_{i,2},B_{i,1},B_{i,2}\in{\mathbb{R}}^{n\times n}$. Then (18)
becomes

(19)
$\max_{\mathbf{x},\mathbf{y}\in{\mathbb{R}}^{n}}\sum_{i=1}^{N}\frac{\mathbf{x}^{\intercal}A_{i,1}\mathbf{x}-2\mathbf{x}^{\intercal}A_{i,2}\mathbf{y}+\mathbf{y}^{\intercal}A_{i,1}\mathbf{y}}{\mathbf{x}^{\intercal}B_{i,1}\mathbf{x}-2\mathbf{x}^{\intercal}B_{i,2}\mathbf{y}+\mathbf{y}^{\intercal}B_{i,1}\mathbf{y}}\quad\text{s.t.
}\ \|\mathbf{x}\|^{2}+\|\mathbf{y}\|^{2}=1.$

In our numerical experiments, we assume that $A_{i}$’s are Hermitian and
$B_{i}$’s are positive definite. To satisfy this condition, we generate random
matrices $C_{i,1},C_{i,2},D_{i,1},D_{i,2}\in{\mathbb{R}}^{n\times n}$ with
each entry being drawn from the uniform distribution on $[0,1]$, and let

$A_{i}=(C_{i,1}+\mathbf{i}C_{i,2})+(C_{i,1}+\mathbf{i}C_{i,2})^{\rm{H}},\quad
B_{i}=(D_{i,1}+\mathbf{i}D_{i,2})^{\rm{H}}(D_{i,1}+\mathbf{i}D_{i,2}).$

We solve one instance of (19) with (D$k$) and (SD$k$) for
$(n,N)\in\\{(3,20),(4,10),(5,5)\\}$, and present the computational results in
Table 9. From the table, we see that by exploiting sign symmetries, we gain
around twice speedup.

Table 9: Computational results for (19). $(n,N)$ |  |  $\sup$(D$k$)/Time |  |  $\sup$(SD$k$)/Time
---|---|---|---|---
| $k=2$ | $k=3$ |  | $k=2$ | $k=3$
$(3,20)$ |  | 406.7/0.61s | 406.7/12.7s |  | 406.7/0.38s | 406.7/5.91s
$(4,10)$ |  | 26.54/1.03s | 20.10/107s |  | 26.54/0.67s | 20.10/50.5s
$(5,5)$ |  | 20.12/2.43s | 19.11/531s |  | 20.12/1.57s | 19.11/339s

## References

  * [1] M. M. Ali, C. Khompatraporn, and Z. B. Zabinsky, A numerical evaluation of several stochastic algorithms on selected continuous global optimization test problems, Journal of global optimization, 31 (2005), pp. 635–672.
  * [2] E. D. Andersen and K. D. Andersen, The Mosek Interior Point Optimizer for Linear Programming: An Implementation of the Homogeneous Algorithm, in High Performance Optimization, H. Frenk, K. Roos, T. Terlaky, and S. Zhang, eds., vol. 33 of Applied Optimization, Springer US, 2000, pp. 197–232.
  * [3] F. Bugarin, D. Henrion, and J. B. Lasserre, Minimizing the sum of many rational functions, Mathematical Programming Computation, 8 (2016), pp. 83–111.
  * [4] M. M. Dundar, G. Fung, J. Bi, S. Sathyakama, and B. Rao, Sparse Fisher discriminant analysis for computer aided detection, in Proceedings of the 2005 SIAM International Conference on Data Mining (SDM), H. Kargupta, C. Kamath, J. Srivastava, and A. Goodman, eds., Philadelphia, PA, 2005, Society for Industrial and Applied Mathematics, pp. 476–480.
  * [5] E. Fung and M. Ng, On sparse Fisher discriminant method for microarray data analysis, Bioinformation, 2 (2007), pp. 230–234.
  * [6] F. Guo, L. Wang, and G. Zhou, Minimizing rational functions by exact jacobian SDP relaxation applicable to finite singularities, Journal of Global Optimization, 58 (2014), pp. 261–284.
  * [7] R. Hartley, F. Kahl, C. Olsson, and Y. Seo, Verifying global minima for l 2 minimization problems in multiple view geometry, International Journal of Computer Vision, 101 (2013), pp. 288–304.
  * [8] D. Jibetean and E. de Klerk, Global optimization of rational functions: a semidefinite programming approach, Math. Program., 106 (2006), pp. 93–109.
  * [9] F. Kahl, S. Agarwal, M. K. Chandraker, D. Kriegman, and S. Belongie, Practical global optimization for multiview geometry, International Journal of Computer Vision, 79 (2008), pp. 271–284.
  * [10] M. Korda and D. Henrion, Convergence rates of moment-sum-of-squares hierarchies for volume approximation of semialgebraic sets, Optimization Letters, 12 (2018), pp. 435–442.
  * [11] M. Korda, D. Henrion, and C. N. Jones, Convergence rates of moment-sum-of-squares hierarchies for optimal control problems, Systems & Control Letters, 100 (2017), pp. 1–5.
  * [12] J. B. Lasserre, V. Magron, S. Marx, and O. Zahm, Minimizing rational functions: A hierarchy of approximations via pushforward measures, SIAM Journal on Optimization, 31 (2021), pp. 2285–2306.
  * [13] J. Löfberg, Pre- and post-processing sum-of-squares programs in practice, IEEE Transactions on Automatic Control, 54 (2009), pp. 1007–1011.
  * [14] V. Magron and J. Wang, TSSOS: a Julia library to exploit sparsity for large-scale polynomial optimization, in The 16th Effective Methods in Algebraic Geometry Conference, 2021.
  * [15] T. Motzkin, The arithmetic-geometric inequality, in Inequalities, O. Shisha, ed., New York, 1967, Academic Press, pp. 205–224.
  * [16] V.-B. Nguyen, R.-L. Sheu, and Y. Xia, Maximizing the sum of a generalized Rayleigh quotient and another Rayleigh quotient on the unit sphere via semidefinite programming, Journal of Global Optimization, 64 (2016), pp. 399–416.
  * [17] J. Nie, An exact jacobian sdp relaxation for polynomial optimization, Mathematical Programming, 137 (2013), pp. 225–255.
  * [18] J. Nie, J. Demmel, and M. Gu, Global minimization of rational functions and the nearest GCDs, Journal of Global Optimization, 40 (2008), pp. 697–718.
  * [19] J. Nie and M. Schweighofer, On the complexity of Putinar’s positivstellensatz, Journal of Complexity, 23 (2007), pp. 135 – 150.
  * [20] B. N. Parlett, The Symmetric Eigenvalue Problem, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1998.
  * [21] G. Primolevo, O. Simeone, and U. Spagnolini, Towards a joint optimization of scheduling and beamforning for MIMO downlink, in 2006 IEEE Ninth International Symposium on Spread Spectrum Techniques and Applications, 2006, pp. 493–497.
  * [22] M. Putinar, Positive polynomials on compact semi-algebraic sets, Indiana University Mathematics Journal, 42 (1993), pp. 969–984.
  * [23] B. Reznick, Some concrete aspects of Hilbert’s 17th problem, in Contemporary Mathematics, vol. 253, American Mathematical Society, 2000, pp. 251–272.
  * [24] S. Schaible and J. Shi, Fractional programming: The sum-of-ratios case, Optimization Methods and Software, 18 (2003), pp. 219–229.
  * [25] A. Shapiro, Semi-infinite programming, duality, discretization and optimality conditions, Optimization, 58 (2009), pp. 133–161.
  * [26] A. Shapiro and K. Scheinber, Duality, optimality conditions and perturbation analysis, in Handbook of Semidefinite Programming - Theory, Algorithms, and Applications, H. Wolkowicz, R. Saigal, and L. Vandenberghe, eds., Kluwer Academic Publisher, Boston, 2000, pp. 67–110.
  * [27] A. Timan, Theory of Approximation of Functions of a Real Variable, International Series of Monographs on Pure and Applied Mathematics, Pergamon, 1963.
  * [28] M. Trnovská, Strong duality conditions in semidefinite programming, Journal of Electrical Engineering, 56 (2005), pp. 1–5.
  * [29] J. Wang, V. Magron, and J.-B. Lasserre, TSSOS: A moment-SOS hierarchy that exploits term sparsity, SIAM Journal on Optimization, 31 (2021), pp. 30–58.
  * [30] J. Wang, V. Magron, J. B. Lasserre, and N. H. A. Mai, Cs-tssos: Correlative and term sparsity for large-scale polynomial optimization, ACM Transactions on Mathematical Software, 48 (2022), pp. 1–26.
  * [31] X. Wang, L. Wang, and Y. Xia, An efficient global optimization algorithm for maximizing the sum of two generalized Rayleigh quotients, Computational and Applied Mathematics, 37 (2018), pp. 4412–4422.
  * [32] M. C. Wu, L. Zhang, Z. Wang, D. C. Christiani, and X. Lin, Sparse linear discriminant analysis for simultaneous testing for the significance of a gene set/pathway and gene selection, Bioinformatics, 25 (2009), pp. 1145–1151.
  * [33] W.-Y. Wu, R.-L. Sheu, and Ş. İ. Birbil, Solving the sum-of-ratios problem by a stochastic search algorithm, Journal of Global Optimization, 42 (2008), pp. 91–109.
  * [34] L.-H. Zhang, On optimizing the sum of the rayleigh quotient and the generalized rayleigh quotient on the unit sphere, Computational Optimization and Applications, 54 (2013), pp. 111–139.