exampleExample remarkRemark hypothesisHypothesis claimClaim A more efficient
reformulation of complex SDP as real SDPJie Wang

# A more efficient reformulation of complex SDP as real SDP††thanks: Submitted
to the editors DATE. This work was funded by NSFC-12201618 and NSFC-12171324.

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

This note proposes a novel reformulation of complex semidefinite programs
(SDPs) as real SDPs. As an application, we present an economical reformulation
of complex SDP relaxations of complex polynomial optimization problems as real
SDPs and derive some further reductions by exploiting structure of the complex
SDP relaxations. Various numerical examples demonstrate that our new
reformulation runs several times (one magnitude in some cases) faster than the
usual popular reformulation.

###### keywords:

complex semidefinite programming, complex polynomial optimization,
semidefinite programming, the complex moment-HSOS hierarchy, quantum
information

90C22, 90C23

##  1 Introduction

Complex semidefinite programs (SDPs) arise from a diverse set of areas, such
as combinatorial optimization [7], optimal power flow [8, 10], quantum
information theory [2, 4, 14], signal processing [9, 12]. In particular, they
appear as convex relaxations of complex polynomial optimization problems
(CPOPs), giving rise to the complex moment-Hermitian-sum-of-squares (moment-
HSOS) hierarchy [8, 13]. However, most modern SDP solvers deal with only real
SDPs111As far as the author knows, SeDuMi [11] and Hypatia [6] are the only
solvers that can handle complex SDPs directly.. In order to handle complex
SDPs, it is then mandatory to reformulate complex SDPs as equivalent real
SDPs. A popular way to do so is to use the equivalent condition

(1) $H\succeq 0\quad\iff\quad Y=\begin{bmatrix}H_{R}&-H_{I}\\\
H_{I}&H_{R}\end{bmatrix}\succeq 0$

for an Hermitian matrix $H=H_{R}+H_{I}\hbox{\bf{i}}\in{\mathbb{C}}^{n\times
n}$ with $H_{R}$ and $H_{I}$ being its real and imaginary parts respectively.
Note that the right-hand-side constraint in (1) entails certain structure and
to feed it to an SDP solver, we need to impose extra affine constraints to the
positive semidefinite (PSD) constraint $Y\succeq 0$:

(2) $Y_{i,j}=Y_{i+n,j+n},Y_{i,j+n}+Y_{j,i+n}=0,\quad
i=1,\ldots,n,j=i,\ldots,n.$

This conversion is quite simple but could be inefficient when $n$ is large. In
this note, we take a dual point of view and propose a novel reformulation of
complex SDPs as real SDPs. The benefit of the new reformulation is that there
is no need to add extra affine constraints and hence it owns a lower
complexity. In the same manner, we can obtain a new reformulation of complex
SDP relaxations of CPOPs as real SDPs. Furthermore, by exploiting structure of
the complex SDP relaxations, we are able to remove a bunch of redundant affine
constraints, which leads to an even more economical real reformulation of the
complex SDP relaxations. Various numerical experiments (on randomly generated
CPOPs and the AC-OPF problem) confirm our theoretical finding and demonstrate
that the new reformulation is indeed more efficient than the usual popular
one.

Notation. ${\mathbb{N}}$ denotes the set of nonnegative integers. For
$n\in{\mathbb{N}}\setminus\\{0\\}$, let $[n]\coloneqq\\{1,2,\ldots,n\\}$. We
use $|A|$ to stand for the cardinality of a set $A$. Let i be the imaginary
unit, satisfying $\hbox{\bf{i}}^{2}=-1$. For $d\in{\mathbb{N}}$, let
${\mathbb{N}}^{n}_{d}\coloneqq\\{(\alpha_{i})_{i}\in{\mathbb{N}}^{n}\mid\sum_{i=1}^{n}\alpha_{i}\leq
d\\}$ and let $\omega_{n,d}\coloneqq\binom{n+d}{d}$ be the cardinality of
${\mathbb{N}}^{n}_{d}$. For
${\boldsymbol{\alpha}}=(\alpha_{i})_{i}\in{\mathbb{N}}^{n}_{d}$, let
${\mathbf{z}}^{{\boldsymbol{\alpha}}}\coloneqq z_{1}^{\alpha_{1}}\cdots
z_{n}^{\alpha_{n}}$. $\overline{a}$ (resp.
${\mathcal{R}}(a),{\mathcal{I}}(a)$) denotes the conjugate (resp. real part,
imaginary part) of a complex number $a$ and $v^{\star}$ denotes the conjugate
transpose of a complex vector $v$. For a positive integer $n$, the set of
$n\times n$ Hermitian matrices is denoted by ${\mathbf{H}}^{n}$. We use
$A\succeq 0$ to indicate that the matrix $A$ is PSD. For
$A,B\in{\mathbb{C}}^{n\times n}$, we denote by $\langle A,B\rangle$ the trace
inner-product, defined by $\langle A,B\rangle=\hbox{\rm{Tr}}(A^{\intercal}B)$.

##  2 Main results

Let us consider the following complex SDP:

(PSDP-${\mathbb{C}}$) $\begin{cases}\sup\limits_{H\in{\mathbf{H}}^{n}}&\langle
C,H\rangle\\\ \,\,\,\,\rm{s.t.}&{\mathscr{A}}(H)=b,\\\ &H\succeq
0,\end{cases}$

where ${\mathscr{A}}$ is a linear operator given by
${\mathscr{A}}(H)\coloneqq(\langle
A_{i},H\rangle)_{i=1}^{m}\in{\mathbb{C}}^{m}$ and
$C\in{\mathbf{H}}^{n},b\in{\mathbb{C}}^{m}$. By writing
${\mathscr{A}}={\mathscr{A}}_{R}+{\mathscr{A}}_{I}\hbox{\bf{i}},H=H_{R}+H_{I}\hbox{\bf{i}},C=C_{R}+C_{I}\hbox{\bf{i}},b=b_{R}+b_{I}\hbox{\bf{i}}$
with ${\mathscr{A}}_{R},{\mathscr{A}}_{I}$ being the real linear operators
associated to ${\mathscr{A}}$,
$H_{R},H_{I},C_{R},C_{I}\in{\mathbb{R}}^{n\times n}$,
$b_{R},b_{I}\in{\mathbb{R}}^{m}$, we can reformulate (PSDP-${\mathbb{C}}$) as
a real SDP:

(PSDP-${\mathbb{R}}$)
$\begin{cases}\sup\limits_{Y\in{\mathbf{S}}^{2n}}&\langle
C_{R},H_{R}\rangle-\langle C_{I},H_{I}\rangle\\\
\,\,\,\,\rm{s.t.}&{\mathscr{A}}_{R}(H_{R})-{\mathscr{A}}_{I}(H_{I})=b_{R},\\\
&{\mathscr{A}}_{R}(H_{I})+{\mathscr{A}}_{I}(H_{R})=b_{I},\\\
&Y=\begin{bmatrix}H_{R}&-H_{I}\\\ H_{I}&H_{R}\end{bmatrix}\succeq
0.\end{cases}$

As mentioned in the introduction, to feed the PSD constraint in
(PSDP-${\mathbb{R}}$) to an SDP solver, we need to include also the extra
$n(n+1)$ affine constraints listed in (2), which could be inefficient in
practice. Below we show that by taking a dual point of view, we can actually
get rid of this issue. By the convex duality theory, the dual problem of
(PSDP-${\mathbb{C}}$) reads as

(DSDP-${\mathbb{C}}$)
$\begin{cases}\inf\limits_{y\in{\mathbb{C}}^{m}}&b^{\intercal}y\\\
\,\,\,\rm{s.t.}&{\mathscr{A}}^{*}(y)\succeq C,\end{cases}$

where ${\mathscr{A}}^{*}(y)\coloneqq\sum_{i=1}^{m}y_{i}A_{i}$ is the adjoint
operator of ${\mathscr{A}}$. By writing $y=y_{R}+y_{I}\hbox{\bf{i}}$ with
$y_{R},y_{I}\in{\mathbb{R}}^{m}$, we can reformulate (DSDP-${\mathbb{C}}$) as
a real SDP:

(DSDP-${\mathbb{R}}$)
$\begin{cases}\inf\limits_{y_{R},y_{I}\in{\mathbb{R}}^{m}}&b_{R}y_{R}-b_{I}y_{I}\\\
\,\,\,\,\,\,\,\,\rm{s.t.}&\begin{bmatrix}{\mathscr{A}}_{R}^{*}(y_{R})-{\mathscr{A}}_{I}^{*}(y_{I})-C_{R}&-{\mathscr{A}}_{R}^{*}(y_{I})-{\mathscr{A}}_{I}^{*}(y_{R})+C_{I}\\\
{\mathscr{A}}_{R}^{*}(y_{I})+{\mathscr{A}}_{I}^{*}(y_{R})-C_{I}&{\mathscr{A}}_{R}^{*}(y_{R})-{\mathscr{A}}_{I}^{*}(y_{I})-C_{R}\end{bmatrix}\succeq
0.\end{cases}$

Let $X=\left[\begin{smallmatrix}X_{1}&X_{3}\\\
X_{3}^{\intercal}&X_{2}\end{smallmatrix}\right]$ be the dual PSD variable of
(DSDP-${\mathbb{R}}$) with $X_{1},X_{2},X_{3}\in{\mathbb{R}}^{n\times n}$.
Then the Lagrangian associated with (DSDP-${\mathbb{R}}$) is

$\displaystyle\,L(X,y_{R},y_{I})$ $\displaystyle=$
$\displaystyle\,-\left\langle\begin{bmatrix}X_{1}&X_{3}\\\
X_{3}^{\intercal}&X_{2}\end{bmatrix},\begin{bmatrix}{\mathscr{A}}_{R}^{*}(y_{R})-{\mathscr{A}}_{I}^{*}(y_{I})-C_{R}&-{\mathscr{A}}_{R}^{*}(y_{I})-{\mathscr{A}}_{I}^{*}(y_{R})+C_{I}\\\
{\mathscr{A}}_{R}^{*}(y_{I})+{\mathscr{A}}_{I}^{*}(y_{R})-C_{I}&{\mathscr{A}}_{R}^{*}(y_{R})-{\mathscr{A}}_{I}^{*}(y_{I})-C_{R}\end{bmatrix}\right\rangle$
$\displaystyle\,+b_{R}y_{R}-b_{I}y_{I}$ $\displaystyle=$
$\displaystyle\,-\langle
X_{1}+X_{2},{\mathscr{A}}_{R}^{*}(y_{R})-{\mathscr{A}}_{I}^{*}(y_{I})-C_{R}\rangle+\langle
X_{3}-X_{3}^{\intercal},{\mathscr{A}}_{R}^{*}(y_{I})+{\mathscr{A}}_{I}^{*}(y_{R})-C_{I}\rangle$
$\displaystyle\,+b_{R}y_{R}-b_{I}y_{I}$ $\displaystyle=$
$\displaystyle\,\langle C_{R},X_{1}+X_{2}\rangle-\langle
C_{I},X_{3}-X_{3}^{\intercal}\rangle+\langle
b_{R}-{\mathscr{A}}_{R}(X_{1}+X_{2})+{\mathscr{A}}_{I}(X_{3}-X_{3}^{\intercal}),y_{R}\rangle$
$\displaystyle\,-\langle
b_{I}-{\mathscr{A}}_{R}(X_{3}-X_{3}^{\intercal})-{\mathscr{A}}_{I}(X_{1}+X_{2}),y_{I}\rangle.$

Thus the dual problem of (DSDP-${\mathbb{R}}$) can be written down as

(PSDP-${\mathbb{R}}$’)
$\begin{cases}\sup\limits_{X\in{\mathbf{S}}^{2n}}&\langle
C_{R},X_{1}+X_{2}\rangle-\langle C_{I},X_{3}-X_{3}^{\intercal}\rangle\\\
\,\,\,\,\rm{s.t.}&{\mathscr{A}}_{R}(X_{1}+X_{2})-{\mathscr{A}}_{I}(X_{3}-X_{3}^{\intercal})=b_{R},\\\
&{\mathscr{A}}_{R}(X_{3}-X_{3}^{\intercal})+{\mathscr{A}}_{I}(X_{1}+X_{2})=b_{I},\\\
&X=\begin{bmatrix}X_{1}&X_{3}\\\ X_{3}^{\intercal}&X_{2}\end{bmatrix}\succeq
0.\end{cases}$

The above reasoning leads to the main theorem of this note.

######  Theorem 2.1.

(PSDP-${\mathbb{R}}$’) is equivalent to (PSDP-${\mathbb{R}}$) (in the sense
that they share the same optimum). As a result, (PSDP-${\mathbb{R}}$’) is
equivalent to (PSDP-${\mathbb{C}}$). In addition, if
$X^{\star}=\left[\begin{smallmatrix}X_{1}^{\star}&X_{3}^{\star}\\\
(X_{3}^{\star})^{\intercal}&X_{2}^{\star}\end{smallmatrix}\right]$ is an
optimal solution to (PSDP-${\mathbb{R}}$’), then
$H^{\star}=(X^{\star}_{1}+X_{2}^{\star})+(X^{\star}_{3}-(X_{3}^{\star})^{\intercal})\hbox{\bf{i}}$
is an optimal solution to (PSDP-${\mathbb{C}}$).

######  Proof 2.2.

Let us denote the optima of (PSDP-${\mathbb{R}}$) and (PSDP-${\mathbb{R}}$’)
by $v$ and $v^{\prime}$ respectively. Suppose
$Y=\left[\begin{smallmatrix}H_{R}&-H_{I}\\\
H_{I}&H_{R}\end{smallmatrix}\right]$ is a feasible solution to
(PSDP-${\mathbb{R}}$). Then one can easily check that
$X\coloneqq\left[\begin{smallmatrix}\frac{1}{2}H_{R}&\frac{1}{2}H_{I}\\\
-\frac{1}{2}H_{I}&\frac{1}{2}H_{R}\end{smallmatrix}\right]$ is a feasible
solution to (PSDP-${\mathbb{R}}$’). Moreover, we have $\langle
C_{R},X_{1}+X_{2}\rangle-\langle C_{I},X_{3}-X_{3}^{\intercal}\rangle=\langle
C_{R},H_{R}\rangle-\langle C_{I},H_{I}\rangle$ and it follows $v\leq
v^{\prime}$. On the other hand, suppose
$X=\left[\begin{smallmatrix}X_{1}&X_{3}\\\
X_{3}^{\intercal}&X_{2}\end{smallmatrix}\right]$ is a feasible solution to
(PSDP-${\mathbb{R}}$’). We then have

$\begin{bmatrix}0&-1\\\ 1&0\end{bmatrix}^{-1}X\begin{bmatrix}0&-1\\\
1&0\end{bmatrix}=\begin{bmatrix}X_{2}&-X_{3}^{\intercal}\\\
-X_{3}&X_{1}\end{bmatrix}\succeq 0,$

and thus

$\begin{bmatrix}X_{1}+X_{2}&X_{3}-X_{3}^{\intercal}\\\
X_{3}^{\intercal}-X_{3}&X_{1}+X_{2}\end{bmatrix}\succeq 0.$

Consequently, we obtain

$Y=\begin{bmatrix}H_{R}&-H_{I}\\\
H_{I}&H_{R}\end{bmatrix}\coloneqq\begin{bmatrix}X_{1}+X_{2}&X_{3}^{\intercal}-X_{3}\\\
X_{3}-X_{3}^{\intercal}&X_{1}+X_{2}\end{bmatrix}\succeq 0.$

One can easily see that $Y$ is a feasible solution to (PSDP-${\mathbb{R}}$)
and in addition, it holds $\langle C_{R},H_{R}\rangle-\langle
C_{I},H_{I}\rangle=\langle C_{R},X_{1}+X_{2}\rangle-\langle
C_{I},X_{3}-X_{3}^{\intercal}\rangle$. Thus $v\geq v^{\prime}$ which proves
the equivalence. The second statement of the theorem is clear from the above
arguments.

In contrast to (PSDP-${\mathbb{R}}$), the PSD constraint in
(PSDP-${\mathbb{R}}$’) is straightforward, and thus no extra affine constraint
is required. This is why the conversion (PSDP-${\mathbb{R}}$’) is more
appealing than (PSDP-${\mathbb{R}}$) from the computational perspective.

######  Remark 2.3.

A similar reformulation to (PSDP-${\mathbb{R}}$’) but for a restricted class
of complex SDP relaxations of multiple-input multiple-output detection has
appeared in [9].

##  3 Application to complex SDP relaxations for CPOPs

In this section, we apply the reformulation (PSDP-${\mathbb{R}}$’) to complex
SDP relaxations arising from the complex moment-HSOS hierarchy for CPOPs. A
CPOP is given by

(CPOP)
$\begin{cases}\inf\limits_{{\mathbf{z}}\in{\mathbb{C}}^{s}}&f({\mathbf{z}},\overline{{\mathbf{z}}})=\sum_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}b_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}{\mathbf{z}}^{{\boldsymbol{\beta}}}\overline{{\mathbf{z}}}^{{\boldsymbol{\gamma}}}\\\
\,\,\rm{s.t.}&g_{i}({\mathbf{z}},\overline{{\mathbf{z}}})=\sum_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}g^{i}_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}{\mathbf{z}}^{{\boldsymbol{\beta}}}\overline{{\mathbf{z}}}^{{\boldsymbol{\gamma}}}\geq
0,\quad i\in[t],\end{cases}$

where
$\overline{{\mathbf{z}}}\coloneqq(\overline{z}_{1},\ldots,\overline{z}_{s})$
stands for the conjugate of complex variables
${\mathbf{z}}\coloneqq(z_{1},\ldots,z_{s})$. The functions
$f,g_{1},\ldots,g_{t}$ are real-valued polynomials and their coefficients
satisfy
$b_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}=\overline{b_{{\boldsymbol{\gamma}},{\boldsymbol{\beta}}}}$,
$g^{i}_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}=\overline{g^{i}_{{\boldsymbol{\gamma}},{\boldsymbol{\beta}}}}$.
The _support_ of $f$ is defined by
$\hbox{\rm{supp}}(f)\coloneqq\\{({\boldsymbol{\beta}},{\boldsymbol{\gamma}})\mid
b_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}\neq 0\\}$. For $i\in[t]$,
$\hbox{\rm{supp}}(g^{i})$ is defined in the same way.

Fix $d\in{\mathbb{N}}$. Let
$y=(y_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}})_{({\boldsymbol{\beta}},{\boldsymbol{\gamma}})\in{\mathbb{N}}_{d}^{n}\times{\mathbb{N}}_{d}^{n}}\subseteq{\mathbb{C}}$
be a sequence indexed by
$({\boldsymbol{\beta}},{\boldsymbol{\gamma}})\in{\mathbb{N}}_{d}^{n}\times{\mathbb{N}}_{d}^{n}$
and satisfying
$y_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}=\overline{y_{{\boldsymbol{\gamma}},{\boldsymbol{\beta}}}}$.
Let $L_{y}$ be the linear functional defined by

$f=\sum_{({\boldsymbol{\beta}},{\boldsymbol{\gamma}})}b_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}{\mathbf{z}}^{{\boldsymbol{\beta}}}\overline{{\mathbf{z}}}^{{\boldsymbol{\gamma}}}\mapsto
L_{y}(f)=\sum_{({\boldsymbol{\beta}},{\boldsymbol{\gamma}})}b_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}y_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}.$

The _complex moment_ matrix ${\mathbf{M}}_{d}(y)$ associated with $y$ is the
matrix indexed by ${\mathbb{N}}^{s}_{d}$ such that

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

Suppose that
$g=\sum_{({\boldsymbol{\beta}}^{\prime},{\boldsymbol{\gamma}}^{\prime})}g_{{\boldsymbol{\beta}}^{\prime},{\boldsymbol{\gamma}}^{\prime}}{\mathbf{z}}^{{\boldsymbol{\beta}}^{\prime}}\overline{{\mathbf{z}}}^{{\boldsymbol{\gamma}}^{\prime}}$
is a complex polynomial. The _complex localizing_ matrix
${\mathbf{M}}_{d}(gy)$ associated with $g$ and $y$ is the matrix indexed by
${\mathbb{N}}^{s}_{d}$ such that

$[{\mathbf{M}}_{d}(gy)]_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}\coloneqq
L_{y}(g{\mathbf{z}}^{{\boldsymbol{\beta}}}\overline{{\mathbf{z}}}^{{\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}}^{s}_{d}.$

For convenience let us set $g_{0}\coloneqq 1$. Let
$d_{i}\coloneqq\lceil\deg(g_{i})/2\rceil$ for $i=0,1,\ldots,t$ and let
$d_{\min}\coloneqq\max\,\\{\lceil\deg(f)/2\rceil,d_{1},\ldots,d_{t}\\}$. For
any $d\geq d_{\min}$, the $d$-th ($d$ is called the _relaxation order_)
complex moment relaxation for (CPOP) is given by

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

(Mom-${\mathbb{C}}$) and its dual form the complex moment-HSOS hierarchy of
(CPOP). For more details on this hierarchy, we refer the reader to [8, 13].

For any
$({\boldsymbol{\beta}},{\boldsymbol{\gamma}})\in{\mathbb{N}}^{s}_{d}\times{\mathbb{N}}^{s}_{d}$,
we associate it with a matrix
$A^{0}_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}\in{\mathbb{R}}^{\omega_{s,d}\times\omega_{s,d}}$
defined by

(3)
$[A^{0}_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}]_{{\boldsymbol{\beta}}^{\prime},{\boldsymbol{\gamma}}^{\prime}}=\begin{cases}1,&\text{if
}({\boldsymbol{\beta}}^{\prime},{\boldsymbol{\gamma}}^{\prime})=({\boldsymbol{\beta}},{\boldsymbol{\gamma}}),\\\
0,&\text{otherwise}.\end{cases}$

Moreover, for each $i\in[t]$, we associate any
$({\boldsymbol{\beta}},{\boldsymbol{\gamma}})\in{\mathbb{N}}^{s}_{d-d_{i}}\times{\mathbb{N}}^{s}_{d-d_{i}}$
with a matrix
$A^{i}_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}\in{\mathbb{C}}^{\omega_{s,d-d_{i}}\times\omega_{s,d-d_{i}}}$
defined by

(4)
$[A^{i}_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}]_{{\boldsymbol{\beta}}^{\prime},{\boldsymbol{\gamma}}^{\prime}}=\begin{cases}g^{i}_{{\boldsymbol{\beta}}^{\prime\prime},{\boldsymbol{\gamma}}^{\prime\prime}},&\text{if
}({\boldsymbol{\beta}}^{\prime}+{\boldsymbol{\beta}}^{\prime\prime},{\boldsymbol{\gamma}}^{\prime}+{\boldsymbol{\gamma}}^{\prime\prime})=({\boldsymbol{\beta}},{\boldsymbol{\gamma}}),\\\
0,&\text{otherwise}.\end{cases}$

Now for each $i=0,1,\ldots,t$, we define the linear operator
${\mathscr{A}}^{i}$ by

${\mathscr{A}}^{i}(H)\coloneqq\left(\langle
A^{i}_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}},H\rangle\right)_{({\boldsymbol{\beta}},{\boldsymbol{\gamma}})\in{\mathbb{N}}^{s}_{d-d_{i}}\times{\mathbb{N}}^{s}_{d-d_{i}}},\quad
H\in{\mathbf{H}}^{\omega_{s,d-d_{i}}}.$

By construction, it holds

${\mathbf{M}}_{d-d_{i}}(g_{i}y)=\sum_{({\boldsymbol{\beta}},{\boldsymbol{\gamma}})\in{\mathbb{N}}^{s}_{d-d_{i}}\times{\mathbb{N}}^{s}_{d-d_{i}}}A_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}^{i}y_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}=({\mathscr{A}}^{i})^{*}(y),\quad
i=0,1,\ldots,t.$

Therefore, we can rewrite (Mom-${\mathbb{C}}$) as follows:

(Mom-${\mathbb{C}}$’) $\begin{cases}\inf\limits_{y}&b^{\intercal}y\\\
\rm{s.t.}&({\mathscr{A}}^{i})^{*}(y)\succeq 0,\quad i=0,1,\ldots,t,\\\
&y_{\mathbf{0},\mathbf{0}}=1,\end{cases}$

whose dual reads as

(HSOS-${\mathbb{C}}$) $\begin{cases}\sup\limits_{\lambda,H^{i}}&\lambda\\\
\,\rm{s.t.}&\sum_{i=0}^{t}[{\mathscr{A}}^{i}(H^{i})]_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}+\delta_{({\boldsymbol{\beta}},{\boldsymbol{\gamma}}),(\mathbf{0},\mathbf{0})}\lambda=b_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}},\quad({\boldsymbol{\beta}},{\boldsymbol{\gamma}})\in{\mathbb{N}}^{s}_{d}\times{\mathbb{N}}^{s}_{d},\\\
&H^{i}\succeq 0,\quad i=0,1,\ldots,t.\end{cases}$

Note that we have used the Kronecker delta
$\delta_{({\boldsymbol{\beta}},{\boldsymbol{\gamma}}),(\mathbf{0},\mathbf{0})}$
in (HSOS-${\mathbb{C}}$).

Let us fix any order “$<$” on ${\mathbb{N}}^{s}$.

######  Proposition 3.1.

(HSOS-${\mathbb{C}}$) is equivalent to the following complex SDP:

(HSOS-${\mathbb{C}}$’) $\begin{cases}\sup\limits_{\lambda,H^{i}}&\lambda\\\
\,\rm{s.t.}&\sum_{i=0}^{t}[{\mathscr{A}}^{i}(H^{i})]_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}+\delta_{({\boldsymbol{\beta}},{\boldsymbol{\gamma}}),(\mathbf{0},\mathbf{0})}\lambda=b_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}},\\\
&{\boldsymbol{\beta}}\leq{\boldsymbol{\gamma}},\quad({\boldsymbol{\beta}},{\boldsymbol{\gamma}})\in{\mathbb{N}}^{s}_{d}\times{\mathbb{N}}^{s}_{d},\\\
&H^{i}\succeq 0,\quad i=0,1,\ldots,t.\end{cases}$

######  Proof 3.2.

It suffices to show that for ${\boldsymbol{\beta}}<{\boldsymbol{\gamma}}$,
$\sum_{i=0}^{t}[{\mathscr{A}}^{i}(H^{i})]_{{\boldsymbol{\gamma}},{\boldsymbol{\beta}}}=b_{{\boldsymbol{\gamma}},{\boldsymbol{\beta}}}$
is equivalent to
$\sum_{i=0}^{t}[{\mathscr{A}}^{i}(H^{i})]_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}=b_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}$.
Indeed, this equivalence follows from
$b_{{\boldsymbol{\gamma}},{\boldsymbol{\beta}}}=\overline{b_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}}$
and

$\displaystyle\sum_{i=0}^{t}[{\mathscr{A}}^{i}(H^{i})]_{{\boldsymbol{\gamma}},{\boldsymbol{\beta}}}$
$\displaystyle=\sum_{i=0}^{t}\langle
A^{i}_{{\boldsymbol{\gamma}},{\boldsymbol{\beta}}},H^{i}\rangle$
$\displaystyle=[H^{0}]_{{\boldsymbol{\gamma}},{\boldsymbol{\beta}}}+\sum_{i=1}^{t}\sum_{\begin{subarray}{c}({\boldsymbol{\gamma}}^{\prime},{\boldsymbol{\beta}}^{\prime})\in{\mathbb{N}}^{s}_{d-d_{i}}\times{\mathbb{N}}^{s}_{d-d_{i}}\\\
({\boldsymbol{\gamma}}^{\prime\prime},{\boldsymbol{\beta}}^{\prime\prime})\in\hbox{\rm{supp}}(g)\\\
({\boldsymbol{\gamma}}^{\prime}+{\boldsymbol{\gamma}}^{\prime\prime},{\boldsymbol{\beta}}^{\prime}+{\boldsymbol{\beta}}^{\prime\prime})=({\boldsymbol{\gamma}},{\boldsymbol{\beta}})\end{subarray}}g^{i}_{{\boldsymbol{\gamma}}^{\prime\prime},{\boldsymbol{\beta}}^{\prime\prime}}[H^{i}]_{{\boldsymbol{\gamma}}^{\prime},{\boldsymbol{\beta}}^{\prime}}$
$\displaystyle=\sum_{i=0}^{t}\langle\overline{A^{i}_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}},H^{i}\rangle=\sum_{i=0}^{t}\overline{[{\mathscr{A}}^{i}(H^{i})]_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}}.$

With
${\mathscr{A}}^{i}={\mathscr{A}}^{i}_{R}+{\mathscr{A}}^{i}_{I}\hbox{\bf{i}},H^{i}=H^{i}_{R}+H^{i}_{I}\hbox{\bf{i}},b=b_{R}+b_{I}\hbox{\bf{i}}$,
(HSOS-${\mathbb{C}}$’) is equivalent to the following real SDP:

(HSOS-${\mathbb{R}}$) $\begin{cases}\sup\limits_{\lambda,Y^{i}}&\lambda\\\
\,\rm{s.t.}&\sum_{i=0}^{t}\left([{\mathscr{A}}^{i}_{R}(H^{i}_{R})]_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}-[{\mathscr{A}}^{i}_{I}(H^{i}_{I})]_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}\right)+\delta_{({\boldsymbol{\beta}},{\boldsymbol{\gamma}}),(\mathbf{0},\mathbf{0})}\lambda=[b_{R}]_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}},\\\
&\sum_{i=0}^{t}\left([{\mathscr{A}}^{i}_{R}(H^{i}_{I})]_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}+[{\mathscr{A}}^{i}_{I}(H^{i}_{R})]_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}\right)=[b_{I}]_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}},\\\
&{\boldsymbol{\beta}}\leq{\boldsymbol{\gamma}},\quad({\boldsymbol{\beta}},{\boldsymbol{\gamma}})\in{\mathbb{N}}^{s}_{d}\times{\mathbb{N}}^{s}_{d},\\\
&Y^{i}=\begin{bmatrix}H^{i}_{R}&-H^{i}_{I}\\\
H^{i}_{I}&H^{i}_{R}\end{bmatrix}\succeq 0,\quad i=0,1,\ldots,t.\end{cases}$

On the other hand, by invoking Theorem 2.1 to (HSOS-${\mathbb{C}}$’), we
obtain another equivalent real SDP of (HSOS-${\mathbb{C}}$’):

(5) $\begin{cases}\sup\limits_{\lambda,X^{i}}&\lambda\\\
\,\rm{s.t.}&\sum_{i=0}^{t}\left([{\mathscr{A}}^{i}_{R}(X^{i}_{1}+X^{i}_{2})]_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}-[{\mathscr{A}}^{i}_{I}(X^{i}_{3}-(X^{i}_{3})^{\intercal})]_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}\right)+\delta_{({\boldsymbol{\beta}},{\boldsymbol{\gamma}}),(\mathbf{0},\mathbf{0})}\lambda=[b_{R}]_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}},\\\
&\sum_{i=0}^{t}\left([{\mathscr{A}}^{i}_{R}(X^{i}_{3}-(X^{i}_{3})^{\intercal})]_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}+[{\mathscr{A}}^{i}_{I}(X^{i}_{1}+X^{i}_{2})]_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}\right)=[b_{I}]_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}},\\\
&{\boldsymbol{\beta}}\leq{\boldsymbol{\gamma}},\quad({\boldsymbol{\beta}},{\boldsymbol{\gamma}})\in{\mathbb{N}}^{s}_{d}\times{\mathbb{N}}^{s}_{d},\\\
&X^{i}=\begin{bmatrix}X^{i}_{1}&X^{i}_{3}\\\
(X^{i}_{3})^{\intercal}&X^{i}_{2}\end{bmatrix}\succeq 0,\quad
i=0,1,\ldots,t.\end{cases}$

######  Proposition 3.3.

(5) is equivalent to the following real SDP:

(HSOS-${\mathbb{R}}$’) $\begin{cases}\sup\limits_{\lambda,X^{i}}&\lambda\\\
\,\rm{s.t.}&\sum_{i=0}^{t}\left([{\mathscr{A}}^{i}_{R}(X^{i}_{1}+X^{i}_{2})]_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}-[{\mathscr{A}}^{i}_{I}(X^{i}_{3}-(X^{i}_{3})^{\intercal})]_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}\right)+\delta_{({\boldsymbol{\beta}},{\boldsymbol{\gamma}}),(\mathbf{0},\mathbf{0})}\lambda=[b_{R}]_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}},\\\
&\sum_{i=0}^{t}\left([{\mathscr{A}}^{i}_{R}(X^{i}_{3}-(X^{i}_{3})^{\intercal})]_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}+[{\mathscr{A}}^{i}_{I}(X^{i}_{1}+X^{i}_{2})]_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}}\right)=[b_{I}]_{{\boldsymbol{\beta}},{\boldsymbol{\gamma}}},\quad{\boldsymbol{\beta}}\neq{\boldsymbol{\gamma}},\\\
&{\boldsymbol{\beta}}\leq{\boldsymbol{\gamma}},\quad({\boldsymbol{\beta}},{\boldsymbol{\gamma}})\in{\mathbb{N}}^{s}_{d}\times{\mathbb{N}}^{s}_{d},\\\
&X^{i}=\begin{bmatrix}X^{i}_{1}&X^{i}_{3}\\\
(X^{i}_{3})^{\intercal}&X^{i}_{2}\end{bmatrix}\succeq 0,\quad
i=0,1,\ldots,t.\end{cases}$

######  Proof 3.4.

We need to show that the following constraints

(6)
$\sum_{i=0}^{t}\left([{\mathscr{A}}^{i}_{R}(X^{i}_{3}-(X^{i}_{3})^{\intercal})]_{{\boldsymbol{\beta}},{\boldsymbol{\beta}}}+[{\mathscr{A}}^{i}_{I}(X^{i}_{1}+X^{i}_{2})]_{{\boldsymbol{\beta}},{\boldsymbol{\beta}}}\right)=[b_{I}]_{{\boldsymbol{\beta}},{\boldsymbol{\beta}}}=0,\quad{\boldsymbol{\beta}}\in{\mathbb{N}}^{s}_{d}$

in (5) are redundant. For each $i=0,1,\ldots,t$ and
${\boldsymbol{\beta}}\in{\mathbb{N}}^{s}_{d}$, we have

$\displaystyle\,\left\langle(A^{i}_{{\boldsymbol{\beta}},{\boldsymbol{\beta}}})_{R},X^{i}_{3}-(X^{i}_{3})^{\intercal}\right\rangle$
$\displaystyle=$
$\displaystyle\,\sum_{\begin{subarray}{c}({\boldsymbol{\beta}}^{\prime},{\boldsymbol{\gamma}}^{\prime})\in{\mathbb{N}}^{s}_{d-d_{i}}\times{\mathbb{N}}^{s}_{d-d_{i}}\\\
({\boldsymbol{\beta}}^{\prime\prime},{\boldsymbol{\gamma}}^{\prime\prime})\in\hbox{\rm{supp}}(g)\\\
({\boldsymbol{\beta}}^{\prime}+{\boldsymbol{\beta}}^{\prime\prime},{\boldsymbol{\gamma}}^{\prime}+{\boldsymbol{\gamma}}^{\prime\prime})=({\boldsymbol{\beta}},{\boldsymbol{\beta}})\end{subarray}}{\mathcal{R}}(g^{i}_{{\boldsymbol{\beta}}^{\prime\prime},{\boldsymbol{\gamma}}^{\prime\prime}})\left([X^{i}_{3}]_{{\boldsymbol{\beta}}^{\prime},{\boldsymbol{\gamma}}^{\prime}}-[(X^{i}_{3})^{\intercal}]_{{\boldsymbol{\beta}}^{\prime},{\boldsymbol{\gamma}}^{\prime}}\right)$
$\displaystyle=$
$\displaystyle\,\frac{1}{2}\sum_{\begin{subarray}{c}({\boldsymbol{\beta}}^{\prime},{\boldsymbol{\gamma}}^{\prime})\in{\mathbb{N}}^{s}_{d-d_{i}}\times{\mathbb{N}}^{s}_{d-d_{i}}\\\
({\boldsymbol{\beta}}^{\prime\prime},{\boldsymbol{\gamma}}^{\prime\prime})\in\hbox{\rm{supp}}(g)\\\
({\boldsymbol{\beta}}^{\prime}+{\boldsymbol{\beta}}^{\prime\prime},{\boldsymbol{\gamma}}^{\prime}+{\boldsymbol{\gamma}}^{\prime\prime})=({\boldsymbol{\beta}},{\boldsymbol{\beta}})\end{subarray}}{\mathcal{R}}(g^{i}_{{\boldsymbol{\beta}}^{\prime\prime},{\boldsymbol{\gamma}}^{\prime\prime}})\left([X^{i}_{3}]_{{\boldsymbol{\beta}}^{\prime},{\boldsymbol{\gamma}}^{\prime}}+[X^{i}_{3}]_{{\boldsymbol{\gamma}}^{\prime},{\boldsymbol{\beta}}^{\prime}}-[(X^{i}_{3})^{\intercal}]_{{\boldsymbol{\beta}}^{\prime},{\boldsymbol{\gamma}}^{\prime}}-[(X^{i}_{3})^{\intercal}]_{{\boldsymbol{\gamma}}^{\prime},{\boldsymbol{\beta}}^{\prime}}\right)$
$\displaystyle=$ $\displaystyle\,0,$

where we have used fact that
$[(X^{i}_{3})^{\intercal}]_{{\boldsymbol{\beta}}^{\prime},{\boldsymbol{\gamma}}^{\prime}}=[X^{i}_{3}]_{{\boldsymbol{\gamma}}^{\prime},{\boldsymbol{\beta}}^{\prime}}$
and
$[(X^{i}_{3})^{\intercal}]_{{\boldsymbol{\gamma}}^{\prime},{\boldsymbol{\beta}}^{\prime}}=[X^{i}_{3}]_{{\boldsymbol{\beta}}^{\prime},{\boldsymbol{\gamma}}^{\prime}}$.
It follows that
$[{\mathscr{A}}^{i}_{R}(X^{i}_{3}-(X^{i}_{3})^{\intercal})]_{{\boldsymbol{\beta}},{\boldsymbol{\beta}}}=\langle(A^{i}_{{\boldsymbol{\beta}},{\boldsymbol{\beta}}})_{R},X^{i}_{3}-(X^{i}_{3})^{\intercal}\rangle=0$.

In addition, for each $i=0,1,\ldots,t$ and
${\boldsymbol{\beta}}\in{\mathbb{N}}^{s}_{d}$, we have

$\displaystyle\,\left\langle(A^{i}_{{\boldsymbol{\beta}},{\boldsymbol{\beta}}})_{I},X^{i}_{1}+X^{i}_{2}\right\rangle$
$\displaystyle=$
$\displaystyle\,\sum_{\begin{subarray}{c}({\boldsymbol{\beta}}^{\prime},{\boldsymbol{\gamma}}^{\prime})\in{\mathbb{N}}^{s}_{d-d_{i}}\times{\mathbb{N}}^{s}_{d-d_{i}}\\\
({\boldsymbol{\beta}}^{\prime\prime},{\boldsymbol{\gamma}}^{\prime\prime})\in\hbox{\rm{supp}}(g)\\\
({\boldsymbol{\beta}}^{\prime}+{\boldsymbol{\beta}}^{\prime\prime},{\boldsymbol{\gamma}}^{\prime}+{\boldsymbol{\gamma}}^{\prime\prime})=({\boldsymbol{\beta}},{\boldsymbol{\beta}})\end{subarray}}{\mathcal{I}}(g^{i}_{{\boldsymbol{\beta}}^{\prime\prime},{\boldsymbol{\gamma}}^{\prime\prime}})\left([X^{i}_{1}]_{{\boldsymbol{\beta}}^{\prime},{\boldsymbol{\gamma}}^{\prime}}+[X^{i}_{2}]_{{\boldsymbol{\beta}}^{\prime},{\boldsymbol{\gamma}}^{\prime}}\right)$
$\displaystyle=$
$\displaystyle\,\frac{1}{2}\sum_{\begin{subarray}{c}({\boldsymbol{\beta}}^{\prime},{\boldsymbol{\gamma}}^{\prime})\in{\mathbb{N}}^{s}_{d-d_{i}}\times{\mathbb{N}}^{s}_{d-d_{i}}\\\
({\boldsymbol{\beta}}^{\prime\prime},{\boldsymbol{\gamma}}^{\prime\prime})\in\hbox{\rm{supp}}(g)\\\
({\boldsymbol{\beta}}^{\prime}+{\boldsymbol{\beta}}^{\prime\prime},{\boldsymbol{\gamma}}^{\prime}+{\boldsymbol{\gamma}}^{\prime\prime})=({\boldsymbol{\beta}},{\boldsymbol{\beta}})\end{subarray}}{\mathcal{I}}\left(g^{i}_{{\boldsymbol{\beta}}^{\prime\prime},{\boldsymbol{\gamma}}^{\prime\prime}}+g^{i}_{{\boldsymbol{\gamma}}^{\prime\prime},{\boldsymbol{\beta}}^{\prime\prime}}\right)\left([X^{i}_{1}]_{{\boldsymbol{\beta}}^{\prime},{\boldsymbol{\gamma}}^{\prime}}+[X^{i}_{2}]_{{\boldsymbol{\beta}}^{\prime},{\boldsymbol{\gamma}}^{\prime}}\right)$
$\displaystyle=$ $\displaystyle\,0,$

where we have used fact that
${\mathcal{I}}(g^{i}_{{\boldsymbol{\beta}}^{\prime\prime},{\boldsymbol{\gamma}}^{\prime\prime}}+g^{i}_{{\boldsymbol{\gamma}}^{\prime\prime},{\boldsymbol{\beta}}^{\prime\prime}})={\mathcal{I}}(g^{i}_{{\boldsymbol{\beta}}^{\prime\prime},{\boldsymbol{\gamma}}^{\prime\prime}}+\overline{g}^{i}_{{\boldsymbol{\beta}}^{\prime\prime},{\boldsymbol{\gamma}}^{\prime\prime}})=0$
and $X^{i}_{1},X^{i}_{2}$ are symmetric. It follows that
$[{\mathscr{A}}^{i}_{I}(X^{i}_{1}+X^{i}_{2})]_{{\boldsymbol{\beta}},{\boldsymbol{\beta}}}=\langle(A^{i}_{{\boldsymbol{\beta}},{\boldsymbol{\beta}}})_{I},X^{i}_{1}+X^{i}_{2}\rangle=0$.

Putting all above together yields (6).

Now we can give the following theorem.

######  Theorem 3.5.

(HSOS-${\mathbb{R}}$’) is equivalent to (HSOS-${\mathbb{C}}$).

Before closing the section, we compare complexity of different real SDP
reformulations for complex SDP relaxations of (CPOP) in Table 1.

Table 1: Comparison of complexity of different real SDP reformulations for complex SDP relaxations of (CPOP). $n_{\rm{sdp}}$: the maximal size of SDP matrix, $m_{\rm{sdp}}$: the number of affine constraints. | (HSOS-${\mathbb{R}}$) | (HSOS-${\mathbb{R}}$’)
---|---|---
$n_{\rm{sdp}}$ | $2\omega_{s,d}$ | $2\omega_{s,d}$
$m_{\rm{sdp}}$ | $2\omega_{s,d}^{2}+2\omega_{s,d}+\sum_{i=1}^{t}\omega_{s,d-d_{i}}$ | $\omega_{s,d}^{2}$

##  4 Numerical experiments

In this section, we compare the performance of the two formulations for
complex SDPs arising from the complex moment-HSOS hierarchy of CPOPs using the
software TSSOS222TSSOS is freely available at
https://github.com/wangjie212/TSSOS. in which MOSEK 10.0 [1] is employed as an
SDP solver with default settings. All numerical experiments were performed on
a desktop computer with Intel(R) Core(TM) i9-10900<EMAIL_ADDRESS>and 64G RAM. In
presenting the results, the column labelled by ‘opt’ records the optimum and
the column labelled by ‘time’ records running time in seconds. Moreover, the
symbol ‘-’ means the SDP solver runs out of memory.

###  4.1 Minimizing a random complex quartic polynomial over the unit sphere

Our first example is to minimize a complex quartic polynomial over the unit
sphere:

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

where $[{\mathbf{z}}]_{2}$ is the vector of monomials in ${\mathbf{z}}$ up to
degree two and $Q\in{\mathbf{H}}^{|[{\mathbf{z}}]_{2}|}$ is a random Hermitian
matrix whose entries are selected with respect to the standard normal
distribution.

We approach (7) for $s=5,7,\ldots,15$ with the second and third HSOS
relaxations. The related results are shown in Table 2. From the table, we see
that the reformulation (HSOS-${\mathbb{R}}$’) is several ($2\sim 7$) times as
fast as the reformulation (HSOS-${\mathbb{R}}$), and the speedup is more
significant as the SDP size grows.

Table 2: Minimizing a random complex quartic polynomial over the unit sphere. $s$ | $d$ | $n_{\rm{sdp}}$ | (HSOS-${\mathbb{R}}$) | (HSOS-${\mathbb{R}}$’)
---|---|---|---|---
$m_{\rm{sdp}}$ | opt | time | $m_{\rm{sdp}}$ | opt | time
5 | 2 | 42 | 966 | -11.2409 | 0.11 | 441 | -11.2409 | 0.05
3 | 112 | 6846 | -9.47725 | 8.13 | 3136 | -9.47725 | 2.00
7 | 2 | 72 | 2736 | -14.2314 | 0.97 | 1296 | -14.2314 | 0.28
3 | 240 | 30372 | -11.0407 | 389 | 14400 | -11.0407 | 57.0
9 | 2 | 110 | 6270 | -19.0019 | 5.73 | 3025 | -19.0019 | 1.62
3 | 440 | 100320 | - | - | 48400 | -15.5614 | 1944
11 | 2 | 156 | 12480 | -22.8630 | 31.7 | 6084 | -22.8630 | 6.67
3 | 728 | 271882 | - | - | 132496 | - | -
13 | 2 | 210 | 22470 | -25.6352 | 145 | 11025 | -25.6352 | 23.5
3 | 1120 | 639450 | - | - | 313600 | - | -
15 | 2 | 272 | 37536 | -29.1672 | 585 | 18496 | -29.1672 | 86.1
3 | 1632 | 1351976 | - | - | 665856 | - | -

###  4.2 Minimizing a random complex quartic polynomial with unit-norm
variables

The second example is to minimize a random complex quartic polynomial with
unit-norm variables:

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

where $Q\in{\mathbf{H}}^{|[{\mathbf{z}}]_{2}|}$ is a random Hermitian matrix
whose entries are selected with respect to the uniform probability
distribution on $[0,1]$.

We approach (8) for $s=5,7,\ldots,15$ with the second and third HSOS
relaxations. The related results are shown in Table 3. From the table, we see
that the reformulation (HSOS-${\mathbb{R}}$’) is about one magnitude faster
than the reformulation (HSOS-${\mathbb{R}}$), and the speedup is more
significant as the SDP size grows.

Table 3: Minimizing a random complex quartic polynomial with unit-norm variables. $s$ | $d$ | $n_{\rm{sdp}}$ | (HSOS-${\mathbb{R}}$) | (HSOS-${\mathbb{R}}$’)
---|---|---|---|---
$m_{\rm{sdp}}$ | opt | time | $m_{\rm{sdp}}$ | opt | time
5 | 2 | 42 | 734 | -24.4919 | 0.10 | 271 | -24.4919 | 0.03
3 | 112 | 4474 | -24.4919 | 2.34 | 1281 | -24.4919 | 0.26
7 | 2 | 72 | 2202 | -56.5289 | 0.65 | 869 | -56.5289 | 0.16
3 | 240 | 21158 | -46.7128 | 132 | 6637 | -46.7128 | 7.44
9 | 2 | 110 | 5242 | -114.342 | 4.62 | 2161 | -114.342 | 0.73
3 | 440 | 73312 | - | - | 24691 | -81.2676 | 184
11 | 2 | 156 | 10718 | -202.436 | 32.1 | 4555 | -202.436 | 3.86
3 | 728 | 206188 | - | - | 73327 | - | -
13 | 2 | 210 | 19686 | -338.041 | 126 | 8555 | -338.041 | 12.7
3 | 1120 | 499438 | - | - | 185277 | - | -
15 | 2 | 272 | 33394 | -514.226 | 678 | 14761 | -514.226 | 55.1
3 | 1632 | 1081514 | - | - | 414841 | - | -

###  4.3 Minimizing a randomly generated sparse complex quartic polynomial
over multi-spheres

Given $l\in{\mathbb{N}}\backslash\\{0\\}$, we randomly generate a sparse
complex quartic polynomial as follows: Let
$f=\sum_{i=1}^{l}f_{i}\in{\mathbb{C}}[z_{1},\ldots,z_{5(l+1)},\overline{z}_{1},\ldots,\overline{z}_{5(l+1)}]$,333${\mathbb{C}}[{\mathbf{z}},\overline{{\mathbf{z}}}]$
denotes the ring of complex polynomials in variables
${\mathbf{z}},\overline{{\mathbf{z}}}$. where for all $i\in[l]$,
$f_{i}=\overline{f}_{i}\in{\mathbb{C}}[z_{5(i-1)+1},\ldots,z_{5(i-1)+10},\overline{z}_{5(i-1)+1},\ldots,\overline{z}_{5(i-1)+10}]$
is a sparse complex quartic polynomial whose coefficients (real/imaginary
parts) are selected with respect to the uniform probability distribution on
$[-1,1]$. Then we consider the following CPOP:

(9)
$\begin{cases}\inf\limits_{{\mathbf{z}}\in{\mathbb{C}}^{5(l+1)}}&f({\mathbf{z}},\overline{{\mathbf{z}}})\\\
\,\quad\rm{s.t.}&\sum_{j=1}^{10}|z_{5(i-1)+j}|^{2}=1,\quad
i=1,\ldots,l.\end{cases}$

The sparsity in (9) can be exploited to derive a sparsity-adapted complex
moment-HSOS hierarchy [13]. We solve the second sparse HSOS relaxation of (9)
for $l=40,80,\ldots,400$. The results are displayed in Table 4. From the table
we see that the reformulation (HSOS-${\mathbb{R}}$’) is $1.5\sim 2$ times as
fast as the reformulation (HSOS-${\mathbb{R}}$).

Table 4: Minimizing a randomly generated sparse complex quartic polynomial over multi-spheres. $l$ | $n_{\rm{sdp}}$ | (HSOS-${\mathbb{R}}$) | (HSOS-${\mathbb{R}}$’)
---|---|---|---
$m_{\rm{sdp}}$ | opt | time | $m_{\rm{sdp}}$ | opt | time
40 | 8 | 23090 | -98.9240 | 3.12 | 12529 | -98.9240 | 2.06
80 | 8 | 46768 | -197.577 | 12.6 | 25549 | -197.577 | 8.07
120 | 8 | 70958 | -292.024 | 30.1 | 38871 | -292.024 | 19.0
160 | 8 | 94278 | -389.652 | 45.9 | 51563 | -389.652 | 30.7
200 | 8 | 117526 | -482.684 | 84.5 | 64185 | -482.684 | 37.7
240 | 8 | 140298 | -578.896 | 130 | 76389 | -578.896 | 59.5
280 | 8 | 162504 | -671.047 | 173 | 89241 | -671.047 | 65.4
320 | 8 | 187528 | -766.403 | 206 | 102171 | -766.403 | 88.5
360 | 8 | 210370 | -866.771 | 291 | 114589 | -866.771 | 147
400 | 8 | 233396 | -963.137 | 297 | 127173 | -963.137 | 138

###  4.4 The AC-OPF problem

The alternating current 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 physical and operational constraints.
Mathematically, it can be formulated as the following CPOP:

(10) $\begin{cases}\inf\limits_{V_{i},S_{k}^{g}}&\sum_{k\in
G}\left(\mathbf{c}_{2k}({\mathcal{R}}(S_{k}^{g}))^{2}+\mathbf{c}_{1k}{\mathcal{R}}(S_{k}^{g})+\mathbf{c}_{0k}\right)\\\
\,\,\,\textrm{s.t.}&\angle V_{r}=0,\\\ &\mathbf{S}_{k}^{gl}\leq
S_{k}^{g}\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,\\\ &\sum_{k\in
G_{i}}S_{k}^{g}-\mathbf{S}_{i}^{d}-\mathbf{Y}_{i}^{sh}|V_{i}|^{2}=\sum_{(i,j)\in
E_{i}\cup E_{i}^{R}}S_{ij},\quad\forall i\in N,\\\
&S_{ij}=(\overline{\mathbf{Y}}_{ij}-\mathbf{i}\frac{\mathbf{b}_{ij}^{c}}{2})\frac{|V_{i}|^{2}}{|\mathbf{T}_{ij}|^{2}}-\overline{\mathbf{Y}}_{ij}\frac{V_{i}\overline{V}_{j}}{\mathbf{T}_{ij}},\quad\forall(i,j)\in
E,\\\
&S_{ji}=(\overline{\mathbf{Y}}_{ij}-\mathbf{i}\frac{\mathbf{b}_{ij}^{c}}{2})|V_{j}|^{2}-\overline{\mathbf{Y}}_{ij}\frac{\overline{V}_{i}V_{j}}{\overline{\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}\overline{V}_{j})\leq\boldsymbol{\theta}_{ij}^{\Delta
u},\quad\forall(i,j)\in E,\\\ \end{cases}$

where $V_{i}$ is the voltage, $S_{k}^{g}$ is the power generation, $S_{ij}$ is
the power flow (all are complex variables; $\angle\cdot$ stands for the angle
of a complex number) and all symbols in boldface are constants. Notice that
$G$ is the collection of generators and $N$ is the collection of buses. For a
full description on the AC-OPF problem, we refer the reader to [3] as well as
[5].

We select test cases from the AC-OPF library PGLiB-OPF [3]. For each case, we
solve the minimal relaxation step of the sparse HSOS hierarchy [13]. The
results are displayed in Table 5. From the table, we see that the
reformulation (HSOS-${\mathbb{R}}$’) is several ($1.4\sim 5$) times as fast as
the reformulation (HSOS-${\mathbb{R}}$).

Table 5: The results for the AC-OPF problem. $s$: the number of CPOP
variables; $t$: the number of CPOP constraints.

Case | $s$ | $t$ | $n_{\rm{sdp}}$ | (HSOS-${\mathbb{R}}$) | (HSOS-${\mathbb{R}}$’)
---|---|---|---|---|---
$m_{\rm{sdp}}$ | opt | time | $m_{\rm{sdp}}$ | opt | time
14_ieee | 19 | 147 | 14 | 2346 | $1.9940\text{e}3$ | 0.19 | 422 | $1.9940\text{e}3$ | 0.10
30_ieee | 36 | 297 | 12 | 4828 | $8.1959\text{e}3$ | 0.73 | 836 | $8.1960\text{e}3$ | 0.37
30_as | 36 | 297 | 12 | 4828 | $5.0371\text{e}2$ | 0.55 | 836 | $5.0371\text{e}2$ | 0.24
39_epri | 49 | 361 | 14 | 5270 | $1.3568\text{e}5$ | 0.74 | 966 | $1.3579\text{e}5$ | 0.54
89_pegase | 101 | 1221 | 96 | 57888 | $9.4098\text{e}4$ | 63.6 | 10262 | $9.4101\text{e}4$ | 15.1
57_ieee | 64 | 563 | 24 | 11102 | $3.6644\text{e}4$ | 2.36 | 2008 | $3.6644\text{e}4$ | 1.06
118_ieee | 172 | 1325 | 20 | 25374 | $9.3216\text{e}4$ | 8.27 | 4471 | $9.3216\text{e}4$ | 2.68
162_ieee_dtc | 174 | 1809 | 40 | 64874 | $1.0492\text{e}5$ | 43.4 | 11327 | $1.0495\text{e}5$ | 13.8
179_goc | 208 | 1827 | 20 | 25712 | $6.0859\text{e}5$ | 10.3 | 4368 | $6.0860\text{e}5$ | 3.57
240_pserc | 383 | 3039 | 24 | 52172 | $2.8153\text{e}6$ | 31.9 | 9243 | $2.8170\text{e}6$ | 10.7
300_ieee | 369 | 2983 | 22 | 53946 | $5.3037\text{e}5$ | 40.6 | 9647 | $5.3037\text{e}5$ | 10.6
500_goc | 671 | 5255 | 24 | 90502 | $3.9697\text{e}5$ | 89.8 | 15918 | $3.9697\text{e}5$ | 25.4
588_sdet | 683 | 5287 | 16 | 79362 | $1.9799\text{e}5$ | 91.7 | 13933 | $1.9749\text{e}5$ | 21.3
793_goc | 890 | 7019 | 16 | 104978 | $1.1194\text{e}5$ | 105 | 18536 | $1.1222\text{e}5$ | 31.5
1888_rte | 2178 | 18257 | 30 | 280580 | $1.2537\text{e}6$ | 939 | 47205 | $1.2545\text{e}6$ | 180
2000_goc | 2238 | 23009 | 34 | 455530 | $9.1876\text{e}5$ | 2087 | 77974 | $9.1881\text{e}5$ | 439

## Acknowledgments

The authors would like to thank Jurij Volčič for helpful comments on an
earlier preprint of this note.

## 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] M. Araújo, M. Huber, M. Navascués, M. Pivoluska, and A. Tavakoli, Quantum key distribution rates from semidefinite programming, Quantum, 7 (2023), p. 1019.
  * [3] 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).
  * [4] J. Bae and L.-C. Kwek, Quantum state discrimination and its applications, Journal of Physics A: Mathematical and Theoretical, 48 (2015), p. 083001.
  * [5] D. Bienstock, M. Escobar, C. Gentile, and L. Liberti, Mathematical programming formulations for the alternating current optimal power flow problem, 4OR, 18 (2020), pp. 249–292.
  * [6] C. Coey, L. Kapelevich, and J. P. Vielma, Solving natural conic formulations with Hypatia.jl, INFORMS Journal on Computing, 34 (2022), pp. 2686–2699, https://doi.org/https://doi.org/10.1287/ijoc.2022.1202.
  * [7] M. X. Goemans and D. Williamson, Approximation algorithms for max-3-cut and other problems via complex semidefinite programming, in Proceedings of the thirty-third annual ACM symposium on Theory of computing, 2001, pp. 443–452.
  * [8] 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.
  * [9] C. Lu, Y.-F. Liu, W.-Q. Zhang, and S. Zhang, Tightness of a new and enhanced semidefinite relaxation for mimo detection, SIAM Journal on Optimization, 29 (2019), pp. 719–742.
  * [10] A. Oustry, C. D’Ambrosio, L. Liberti, and M. Ruiz, Certified and accurate sdp bounds for the acopf problem, Electric Power Systems Research, 212 (2022), p. 108278.
  * [11] J. F. Sturm, Using sedumi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optimization Methods and Software, 11 (1999), pp. 625–653, https://doi.org/10.1080/10556789908805766, https://doi.org/10.1080/10556789908805766.
  * [12] I. Waldspurger, A. d’Aspremont, and S. Mallat, Phase recovery, maxcut and complex semidefinite programming, Mathematical Programming, 149 (2015), pp. 47–81.
  * [13] J. Wang and V. Magron, Exploiting sparsity in complex polynomial optimization, Journal of Optimization Theory and Applications, 192 (2022), pp. 335–359.
  * [14] J. Watrous, Semidefinite programs for completely bounded norms, arXiv preprint arXiv:0901.4709, (2009).