exampleExample remarkRemark hypothesisHypothesis claimClaim Strengthening
Lasserre’s HierarchyJie Wang

# Strengthening Lasserre’s Hierarchy in Real and Complex Polynomial
Optimization††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.

Jie Wang Academy of Mathematics and Systems Science, Chinese Academy of
Sciences, Beijing, China (, https://wangjie212.github.io/jiewang/)
<EMAIL_ADDRESS>
###### Abstract

We establish a connection between multiplication operators and shift
operators. Moreover, we derive positive semidefinite conditions of finite rank
moment sequences and use these conditions to strengthen Lasserre’s hierarchy
for real and complex polynomial optimization. Integration of the strengthening
technique with sparsity is considered. Extensive numerical experiments show
that our strengthening technique can significantly improve the bound
(especially for complex polynomial optimization) and allows to achieve global
optimality at lower relaxation orders, thus providing substantial
computational savings.

###### keywords:

polynomial optimization, complex polynomial optimization, semidefinite
relaxation, Lasserre’s hierarchy, multiplication operator, shift operator

Primary, 90C23; Secondary, 90C22,90C26

##  1 Introduction

Lasserre’s hierarchy [6] is a well-established scheme for globally solving
(real) polynomial optimization problems and attracts a lot of attentions of
researchers from diverse fields due to its nice theoretical properties in
recent years [3, 11]. There is also a complex variant of Lasserre’s hierarchy
for globally solving complex polynomial optimization problems [5].

A bottleneck of Lasserre’s hierarchy is its limited scalability as the size of
associated semidefinite relaxations grows rapidly with relaxation orders. One
way for overcoming this is exploiting structures (sparsity, symmetry) of
polynomial optimization problems to obtain structured semidefinite relaxations
of reduced sizes. We refer the reader to the recent works [12, 18, 19] on this
topic. Another practical idea is strengthening Lasserre’s hierarchy to
accelerate its convergence, for instance, using Lagrange multiplier
expressions as done in [10].

In this paper we propose to strengthen Lasserre’s hierarchy using positive
semidefinite (PSD) optimality conditions for any real and complex polynomial
optimization problem. These PSD optimality conditions arise from the
characterization of normality of _shift operators_ which is closely related to
_multiplication operators_. Both operators have applications in extractions of
optimal solutions when solving polynomial optimization problems with
Lasserre’s hierarchy [4, 5]. We establish a connection between shift operators
and multiplication operators. Further, we derive PSD conditions of finite rank
moment sequences via shift operators. These PSD conditions are then employed
to strengthen Lasserre’s hierarchy. In particular, for real polynomial
optimization, we present an intermediate relaxation between two successive
moment relaxations; for complex polynomial optimization, we present a two-
level hierarchy of moment relaxations which thus offers one more level of
flexibility. To improve scalability, the strengthening technique is further
integrated into different sparse versions of Lasserre’s hierarchy. Diverse
numerical experiments are performed. It is shown that the strengthening
technique can indeed improve the bound provided by the usual Lasserre’s
hierarchy and very likely allows to achieve global optimality at lower
relaxation orders, especially in complex polynomial optimization.

##  2 Notation and preliminaries

Let ${\mathbb{N}}$ be the set of nonnegative integers. For
$n\in{\mathbb{N}}\setminus\\{0\\}$, let $[n]\coloneqq\\{1,2,\ldots,n\\}$. For
${\boldsymbol{\alpha}}=(\alpha_{i})\in{\mathbb{N}}^{n}$, let
$|{\boldsymbol{\alpha}}|\coloneqq\sum_{i=1}^{n}\alpha_{i}$. For
$r\in{\mathbb{N}}$, let
${\mathbb{N}}^{n}_{r}\coloneqq\\{{\boldsymbol{\alpha}}\in{\mathbb{N}}^{n}\mid|{\boldsymbol{\alpha}}|\leq
r\\}$ and $|{\mathbb{N}}^{n}_{r}|$ stands for its cardinality. We use
$A\succeq 0$ to indicate that the matrix $A$ is positive semidefinite (PSD).
Let i be the imaginary unit, satisfying $\hbox{\bf{i}}^{2}=-1$. Throughout the
paper, let ${\mathbb{F}}\in\\{{\mathbb{R}},{\mathbb{C}}\\}$. Let
${\mathbb{F}}[{\mathbf{x}}]\coloneqq{\mathbb{F}}[x_{1},\ldots,x_{n}]$ be the
ring of multivariate polynomials in $n$ variables over the field
${\mathbb{F}}$, and ${\mathbb{F}}[{\mathbf{x}}]_{d}$ denote the subset of
polynomials of degree no greater than $d$. A polynomial
$f\in{\mathbb{F}}[{\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{F}}$ and
${\mathbf{x}}^{{\boldsymbol{\alpha}}}\coloneqq x_{1}^{\alpha_{1}}\cdots
x_{n}^{\alpha_{n}}$. For $d\in{\mathbb{N}}$, $[{\mathbf{x}}]_{d}$ stands for
the standard monomial basis of degree up to $d$, and $[{\mathbf{x}}]$ stands
for the standard monomial basis.

Let $\overline{a}$ denote the conjugate of a complex number $a$ and
${\boldsymbol{v}}^{*}$ (resp. $A^{*}$) denote the conjugate transpose of a
complex vector ${\boldsymbol{v}}$ (resp. a complex matrix $A$). We use
$\overline{{\mathbf{x}}}=(\overline{x}_{1},\ldots,\overline{x}_{n})$ to denote
the conjugate of the tuple of complex variables ${\mathbf{x}}$. We denote by
${\mathbb{C}}[{\mathbf{x}},\overline{{\mathbf{x}}}]\coloneqq{\mathbb{C}}[x_{1},\ldots,x_{n},\overline{x}_{1},\ldots,\overline{x}_{n}]$
the complex polynomial rings in ${\mathbf{x}},\overline{{\mathbf{x}}}$. A
polynomial $f\in{\mathbb{C}}[{\mathbf{x}},\overline{{\mathbf{x}}}]$ can be
written as
$f=\sum_{({\boldsymbol{\beta}},{\boldsymbol{\gamma}})\in{\mathbb{N}}^{n}\times{\mathbb{N}}^{n}}f_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}{\mathbf{x}}^{{\boldsymbol{\beta}}}\overline{{\mathbf{x}}}^{{\boldsymbol{\gamma}}}$
with $f_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}\in{\mathbb{C}}$. The
_conjugate_ of $f$ is defined as
$\overline{f}=\sum_{({\boldsymbol{\beta}},{\boldsymbol{\gamma}})\in{\mathbb{N}}^{n}\times{\mathbb{N}}^{n}}\overline{f}_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}{\mathbf{x}}^{{\boldsymbol{\gamma}}}\overline{{\mathbf{x}}}^{{\boldsymbol{\beta}}}$.
The polynomial $f$ is _self-conjugate_ if $\overline{f}=f$. It is clear that
self-conjugate polynomials take only real values.

###  2.1 The real Lasserre’s hierarchy for real polynomial optimization

Consider the real polynomial optimization problem:

(RPOP)
$f_{\min}\coloneqq\inf\,\\{f({\mathbf{x}}):{\mathbf{x}}\in\mathbf{K}\\},$

where $f\in{\mathbb{R}}[{\mathbf{x}}]$ and the feasible set $\mathbf{K}$ is
given by

(1)
$\mathbf{K}\coloneqq\\{{\mathbf{x}}\in{\mathbb{R}}^{n}:g_{1}({\mathbf{x}})\geq
0,\dots,g_{m}({\mathbf{x}})\geq 0\\},$

for some polynomials $g_{1},\dots,g_{m}\in{\mathbb{R}}[{\mathbf{x}}]$. By
invoking Borel measures, (RPOP) admits the following reformulation:

(2)
$\begin{cases}\inf\limits_{\mu\in\mathcal{M}_{+}(\mathbf{K})}&\int_{\mathbf{K}}f\,\mathrm{d}\mu\\\
\quad\,\,\rm{s.t.}&\int_{\mathbf{K}}\,\mathrm{d}\mu=1,\\\ \end{cases}$

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

Suppose that
${\mathbf{y}}=(y_{{\boldsymbol{\alpha}}})_{{\boldsymbol{\alpha}}\in{\mathbb{N}}^{n}}$
is a (pseudo-moment) sequence in ${\mathbb{R}}$. We associate it with a linear
functional
$L_{{\mathbf{y}}}:{\mathbb{R}}[{\mathbf{x}}]\rightarrow{\mathbb{R}}$ by

$f=\sum_{{\boldsymbol{\alpha}}}f_{{\boldsymbol{\alpha}}}{\mathbf{x}}^{{\boldsymbol{\alpha}}}\longmapsto
L_{{\mathbf{y}}}(f)=\sum_{{\boldsymbol{\alpha}}}f_{{\boldsymbol{\alpha}}}y_{{\boldsymbol{\alpha}}}.$

For $r\in{\mathbb{N}}$, the $r$-th order _real moment matrix_
${\mathbf{M}}^{{\mathbb{R}}}_{r}({\mathbf{y}})$ is the matrix indexed by
${\mathbb{N}}^{n}_{r}$ such that

$[{\mathbf{M}}^{{\mathbb{R}}}_{r}({\mathbf{y}})]_{{\boldsymbol{\beta}}{\boldsymbol{\gamma}}}\coloneqq
L_{{\mathbf{y}}}({\mathbf{x}}^{{\boldsymbol{\beta}}}{\mathbf{x}}^{{\boldsymbol{\gamma}}})=y_{{\boldsymbol{\beta}}+{\boldsymbol{\gamma}}},\quad\forall{\boldsymbol{\beta}},{\boldsymbol{\gamma}}\in{\mathbb{N}}^{n}_{r}.$

The real moment matrix ${\mathbf{M}}^{{\mathbb{R}}}({\mathbf{y}})$ indexed by
${\mathbb{N}}^{n}$ is defined similarly. For a polynomial
$g=\sum_{{\boldsymbol{\alpha}}}g_{{\boldsymbol{\alpha}}}{\mathbf{x}}^{{\boldsymbol{\alpha}}}\in{\mathbb{R}}[{\mathbf{x}}]$,
the $r$-th order _real localizing matrix_
${\mathbf{M}}^{{\mathbb{R}}}_{r}(g{\mathbf{y}})$ associated with $g$ is the
matrix indexed by ${\mathbb{N}}^{n}_{r}$ such that

$[{\mathbf{M}}^{{\mathbb{R}}}_{r}(g{\mathbf{y}})]_{{\boldsymbol{\beta}}{\boldsymbol{\gamma}}}\coloneqq
L_{{\mathbf{y}}}(g{\mathbf{x}}^{{\boldsymbol{\beta}}}{\mathbf{x}}^{{\boldsymbol{\gamma}}})=\sum_{{\boldsymbol{\alpha}}}g_{{\boldsymbol{\alpha}}}y_{{\boldsymbol{\alpha}}+{\boldsymbol{\beta}}+{\boldsymbol{\gamma}}},\quad\forall{\boldsymbol{\beta}},{\boldsymbol{\gamma}}\in{\mathbb{N}}^{n}_{r}.$

The sequence ${\mathbf{y}}$ is called a _real moment sequence_ if it can be
realized by a Borel measure $\mu$, i.e.,
$y_{{\boldsymbol{\alpha}}}=\int_{\mathbf{K}}{\mathbf{x}}^{{\boldsymbol{\alpha}}}\,\mathrm{d}\mu$
for any ${\boldsymbol{\alpha}}\in{\mathbb{N}}^{n}$, and ${\mathbf{y}}$ is said
to be of finite rank if $\mu$ is a finitely atomic measure (that is, a linear
positive combination of finitely many Dirac measures), where the rank of
${\mathbf{y}}$ is defined as the number of atoms.

######  Lemma 2.1 ([8], Lemma 4.2).

If ${\mathbf{y}}$ is a real moment sequence of finite rank, then
${\mathbf{M}}^{{\mathbb{R}}}({\mathbf{y}})\succeq 0$ and the rank of
${\mathbf{y}}$ is equal to $\hbox{\rm{rank}}\,M^{{\mathbb{R}}}({\mathbf{y}})$.

Let $d_{i}\coloneqq\lceil\deg(g_{i})/2\rceil,i=1,\ldots,m$,
$d_{\min}\coloneqq\max\\{\lceil\deg(f)/2\rceil,d_{1},\ldots,d_{m}\\}$. With
$r\geq d_{\min}$, the real Lasserre’s hierarchy of moment relaxations for
(RPOP) [6] is given by

(3)
$\rho_{r}\coloneqq\begin{cases}\inf\limits_{{\mathbf{y}}}&L_{{\mathbf{y}}}(f)\\\
\rm{s.t.}&{\mathbf{M}}^{{\mathbb{R}}}_{r}({\mathbf{y}})\succeq 0,\quad
y_{\mathbf{0}}=1,\\\
&{\mathbf{M}}^{{\mathbb{R}}}_{r-d_{i}}(g_{i}{\mathbf{y}})\succeq 0,\quad
i\in[m].\end{cases}$

###  2.2 The complex Lasserre’s hierarchy for complex polynomial optimization

Consider the complex polynomial optimization problem:

(CPOP)
$f_{\min}\coloneqq\inf\,\\{f({\mathbf{x}},\overline{{\mathbf{x}}}):{\mathbf{x}}\in\mathbf{K}\\},$

where

(4) $\mathbf{K}\coloneqq\left\\{{\mathbf{x}}\in{\mathbb{C}}^{n}\mid
g_{i}({\mathbf{x}},\overline{{\mathbf{x}}})\geq 0,i\in[m]\right\\},$

and
$f,g_{1},\ldots,g_{m}\in{\mathbb{C}}[{\mathbf{x}},\overline{{\mathbf{x}}}]$
are self-conjugate polynomials. By invoking Borel measures, (CPOP) also admits
the following reformulation:

(5)
$\begin{cases}\inf\limits_{\mu\in\mathcal{M}_{+}(\mathbf{K})}&\int_{\mathbf{K}}f\,\mathrm{d}\mu\\\
\quad\,\,\rm{s.t.}&\int_{\mathbf{K}}\,\mathrm{d}\mu=1,\\\ \end{cases}$

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

Suppose that
${\mathbf{y}}=(y_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}})_{({\boldsymbol{\beta}},{\boldsymbol{\gamma}})\in{\mathbb{N}}^{n}\times{\mathbb{N}}^{n}}$
in ${\mathbb{C}}$ is a (pseudo-moment) sequence satisfying
$y_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}=\overline{y}_{{\boldsymbol{\gamma}},{\boldsymbol{\beta}}}$.
We associate it with a linear functional
$L_{{\mathbf{y}}}:{\mathbb{C}}[{\mathbf{x}},\overline{{\mathbf{x}}}]\rightarrow{\mathbb{C}}$
by

$f=\sum_{({\boldsymbol{\beta}},{\boldsymbol{\gamma}})}f_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}{\mathbf{x}}^{{\boldsymbol{\beta}}}\overline{{\mathbf{x}}}^{{\boldsymbol{\gamma}}}\longmapsto
L_{{\mathbf{y}}}(f)=\sum_{({\boldsymbol{\beta}},{\boldsymbol{\gamma}})}f_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}y_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}.$

For $r\in{\mathbb{N}}$, the $r$-th order _complex moment matrix_
${\mathbf{M}}^{{\mathbb{C}}}_{r}({\mathbf{y}})$ is the matrix indexed by
${\mathbb{N}}^{n}_{r}$ such that

$[{\mathbf{M}}^{{\mathbb{C}}}_{r}({\mathbf{y}})]_{{\boldsymbol{\beta}}{\boldsymbol{\gamma}}}\coloneqq
L_{{\mathbf{y}}}({\mathbf{x}}^{{\boldsymbol{\beta}}}\overline{{\mathbf{x}}}^{{\boldsymbol{\gamma}}})=y_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}},\quad\forall{\boldsymbol{\beta}},{\boldsymbol{\gamma}}\in{\mathbb{N}}^{n}_{r}.$

The complex moment matrix ${\mathbf{M}}^{{\mathbb{C}}}({\mathbf{y}})$ indexed
by ${\mathbb{N}}^{n}$ is defined similarly. For a self-conjugate polynomial
$g=\sum_{({\boldsymbol{\beta}}^{\prime},{\boldsymbol{\gamma}}^{\prime})}g_{{\boldsymbol{\beta}}^{\prime},{\boldsymbol{\gamma}}^{\prime}}{\mathbf{x}}^{{\boldsymbol{\beta}}^{\prime}}\overline{{\mathbf{x}}}^{{\boldsymbol{\gamma}}^{\prime}}\in{\mathbb{C}}[{\mathbf{x}},\overline{{\mathbf{x}}}]$,
the $r$-th order _complex localizing matrix_
${\mathbf{M}}^{{\mathbb{C}}}_{r}(g{\mathbf{y}})$ associated with $g$ is the
matrix indexed by ${\mathbb{N}}^{n}_{r}$ such that

$[{\mathbf{M}}^{{\mathbb{C}}}_{r}(g{\mathbf{y}})]_{{\boldsymbol{\beta}}{\boldsymbol{\gamma}}}\coloneqq
L_{{\mathbf{y}}}(g{\mathbf{x}}^{{\boldsymbol{\beta}}}\overline{{\mathbf{x}}}^{{\boldsymbol{\gamma}}})=\sum_{({\boldsymbol{\beta}}^{\prime},{\boldsymbol{\gamma}}^{\prime})}g_{{\boldsymbol{\beta}}^{\prime},{\boldsymbol{\gamma}}^{\prime}}y_{{\boldsymbol{\beta}}+{\boldsymbol{\beta}}^{\prime},{\boldsymbol{\gamma}}+{\boldsymbol{\gamma}}^{\prime}},\quad\forall{\boldsymbol{\beta}},{\boldsymbol{\gamma}}\in{\mathbb{N}}^{n}_{r}.$

The sequence ${\mathbf{y}}$ is called a _complex moment sequence_ if it can be
realized by a Borel measure $\mu$, i.e.,
$y_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}=\int_{\mathbf{K}}{\mathbf{x}}^{{\boldsymbol{\beta}}}\overline{{\mathbf{x}}}^{{\boldsymbol{\gamma}}}\,\mathrm{d}\mu$
for any ${\boldsymbol{\beta}},{\boldsymbol{\gamma}}\in{\mathbb{N}}^{n}$, and
${\mathbf{y}}$ is said to be of finite rank if $\mu$ is a finitely atomic
measure.

######  Lemma 2.2 ([5], Theorem 5.1).

If ${\mathbf{y}}$ is a complex moment sequence of finite rank, then
${\mathbf{M}}^{{\mathbb{C}}}({\mathbf{y}})\succeq 0$ and the rank of
${\mathbf{y}}$ is equal to $\hbox{\rm{rank}}\,M^{{\mathbb{C}}}({\mathbf{y}})$.

Let
$d_{0}\coloneqq\max\,\\{|{\boldsymbol{\beta}}|,|{\boldsymbol{\gamma}}|:f_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}\neq
0\\}$,
$d_{i}\coloneqq\max\,\\{|{\boldsymbol{\beta}}|,|{\boldsymbol{\gamma}}|:g^{i}_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}\neq
0\\}$ for $i\in[m]$, where
$f=\sum_{({\boldsymbol{\beta}},{\boldsymbol{\gamma}})}f_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}{\mathbf{x}}^{{\boldsymbol{\beta}}}\overline{{\mathbf{x}}}^{{\boldsymbol{\gamma}}},g_{i}=\sum_{({\boldsymbol{\beta}},{\boldsymbol{\gamma}})}g^{i}_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}{\mathbf{x}}^{{\boldsymbol{\beta}}}\overline{{\mathbf{x}}}^{{\boldsymbol{\gamma}}}$.
Set $d_{\min}\coloneqq\max\,\\{d_{0},d_{1},\ldots,d_{m}\\}$. With $r\geq
d_{\min}$, the complex Lasserre’s hierarchy of moment relaxations for (CPOP)
[5] is given by

(6)
$\tau_{r}\coloneqq\begin{cases}\inf\limits_{{\mathbf{y}}}&L_{{\mathbf{y}}}(f)\\\
\rm{s.t.}&{\mathbf{M}}^{{\mathbb{C}}}_{r}({\mathbf{y}})\succeq 0,\quad
y_{\mathbf{0},\mathbf{0}}=1\\\
&{\mathbf{M}}^{{\mathbb{C}}}_{r-d_{i}}(g_{i}{\mathbf{y}})\succeq 0,\quad
i\in[m].\end{cases}$

Note that (6) is a complex semidefinite program (SDP). To reformulate it as a
real SDP, we refer the reader to [15].

##  3 Multiplication operators and shift operators

In this section, we establish an interesting connection between multiplication
operators and shift operators.

For $p\in{\mathbb{F}}[{\mathbf{x}}]_{r}$ (resp. ${\mathbb{F}}[{\mathbf{x}}]$),
we write ${\mathbf{p}}$ for the coefficient vector of $p$ such that
$p={\mathbf{p}}^{\intercal}[{\mathbf{x}}]_{r}$ (resp.
$p={\mathbf{p}}^{\intercal}[{\mathbf{x}}]$).

######  Lemma 3.1 ([8], Lemma 5.2).

The kernel
$I\coloneqq\\{p\in{\mathbb{R}}[{\mathbf{x}}]\mid{\mathbf{M}}^{{\mathbb{R}}}({\mathbf{y}}){\mathbf{p}}=\mathbf{0}\\}$
of a moment matrix ${\mathbf{M}}^{{\mathbb{R}}}({\mathbf{y}})$ is an ideal in
${\mathbb{R}}[{\mathbf{x}}]$. Moreover, if
${\mathbf{M}}^{{\mathbb{R}}}({\mathbf{y}})\succeq 0$, then $I$ is a real
radical ideal.

######  Lemma 3.2 ([7]).

Let ${\mathbf{y}}$ be a complex moment sequence of finite rank. The kernel
$I\coloneqq\\{p\in{\mathbb{C}}[{\mathbf{x}}]\mid{\mathbf{M}}^{{\mathbb{C}}}({\mathbf{y}}){\mathbf{p}}=\mathbf{0}\\}$
of the moment matrix ${\mathbf{M}}^{{\mathbb{C}}}({\mathbf{y}})$ is a radical
ideal in ${\mathbb{C}}[{\mathbf{x}}]$.

Suppose that ${\mathbf{y}}$ is a (real or complex) moment sequence of rank
$t$. Let
$I\coloneqq\\{p\in{\mathbb{F}}[{\mathbf{x}}]\mid{\mathbf{M}}^{{\mathbb{F}}}({\mathbf{y}}){\mathbf{p}}=\mathbf{0}\\}$.
Then ${\mathbb{F}}[{\mathbf{x}}]/I$ is a linear space over ${\mathbb{F}}$ of
dimension $t$. The multiplication operators $M_{i},i\in[n]$ acting on
${\mathbb{F}}[{\mathbf{x}}]/I$ are defined by

(7) $\displaystyle M_{i}:{\mathbb{F}}[{\mathbf{x}}]/I$
$\displaystyle\longrightarrow{\mathbb{F}}[{\mathbf{x}}]/I,$ $\displaystyle
p\quad$ $\displaystyle\longmapsto\quad x_{i}p.$

Since the moment matrix ${\mathbf{M}}^{{\mathbb{F}}}({\mathbf{y}})$ is PSD
with $\hbox{\rm{rank}}\,{\mathbf{M}}^{{\mathbb{F}}}({\mathbf{y}})=t$, it can
be factorized in the Grammian form such that

(8)
$[{\mathbf{M}}^{{\mathbb{F}}}({\mathbf{y}})]_{{\boldsymbol{\beta}}{\boldsymbol{\gamma}}}={\mathbf{a}}_{{\boldsymbol{\beta}}}^{*}{\mathbf{a}}_{{\boldsymbol{\gamma}}},\quad\forall{\boldsymbol{\beta}},{\boldsymbol{\gamma}}\in{\mathbb{N}}^{n},$

where
$\\{{\mathbf{a}}_{{\boldsymbol{\alpha}}}\\}_{{\boldsymbol{\alpha}}\in{\mathbb{N}}^{n}}\subseteq{\mathbb{F}}^{t}$.
The shift operators $T_{1},\ldots,T_{n}:{\mathbb{F}}^{t}\to{\mathbb{F}}^{t}$
are defined by

(9)
$T_{i}:\sum_{{\boldsymbol{\alpha}}}p_{{\boldsymbol{\alpha}}}{\mathbf{a}}_{{\boldsymbol{\alpha}}}\longmapsto\sum_{{\boldsymbol{\alpha}}}p_{{\boldsymbol{\alpha}}}{\mathbf{a}}_{{\boldsymbol{\alpha}}+{\mathbf{e}}_{i}},$

where $\\{{\mathbf{e}}_{1},\ldots,{\mathbf{e}}_{n}\\}$ is the standard vector
basis of ${\mathbb{N}}^{n}$.

Let us define the following linear map

(10) $\theta:{\mathbb{F}}[{\mathbf{x}}]\longrightarrow{\mathbb{F}}^{t},\quad
p=\sum_{{\boldsymbol{\alpha}}}p_{{\boldsymbol{\alpha}}}{\mathbf{x}}^{{\boldsymbol{\alpha}}}\longmapsto\sum_{{\boldsymbol{\alpha}}}p_{{\boldsymbol{\alpha}}}{\mathbf{a}}_{{\boldsymbol{\alpha}}}.$

######  Lemma 3.3.

The linear map $\theta$ induces an isomorphism:
${\mathbb{F}}[{\mathbf{x}}]/I\cong{\mathbb{F}}^{t}$.

######  Proof 3.4.

It is clear that $\theta$ is surjective. We remain to show that the kernel of
$\theta$ is $I$. First, let
$p=\sum_{{\boldsymbol{\beta}}}p_{{\boldsymbol{\beta}}}{\mathbf{x}}^{{\boldsymbol{\beta}}}\in
I$. It follows from

(11)
${\mathbf{M}}^{{\mathbb{F}}}({\mathbf{y}}){\mathbf{p}}=\left(\sum_{{\boldsymbol{\beta}}}{\mathbf{a}}_{{\boldsymbol{\alpha}}}^{*}{\mathbf{a}}_{{\boldsymbol{\beta}}}p_{{\boldsymbol{\beta}}}\right)_{{\boldsymbol{\alpha}}\in{\mathbb{N}}^{n}}=\mathbf{0}$

that
${\mathbf{a}}_{{\boldsymbol{\alpha}}}^{*}(\sum_{{\boldsymbol{\beta}}}p_{{\boldsymbol{\beta}}}{\mathbf{a}}_{{\boldsymbol{\beta}}})=0$
for all ${\mathbf{a}}_{{\boldsymbol{\alpha}}}$. Since
$\\{{\mathbf{a}}_{{\boldsymbol{\alpha}}}\\}_{{\boldsymbol{\alpha}}\in{\mathbb{N}}^{n}}$
spans ${\mathbb{F}}^{t}$, we obtain
$\sum_{{\boldsymbol{\beta}}}p_{{\boldsymbol{\beta}}}{\mathbf{a}}_{{\boldsymbol{\beta}}}=\mathbf{0}$.
This proves $p\in\ker(\theta)$ and hence $I\subseteq\ker(\theta)$. Conversely,
let $p\in{\mathbb{F}}[{\mathbf{x}}]$ such that
$\sum_{{\boldsymbol{\beta}}}p_{{\boldsymbol{\beta}}}{\mathbf{a}}_{{\boldsymbol{\beta}}}=\mathbf{0}$.
Then we see $p\in I$. This proves $\ker(\theta)\subseteq I$.

######  Theorem 3.5.

Let ${\mathbf{y}}$ be a moment sequence of finite rank. Then the
multiplication operator $M_{i}$ is similar to the shift operator $T_{i}$ for
$i\in[n]$. More concretely, we have $T_{i}=\theta\circ M_{i}\circ\theta^{-1}$
for $i\in[n]$.

######  Proof 3.6.

Let
$p=\sum_{{\boldsymbol{\alpha}}}p_{{\boldsymbol{\alpha}}}{\mathbf{x}}^{{\boldsymbol{\alpha}}}\in{\mathbb{F}}[{\mathbf{x}}]$.
We have

(12)
$T_{i}(\theta(p))=T_{i}\left(\sum_{{\boldsymbol{\alpha}}}p_{{\boldsymbol{\alpha}}}{\mathbf{a}}_{{\boldsymbol{\alpha}}}\right)=\sum_{{\boldsymbol{\alpha}}}p_{{\boldsymbol{\alpha}}}{\mathbf{a}}_{{\boldsymbol{\alpha}}+{\mathbf{e}}_{i}}.$

On the other hand, we have

(13)
$\theta(M_{i}(p))=\theta(x_{i}p)=\theta\left(\sum_{{\boldsymbol{\alpha}}}p_{{\boldsymbol{\alpha}}}{\mathbf{x}}^{{\boldsymbol{\alpha}}+{\mathbf{e}}_{i}}\right)=\sum_{{\boldsymbol{\alpha}}}p_{{\boldsymbol{\alpha}}}{\mathbf{a}}_{{\boldsymbol{\alpha}}+{\mathbf{e}}_{i}}.$

Thus, $T_{i}(\theta(p))=\theta(M_{i}(p))$. It follows
$T_{i}\circ\theta=\theta\circ M_{i}$. As $\theta$ is invertible by Lemma 3.3,
we obtain $T_{i}=\theta\circ M_{i}\circ\theta^{-1}$.

######  Corollary 3.7.

Let ${\mathbf{y}}$ be a moment sequence of finite rank. Then the shift
operators $T_{1},\ldots,T_{n}$ are well-defined.

######  Proof 3.8.

We need to show that
$T_{i}(\sum_{{\boldsymbol{\alpha}}}p_{{\boldsymbol{\alpha}}}{\mathbf{a}}_{{\boldsymbol{\alpha}}})=\mathbf{0}$
if
$\sum_{{\boldsymbol{\alpha}}}p_{{\boldsymbol{\alpha}}}{\mathbf{a}}_{{\boldsymbol{\alpha}}}=\mathbf{0}$.
The assumption
$\sum_{{\boldsymbol{\alpha}}}p_{{\boldsymbol{\alpha}}}{\mathbf{a}}_{{\boldsymbol{\alpha}}}=\mathbf{0}$
implies
$\theta(\sum_{{\boldsymbol{\alpha}}}p_{{\boldsymbol{\alpha}}}{\mathbf{x}}^{{\boldsymbol{\alpha}}})=\mathbf{0}$
and so
$\sum_{{\boldsymbol{\alpha}}}p_{{\boldsymbol{\alpha}}}{\mathbf{x}}^{{\boldsymbol{\alpha}}}\in
I$. By Theorem 3.5, we have

$\displaystyle
T_{i}\left(\sum_{{\boldsymbol{\alpha}}}p_{{\boldsymbol{\alpha}}}{\mathbf{a}}_{{\boldsymbol{\alpha}}}\right)$
$\displaystyle=\theta\circ
M_{i}\circ\theta^{-1}\left(\sum_{{\boldsymbol{\alpha}}}p_{{\boldsymbol{\alpha}}}{\mathbf{a}}_{{\boldsymbol{\alpha}}}\right)$
$\displaystyle=\theta\circ
M_{i}\left(\sum_{{\boldsymbol{\alpha}}}p_{{\boldsymbol{\alpha}}}{\mathbf{x}}^{{\boldsymbol{\alpha}}}\right)$
$\displaystyle=\theta\left(\sum_{{\boldsymbol{\alpha}}}p_{{\boldsymbol{\alpha}}}{\mathbf{x}}^{{\boldsymbol{\alpha}}+{\mathbf{e}}_{i}}\right)$
$\displaystyle=\theta\left(x_{i}\sum_{{\boldsymbol{\alpha}}}p_{{\boldsymbol{\alpha}}}{\mathbf{x}}^{{\boldsymbol{\alpha}}}\right)=\mathbf{0},$

where the last equality follows from the fact that $I$ is an ideal and so
$x_{i}\sum_{{\boldsymbol{\alpha}}}p_{{\boldsymbol{\alpha}}}{\mathbf{x}}^{{\boldsymbol{\alpha}}}\in
I$.

For the remainder of the paper, we assume a basis of ${\mathbb{R}}^{t}$ is
given and identify the shift operators with their representing matrices for
convenience.

The real shift operators have the distinguished property of being symmetric.

######  Lemma 3.9.

Let ${\mathbf{y}}$ be a real moment sequence of finite rank. The shift
operators $T_{i},i\in[n]$ are symmetric.

######  Proof 3.10.

Suppose that $\hbox{\rm{rank}}\,{\mathbf{M}}^{{\mathbb{R}}}({\mathbf{y}})=t$
and
$[{\mathbf{M}}^{{\mathbb{R}}}({\mathbf{y}})]_{{\boldsymbol{\beta}}{\boldsymbol{\gamma}}}={\mathbf{a}}_{{\boldsymbol{\beta}}}^{\intercal}{\mathbf{a}}_{{\boldsymbol{\gamma}}}$
for ${\boldsymbol{\beta}},{\boldsymbol{\gamma}}\in{\mathbb{N}}^{n}$, where
$\\{{\mathbf{a}}_{{\boldsymbol{\alpha}}}\\}_{{\boldsymbol{\alpha}}\in{\mathbb{N}}^{n}}\subseteq{\mathbb{R}}^{t}$.
Let ${\mathbf{u}}\in{\mathbb{R}}^{t}$ be arbitrary and we may write

${\mathbf{u}}=\sum_{{\boldsymbol{\alpha}}}u_{{\boldsymbol{\alpha}}}{\mathbf{a}}_{{\boldsymbol{\alpha}}},\quad\mathop{{\mathbf{u}}}\limits^{\rightarrow}\coloneqq(u_{{\boldsymbol{\alpha}}})_{{\boldsymbol{\alpha}}}.$

From

$\displaystyle{\mathbf{u}}^{\intercal}T_{i}{\mathbf{u}}$
$\displaystyle=\sum_{{\boldsymbol{\alpha}},{\boldsymbol{\beta}}}u_{{\boldsymbol{\alpha}}}u_{{\boldsymbol{\beta}}}{\mathbf{a}}_{{\boldsymbol{\alpha}}}^{\intercal}(T_{i}{\mathbf{a}}_{{\boldsymbol{\beta}}})=\sum_{{\boldsymbol{\alpha}},{\boldsymbol{\beta}}}u_{{\boldsymbol{\alpha}}}u_{{\boldsymbol{\beta}}}{\mathbf{a}}_{{\boldsymbol{\alpha}}}^{\intercal}{\mathbf{a}}_{{\boldsymbol{\beta}}+{\mathbf{e}}_{i}}={\mathop{{\mathbf{u}}}\limits^{\rightarrow}}^{\intercal}{\mathbf{M}}^{{\mathbb{R}}}(x_{i}{\mathbf{y}})\mathop{{\mathbf{u}}}\limits^{\rightarrow},$
$\displaystyle{\mathbf{u}}^{\intercal}T_{i}^{\intercal}{\mathbf{u}}$
$\displaystyle=\sum_{{\boldsymbol{\alpha}},{\boldsymbol{\beta}}}u_{{\boldsymbol{\alpha}}}u_{{\boldsymbol{\beta}}}(T_{i}{\mathbf{a}}_{{\boldsymbol{\alpha}}})^{\intercal}{\mathbf{a}}_{{\boldsymbol{\beta}}}=\sum_{{\boldsymbol{\alpha}},{\boldsymbol{\beta}}}u_{{\boldsymbol{\alpha}}}u_{{\boldsymbol{\beta}}}{\mathbf{a}}_{{\boldsymbol{\alpha}}+{\mathbf{e}}_{i}}^{\intercal}{\mathbf{a}}_{{\boldsymbol{\beta}}}={\mathop{{\mathbf{u}}}\limits^{\rightarrow}}^{\intercal}{\mathbf{M}}^{{\mathbb{R}}}(x_{i}{\mathbf{y}})\mathop{{\mathbf{u}}}\limits^{\rightarrow},$

we obtain ${\mathbf{u}}^{\intercal}(T_{i}-T_{i}^{\intercal}){\mathbf{u}}=0$.
Thus, $T_{i}=T_{i}^{\intercal}$.

##  4 Strengthening Lasserre’s hierarchy

The study of shift operators enables us to give the following PSD optimality
conditions for the pseudo-moment sequence ${\mathbf{y}}$.

######  Theorem 4.1.

  1. (i)

Suppose that ${\mathbf{M}}^{{\mathbb{R}}}_{r}({\mathbf{y}})\succeq 0$ for some
$r\in{\mathbb{N}}$. Then for any $s\in{\mathbb{N}}$ with $s<r$,

(14)
$\begin{bmatrix}{\mathbf{M}}^{{\mathbb{R}}}_{s}({\mathbf{y}})&{\mathbf{M}}^{{\mathbb{R}}}_{s}(x_{i}{\mathbf{y}})\\\
{\mathbf{M}}^{{\mathbb{R}}}_{s}(x_{i}{\mathbf{y}})&{\mathbf{M}}^{{\mathbb{R}}}_{s}(x_{i}^{2}{\mathbf{y}})\\\
\end{bmatrix}\succeq 0,\quad i\in[n].$

  2. (ii)

Suppose that ${\mathbf{y}}$ is a complex moment sequence admitting a Dirac
representing measure. Then for any $s\in{\mathbb{N}}$,

(15)
$\begin{bmatrix}{\mathbf{M}}^{{\mathbb{C}}}_{s}({\mathbf{y}})&{\mathbf{M}}^{{\mathbb{C}}}_{s}(x_{i}{\mathbf{y}})\\\
{\mathbf{M}}^{{\mathbb{C}}}_{s}(\overline{x}_{i}{\mathbf{y}})&{\mathbf{M}}^{{\mathbb{C}}}_{s}(|x_{i}|^{2}{\mathbf{y}})\\\
\end{bmatrix}\succeq 0,\quad i\in[n].$

######  Proof 4.2.

(i). Assume that
$\hbox{\rm{rank}}\,{\mathbf{M}}_{r}^{{\mathbb{R}}}({\mathbf{y}})=t$ and
$[{\mathbf{M}}_{r}^{{\mathbb{R}}}({\mathbf{y}})]_{{\boldsymbol{\beta}}{\boldsymbol{\gamma}}}={\mathbf{a}}_{{\boldsymbol{\beta}}}^{\intercal}{\mathbf{a}}_{{\boldsymbol{\gamma}}}$
for $|{\boldsymbol{\beta}}|,|{\boldsymbol{\gamma}}|\leq r$, where
$\\{{\mathbf{a}}_{{\boldsymbol{\alpha}}}\\}_{|{\boldsymbol{\alpha}}|\leq
r}\subseteq{\mathbb{R}}^{t}$. Let

(16)
$A\coloneqq\left[\\{{\mathbf{a}}_{{\boldsymbol{\alpha}}}\\}_{|{\boldsymbol{\alpha}}|\leq
s},\\{{\mathbf{a}}_{{\boldsymbol{\alpha}}+{\mathbf{e}}_{i}}\\}_{|{\boldsymbol{\alpha}}|\leq
s}\right]\in{\mathbb{R}}^{t\times 2|{\mathbb{N}}_{s}^{n}|}.$

Then one can easily see that

$\begin{bmatrix}{\mathbf{M}}^{{\mathbb{R}}}_{s}({\mathbf{y}})&{\mathbf{M}}^{{\mathbb{R}}}_{s}(x_{i}{\mathbf{y}})\\\
{\mathbf{M}}^{{\mathbb{R}}}_{s}(x_{i}{\mathbf{y}})&{\mathbf{M}}^{{\mathbb{R}}}_{s}(x_{i}^{2}{\mathbf{y}})\\\
\end{bmatrix}=A^{\intercal}A\succeq 0,\quad\forall i\in[n].$

(ii). Since ${\mathbf{y}}$ has a Dirac representing measure, the moment matrix
${\mathbf{M}}^{{\mathbb{C}}}_{s}({\mathbf{y}})$ has rank one and the shift
operators $T_{i},i\in[n]$ are complex numbers. It follows that

(17) $\begin{bmatrix}1&\overline{T}_{i}\\\
T_{i}&\overline{T}_{i}T_{i}\end{bmatrix}\succeq 0,\quad i\in[n].$

Assume that
${\mathbf{M}}^{{\mathbb{C}}}({\mathbf{y}})={\mathbf{a}}^{*}{\mathbf{a}}$,
where
${\mathbf{a}}=(a_{{\boldsymbol{\alpha}}})_{{\boldsymbol{\alpha}}\in{\mathbb{N}}^{n}}\in{\mathbb{C}}^{{\mathbb{N}}^{n}}$.
For any ${\mathbf{u}}=(u_{{\boldsymbol{\alpha}}})_{|{\boldsymbol{\alpha}}|\leq
s},{\boldsymbol{v}}=(v_{{\boldsymbol{\beta}}})_{|{\boldsymbol{\beta}}|\leq
s}\in{\mathbb{C}}^{|{\mathbb{N}}^{n}_{s}|}$, let
$u=\sum_{|{\boldsymbol{\alpha}}|\leq
s}u_{{\boldsymbol{\alpha}}}a_{{\boldsymbol{\alpha}}},v=\sum_{|{\boldsymbol{\beta}}|\leq
s}v_{{\boldsymbol{\beta}}}a_{{\boldsymbol{\beta}}}$. We have

$\displaystyle\overline{u}u$
$\displaystyle=\sum_{{\boldsymbol{\alpha}},{\boldsymbol{\beta}}}\overline{u}_{{\boldsymbol{\alpha}}}u_{{\boldsymbol{\beta}}}\overline{a}_{{\boldsymbol{\alpha}}}a_{{\boldsymbol{\beta}}}={\mathbf{u}}^{*}{\mathbf{M}}^{{\mathbb{C}}}_{s}({\mathbf{y}}){\mathbf{u}},$
$\displaystyle\overline{u}\overline{T}_{i}v$
$\displaystyle=\sum_{{\boldsymbol{\alpha}},{\boldsymbol{\beta}}}\overline{u}_{{\boldsymbol{\alpha}}}v_{{\boldsymbol{\beta}}}\overline{T_{i}a_{{\boldsymbol{\alpha}}}}a_{{\boldsymbol{\beta}}}=\sum_{{\boldsymbol{\alpha}},{\boldsymbol{\beta}}}\overline{u}_{{\boldsymbol{\alpha}}}v_{{\boldsymbol{\beta}}}\overline{a}_{{\boldsymbol{\alpha}}+{\mathbf{e}}_{i}}a_{{\boldsymbol{\beta}}}={\mathbf{u}}^{*}{\mathbf{M}}^{{\mathbb{C}}}_{s}(x_{i}{\mathbf{y}}){\boldsymbol{v}},$
$\displaystyle\overline{v}T_{i}u$
$\displaystyle=\sum_{{\boldsymbol{\alpha}},{\boldsymbol{\beta}}}\overline{v}_{{\boldsymbol{\alpha}}}u_{{\boldsymbol{\beta}}}\overline{a}_{{\boldsymbol{\alpha}}}(T_{i}a_{{\boldsymbol{\beta}}})=\sum_{{\boldsymbol{\alpha}},{\boldsymbol{\beta}}}\overline{v}_{{\boldsymbol{\alpha}}}u_{{\boldsymbol{\beta}}}\overline{a}_{{\boldsymbol{\alpha}}}a_{{\boldsymbol{\beta}}+{\mathbf{e}}_{i}}={\boldsymbol{v}}^{*}{\mathbf{M}}^{{\mathbb{C}}}_{s}(\overline{x}_{i}{\mathbf{y}}){\mathbf{u}},$

and

$\overline{v}\overline{T}_{i}T_{i}v=\sum_{{\boldsymbol{\alpha}},{\boldsymbol{\beta}}}\overline{v}_{{\boldsymbol{\alpha}}}v_{{\boldsymbol{\beta}}}\overline{T_{i}a_{{\boldsymbol{\alpha}}}}(T_{i}a_{{\boldsymbol{\beta}}})=\sum_{{\boldsymbol{\alpha}},{\boldsymbol{\beta}}}\overline{v}_{{\boldsymbol{\alpha}}}v_{{\boldsymbol{\beta}}}\overline{a}_{{\boldsymbol{\alpha}}+{\mathbf{e}}_{i}}a_{{\boldsymbol{\beta}}+{\mathbf{e}}_{i}}={\boldsymbol{v}}^{*}{\mathbf{M}}^{{\mathbb{C}}}_{s}(|x_{i}|^{2}{\mathbf{y}}){\boldsymbol{v}},$

which gives

(18)
$\begin{bmatrix}\overline{u}&\overline{v}\end{bmatrix}\begin{bmatrix}I&\overline{T}_{i}\\\
T_{i}&\overline{T}_{i}T_{i}\end{bmatrix}\begin{bmatrix}{\mathbf{u}}\\\
{\boldsymbol{v}}\end{bmatrix}=\begin{bmatrix}{\mathbf{u}}^{*}&{\boldsymbol{v}}^{*}\end{bmatrix}\begin{bmatrix}{\mathbf{M}}^{{\mathbb{C}}}_{s}({\mathbf{y}})&{\mathbf{M}}^{{\mathbb{C}}}_{s}(x_{i}{\mathbf{y}})\\\
{\mathbf{M}}^{{\mathbb{C}}}_{s}(\overline{x}_{i}{\mathbf{y}})&{\mathbf{M}}^{{\mathbb{C}}}_{s}(|x_{i}|^{2}{\mathbf{y}})\\\
\end{bmatrix}\begin{bmatrix}{\mathbf{u}}\\\ {\boldsymbol{v}}\end{bmatrix}.$

From this and (17), we obtain (15) as desired.

We say that an operator $T$ is _normal_ if $T^{*}T=TT^{*}$. In case that $T$
is of finite dimension, it is not hard to see that the normality of $T$ is
equivalent to the PSD condition $T^{*}T-TT^{*}\succeq 0$, which is further
equivalent to

(19) $\begin{bmatrix}I&T^{*}\\\ T&T^{*}T\end{bmatrix}\succeq 0.$

Suppose that ${\mathbf{y}}$ is a complex moment sequence such that
$\hbox{\rm{rank}}\,{\mathbf{M}}^{{\mathbb{C}}}({\mathbf{y}})=\hbox{\rm{rank}}\,{\mathbf{M}}^{{\mathbb{C}}}_{s}({\mathbf{y}})$.
In a similar manner as the proof of Theorem 4.1 (ii), we can show that the
shift operators $T_{i},i\in[n]$ are normal if and only if the PSD conditions
(15) hold. It would be interesting to ask: if ${\mathbf{y}}$ is a complex
moment sequence of finite rank, do we have that the shift operators
$T_{i},i\in[n]$ are normal? We will explore this question in the future work.

Using the PSD optimality conditions in Theorem 4.1, we can strengthen
Lasserre’s hierarchy of moment relaxations. In particular, for real polynomial
optimization, we consider

(20)
$\rho^{\prime}_{r}\coloneqq\begin{cases}\inf\limits_{{\mathbf{y}}}&L_{{\mathbf{y}}}(f)\\\
\rm{s.t.}&y_{\mathbf{0}}=1,\\\
&{\mathbf{M}}^{{\mathbb{R}}}_{r-d_{i}}(g_{i}{\mathbf{y}})\succeq 0,\quad
i\in[m],\\\
&\begin{bmatrix}{\mathbf{M}}^{{\mathbb{R}}}_{r}({\mathbf{y}})&{\mathbf{M}}^{{\mathbb{R}}}_{r}(x_{i}{\mathbf{y}})\\\
{\mathbf{M}}^{{\mathbb{R}}}_{r}(x_{i}{\mathbf{y}})&{\mathbf{M}}^{{\mathbb{R}}}_{r}(x_{i}^{2}{\mathbf{y}})\\\
\end{bmatrix}\succeq 0,\quad i\in[n].\end{cases}$

######  Theorem 4.3.

It holds $\rho_{r}\leq\rho^{\prime}_{r}\leq\rho_{r+1}\leq f_{\min}$ for any
$r\geq d_{\min}$.

######  Proof 4.4.

Since (20) is a strengthening of (3), it follows
$\rho_{r}\leq\rho^{\prime}_{r}$. The inequality
$\rho^{\prime}_{r}\leq\rho_{r+1}$ follows from the fact that the second PSD
constraints of (20) are implied by
${\mathbf{M}}^{{\mathbb{R}}}_{r+1}({\mathbf{y}})\succeq 0$ due to Theorem 4.1
(i).

By Theorem 4.3, (20) provides an intermediate relaxation between the $r$-th
and $r+1$-th moment relaxations for (RPOP).

For complex polynomial optimization, we consider

(21)
$\tau^{\prime}_{r,s}\coloneqq\begin{cases}\inf\limits_{{\mathbf{y}}}&L_{{\mathbf{y}}}(f)\\\
\rm{s.t.}&{\mathbf{M}}^{{\mathbb{C}}}_{r}({\mathbf{y}})\succeq 0,\quad
y_{\mathbf{0},\mathbf{0}}=1,\\\
&{\mathbf{M}}^{{\mathbb{C}}}_{r-d_{i}}(g_{i}{\mathbf{y}})\succeq 0,\quad
i\in[m],\\\
&\begin{bmatrix}{\mathbf{M}}^{{\mathbb{C}}}_{s}({\mathbf{y}})&{\mathbf{M}}^{{\mathbb{C}}}_{s}(x_{i}{\mathbf{y}})\\\
{\mathbf{M}}^{{\mathbb{C}}}_{s}(\overline{x}_{i}{\mathbf{y}})&{\mathbf{M}}^{{\mathbb{C}}}_{s}(|x_{i}|^{2}{\mathbf{y}})\\\
\end{bmatrix}\succeq 0,\quad i\in[n].\end{cases}$

Here $s\in{\mathbb{N}}$ is a tunable parameter which we call the _normal
order_.

######  Theorem 4.5.

It hold $\tau_{r}\leq\tau^{\prime}_{r,s}\leq\tau^{\prime}_{r,s+1}\leq
f_{\min}$ and $\tau^{\prime}_{r,s}\leq\tau^{\prime}_{r+1,s}$ for any $r\geq
d_{\min}$ and any $s\in{\mathbb{N}}$.

######  Proof 4.6.

Since (21) is a strengthening of (6), it follows
$\tau_{r}\leq\tau^{\prime}_{r}$. If the infimum of (CPOP) is attained, let
${\mathbf{w}}$ be a minimizer of (CPOP) and ${\mathbf{y}}$ be the moment
sequence of the Dirac measure $\delta_{{\mathbf{w}}}$. By Theorem 4.1 (ii),
${\mathbf{y}}$ is a feasible solution of (21) and
$L_{{\mathbf{y}}}(f)=f_{\min}$. Thus, $\tau^{\prime}_{r}\leq f_{\min}$. If the
infimum of (CPOP) is not attained, let $\\{{\mathbf{w}}^{(k)}\\}_{k\geq 1}$ be
a minimizing sequence of (CPOP) and ${\mathbf{y}}^{(k)}$ be the moment
sequence of the Dirac measure $\delta_{{\mathbf{w}}^{(k)}}$, respectively. We
have that every ${\mathbf{y}}^{(k)}$ is a feasible solution of (21) and
$\lim_{k\rightarrow\infty}L_{{\mathbf{y}}^{(k)}}(f)=f_{\min}$. Thus,
$\tau^{\prime}_{r}\leq f_{\min}$. The inequalities
$\tau^{\prime}_{r,s}\leq\tau^{\prime}_{r,s+1}$ and
$\tau^{\prime}_{r,s}\leq\tau^{\prime}_{r+1,s}$ are easily obtained from the
constructions.

By Theorem 4.5, (21) is a two-level hierarchy indexed by the relaxation order
$r$ and the normal order $s$, and hence allows one more level of flexibility
by playing with the two parameters.

##  5 Integration with sparsity

The strengthening technique discussed in Section 4 can be integrated into
different sparse versions of Lasserre’s hierarchy to improve scalability. We
refer the reader to [9] for relevant details on different sparse versions of
Lasserre’s hierarchy.

###  5.1 Correlative sparsity

Consider (RPOP) (resp. (CPOP)). Suppose that the two index sets $[n]$ and
$[m]$ can be decomposed into $\\{I_{1},\dots,I_{p}\\}$ and
$\\{J_{1},\dots,J_{p}\\}$, respectively, such that 1) $f=f_{1}+\cdots+f_{p}$
with $f_{k}\in{\mathbb{R}}[{\mathbf{x}}_{I_{k}}]$ (resp.
${\mathbb{C}}[{\mathbf{x}}_{I_{k}},\overline{{\mathbf{x}}}_{I_{k}}]$) for
$k\in[p]$; 2) for all $k\in[p]$ and $i\in J_{k}$,
$g_{i}\in{\mathbb{R}}[{\mathbf{x}}_{I_{k}}]$ (resp.
${\mathbb{C}}[{\mathbf{x}}_{I_{k}},\overline{{\mathbf{x}}}_{I_{k}}]$), where
${\mathbb{R}}[{\mathbf{x}}_{I_{k}}]$ (resp.
${\mathbb{C}}[{\mathbf{x}}_{I_{k}},\overline{{\mathbf{x}}}_{I_{k}}]$) denotes
the polynomial ring in those variables indexed by $I_{k}$. Let
${\mathbf{M}}^{{\mathbb{R}}}_{r}({\mathbf{y}},I_{k})$ (resp.
${\mathbf{M}}^{{\mathbb{R}}}_{r}(g{\mathbf{y}},I_{k})$) be the submatrix
obtained from ${\mathbf{M}}^{{\mathbb{R}}}_{r}({\mathbf{y}})$ (resp.
${\mathbf{M}}^{{\mathbb{R}}}_{r}(g{\mathbf{y}})$) by retaining only those rows
and columns indexed by ${\boldsymbol{\beta}}\in{\mathbb{N}}_{r}^{n}$ of
${\mathbf{M}}^{{\mathbb{R}}}_{r}({\mathbf{y}})$ (resp.
${\mathbf{M}}^{{\mathbb{R}}}_{r}(g{\mathbf{y}})$) with $\beta_{i}=0$ if
$i\notin I_{k}$. Then, we can strengthen the correlative sparse Lasserre’s
hierarchy of moment relaxations for real polynomial optimization by
considering

(22) $\begin{cases}\inf\limits_{{\mathbf{y}}}&L_{{\mathbf{y}}}(f)\\\
\rm{s.t.}&{\mathbf{M}}^{{\mathbb{R}}}_{r}({\mathbf{y}},I_{k})\succeq 0,\quad
k\in[p],\\\
&{\mathbf{M}}^{{\mathbb{R}}}_{r-d_{i}}(g_{i}{\mathbf{y}},I_{k})\succeq 0,\quad
i\in J_{k},k\in[p],\\\
&\begin{bmatrix}{\mathbf{M}}^{{\mathbb{R}}}_{1}({\mathbf{y}})&{\mathbf{M}}^{{\mathbb{R}}}_{1}(x_{i}{\mathbf{y}})\\\
{\mathbf{M}}^{{\mathbb{R}}}_{1}(x_{i}{\mathbf{y}})&{\mathbf{M}}^{{\mathbb{R}}}_{1}(x_{i}^{2}{\mathbf{y}})\\\
\end{bmatrix}\succeq 0,\quad i\in[n],\\\ &y_{\mathbf{0}}=1.\end{cases}$

Also, we can strengthen the correlative sparse Lasserre’s hierarchy of moment
relaxations for complex polynomial optimization by considering

(23) $\begin{cases}\inf\limits_{{\mathbf{y}}}&L_{{\mathbf{y}}}(f)\\\
\rm{s.t.}&{\mathbf{M}}^{{\mathbb{C}}}_{r}({\mathbf{y}},I_{k})\succeq 0,\quad
k\in[p],\\\
&{\mathbf{M}}^{{\mathbb{C}}}_{r-d_{i}}(g_{i}{\mathbf{y}},I_{k})\succeq 0,\quad
i\in J_{k},k\in[p],\\\
&\begin{bmatrix}{\mathbf{M}}^{{\mathbb{C}}}_{s}({\mathbf{y}},I_{k})&{\mathbf{M}}^{{\mathbb{C}}}_{s}(x_{i}{\mathbf{y}},I_{k})\\\
{\mathbf{M}}^{{\mathbb{C}}}_{s}(\overline{x}_{i}{\mathbf{y}},I_{k})&{\mathbf{M}}^{{\mathbb{C}}}_{s}(|x_{i}|^{2}{\mathbf{y}},I_{k})\\\
\end{bmatrix}\succeq 0,\quad i\in I_{k},k\in[p],\\\
&y_{\mathbf{0},\mathbf{0}}=1.\end{cases}$

###  5.2 Sign symmetry

For $p\in{\mathbb{R}}[{\mathbf{x}}]$ and a binary vector
$\mathbf{s}\in\\{0,1\\}^{n}$, let
$[p]_{\mathbf{s}}\in{\mathbb{R}}[{\mathbf{x}}]$ be defined by
$[p]_{\mathbf{s}}(x_{1},\ldots,x_{n})\coloneqq
p((-1)^{s_{1}}x_{1},\ldots,(-1)^{s_{n}}x_{n})$. Then $p$ is said to have the
sign symmetry represented by $\mathbf{s}\in\\{0,1\\}^{n}$ if
$[p]_{\mathbf{s}}=p$. We use $S(p)\subseteq\\{0,1\\}^{n}$ to denote all sign
symmetries of $p$. Consider (RPOP) and let $U\coloneqq
S(f)\cap\bigcap_{i=1}^{m}S(g_{i})$. We define an equivalence relation $\sim$
on $[x]$ by

(24)
${\mathbf{x}}^{{\boldsymbol{\alpha}}}\sim{\mathbf{x}}^{{\boldsymbol{\beta}}}\iff
U\subseteq S({\mathbf{x}}^{{\boldsymbol{\alpha}}+{\boldsymbol{\beta}}}).$

For each $i\in[m]$, the equivalence relation $\sim$ gives rise to a partition
of $[{\mathbf{x}}]_{r-d_{i}}$:

(25)
$[{\mathbf{x}}]_{r-d_{i}}=\bigsqcup_{k=1}^{p_{i}}[{\mathbf{x}}]_{r-d_{i},k}.$

We then build the submatrix
${\mathbf{M}}^{{\mathbb{R}}}_{r-d_{i},k}(g_{i}{\mathbf{y}})$ of
${\mathbf{M}}^{{\mathbb{R}}}_{r-d_{i}}(g_{i}{\mathbf{y}})$ with respect to the
sign symmetry by retaining only those rows and columns indexed by
$[{\mathbf{x}}]_{r-d_{i},k}$ for each $k\in[p_{i}]$. Moreover, for each
$i\in[n]$, the equivalence relation $\sim$ gives rise to a partition of
$[{\mathbf{x}}]_{r}\cup x_{i}[{\mathbf{x}}]_{r}$: $[{\mathbf{x}}]_{r}\cup
x_{i}[{\mathbf{x}}]_{r}=\bigsqcup_{k=1}^{q_{i}}[{\mathbf{x}}]_{r,i,k}$. We
build the submatrix ${\mathbf{N}}^{{\mathbb{R}}}_{r,i,k}({\mathbf{y}})$ of the
second PSD matrix in (20) by retaining only those rows and columns indexed by
$[{\mathbf{x}}]_{r,i,k}$ for each $k\in[q_{i}]$. Then, we can strengthen the
sign-symmetry Lasserre’s hierarchy of moment relaxations for real polynomial
optimization by considering

(26) $\begin{cases}\inf\limits_{{\mathbf{y}}}&L_{{\mathbf{y}}}(f)\\\
\rm{s.t.}&{\mathbf{M}}^{{\mathbb{R}}}_{r-d_{i},k}(g_{i}{\mathbf{y}})\succeq
0,\quad k\in[p_{i}],\\\
&{\mathbf{N}}^{{\mathbb{R}}}_{r,i,k}({\mathbf{y}})\succeq 0,\quad
k\in[q_{i}],i\in[n],\\\ &y_{\mathbf{0}}=1.\end{cases}$

The complex case proceeds in a similar way, which we omit for conciseness.

##  6 Numerical experiments

The strengthened real and complex Lasserre’s hierarchies have been implemented
in the Julia package TSSOS111TSSOS is freely available at
https://github.com/wangjie212/TSSOS.. In this section, we evaluate their
performance on diverse polynomial optimization problems using TSSOS and Mosek
10.0 [1] is employed as an SDP solver with default settings. When presenting
the results, ‘LAS’ means the usual Lasserre’s hierarchy and ‘S-LAS’ means the
strengthened Lasserre’s hierarchy; the column labelled by ‘opt’ records optima
of SDPs and the column labelled by ‘time’ records running time in seconds.
Moreover, the symbol ‘-’ means that Mosek runs out of memory. All numerical
experiments were performed on a desktop computer with Intel(R) Core(TM)
i9-10900<EMAIL_ADDRESS>and 64G RAM.

###  6.1 Minimizing a random real quadratic polynomial with binary variables

Let us minimize a random real quadratic polynomial with binary variables:

(27)
$\begin{cases}\inf\limits_{{\mathbf{x}}\in{\mathbb{R}}^{n}}&[{\mathbf{x}}]_{1}^{\intercal}Q[{\mathbf{x}}]_{1}\\\
\,\,\,\rm{s.t.}&x_{i}^{2}=1,\quad i=1,\ldots,n,\end{cases}$

where $Q\in{\mathbb{R}}^{(n+1)\times(n+1)}$ is a random symmetric matrix whose
entries are selected with respect to the uniform probability distribution on
$[0,1]$. For each $n\in\\{10,20,30,40\\}$, we solve three instances using LAS
($r=1,2$) and S-LAS ($r=1,s=1$), respectively. The results are presented in
Table 1. For this problem, we empirically observe that LAS at $r=2$ achieves
global optimality. It can be seen from the table that the strengthening
technique significantly improves the bound provided by LAS at $r=1$ while it
is much cheaper than going to LAS at $r=2$.

Table 1: Minimizing a random real quadratic polynomial with binary variables. $n$ | trial | LAS ($r=1$) | LAS ($r=2$) | S-LAS ($r=1$)
---|---|---|---|---
opt | time | opt | time | opt | time
$10$ | 1 | -6.9868 | 0.006 | -6.6118 | 0.04 | -6.6118 | 0.03
2 | -9.9016 | 0.006 | -9.6732 | 0.04 | -9.6732 | 0.03
3 | -8.6265 | 0.007 | -6.6963 | 0.04 | -6.8216 | 0.03
$20$ | 1 | -26.613 | 0.01 | -23.407 | 5.95 | -23.521 | 0.43
2 | -28.474 | 0.01 | -24.330 | 6.08 | -26.575 | 0.44
3 | -30.996 | 0.01 | -27.657 | 5.61 | -27.657 | 0.47
$30$ | 1 | -51.429 | 0.08 | -44.597 | 382 | -47.817 | 6.29
2 | -57.277 | 0.03 | -49.871 | 435 | -53.539 | 5.74
3 | -49.950 | 0.03 | -42.548 | 479 | -46.970 | 5.30
$40$ | 1 | -79.672 | 0.09 | - | - | -74.532 | 43.1
2 | -83.814 | 0.13 | - | - | -81.274 | 36.9
3 | -85.887 | 0.09 | - | - | -79.748 | 41.0

###  6.2 The point cloud registration problem

Given two sets of 3D points
$\\{{\mathbf{a}}_{i}\\}_{i=1}^{N},\\{{\mathbf{b}}_{i}\\}_{i=1}^{N}$ with
putative correspondences ${\mathbf{a}}_{i}\leftrightarrow{\mathbf{b}}_{i}$,
the point cloud registration problem in computer vision is to find the best 3D
rotation $R$ and translation $\mathbf{t}$ to align them while explicitly
tolerating outliers. It can be formulated as the nonlinear optimization
problem:

(28) $\min_{R\in
SO(3),\mathbf{t}\in{\mathbb{R}}^{3}}\sum_{i=1}^{N}\min\left\\{\frac{\|{\mathbf{b}}_{i}-R{\mathbf{a}}_{i}-\mathbf{t}\|^{2}}{\beta_{i}^{2}},1\right\\},$

where $\beta_{i}>0$ is a given threshold that determines the maximum inlier
residual. By introducing $N$ binary variables $\\{\theta_{i}\\}_{i=1}^{N}$,
(28) can be equivalently reformulated as a polynomial optimization problem:

(29) $\min_{\begin{subarray}{c}R\in SO(3),\mathbf{t}\in{\mathbb{R}}^{3},\\\
\theta_{i}\in\\{-1,1\\}\end{subarray}}\sum_{i=1}^{N}\frac{1+\theta_{i}}{2}\frac{\|{\mathbf{b}}_{i}-R{\mathbf{a}}_{i}-\mathbf{t}\|^{2}}{\beta_{i}^{2}}+\frac{1-\theta_{i}}{2}.$

Note that in (29), the rotation matrix $R$ can be parametrized by its entries
which we denote by ${\mathbf{r}}$ and the constraint $R\in SO(3)$ can be
expressed by polynomial constraints in ${\mathbf{r}}$. Yang and Carlone [20]
proposed a customized monomial basis for the dense Lasserre’s hierarchy for
(29) which is
$[1,{\mathbf{x}},{\boldsymbol{\theta}},{\mathbf{r}}\otimes\mathbf{t},{\mathbf{x}}\otimes{\boldsymbol{\theta}}]$
with ${\mathbf{x}}\coloneqq[{\mathbf{r}},\mathbf{t}]$ and
${\boldsymbol{\theta}}\coloneqq\\{\theta_{i}\\}_{i=1}^{N}$. Moreover, they
also proposed a sparse Lasserre’s hierarchy for (29) in which the variables
are decomposed into $N$ cliques: $[{\mathbf{x}},\theta_{i}],i\in[N]$ and for
the $i$-th clique, the monomial basis
$[1,{\mathbf{x}},\theta_{i},{\mathbf{r}}\otimes\mathbf{t},{\mathbf{x}}\otimes\theta_{i}]$
is used. It was empirically shown in [20] that the dense Lasserre’s hierarchy
achieves global optimality at relaxation order $r=2$ while the sparse
Lasserre’s hierarchy is usually not tight at the same relaxation order.

For each $N\in\\{10,20,30,40\\}$, we randomly generate three instances of (29)
with $60\%$ outliers. We solve each instance using the dense LAS (with the
above monomial basis) at $r=2$, the sparse LAS (with the above monomial basis)
at $r=2,s=1$, and the sparse S-LAS (with the above monomial basis) at $r=2$,
respectively. The results are presented in Table 2 from which we can see that
the strengthening technique improves the bound provided by the sparse LAS
while it is much cheaper than the dense LAS.

Table 2: The point cloud registration problem. $N$ | trial | dense LAS | sparse LAS | sparse S-LAS
---|---|---|---|---
opt | time | opt | time | opt | time
$10$ | 1 | 6.5437 | 18.3 | 6.1294 | 1.32 | 6.2392 | 4.05
2 | 6.4687 | 17.8 | 6.2538 | 1.33 | 6.4461 | 4.56
3 | 6.3971 | 21.0 | 6.1144 | 1.32 | 6.2634 | 4.50
$20$ | 1 | 14.062 | 424 | 12.345 | 2.28 | 13.007 | 28.3
2 | 14.256 | 350 | 12.423 | 2.79 | 13.053 | 29.1
3 | 13.780 | 321 | 12.279 | 2.57 | 12.851 | 26.8
$30$ | 1 | 20.870 | 2461 | 18.670 | 3.47 | 19.696 | 138
2 | 20.263 | 2808 | 18.522 | 4.98 | 19.381 | 139
3 | 20.452 | 2435 | 18.459 | 3.64 | 19.792 | 136
$40$ | 1 | - | - | 24.942 | 4.84 | 26.495 | 662
2 | - | - | 24.783 | 4.62 | 26.751 | 630
3 | - | - | 24.888 | 4.25 | 27.295 | 632

###  6.3 Minimizing a random complex quadratic polynomial with unit-norm
variables

Let us now minimize a random complex quadratic polynomial with unit-norm
variables:

(30)
$\begin{cases}\inf\limits_{{\mathbf{x}}\in{\mathbb{C}}^{n}}&[{\mathbf{x}}]_{1}^{\star}Q[{\mathbf{x}}]_{1}\\\
\,\,\,\rm{s.t.}&|x_{i}|^{2}=1,\quad i=1,\ldots,n,\end{cases}$

where $Q\in{\mathbb{C}}^{(n+1)\times(n+1)}$ is a random Hermitian matrix whose
entries (both real and imaginary parts) are selected with respect to the
uniform probability distribution on $[0,1]$. For each $n\in\\{10,20,30\\}$, we
solve three instances using LAS ($r=1,2$) and S-LAS ($r=1,s=1$), respectively.
The results are presented in Table 3. For this problem, we empirically observe
that LAS at $r=2$ achieves global optimality. It is evident from the table
that the strengthening technique significantly improves the bound (indeed,
achieving global optimality for $n\leq 20$) provided by LAS at $r=1$ while it
is much cheaper than going to LAS at $r=2$.

Table 3: Minimizing a random complex quadratic polynomial with unit-norm variables. $n$ | trial | LAS ($r=1$) | LAS ($r=2$) | S-LAS ($r=1$)
---|---|---|---|---
opt | time | opt | time | opt | time
$10$ | 1 | -10.830 | 0.01 | -10.474 | 1.57 | -10.474 | 0.15
2 | -14.005 | 0.01 | -13.905 | 1.76 | -13.905 | 0.15
3 | -14.308 | 0.01 | -13.751 | 1.71 | -13.751 | 0.16
$20$ | 1 | -39.274 | 0.03 | -38.323 | 1227 | -38.323 | 6.39
2 | -44.009 | 0.03 | -43.911 | 1076 | -43.911 | 5.51
3 | -43.043 | 0.03 | -42.017 | 1061 | -42.017 | 5.76
$30$ | 1 | -75.249 | 0.14 | - | - | -72.948 | 234
2 | -79.995 | 0.13 | - | - | -79.382 | 161
3 | -74.888 | 0.12 | - | - | -73.680 | 148

###  6.4 Minimizing a random complex quartic polynomial on a sphere

Let us minimize a random complex quartic polynomial on a unit sphere:

(31)
$\begin{cases}\inf\limits_{{\mathbf{x}}\in{\mathbb{C}}^{n}}&[{\mathbf{x}}]_{2}^{\star}Q[{\mathbf{x}}]_{2}\\\
\,\,\,\rm{s.t.}&|x_{1}|^{2}+\cdots+|x_{n}|^{2}=1,\end{cases}$

where $Q\in{\mathbb{C}}^{|[{\mathbf{x}}]_{2}|\times|[{\mathbf{x}}]_{2}|}$
($|[{\mathbf{x}}]_{2}|$ is the cardinality of $[{\mathbf{x}}]_{2}$) is a
random Hermitian matrix whose entries (both real and imaginary parts) are
selected with respect to the uniform probability distribution on $[0,1]$. For
each $n\in\\{5,10,15\\}$, we solve three instances using LAS ($r=2,3$) and
S-LAS ($r=2,s=1$), respectively. The results are presented in Table 4. We can
see from the table that the strengthening technique significantly improves the
bound provided by LAS at both $r=2$ and $r=3$ while it is much cheaper than
going to LAS at $r=3$.

Table 4: Minimizing a random complex quartic polynomial on a unit sphere. $n$ | trial | LAS ($r=2$) | LAS ($r=3$) | S-LAS ($r=2$)
---|---|---|---|---
opt | time | opt | time | opt | time
$5$ | 1 | -4.4125 | 0.04 | -4.1976 | 2.09 | -4.0517 | 0.06
2 | -2.9632 | 0.04 | -2.5182 | 1.94 | -2.3767 | 0.05
3 | -3.9058 | 0.04 | -3.3651 | 1.97 | -3.1354 | 0.05
$10$ | 1 | -5.9950 | 3.08 | - | - | -4.6231 | 4.50
2 | -5.9757 | 2.93 | - | - | -4.5794 | 4.08
3 | -5.6221 | 3.05 | - | - | -4.1087 | 4.18
$15$ | 1 | -8.5265 | 82.3 | - | - | -6.5370 | 130
2 | -8.0241 | 87.4 | - | - | -6.3118 | 121
3 | -8.0791 | 85.7 | - | - | -6.1881 | 123

###  6.5 Minimizing a random complex quartic polynomial with correlative
sparsity on multi-spheres

Let us minimize a random complex quartic polynomial with correlative sparsity
on multi-spheres:

(32)
$\begin{cases}\inf\limits_{{\mathbf{x}}\in{\mathbb{C}}^{n}}&\sum_{i=1}^{l}[{\mathbf{x}}_{i}]_{2}^{\star}Q_{i}[{\mathbf{x}}_{i}]_{2}\\\
\,\,\,\rm{s.t.}&\|{\mathbf{x}}_{i}\|^{2}=1,\quad i\in[l],\end{cases}$

where $n=4l+2$, ${\mathbf{x}}_{i}\coloneqq\\{x_{4i-3},\ldots,x_{4i+2}\\}$, and
$Q_{i}\in{\mathbb{C}}^{|[{\mathbf{x}}_{i}]_{2}|\times|[{\mathbf{x}}_{i}]_{2}|}$
is a random Hermitian matrix whose entries (both real and imaginary parts) are
selected with respect to the uniform probability distribution on $[0,1]$. For
each $l\in\\{5,10,50,100\\}$, we solve three instances using the sparse LAS
($r=2,3$) and the sparse S-LAS ($r=2,s=1$), respectively. The results are
presented in Table 5. Again, we can conclude from the table that the
strengthening technique significantly improves the bound provided by the
sparse LAS at both $r=2$ and $r=3$ while it is much cheaper than going to the
sparse LAS at $r=3$.

Table 5: Minimizing a random complex quartic polynomial on multi-spheres. $n$ | trial | LAS ($r=2$) | LAS ($r=3$) | S-LAS ($r=2$)
---|---|---|---|---
opt | time | opt | time | opt | time
$22$ | 1 | -16.561 | 0.48 | -13.190 | 87.7 | -12.911 | 0.74
2 | -17.891 | 0.47 | -14.468 | 89.5 | -13.918 | 0.72
3 | -18.119 | 0.51 | -14.408 | 90.7 | -14.094 | 0.71
$42$ | 1 | -34.424 | 1.28 | -27.404 | 122 | -26.607 | 1.68
2 | -35.052 | 1.30 | -28.862 | 124 | -27.896 | 1.81
3 | -34.392 | 1.24 | -27.796 | 122 | -27.071 | 1.66
$202$ | 1 | -168.10 | 5.15 | -133.07 | 645 | -132.14 | 9.81
2 | -168.90 | 5.14 | -135.14 | 597 | -133.14 | 8.34
3 | -166.92 | 4.35 | -135.01 | 612 | -132.40 | 8.89
$402$ | 1 | -339.50 | 10.7 | - | - | -268.95 | 23.5
2 | -328.91 | 12.1 | - | - | -259.32 | 23.5
3 | -333.95 | 11.0 | - | - | -264.59 | 21.8

###  6.6 Smale’s Mean Value conjecture

The following complex polynomial optimization problem is borrowed from [17]:

(33) $\begin{cases}\sup\limits_{({\mathbf{z}},u)\in{\mathbb{C}}^{n+1}}&|u|\\\
\,\,\quad\rm{s.t.}&|H(z_{i})|\geq|u|,\quad i=1,\ldots,n,\\\ &z_{1}\cdots
z_{n}=\frac{(-1)^{n}}{n+1},\\\
&|z_{1}|^{2}+|z_{2}|^{2}+\cdots+|z_{n}|^{2}=n\left(\frac{1}{n+1}\right)^{\frac{2}{n}},\end{cases}$

where $H(y)\coloneqq\frac{1}{y}\int_{0}^{y}p(z)\,\mathrm{d}z$ and
$p(z)\coloneqq(n+1)(z-z_{1})\cdots(z-z_{n})$ with $p(0)=1$. This problem is
used in [17] to verify Smale’s Mean Value conjecture [13, 14] which is open
for $n\geq 4$ since 1981. The optimum of (33) is conjectured to be
$\frac{n}{n+1}$. We refer the reader to [17] for more details. Here we solve
(33) with $n=4$ using LAS ($r=4,6,8$) and S-LAS ($r=4,s=1,2,3$). The results
are presented in Table 6, from which we see that the strengthening technique
enables us to achieve global optimality at lower relaxation orders so that the
computational cost is significantly reduced.

Table 6: The results for (33) with $n=4$. LAS | $r=4$ | $r=6$ | $r=8$
---|---|---|---
opt | time | opt | time | opt | time
1.4218 | 0.16 | 0.8404 | 22.8 | - | -
S-LAS | $r=4,s=1$ | $r=4,s=2$ | $r=4,s=3$
opt | time | opt | time | opt | time
1.4218 | 0.17 | 1.2727 | 0.45 | 0.8000 | 18.2

###  6.7 The Mordell inequality conjecture

Our next example concerns the Mordell inequality conjecture due to Birch in
1958: if the numbers $z_{1},\ldots,z_{n}\in{\mathbb{C}}$ satisfies
$|z_{1}|^{2}+\cdots+|z_{n}|^{2}=n$, then the maximum of $\prod_{1\leq i<j\leq
n}|z_{i}-z_{j}|^{2}$ is $n^{n}$. This conjecture was proved for $n\leq 4$ and
disproved for $n\geq 6$, and so the only remaining open case is when $n=5$.
The reader is referred to [17] for more details. Without loss of generality,
we may eliminate one variable and reformulate the conjecture as the following
complex polynomial optimization problem:

(34)
$\begin{cases}\sup\limits_{{\mathbf{z}}\in{\mathbb{C}}^{n-1}}&\prod_{1\leq
i<j\leq
n-1}|z_{i}-z_{j}|^{2}\prod_{i=1}^{n-1}|z_{i}+z_{1}+\ldots+z_{n-1}|^{2}\\\
\,\,\,\,\,\rm{s.t.}&|z_{1}|^{2}+\cdots+|z_{n-1}|^{2}+|z_{1}+\ldots+z_{n-1}|^{2}=n.\\\
\end{cases}$

Here we solve (34) with $n=3,4$ using LAS and S-LAS. The results are presented
in Tables 7 and 8, respectively. From the tables, we see that the
strengthening technique enables us to achieve global optimality at much lower
relaxation orders so that the computational cost is significantly reduced.

Table 7: The results for (34) with $n=3$. LAS | $r=4$ | $r=6$ | $r=8$
---|---|---|---
opt | time | opt | time | opt | time
27.347 | 0.04 | 27.122 | 0.19 | 27.074 | 0.35
S-LAS | $r=3,s=0$ | $r=3,s=1$ | $r=3,s=2$
opt | time | opt | time | opt | time
54.000 | 0.005 | 54.000 | 0.008 | 27.000 | 0.01
Table 8: The results for (34) with $n=4$.

LAS | $r=10$ | $r=12$ | $r=14$ | $r=16$ | $r=18$
---|---|---|---|---|---
opt | time | opt | time | opt | time | opt | time | opt | time
343.66 | 8.58 | 326.85 | 50.1 | 292.89 | 212 | 277.64 | 790 | - | -
S-LAS | $r=6,s=1$ | $r=6,s=2$ | $r=6,s=3$ | $r=6,s=4$ | $r=6,s=5$
opt | time | opt | time | opt | time | opt | time | opt | time
1638.4 | 0.13 | 1337.5 | 0.20 | 932.20 | 0.25 | 582.86 | 0.76 | 256.00 | 3.10

###  6.8 The AC-OPF problem

The AC optimal power flow (AC-OPF) is a central problem in power systems,
which aims to minimize the generation cost of an alternating current
transmission network under the physical constraints. Mathematically, it can be
formulated as the following complex polynomial optimization problem:

(35) $\begin{cases}\inf\limits_{\\{V_{i}\\}_{i\in N}}&\sum_{k\in
G}\Bigl{(}\mathbf{c}_{2k}\Re\bigl{(}\mathbf{S}_{i_{k}}^{d}+\mathbf{Y}_{i_{k}}^{sh}|V_{i_{k}}|^{2}+\sum_{(i_{k},j)\in
E_{i_{k}}\cup E_{i_{k}}^{R}}S_{i_{k}j}\bigr{)}^{2}\\\
&\quad\quad\quad+\mathbf{c}_{1k}\Re\bigl{(}\mathbf{S}_{i_{k}}^{d}+\mathbf{Y}_{i_{k}}^{sh}|V_{i_{k}}|^{2}+\sum_{(i_{k},j)\in
E_{i_{k}}\cup E_{i_{k}}^{R}}S_{i_{k}j}\bigr{)}+\mathbf{c}_{0k}\Bigr{)}\\\
\,\,\,\,\,\textrm{s.t.}&\angle V_{ref}=0,\\\
&\mathbf{S}_{k}^{gl}\leq\mathbf{S}_{i_{k}}^{d}+\mathbf{Y}_{i_{k}}^{sh}|V_{i_{k}}|^{2}+\sum_{(i_{k},j)\in
E_{i_{k}}\cup E_{i_{k}}^{R}}S_{i_{k}j}\leq\mathbf{S}_{k}^{gu},\quad\forall
k\in G,\\\
&\boldsymbol{\upsilon}_{i}^{l}\leq|V_{i}|\leq\boldsymbol{\upsilon}_{i}^{u},\quad\forall
i\in N,\\\
&S_{ij}=\left(\mathbf{Y}_{ij}^{*}-\mathbf{i}\frac{\mathbf{b}_{ij}^{c}}{2}\right)\frac{|V_{i}|^{2}}{|\mathbf{T}_{ij}|^{2}}-\mathbf{Y}_{ij}^{*}\frac{V_{i}V_{j}^{*}}{\mathbf{T}_{ij}},\quad\forall(i,j)\in
E,\\\
&S_{ji}=\left(\mathbf{Y}_{ij}^{*}-\mathbf{i}\frac{\mathbf{b}_{ij}^{c}}{2}\right)|V_{j}|^{2}-\mathbf{Y}_{ij}^{*}\frac{V_{i}^{*}V_{j}}{\mathbf{T}_{ij}^{*}},\quad\forall(i,j)\in
E,\\\ &|S_{ij}|\leq\mathbf{s}_{ij}^{u},\quad\forall(i,j)\in E\cup E^{R},\\\
&\boldsymbol{\theta}_{ij}^{\Delta
l}\leq\angle(V_{i}V_{j}^{*})\leq\boldsymbol{\theta}_{ij}^{\Delta
u},\quad\forall(i,j)\in E.\\\ \end{cases}$

For a full description on the AC-OPF problem, the reader may refer to [2] as
well as [16]. For an AC-OPF instance, we can obtain an upper bound (‘ub’) on
the optimum from a local solver. Then the optimality gap between the upper
bound and the lower bound (‘lb’) provided by SDP relaxations is defined by

$\textrm{gap}\coloneqq\frac{\textrm{ub}-\textrm{lb}}{\textrm{ub}}\times
100\%.$

For our purpose, we select instances from the AC-OPF library PGLiB [2] that
exhibit significant optimality gaps. The number appearing in each case name
stands for the number of buses, which is equal to the number of complex
variables involved in (35). We solve each instance using the sparse LAS and
the sparse S-LAS with minimum relaxation order [16]. The results are presented
in Table 9, from which we see that the strengthening technique substantially
reduce the optimality gap in most cases.

Table 9: The results for the AC-OPF problem. case name | LAS | S-LAS
---|---|---
opt | time | gap | opt | time | gap
30_as | 7.3351e2 | 0.35 | 8.66% | 7.4426e2 | 1.13 | 7.32%
39_epri | 1.3749e5 | 0.27 | 0.66% | 1.3841e5 | 0.71 | 0.00%
162_ieee_dtc | 1.0176e5 | 13.5 | 5.84% | 1.0647e5 | 114 | 1.49%
179_goc | 7.5150e5 | 2.26 | 0.36% | 7.5386e5 | 7.69 | 0.05%
30_as_sad | 8.6569e2 | 0.33 | 3.52% | 8.7496e2 | 1.33 | 2.49%
118_ieee_sad | 9.6760e4 | 2.10 | 7.98% | 1.0294e5 | 5.79 | 2.10%
162_ieee_dtc_sad | 1.0176e5 | 10.8 | 6.36% | 1.0738e5 | 118 | 1.20%
179_goc_sad | 7.5279e5 | 2.43 | 1.27% | 7.5581e5 | 7.41 | 0.88%
30_as_api | 2.6237e3 | 0.41 | 47.4% | 4.9935e3 | 1.19 | 0.05%
39_epri_api | 2.4511e5 | 0.23 | 1.82% | 2.4963e5 | 0.73 | 0.01%
89_pegase_api | 1.0139e5 | 15.2 | 22.1% | 1.0507e5 | 44.1 | 19.2%
118_ieee_api | 1.7571e5 | 2.01 | 27.4% | 2.2293e5 | 5.99 | 7.96%
162_ieee_dtc_api | 1.1526e5 | 9.81 | 4.73% | 1.1956e5 | 119 | 1.17%
179_goc_api | 1.8603e6 | 2.74 | 3.70% | 1.9226e6 | 8.11 | 0.48%

## References

  * [1] 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, vol. 33 of Applied Optimization, Springer US, 2000, pp. 197–232, https://doi.org/10.1007/978-1-4757-3216-0_8.
  * [2] S. Babaeinejadsarookolaee, A. Birchfield, R. D. Christie, C. Coffrin, C. DeMarco, R. Diao, M. Ferris, S. Fliscounakis, S. Greene, R. Huang, et al., The power grid library for benchmarking AC optimal power flow algorithms, arXiv preprint arXiv:1908.02788, (2019).
  * [3] D. Henrion, M. Korda, and J. B. Lasserre, Moment-sos Hierarchy, The: Lectures In Probability, Statistics, Computational Geometry, Control And Nonlinear Pdes, vol. 4, World Scientific, 2020.
  * [4] D. Henrion and J.-B. Lasserre, Detecting global optimality and extracting solutions in gloptipoly, in Positive Polynomials in Control, Springer, 2005, pp. 293–310.
  * [5] C. Josz and D. K. Molzahn, Lasserre hierarchy for large scale polynomial optimization in real and complex variables, SIAM Journal on Optimization, 28 (2018), pp. 1017–1048.
  * [6] J.-B. Lasserre, Global Optimization with Polynomials and the Problem of Moments, SIAM Journal on Optimization, 11 (2001), pp. 796–817.
  * [7] J. B. Lasserre, M. Laurent, and P. Rostalski, Semidefinite characterization and computation of zero-dimensional real radical ideals, Foundations of Computational Mathematics, 8 (2008), pp. 607–647.
  * [8] M. Laurent, Sums of squares, moment matrices and optimization over polynomials, in Emerging applications of algebraic geometry, Springer, 2009, pp. 157–270.
  * [9] V. Magron and J. Wang, Sparse polynomial optimization: theory and practice, World Scientific, 2023.
  * [10] J. Nie, Tight relaxations for polynomial optimization and lagrange multiplier expressions, Mathematical Programming, 178 (2019), pp. 1–37.
  * [11] J. Nie, Moment and Polynomial Optimization, 2023.
  * [12] C. Riener, T. Theobald, L. J. Andrén, and J. B. Lasserre, Exploiting symmetries in sdp-relaxations for polynomial optimization, Mathematics of Operations Research, 38 (2013), pp. 122–141.
  * [13] S. Smale, The fundamental theorem of algebra and complexity theory, Bulletin (New Series) of the American Mathematical Society, 4 (1981), pp. 1–36.
  * [14] S. Smale, Mathematical problems for the next century, The mathematical intelligencer, 20 (1998), pp. 7–15.
  * [15] J. Wang, A more efficient reformulation of complex SDP as real SDP, 2023.  Preprint https:arXiv.org/abs/2307.11599.
  * [16] J. Wang and V. Magron, Exploiting sparsity in complex polynomial optimization, Journal of Optimization Theory and Applications, 192 (2022), pp. 335–359.
  * [17] J. Wang and V. Magron, A real moment-hsos hierarchy for complex polynomial optimization with real coefficients, arXiv preprint arXiv:2308.14631, (2023).
  * [18] 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.
  * [19] J. Wang, V. Magron, J.-B. Lasserre, and N. H. A. Mai, CS-TSSOS: Correlative and term sparsity for large-scale polynomial optimization, arXiv:2005.02828, (2020).
  * [20] H. Yang and L. Carlone, One ring to rule them all: Certifiably robust geometric perception with outliers, in Advances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, eds., vol. 33, Curran Associates, Inc., 2020, pp. 18846–18859.