# Iterative Inner/outer Approximations for Scalable Semidefinite Programs
using Block Factor-width-two Matrices

Feng-Yi Liao and Yang Zheng† †F. Liao and Y. Zheng are with ECE Department,
University of California, San Diego. Emails<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In this paper, we propose iterative inner/outer approximations based on a
recent notion of block factor-width-two matrices for solving semidefinite
programs (SDPs). Our inner/outer approximating algorithms generate a sequence
of upper/lower bounds of increasing accuracy for the optimal SDP cost. The
block partition in our algorithms offers flexibility in terms of both
numerical efficiency and solution quality, which includes the approach of
scaled diagonally dominance (SDD) approximation as a special case. We discuss
both the theoretical results and numerical implementation in detail. Our main
theorems guarantee that the proposed iterative algorithms generate
monotonically decreasing upper (increasing lower) bounds. Extensive numerical
results confirm our findings.

##  I Introduction

Semidefinite programs (SDPs) are a class of convex optimization problems over
the positive semidefinite (PSD) cone. The standard primal and dual SDPs are in
the form of

$\displaystyle p^{\star}:=\min_{X}\quad$ $\displaystyle\langle C,X\rangle$
$\displaystyle\mathrm{subject~{}to}\quad$ $\displaystyle\langle
A_{i},X\rangle=b_{i},\quad i=1,\ldots,m,$ (1a) $\displaystyle
X\in\mathbb{S}^{n}_{+},$ $\displaystyle d^{\star}:=\max_{y,Z}\quad$
$\displaystyle b^{{\mathsf{T}}}y$ $\displaystyle\mathrm{subject~{}to}\quad$
$\displaystyle Z+\sum_{i=1}^{m}A_{i}y_{i}=C,$ (1b) $\displaystyle
Z\in\mathbb{S}^{n}_{+},$

where $b\in\mathbb{R}^{m},C,A_{1},\ldots,A_{m}\in\mathbb{S}^{n}$ are the
problem data, $\mathbb{S}^{n}_{+}$ denotes the set of $n\times n$ PSD matrices
(we also write $X\succeq 0$ to denote $X\in\mathbb{S}^{n}_{+}$ when the
dimension is clear from the context), and $\langle\cdot,\cdot\rangle$ denotes
the standard inner product in an approximate space. We assume the strong
duality holds for the primal and dual SDPs (1), i.e., $p^{\star}=d^{\star}$.

Semidefinite optimization (1a) and (1b) is a powerful computational tool in
control theory [1], combinatorial problems [2], non-convex polynomial
optimization [3], and many other areas [4]. While interior-point methods can
solve SDPs in polynomial time to arbitrary accuracy in theory [4], they are
not scalable to address many large-scale problems of practical interest [5,
6]. One main difficulty is due to the need of storage, computation, and
factorization of a large matrix at each iteration of interior-point methods.
Existing general-purpose SDP solvers (including the state-of-the-art solver
MOSEK [7]) are limited to medium-scale problem instances (with $n$ less than
1000 and $m$ being a few hundreds in (1)).

Overcoming the challenge of scalability has received much attention [5, 6].
One class of approaches is to develop efficient algorithms based on first-
order methods. For instance, a general conic solver based on alternating
direction method of multipliers (ADMM) was developed in [8], and a sparse
conic solver based on ADMM for SDPs with chordal sparsity was developed in [9,
10]; see [5, Section 3] for a recent overview. While first-order methods
considerably speed up the computational time at each iteration, achieving
solutions of high accuracy remains a central challenge and may require
unacceptable many iterations. Therefore, first-order methods are mainly
suitable for applications that only require solutions of moderate accuracy.

Another class of approaches for efficiency improvement is to (equivalently or
approximately) decompose a large PSD matrix into the sum of smaller PSD
matrices that are easier to handle [5]. Specifically, one can try to decompose
$X=\sum_{i=1}^{t}Q_{i}$, where $Q_{i}\succeq 0$ are nonzero only on a certain
(and, ideally, small) principal submatrix. When $X$ has a special chordal
sparsity pattern, such a decomposition is equivalent [5, 11, 12]. In general,
the decomposition above gives an inner approximation of the PSD cone
$\mathbb{S}^{n}_{+}$. One widely used strategy is so-called scaled-diagonally
dominant (SDD) matrices [13], where each $Q_{i}$ only involves a $2\times 2$
nonzero principal matrix that is equivalent to a second-order cone constraint.
Second-order cone programs (SOCPs) admit much more efficient algorithms than
SDPs. This scalability feature is one main motivation in the recent studies
[14, 15, 16, 17, 18, 19]. In particular, this idea has been extensively used
in the context of sum-of-squares optimization [14]. While the SDD
approximation brings considerable computational efficiency in solving (1), the
solution might be very conservative [14, 5]. Several iterative methods have
been further proposed to improve solution quality, such as adding linear cuts
or second-order cuts [16, 17, 15], and basis pursuit searching [18, 19]. These
methods [16, 15, 17, 18, 19] solve a linear program (LP) or a SOCP at each
iteration, but may require many iterations to get a reasonable good solution
(if possible).

Recently, a new block extension of SDD matrices, called block factor-width-two
matrices, has been introduced in [20, 21], where $Q_{i}\succeq 0$ involves a
$2\times 2$ block principle matrix. This notion works on block-partitioned
matrices, and the block partition brings flexibility in terms of both solution
quality and numerical efficiency in solving (1), as demonstrated extensively
in [20, 21]. In this paper, we further develop iterative inner/outer
approximations based on the new notion of block factor-width-two matrices. Our
iterative algorithms generalize the results in [18] to the case of block
factor-width-two matrices and include [18] as a special case (cf. Algorithms
1-2). Our algorithms provide a sequence of upper and lower bounds of
increasing accuracy on the optimal SDP cost $p^{\star}=d^{\star}$ (cf.
Propositions 1-2 and Theorems 2-3). Numerical results on independent stable
set, binary quadratic optimization, and random SDPs confirm the performance of
our iterative inner/outer approximations.

The rest of this paper is organized as follows. In Section II, we review the
SDD and block SDD matrices. The iterative inner/outer approximations and their
solution quality are presented in Section III and Section IV. In Section V, we
present the numerical results. Section VI concludes the paper.

##  II Preliminaries and Problem Statement

In this section, we first give a brief overview of the existing approximation
strategies for the PSD cone $\mathbb{S}^{n}_{+}$, including (scaled-)
diagonally dominant matrices [13] and their block extensions [20]. These
approximation strategies have shown promising computational efficiency
improvement to solve (1a)-(1b), but may also suffer from conservatism in
solution quality [20, 14]. We then present the problem statement of improving
the approximation quality via iterative algorithms.

###  II-A DD and SDD matrices

The class of (scaled-) diagonally dominant matrices is defined as follows
[13].

###### Definition 1

A symmetric matrix $A=[a_{ij}]\in\mathbb{S}^{n}$ is diagonally dominant (DD)
if and only if

$a_{ii}\geq\sum_{j\neq i}|a_{ij}|,\ i=1,2,\ldots,n.\vspace{1mm}$ (2)

###### Definition 2

A symmetric matrix $A$ is scaled diagonally dominant (SDD) if and only if
there exists a diagonal matrix $D$ with positive entries such that $DAD$ is
DD.

We denote the set of of $n\times n$ DD matrices as $DD_{n}$ and the set of
$n\times n$ SDD matrices as $SDD_{n}$. It is known that the following
inclusion holds (e.g., by Gershgorin’s circle theorem) [13]

$DD_{n}\subseteq SDD_{n}\subseteq\mathbb{S}^{n}_{+}.$

An SDD matrix $A$ has an equivalent characterization as a factor-width-two
matrix, i.e., $A=VV^{{\mathsf{T}}}$ where each column of $V$ contains at most
two non-zero elements [13]. Furthermore,

$A\\!\in\\!SDD_{n}\Leftrightarrow A\\!=\\!\\!\\!\sum_{1\leq i<j\leq
n}E_{ij}^{{\mathsf{T}}}M_{ij}E_{ij},\text{with}\;M_{ij}\\!\in\\!\mathbb{S}^{2}_{+},$
(3)

where $E_{ij}\in\mathbb{R}^{2\times n}$ with $i$th entry in row 1 and $j$th
entry in row 2 being 1 and other entries being zero.

It is not difficult to see that (2) can be written as a set of linear
constraints and (3) can be reformulated to a set of second-order constraints.
Thus approximating $\mathbb{S}^{n}_{+}$ by $DD_{n}$ ($SDD_{n}$ respectively)
in (1) becomes a linear program (second-order cone program, respectively), for
which very efficient algorithms exist [22]. This computational feature is one
main motivation in the recent studies [18, 14].

###  II-B Block SDD matrices

The characterization in (3) only involves $2\times 2$ PSD matrices. A recent
study has introduced a block extension to bridge the gap between $SDD_{n}$ and
$\mathbb{S}^{n}_{+}$ [20]. The main idea is to allow (3) use $2\times 2$ block
matrices. To introduce this block extension, we need to define block-
partitioned matrices.

Given a set of integers $\alpha=\\{\alpha_{1},\alpha_{2},\ldots,\alpha_{p}\\}$
with $\sum_{i=1}^{p}\alpha_{i}=n$, we say a matrix $A\in\mathbb{R}^{n\times
n}$ is block-partitioned by $\alpha$ if we can write $A$ as

$\begin{bmatrix}A_{11}&A_{12}&\ldots&A_{1p}\\\ A_{21}&A_{22}&\ldots&A_{2p}\\\
\vdots&\vdots&\ddots&\vdots\\\ A_{p1}&A_{p2}&\ldots&A_{pp}\end{bmatrix},$ (4)

where $A_{ij}\in\mathbb{R}^{\alpha_{i}\times\alpha_{j}},\forall
i,j=1,2,\ldots,p$. Given a partition
$\alpha=\\{\alpha_{1},\alpha_{2},\cdots,\alpha_{p}\\}$, we define a 0/1 index
matrix $E_{i}^{\alpha}$ as

$E_{i}^{\alpha}=\begin{bmatrix}0&0&\ldots&I_{\alpha_{i}}&\ldots&0\end{bmatrix}\in\mathbb{R}^{\alpha_{i}\times
n},$ (5)

and another matrix

$E_{ij}^{\alpha}=\begin{bmatrix}E_{i}^{\alpha}\\\
E_{j}^{\alpha}\end{bmatrix}\in\mathbb{R}^{(\alpha_{i}+\alpha_{j})\times
n},\quad i\neq j.$

It is clear that $E_{ij}$ in (3) is the same as $E_{ij}^{\alpha}$ when
$\alpha=\\{1,1,\ldots,1\\}$ (i.e., the trivial partition). Now, we are ready
to introduce the notion of block factor-width-two matrices.

######  Definition 3 ([20])

A symmetric matrix $A$ with partition
$\alpha=\\{\alpha_{1},\alpha_{2},\cdots,\alpha_{p}\\}$ belongs to block
factor-width-two matrices, denoted as $\mathcal{FW}^{n}_{\alpha,2}$, if there
exist $X_{ij}$ such that

$A=\sum_{1\leq i<j\leq
p}^{p}(E_{ij}^{\alpha})^{{\mathsf{T}}}X_{ij}E_{ij}^{\alpha},\quad\text{with}\;\;X_{ij}\in\mathbb{S}^{\alpha_{i}+\alpha_{j}}_{+}.$
(6)

We note that a matrix can be partitioned in different ways. This flexibility
in block factor-width-two matrices can be used to build a converging hierarchy
of approximations for $\mathbb{S}^{n}_{+}$ [20, Theorem 2]. For example, three
possible partitions for a $10\times 10$ matrix are
$\alpha=\\{1,1,\ldots,1\\}$, $\beta=\\{2,2,2,2,2\\}$, $\gamma=\\{4,4,2\\}$,
for which we have that [20]

$SDD_{10}=\mathcal{FW}^{10}_{\alpha,2}\subseteq\mathcal{FW}^{10}_{\beta,2}\subseteq\mathcal{FW}^{10}_{\gamma,2}.$

This inclusion relation is illustrated in Figure 1, which shows the feasible
set of $x$ and $y$ for which the $10\times 10$ symmetric matrix $I_{10}+xA+yB$
($A$ and $B$ are two random generated $10\times 10$ symmetric matrices)
belongs to PSD, $\mathcal{FW}^{10}_{\alpha,2}$, $\mathcal{FW}^{10}_{\beta,2}$,
and $\mathcal{FW}^{10}_{\gamma,2}$.

In particular, we say a partition $\alpha$ is a finer partition of $\beta$,
denoted as $\alpha\sqsubseteq\beta$, if $\alpha$ can be formed by breaking
some blocks in $\beta$ (or equivalently, $\beta$ can be formed by merging some
blocks in $\alpha$); see [20, Definition 1]. We have the following theorem.

######  Theorem 1 ([20, Theorem 2])

Given
$\\{1,1,\ldots,1\\}\sqsubseteq\alpha\sqsubseteq\beta\sqsubseteq\gamma=\\{\gamma_{1},\gamma_{2}\\}$
with $\gamma_{1}+\gamma_{2}=n$, we have a converging hierarchy of inner and
outer approximations

$\displaystyle
SDD_{n}\subseteq\mathcal{FW}^{n}_{\alpha,2}\subseteq\mathcal{FW}^{n}_{\beta,2}\subseteq\mathcal{FW}^{n}_{\gamma,2}=\mathbb{S}^{n}_{+}$
(7)
$\displaystyle=(\mathcal{FW}^{n}_{\gamma,2})^{*}\\!\subseteq\\!(\mathcal{FW}^{n}_{\beta,2})^{*}\\!\subseteq\\!(\mathcal{FW}^{n}_{\alpha,2})^{*}\subseteq(SDD_{n})^{*},$

where $(\mathcal{FW}^{n}_{\alpha,2})^{*}$ denotes the dual of
$\mathcal{FW}^{n}_{\alpha,2}$.

Figure 1: Feasible region of the set of $x$ and $y$ for which the $10\times
10$ $I_{10}+xA+yB$ belongs to PSD, $\mathcal{FW}^{10}_{\alpha,2}$,
$\mathcal{FW}^{10}_{\beta,2}$, and $\mathcal{FW}^{10}_{\gamma,2}$, where
$\alpha=\\{1,1,\ldots,1\\}$, $\beta=\\{2,2,2,2,2\\}$, $\gamma=\\{4,4,2\\}$.

###  II-C Problem statement

In [18], we have seen significant numerical efficiency improvements by
approximating $\mathbb{S}^{n}_{+}$ using $DD_{n}$ and $SDD_{n}$ for solving
the SDP (1), but the solution quality can be unsatisfactory. As shown in
Theorem 1, the block factor-width-two matrices can improve the solution
quality by using a coarser partition $\beta$ [20]. This leads to larger PSD
constraints shown in (6), potentially compromising the numerical efficiency.

In this work, we aim to develop iterative inner and outer approximations for
solving the SDP (1) and at each iteration the partition $\alpha$ is fixed. In
this way, we solve the SDP (1) by solving smaller SDPs iteratively and
maintaining the scalability at each iteration. In particular, we will combine
the basis pursuit idea in [18] and the tight approximation quality of block
factor-width-two matrices in [20].

##  III Inner approximations of the psd cone

Given a partition $\alpha$, we know
$\mathcal{FW}^{n}_{\alpha,2}\subseteq\mathbb{S}^{n}_{+}\subseteq(\mathcal{FW}^{n}_{\alpha,2})^{*}$.
Then, replacing $\mathbb{S}^{n}_{+}$ with $\mathcal{FW}^{n}_{\alpha,2}$ (or
$(\mathcal{FW}^{n}_{\alpha,2})^{*}$, respectively) in (1) naturally gives an
inner (outer, respectively) approximation for solving SDPs [20]. In this
section, motivated by the basis pursuit idea in [18], we introduce an
iterative algorithm for inner approximations of (1). Our algorithm returns a
sequence of upper bounds with increasing accuracy.

###  III-A Inner Approximations

For the inner approximation, we start from replacing the PSD constraint in
(1a) by $\mathcal{FW}^{n}_{\alpha,2}$, leading to

$\displaystyle{\mathsf{U}}_{\alpha}^{1}:=\min_{X}\quad$ $\displaystyle\langle
C,X\rangle$ $\displaystyle\mathrm{subject~{}to}\quad$ $\displaystyle\langle
A_{i},X\rangle=b_{i},\quad i=1,\ldots,m,$ (8a) $\displaystyle
X\in\mathcal{FW}^{n}_{\alpha,2},$ (8b)

which provides an upper bound for (1a). The cyclic property of the trace
operator leads to

$\displaystyle\langle C,X\rangle$ $\displaystyle=\left\langle C,\sum_{1\leq
k<l\leq p}(E_{kl}^{\alpha})^{{\mathsf{T}}}X_{kl}E_{kl}^{\alpha}\right\rangle$
$\displaystyle=\sum_{1\leq k<l\leq p}\left\langle
E_{kl}^{\alpha}C(E_{kl}^{\alpha})^{{\mathsf{T}}},X_{kl}\right\rangle.$

This allows us to equivalently rewrite (8) into

$\displaystyle{\mathsf{U}}_{\alpha}^{1}:=\min_{X_{kl}}$
$\displaystyle\sum_{1\leq k<l\leq p}\left\langle C_{kl},X_{kl}\right\rangle$
(9) $\displaystyle\mathrm{subject~{}to}$ $\displaystyle\sum_{1\leq k<l\leq
p}\left\langle A_{i,kl},X_{kl}\right\rangle=b_{i},i=1,\ldots,m,$
$\displaystyle\;\;X_{kl}\in\mathbb{S}^{\alpha_{k}+\alpha_{l}}_{+},\qquad\quad
1\leq k<l\leq p,$

where
$C_{kl}=E_{kl}^{\alpha}C(E_{kl}^{\alpha})^{{\mathsf{T}}},A_{i,kl}=E_{kl}^{\alpha}A_{i}(E_{kl}^{\alpha})^{{\mathsf{T}}},1\leq
k<l\leq p,i=1,\ldots,m$. We can now use standard conic solvers (such as SeDuMi
[23] and MOSEK [7]) to solve (9). This gives an upper bound

$d^{\star}=p^{\star}\leq{\mathsf{U}}_{\alpha}^{1}.$ (10)

The gap ${\mathsf{U}}_{\alpha}^{1}-p^{\star}$ may be large. By Theorem 1,
using a coarser partition $\alpha\sqsubseteq\beta$ can reduce the gap
${\mathsf{U}}_{\beta}^{1}-p^{\star}\leq{\mathsf{U}}_{\alpha}^{1}-p^{\star}$,
but this leads to an SDP with a larger PSD constraint in (9).

We introduce another way to reduce the gap by solving a sequence of SDPs in
the form of (9) while keeping the same partition $\alpha$. In particular,
given an $n\times n$ matrix $V$, we define a family of cones

$\displaystyle\mathcal{FW}^{n}_{\alpha,2}(V)\\!\coloneqq\\!\\{M\in\mathbb{S}^{n}\mid
M\\!=\\!V^{{\mathsf{T}}}QV,\,Q\\!\in\\!\mathcal{FW}^{n}_{\alpha,2}\\}.$ (11)

It is clear that $\mathcal{FW}^{n}_{\alpha,2}(V)=\mathcal{FW}^{n}_{\alpha,2}$
when $V=I$, and that $\mathcal{FW}^{n}_{\alpha,2}(V)$ is an inner
approximation of $\mathbb{S}^{n}_{+}$ for any $V$.

When $V$ is fixed, linear optimization over $\mathcal{FW}^{n}_{\alpha,2}(V)$
amounts to solve an SDP in a similar form to (9). In particular, at each
iteration $t$, we replace $\mathcal{FW}^{n}_{\alpha,2}$ in (8) with
$\mathcal{FW}^{n}_{\alpha,2}(V_{t})$, and get the following problem

$\displaystyle{\mathsf{U}}_{\alpha}^{t}:=\min_{X_{kl}}{}$
$\displaystyle\sum_{1\leq k<l\leq
p}\left\langle\hat{C}_{kl},X_{kl}\right\rangle$ (12)
$\displaystyle\mathrm{subject~{}to}{}$ $\displaystyle\sum_{1\leq k<l\leq
p}\left\langle\hat{A}_{i,kl},X_{kl}\right\rangle=b_{i},i=1,\ldots,m$
$\displaystyle\;\;X_{kl}\in\mathbb{S}^{\alpha_{k}+\alpha_{l}}_{+},\qquad 1\leq
k<l\leq p,$

where the problem data are

$\displaystyle\hat{C}_{kl}$
$\displaystyle=E_{kl}^{\alpha}\left(V_{t}CV_{t}^{{\mathsf{T}}}\right)(E_{kl}^{\alpha})^{{\mathsf{T}}},$
(13) $\displaystyle\hat{A}_{i,kl}$
$\displaystyle=E_{kl}^{\alpha}\left(V_{t}A_{i}V_{t}^{{\mathsf{T}}}\right)(E_{kl}^{\alpha})^{{\mathsf{T}}},\quad
1\leq k<l\leq p.$

We choose the sequence of matrices $\\{V_{t}\\}$ as

$\begin{split}V_{1}&=I\\\ V_{t+1}&=\mathrm{chol}(X_{t}^{\star}),\end{split}$
(14)

where $\mathrm{chol}(\cdot)$ denotes a Cholesky factorization, and
$X_{t}^{\star}:=\sum_{1\leq k<l\leq
p}V_{t}^{{\mathsf{T}}}(E_{kl}^{\alpha})^{{\mathsf{T}}}X_{kl}^{t,\star}E_{kl}^{\alpha}V_{t}$
is the optimal solution to (12) at iteration $t$111We assume that the first
iteration is feasible. This guarantees the feasibility of the rest of
iterations.. When choosing $V_{1}=I$ at iteration 1, problem (12) reduces to
(9).

###  III-B Monotonically decreasing upper bounds

The choice of the matrices $V_{t+1}$ as the factorization of $X_{t}^{\star}$
in (14) leads to a sequence of monotonically decreasing cost values in (12).
We have the following proposition.

###### Proposition 1

Given any partition $\alpha$, solving (12) with matrices $\\{V_{t}\\}$ in (14)
leads to

${\mathsf{U}}^{1}_{\alpha}\geq{\mathsf{U}}^{2}_{\alpha}\geq\ldots\geq{\mathsf{U}}^{t}_{\alpha}\geq{\mathsf{U}}^{t+1}_{\alpha}\geq
p^{\star}.$

###### Proof:

Upon choosing $V_{t+1}=\mathrm{chol}(X_{t}^{\star})$, we naturally have
$X_{t}=V_{t+1}^{{\mathsf{T}}}\times I\times V_{t+1}$. Since
$I\in\mathcal{FW}^{n}_{\alpha,2}$, we have
$X_{t}^{\star}\in\mathcal{FW}^{n}_{\alpha,2}(V_{t+1})$. It means that the
optimal solution $X_{t}^{\star}$ at iteration $t$ is in the feasible region of
the SDP at iteration $t+1$. Thus, we have
${\mathsf{U}}^{t}_{\alpha}\geq{\mathsf{U}}^{t+1}_{\alpha}$. ∎

Input: SDP data $A_{i},C\in\mathbb{S}^{n},b\in\mathbb{R}^{m}$, block partition
$\alpha$, and maximum iteration $t_{\max}$

Output: Upper bound ${\mathsf{U}}_{\alpha}$

Initialize $t=1;$ $V_{1}=I;$

while  _$t <t_{\max}$ _ do

Solve (12) to get ${\mathsf{U}}_{\alpha}^{t}$ and $X_{kl}^{t,\star},1\leq
k<l\leq p;$

Set ${\mathsf{U}}_{\alpha}={\mathsf{U}}_{\alpha}^{t};$

Compute  $\displaystyle X_{t}^{\star}=\sum_{1\leq k<l\leq
p}V_{t}^{{\mathsf{T}}}(E_{kl}^{\alpha})^{{\mathsf{T}}}X_{kl}^{t,\star}E_{kl}^{\alpha}V_{t};$
$\displaystyle V_{t+1}=\mathrm{chol}(X_{t}^{\star});$

Update $\hat{C}_{kl},\hat{A}_{i,kl}$ as (13); Set $t=t+1;$

end while

return _${\mathsf{U}}_{\alpha}$ _

Algorithm 1 Inner-approximations using $\mathcal{FW}^{n}_{\alpha,2}$

When $X_{t}^{\star}$ is positive definite, we have a strictly decreasing cost
value, as summarized in the following theorem.

###### Theorem 2

Given any partition $\alpha$, let $X_{t}^{\star}$ be an optimal solution of
(12) at iterate $t$. If $X_{t}^{\star}$ is positive definite and
${\mathsf{U}}^{t}_{\alpha}>p^{\star}$, then
${\mathsf{U}}^{t}_{\alpha}>{\mathsf{U}}^{t+1}_{\alpha}\geq p^{\star}$.

###### Proof:

Let $X^{\star}$ and $p^{\star}$ be the optimal solution and cost value of (1).
We construct a point

$\hat{X}\coloneqq(1-\lambda)X_{t}^{\star}+\lambda X^{\star},$ (15)

with some $\lambda\in(0,1)$. We will prove there exists a $\lambda\in(0,1)$
such that $\hat{X}$ in (15) is feasible for (12) at iteration $t+1$.
Therefore, we complete the proof by observing

$U^{t+1}_{\alpha}\leq\langle C,\hat{X}\rangle=(1-\lambda)\langle
C,X_{t}^{\star}\rangle+\lambda\langle C,X^{\star}\rangle<U^{t}_{\alpha}.$

To prove $\hat{X}$ is feasible at iteration $t+1$ for some $\lambda\in(0,1)$,
we need to show $\hat{X}$ satisfies

  * •

the linear constraint (8a),

  * •

the conic constraint (8b) with $\mathcal{FW}^{n}_{\alpha,2}(V_{t+1})$.

First, it is clear that both $X_{t}^{\star}$ and $X^{\star}$ satisfy (8a),
i.e.,

$\displaystyle\langle A_{i},X_{t}^{\star}\rangle$
$\displaystyle=b_{i},\;\;i=1,\ldots,m,$ $\displaystyle\langle
A_{i},X^{\star}\rangle$ $\displaystyle=b_{i},\;\;i=1,\ldots,m.$

Then, we have $\forall i=1,\ldots,m$,

$\displaystyle\left\langle A_{i},\hat{X}\right\rangle$ $\displaystyle=\langle
A_{i},(1-\lambda)X_{t}^{\star}+\lambda X^{\star}\rangle$
$\displaystyle=(1-\lambda)\langle A_{i},X_{t}^{\star}\rangle+\lambda\langle
A_{i},X^{\star}\rangle=b_{i}.$

Since $X_{t}^{\star}=V_{t+1}^{{\mathsf{T}}}V_{t+1}$ and $X_{t}^{\star}$ is
positive definite, $V_{t+1}$ must be invertible. We let

$\tilde{X}_{t+1}\coloneqq\left(V_{t+1}^{-1}\right)^{{{\mathsf{T}}}}X^{\star}V_{t+1}^{-1}.$

Then, for small enough $\lambda>0$, the matrix
$(1-\lambda)I+\lambda\tilde{X}_{t+1}\in\mathcal{FW}^{n}_{\alpha,2}$. Hence,
from (15), we have

$\hat{X}=V^{{{\mathsf{T}}}}_{t+1}((1-\lambda)I+\lambda\tilde{X}_{t+1})V_{t+1}\in\mathcal{FW}^{n}_{\alpha,2}(V_{t+1}).$

This completes the proof. ∎

Our proof is inspired by [18, Theorem 3.1], and we generalize it to any block
partition $\alpha$, including the iterative algorithm based on SDD matrices
[18, Section 4] as a special case. The key idea is to make sure the optimal
solution of the previous iteration is a feasible point in the next iteration.
Thus, instead of the Cholesky decomposition, we can use other choices, such as
spectral decomposition $X_{t}^{\star}=PDP^{{\mathsf{T}}}$.

Algorithm 1 lists the overall procedure of the proposed iterative inner
approximations for solving (1). We use a simple example to illustrate our
algorithm.

Figure 2: Feasible regions of inner approximations of (16) in Algorithm 1 using $DD$, $SDD$, and $\mathcal{FW}^{n}_{\alpha,2}$ with $\alpha=\\{2,2,2,2,2\\}$. The red arrows denote the decreasing direction of the cost value.  TABLE I: Cost values of inner approximations in Algorithm 1 for solving (16). We used $DD$, $SDD$, and $\mathcal{FW}^{n}_{\alpha,2}$ with $\alpha=\\{2,2,2,2,2\\}$. The optimal cost of (16) is $-0.298$. | DD | SDD | $\mathcal{FW}^{n}_{\alpha,2}$
---|---|---|---
Iter |  Cost |  Gap |  Cost |  Gap |  Cost |  Gap
$1$ |  $-0.148$ |  $50.3$% |  $-0.176$ |  $40.9$% |  $-0.232$ |  $22.2$%
$2$ |  $-0.236$ |  $20.8$% |  $-0.277$ |  $7.04$% |  $-0.298$ |  $0$%

###### Example 1

Consider an SDP of the form

$\displaystyle\min_{x,y}$ $\displaystyle-x-y$ (16)
$\displaystyle\mathrm{subject~{}to}$ $\displaystyle I+xA+yB\succeq 0,$

where $A$ and $B$ are two $10\times 10$ matrices with each entry randomly
generated. We consider inner approximations by DD, SDD and
$\mathcal{FW}_{\alpha}^{10}$ with $\alpha=\\{2,2,2,2,2\\}$. The results are
shown in Figure 2. The blue part in Figure 2 shows the feasible region of
(16). We then replace the semidefinite constraint by $DD$, $SDD$ and
$\mathcal{FW}^{10}_{\alpha,2}$. Orange and green parts in Figure 2 show the
feasible regions in iteration 1 and 2 of Algorithm 1. It is clear that the
feasible region moves towards the direction where the cost decreases. As shown
in Table I (also in Figure 2), our algorithm using
$\mathcal{FW}^{n}_{\alpha,2}$ achieves the optimal cost at the second
iteration, while the results from DD/SDD approximations [18] are still far
away from the optimal cost. $\square$

##  IV Outer Approximations of the PSD cone

The inner approximation in (8) provides an upper bound of the SDPs (1). Here,
we introduce an outer approximation for the same problem (1a), which provides
a lower bound. Therefore, the optimal cost of (1) can be bounded above and
below simultaneously.

###  IV-A Outer approximations

Consider the relationship
$\mathcal{FW}^{n}_{\alpha,2}\subseteq\mathbb{S}^{n}_{+}\subseteq(\mathcal{FW}^{n}_{\alpha,2})^{*}$.
Replacing PSD cone $\mathbb{S}^{n}_{+}$ by the dual cone
$(\mathcal{FW}^{n}_{\alpha,2})^{*}$ gives an outer approximation of (1a),
i.e.,

$\displaystyle{\mathsf{L}}_{\alpha}^{1}\coloneqq\min_{X}$
$\displaystyle\langle C,X\rangle$ (17) $\displaystyle\mathrm{subject~{}to}$
$\displaystyle\langle A_{i},X\rangle=b_{i},\qquad i=1,\ldots,m,$
$\displaystyle X\in(\mathcal{FW}^{n}_{\alpha,2})^{*}.$

We have ${\mathsf{L}}_{\alpha}^{1}\leq d^{\star}=p^{\star}.$ Note that the
dual cone $(\mathcal{FW}^{n}_{\alpha,2})^{*}$ admits a decomposition as [20]

$\displaystyle(\mathcal{FW}^{n}_{\alpha,2})^{*}=\Big{\\{}X\in\mathbb{S}^{n}\mid$
$\displaystyle
E_{kl}^{\alpha}X(E_{kl}^{\alpha})^{{\mathsf{T}}}\in\mathbb{S}^{\alpha_{k}+\alpha_{l}}_{+},$
(18) $\displaystyle\qquad\qquad 1\leq k<l\leq p\Big{\\}}.$

Therefore, problem (17) can be rewritten as:

$\displaystyle{\mathsf{L}}_{\alpha}^{1}=\min_{X}$ $\displaystyle\langle
C,X\rangle$ (19) $\displaystyle\mathrm{subject~{}to}$ $\displaystyle\langle
A_{i},X\rangle=b_{i},\qquad i=1,\ldots,m,$ $\displaystyle
E_{kl}^{\alpha}X(E_{kl}^{\alpha})^{{\mathsf{T}}}\in\mathbb{S}^{\alpha_{k}+\alpha_{l}}_{+},1\leq
k<l\leq p.$

The gap $p^{\star}-{\mathsf{L}}_{\alpha}^{1}$ might be large. Similar to inner
approximations, we aim to solve a sequence of outer approximations in the
following form

$\displaystyle{\mathsf{L}}_{\alpha}^{t}\coloneqq\min_{X}\quad$
$\displaystyle\langle C,X\rangle$ $\displaystyle\mathrm{subject~{}to}\quad$
$\displaystyle\langle A_{i},X\rangle=b_{i},\qquad i=1,\ldots,m,$ (20)
$\displaystyle
E_{kl}^{\alpha}V_{t}XV_{t}^{{\mathsf{T}}}(E_{kl}^{\alpha})^{{\mathsf{T}}}\in\mathbb{S}^{\alpha_{k}+\alpha_{l}}_{+},1\leq
k<l\leq p,$

which is parameterized by $V_{t}\in\mathbb{R}^{n\times n}$. However, we cannot
generate the matrix $V_{t+1}$ by Cholesky decomposition of the optimal
solution $X_{t}$ of (20), since it is not positive semidefinite. To resolve
this, motivated by [18], we look into the dual problem of (20), which is

$\displaystyle{\mathsf{L}}_{\alpha}^{t}=\max_{y,X_{kl}}\quad$ $\displaystyle
b^{{\mathsf{T}}}y$ $\displaystyle\mathrm{subject~{}to}\quad$ $\displaystyle
C-\sum_{i=1}^{m}y_{i}A_{i}=\sum_{1\leq k<l\leq
p}V_{t}^{{\mathsf{T}}}(E_{kl}^{\alpha})^{{\mathsf{T}}}X_{kl}E_{kl}^{\alpha}V_{t},$
$\displaystyle X_{kl}\in\mathbb{S}^{\alpha_{k}+\alpha_{l}}_{+},\quad 1\leq
k<l\leq p.$ (21)

For the optimal solution $y^{t,\star}$ of (21) at iteration $t$, the matrix
$C-\sum_{i=1}^{m}y_{i}^{t,\star}A_{i}$ is guaranteed to be positive
semidefinite. Then, we choose a sequence of matrices $\\{V_{t}\\}$ for (21) as

$\begin{split}V_{1}&=I\\\
V_{t+1}&=\mathrm{chol}\left(C-\sum_{i=1}^{m}y_{i}^{t,\star}A_{i}\right),\end{split}$
(22)

where $y^{t,\star}$ is the optimal solution of (21) at iteration $t$.

###  IV-B Monotonically increasing lower bounds

The lower bounds from the sequence of outer approximations defined in (21) and
(22) are monotonically increasing, as proved in the following result.

###### Proposition 2

Given any partition $\alpha$, solving (21) with matrices $\\{V_{t}\\}$ in (22)
leads to

${\mathsf{L}}^{1}_{\alpha}\leq{\mathsf{L}}^{2}_{\alpha}\leq\ldots\leq{\mathsf{L}}^{t}_{\alpha}\leq{\mathsf{L}}^{t+1}_{\alpha}\leq
d^{\star}=p^{\star}.$

###### Proof:

It is not difficult to see that the dual problem (21) is equivalent to

$\displaystyle\max_{y}\quad$ $\displaystyle b^{{\mathsf{T}}}y$
$\displaystyle\mathrm{subject~{}to}\quad$ $\displaystyle
C-\sum_{i=1}^{m}y_{i}A_{i}\in\mathcal{FW}^{n}_{\alpha,2}(V_{t}).$ (23)

Suppose the optimal solution to (23) at iteration $t$ is $y_{i}^{t,\star}$.
Let

$Z_{t}^{\star}=C-\sum_{i=1}^{m}y_{i}^{t,\star}A_{i},\quad
V_{t+1}=\mathrm{chol}(Z_{t}^{\star}).$

We have $Z_{t}^{\star}=V_{t+1}^{{\mathsf{T}}}\times I\times
V_{t+1}\in\mathcal{FW}^{n}_{\alpha,2}(V_{t+1})$ since
$I\in\mathcal{FW}^{n}_{\alpha,2}$. It means that $y_{i}^{t,\star}$ is feasible
to (23) at iteration $t+1$. Thus, we have
${\mathsf{L}}^{t}_{\alpha}\leq{\mathsf{L}}^{t+1}_{\alpha}$. ∎

Similar to Theorem 2, when $C-\sum_{i=1}^{m}y_{i}^{t,\star}A_{i}$ is strictly
positive definite, we have a strictly increasing cost, as summarized in the
following theorem.

###### Theorem 3

Given any partition $\alpha$, let $\\{y_{i}^{t,\star},X_{kl}^{t,\star}\\}$ be
an optimal solution of (21) at iterate $t$. If
$C-\sum_{i=1}^{m}y_{i}^{t,\star}A_{i}$ is strictly positive definite and
${\mathsf{L}}^{t}_{\alpha}<d^{\star}$, then
${\mathsf{L}}^{t}_{\alpha}<{\mathsf{L}}^{t+1}_{\alpha}\leq d^{\star}$.

###### Proof:

Let $({y^{\star},Z^{\star}})$ be the optimal solution of (1b), and
$y_{i}^{t,\star}$ is an optimal solution of (23) at iteration $t$. We
construct

$\hat{y}\coloneqq(1-\lambda)y^{t,\star}+\lambda y^{\star},$ (24)

with some $\lambda\in(0,1)$. We will prove there exists a $\lambda\in(0,1)$
such that $\hat{y}$ in (24) is feasible for (23) at iteration $t+1$. We then
complete the proof by observing

${\mathsf{L}}^{t+1}_{\alpha}=b^{{\mathsf{T}}}y^{t+1,\star}\geq
b^{{\mathsf{T}}}\hat{y}=(1-\lambda)b^{{\mathsf{T}}}y^{t,\star}+\lambda
b^{{\mathsf{T}}}y^{\star}>{\mathsf{L}}^{t}_{\alpha}.$

To prove $\hat{y}$ is feasible at iteration $t+1$, we need to show

$C-\sum_{i=1}^{m}\hat{y}_{i}A_{i}\in\mathcal{FW}^{n}_{\alpha,2}(V_{t+1}),\;\text{for
some}\;\lambda\in(0,1).$ (25)

Indeed, we have

$\displaystyle C-\sum_{i=1}^{m}\hat{y}_{i}A_{i}$ $\displaystyle=$
$\displaystyle(1-\lambda)\left(C-\sum_{i=1}^{m}y^{t,\star}_{i}A_{i}\right)+\lambda\left(C-\sum_{i=1}^{m}y^{\star}_{i}A_{i}\right).$

Since $C-\sum_{i=1}^{m}y^{t,\star}_{i}A_{i}=V_{t+1}^{{\mathsf{T}}}V_{t+1}$
that is strictly positive definite, $V_{t+1}$ must be invertible. Then, we
have

$\displaystyle\left(V_{t+1}^{-1}\right)^{{{\mathsf{T}}}}\left(C-\sum_{i=1}^{m}\hat{y}_{i}A_{i}\right)V_{t+1}^{-1}$
$\displaystyle=$
$\displaystyle(1-\lambda)I+\lambda\left(V_{t+1}^{-1}\right)^{{{\mathsf{T}}}}\left(C-\sum_{i=1}^{m}y^{\star}_{i}A_{i}\right)V_{t+1}^{-1}\in\mathcal{FW}^{n}_{\alpha}$

when $\lambda\in(0,1)$ is small enough. It means that (25) holds with this
$\lambda$ for $\hat{y}$ in (24). This completes the proof. ∎

Input: SDP data $A_{i},C\in\mathbb{S}^{n},b\in\mathbb{R}^{m}$, block partition
$\alpha$, and maximum iteration $t_{\max}$

Output: Lower bound ${\mathsf{L}}_{\alpha}$

Initialize $t=1;V_{1}=I;$

while  _$t <t_{\max}$ _ do

Solve $\eqref{eq:outer-approximation-step-t-dual}$ to get
${\mathsf{L}}_{\alpha}^{t}$ and $y^{t,\star};$

Set ${\mathsf{L}}_{\alpha}={\mathsf{L}}_{\alpha}^{t};$

Compute $V_{t+1}=\mathrm{chol}(C-\sum_{i=1}^{m}y_{i}^{t,\star}A_{i});$

Set $t=t+1;\;$

end while

return _${\mathsf{L}}_{\alpha}$ _

Algorithm 2 Outer-approximations using $\mathcal{FW}^{n}_{\alpha,2}$

######  Remark 1 (Solving outer approximations)

Unlike the inner approximations (12), the outer approximations (20) and (21)
are not in the standard form of SDPs. Thus they cannot be solved directly
using standard conic solvers. In our implementation, we apply the idea in [24]
and transform (21) into the following primal form of SDPs

$\displaystyle\min_{y,X_{kl}}\;$ $\displaystyle-b^{{\mathsf{T}}}y$
$\displaystyle\mathrm{subject~{}to}\;$ $\displaystyle\sum_{1\leq k<l\leq
p}V_{t}^{{\mathsf{T}}}(E_{kl}^{\alpha})^{{\mathsf{T}}}X_{kl}E_{kl}^{\alpha}V_{t}+\sum_{i=1}^{m}y_{i}A_{i}=C,$
$\displaystyle X_{kl}\in\mathbb{S}^{\alpha_{k}+\alpha_{l}}_{+},1\leq k<l\leq
p,$ (26)

which is ready to be solved using standard conic solvers. We note that the
size of PSD constraints has been reduced in (23), but the number of equality
constraints is $n^{2}$. Thus, solving (23) might not be as efficient as
solving (12). $\square$

Our iterative outer approximations for solving (1) is listed in Algorithm 2.
We use SDP (16) to illustrate our algorithm.

###### Example 2

The feasible regions in the first and $11$th iterations are shown in Figure 3.
In particular, the blue part shows the feasible region of (16). We then
replace the PSD constraint by $(DD)^{*}$, $(SDD)^{*}$ and
$(\mathcal{FW}^{10}_{\alpha,2})^{*}$. Orange and green regions are the
feasible regions in iterations 1 and 11. It is clear that the feasible region
moves towards the direction where the cost increases. As shown in Table II
(also in Figure 3), our algorithm using $\mathcal{FW}^{n}_{\alpha,2}$ achieves
the optimal cost at iteration 11, while the results from DD/SDD approximations
[18] are still far away from the optimal cost. $\square$

Figure 4 shows the convergence of the upper and lower bounds of SDP (16) from
Algorithm 1 and 2. In this case, the convergence using
$\mathcal{FW}^{n}_{\alpha,2}$ is much faster than the DD/SDD strategies [14,
18].

Figure 3: Feasible regions of outer approximations in Algorithm 2 by $DD$, $SDD$, and $\mathcal{FW}^{n}_{\alpha,2}$ with $\alpha=\\{2,2,2,2,2\\}$. The red arrow denotes the increasing direction of the cost value.  TABLE II: Cost values of iteratively outer approximation (16) using $DD$, $SDD$, and $\mathcal{FW}^{n}_{\alpha,2}$. The optimal cost value of (16) is $-0.298$. | DD | SDD | $\mathcal{FW}^{n}_{\alpha,2}$
---|---|---|---
Iter |  Cost |  Gap |  Cost |  Gap |  Cost |  Gap
$1$ |  $-0.499$ |  $67.5$% |  $-0.469$ |  $57.4$% |  $-0.401$ |  $34.6$%
$11$ |  $-0.443$ |  $48.7$% |  $-0.350$ |  $17.6$% |  $-0.298$ |  $0$%
Figure 4: Inner/Outer approximations of SDP (16) using DD, SDD, and
$\mathcal{FW}^{n}_{2,\alpha}$ with $\alpha=\\{2,\ldots,2\\}$.

######  Remark 2 (Role of partition $\alpha$)

In our Algorithms 1-2, the choice of partition $\alpha$ brings flexibility in
balancing the computational efficiency and solution quality at each iteration.
Choosing a suitable partition might be problem dependent; we refer interested
readers to [20] for more discussions. Here, we highlight that 1) a coarser
partition normally leads to faster convergence in Algorithms 1-2, as shown in
our extensive numerical experiments in Section V; 2) a coarser partition also
leads to a smaller number $p$ in (21) and (12). The latter fact is important
in constructing the problem in each iteration, especially for large-scale
cases. For example, when $n=2000$, if we use the SDD matrices for inner/outer
approximations [14, 18], the number of small blocks is
$\binom{2000}{2}=1\,999\,000$ which is too large to even construct the problem
instances (21) and (12). We indeed failed to construct such problems in our
experiments in Section V-C. Instead, for $\alpha=\\{10,\ldots,10\\}$
($\beta=\\{20,\ldots,20\\}$, respectively), the number of blocks is reduced to
$\binom{200}{2}=19900$ ($\binom{100}{2}=4950$, respectively), for which
efficient constructions exist.

##  V Numerical Results

In this section, we present computational results of Algorithms 1-2 on three
classes of SDPs: 1) independent stable set, 2) binary quadratic optimization,
and 3) SDPs with random data. Our experiments were carried out in MATLAB
R2021a on a Windows PC with 2.6 GHz speed and 24 GB RAM. All the SDP instances
at each iteration of Algorithms 1-2 were solved by MOSEK [7].

Figure 5: Inner/Outer approximations of Lov$\acute{a}$sz theta number (28) by different partitions: $\alpha=\\{2,\ldots,2\\}$, and $\beta=\\{5,\ldots,5\\}$. TABLE III: Success rate of upper bounds of $\vartheta(\mathcal{G})$ in (28) for $140$ instances of 30-nodes Erd$\ddot{o}$s-$\acute{R}$enyi graphs using Algorithm 2, where $\alpha=\\{2,\ldots,2\\}$ and $\beta=\\{5,\ldots,5\\}$.  Iteration $t$ | SDD | $\mathcal{FW}^{n}_{\alpha,2}$ | $\mathcal{FW}^{n}_{\beta,2}$
---|---|---|---
$1$ | $0\%$ | $0\%$ | $0\%$
$3$ | $0\%$ | $5.7\%$ | $36.4\%$
$5$ | $20\%$ | $36.4\%$ | $86.4\%$
$7$ | $35.7\%$ | $79.3\%$ | $95.7\%$

###  V-A The maximum stable set problem

The maximum stable set problem is a classical combinatorial problem, which
aims to find the stability number of a graph. A stable set of a undirected
graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ is a set of nodes of
$\mathcal{G}$ such that there are no edges between them. The maximum stable
number of $\mathcal{G}$, denoted as $\alpha(\mathcal{G})$, is the size of
maximum stable set. However, testing whether a $\alpha(\mathcal{G})$ is
greater than an integer $k$ is well-known to be NP-complete [25]. This problem
can be formulated as

$\displaystyle\alpha(\mathcal{G})\coloneqq\max_{x_{i}}$
$\displaystyle\sum_{i=1}^{n}x_{i}$ (27) $\displaystyle\mathrm{subject~{}to}$
$\displaystyle x_{i}\in\\{0,1\\},\quad i=1,2,\ldots,n,$ $\displaystyle
x_{i}x_{j}=0,\quad\forall(i,j)\in\mathcal{E}.$

A well-known SDP-based upper bound, introduced in [26], can be computed by

$\displaystyle\vartheta(\mathcal{G})\coloneqq\max_{X}$ $\displaystyle\langle
J,X\rangle$ (28) $\displaystyle\mathrm{subject~{}to}$ $\displaystyle\langle
I,X\rangle=1,$ $\displaystyle X_{ij}=0,\quad\forall(i,j)\in\mathcal{E},$
$\displaystyle X\succeq 0,$

where $J$ is an all-one matrix and $I$ is the identity matrix. The cost of
(28) is called Lov$\acute{a}$sz theta number, denoted as
$\vartheta(\mathcal{G})$, which provides an upper bound
$\vartheta(\mathcal{G})\geq\alpha(\mathcal{G})$. We now apply Algorithms 1 and
2 to get a sequence of upper and lower bounds on Lov$\acute{a}$sz theta
number.

We first generated a Erd$\ddot{o}$s-$\acute{R}$enyi graph of 30 nodes with
edge probability 0.2, and then applied Algorithms 1 and 2 using three
different partitions: SDD (trivial partition), $\alpha=\\{2,\ldots,2\\}$, and
$\beta=\\{5,\ldots,5\\}$. As shown in Figure 5, a coarser partition $\beta$
leads to the fastest convergence for both inner and outer approximation in
this case. To give a more quantitative comparison, we further generated 140
instances of 30-node Erd$\ddot{o}$s-$\acute{R}$enyi graphs with edge
probability from 0.2 to 0.8. We use Algorithm 2 to compute the upper bound of
$\vartheta(\mathcal{G})$. When the upper bound is within 99% suboptimality to
$\vartheta(\mathcal{G})$, we consider it as a success. Table III lists the
success rate at different iterations of Algorithm 2. As expected, a coarser
partition $\beta$ gives much higher success rates compared to SDD
approximation [18]. Specifically, in the seventh iteration,
$\mathcal{FW}^{n}_{\beta,2}$ obtains $95.7\%$ success rate, while SDD only has
$35.7\%$ success rate.

Figure 6: Inner approximation on the binary quadratic optimization (30) with $\alpha=\\{10,\ldots,10\\}$ and $\beta=\\{20,\ldots,20\\}$. TABLE IV: Upper bounds of (30) at iteration 10 using SDD, $\mathcal{FW}^{n}_{\alpha,2}$, $\mathcal{FW}^{n}_{\beta,2}$ with $\alpha=\\{10,\ldots,10\\},~{}\beta=\\{20,\ldots,20\\}$. | SDD | $\mathcal{FW}^{n}_{\alpha,2}$ | $\mathcal{FW}^{n}_{\beta,2}$
---|---|---|---
Instance | Gap | Time | Gap | Time | Gap | Time
1 | $28.77$ | $43.5$ | $3.02$ | $27.0$ | $0.05$ | $32.4$
2 | $30.81$ | $51.4$ | $2.31$ | $25.6$ | $0.03$ | $30.4$
3 | $29.24$ | $48.4$ | $3.54$ | $27.5$ | $0.04$ | $29.2$
4 | $29.45$ | $47.2$ | $3.14$ | $26.5$ | $0.04$ | $32.7$
5 | $29.40$ | $55.8$ | $2.43$ | $26.7$ | $0.03$ | $36.9$

###  V-B Binary quadratic optimization

Binary quadratic optimization is another classical combinatorial problem, in
which we have a quadratic cost and a binary decision variable $x$. Formally,
the problem is

$\displaystyle\min_{x}$ $\displaystyle x^{T}Qx$ (29)
$\displaystyle\mathrm{subject~{}to}$ $\displaystyle x_{i}^{2}=1,\quad
i=1,2,\ldots,n,$

where $Q\in\mathbb{S}^{n}$. Many well-known problems are in the form of (29),
such as max-cut problems [27]. The quadratic constraint define a finite set.
The number of elements grows with the rate $2^{n}$. It is well-known that such
a problem is NP-complete [28]. A standard semidefinite relaxation is

$\displaystyle\min_{X}$ $\displaystyle\langle Q,X\rangle$ (30)
$\displaystyle\mathrm{subject~{}to}$ $\displaystyle X_{ii}=1,\quad
i=1,2,\ldots,n,$ $\displaystyle X\in\mathbb{S}^{n}_{+},$

which returns a lower bound for (29).

We apply Algorithm 1 for inner approximations of (30). We generated five
random cost matrices $Q\in\mathbb{S}^{100}$. We apply three different
partitions: SDD, $\alpha=\\{10,\ldots,10\\}$, and $\beta=\\{20,\ldots,20\\}$.
We set the maximum iteration as $10$. The results are shown in Figure 6 and
Table IV. As expected again, as the partition becomes coarser, the
approximation quality increases. For example, inner approximation by partition
$\beta$ obtains almost optimal solution ($\geq 99.9\%$ optimality) within $10$
iterations, while SDD can only achieve around $70\%$ optimality while taking a
longer time (the longer time consumption is related to the large number of
small blocks; see Remark 2).

###  V-C Random SDPs

Our final experiment is to show the scalability of the inner approximations in
Algorithm 1. We generated seven random large-scale SDPs with PSD constraints
of $1500$, $2000$, $2500$, $3000$, $3500$, $4000$, and $4500$. The number of
linear constraints is fixed as $m=10$. We approximate the PSD cone using two
different partitions $\alpha=\\{10,\ldots,10\\}$ and
$\beta=\\{20,\ldots,20\\}$. As discussed in Remark 2, we failed to use SDD
approximation in this large-scale experiment.

We ran Algorithm 1 for 30 minutes and then compare the solution quality. The
optimality gap is computed by
$\lvert\frac{p^{\star}-f_{30}}{p^{\star}}\rvert\times 100\%$, where
$p^{\star}$ is the optimal cost value of original SDP, and $f_{30}$ is the
obtained upper bound after running $30$ minutes. The results are listed in
Table V. Our proposed method shows promising efficiency and accuracy. For
example, when $n=4500$ and $m=10$, Algorithm 1 with partition $\beta$ obtained
a solution with $99.9\%$ optimality in $30$ minutes, while original SDP took
over 4.5 hours to solve.

TABLE V: Computational results of 6 different large-scale SDPs using Algorithm 1 with $\alpha=\\{10,\ldots,10\\}$ and $\beta=\\{20,\ldots,20\\}$. $f_{1}$ denotes the cost value of the first iteration. $f_{30}$ denotes the cost value after $30$ minutes. The time consumption (in seconds) for solving the original SDP is listed in the last column.  | $\mathcal{FW}^{n}_{\alpha,2}$ | $\mathcal{FW}^{n}_{\beta,2}$ | PSD
---|---|---|---
$n$ |  $f_{1}$ |  $f_{30}$ |  Gap |  $f_{1}$ |  $f_{30}$ |  Gap |  Time
$1500$ |  $5.63e6$ |  $4.76e6$ |  $0.03$ |  $5.20e6$ |  $4.76e6$ |  $0.03$ |  $603$
$2000$ |  $3.33e6$ |  $2.86e6$ |  $0.10$ |  $3.09e6$ |  $2.86e6$ |  $0.05$ |  $1\,201$
$2500$ |  $6.11e6$ |  $5.29e6$ |  $0.07$ |  $5.70e6$ |  $5.29e6$ |  $0.05$ |  $2\,893$
$3000$ |  $1.81e7$ |  $1.32e7$ |  $0.79$ |  $1.57e7$ |  $1.32e7$ |  $0.79$ |  $5\,508$
$3500$ |  $8.96e6$ |  $7.08e6$ |  $0.10$ |  $8.02e6$ |  $7.07e6$ |  $0.08$ |  $7\,369$
$4000$ |  $9.52e6$ |  $6.89e6$ |  $0.15$ |  $8.21e6$ |  $6.89e6$ |  $0.11$ |  $10\,689$
$4500$ |  $2.05e7$ |  $1.70e7$ |  $0.08$ |  $1.88e7$ |  $1.69e7$ |  $0.06$ |  $16\,989$

##  VI Conclusions

In this paper, we have introduced the iterative inner/outer approximations for
solving SDPs (cf. Algorithm 1-2), and analyzed their solution quality (cf.
Propositions 1-2 and Theorems 2-3). Numerical results on stable set, binary
quadratic optimization, and random SDPs have shown promising accuracy and
computational scalability when proper partitions were used. Future work
includes analyzing the convergence of (or modified) Algorithm 1-2 (some recent
results appeared in [19]). Developing other types of iterative algorithms
based on block factor-width matrices will also be interesting.

## References

  * [1] S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan, _Linear matrix inequalities in system and control theory_. SIAM, 1994.
  * [2] R. Sotirov, “SDP relaxations for some combinatorial optimization problems,” in _Handbook on Semidefinite, Conic and Polynomial Optimization_. Springer, 2012, pp. 795–819.
  * [3] G. Blekherman, P. A. Parrilo, and R. R. Thomas, _Semidefinite optimization and convex algebraic geometry_. SIAM, 2012\.
  * [4] L. Vandenberghe and S. Boyd, “Semidefinite programming,” _SIAM review_ , vol. 38, no. 1, pp. 49–95, 1996.
  * [5] Y. Zheng, G. Fantuzzi, and A. Papachristodoulou, “Chordal and factor-width decompositions for scalable semidefinite and polynomial optimization,” _Annual Reviews in Control_ , vol. 52, pp. 243–279, 2021.
  * [6] A. Majumdar, G. Hall, and A. A. Ahmadi, “Recent scalability improvements for semidefinite programming with applications in machine learning, control, and robotics,” _Annual Review of Control, Robotics, and Autonomous Systems_ , vol. 3, pp. 331–360, 2020.
  * [7] M. ApS, “Mosek optimization toolbox for matlab,” _User’s Guide and Reference Manual, Version_ , vol. 4, 2019.
  * [8] B. O’donoghue, E. Chu, N. Parikh, and S. Boyd, “Conic optimization via operator splitting and homogeneous self-dual embedding,” _Journal of Optimization Theory and Applications_ , vol. 169, no. 3, pp. 1042–1068, 2016.
  * [9] Y. Zheng, G. Fantuzzi, A. Papachristodoulou, P. Goulart, and A. Wynn, “Chordal decomposition in operator-splitting methods for sparse semidefinite programs,” _Mathematical Programming_ , vol. 180, no. 1, pp. 489–532, 2020\.
  * [10] ——, “CDCS: Cone decomposition conic solver, version 1.1,” 2016.
  * [11] L. Vandenberghe and M. S. Andersen, “Chordal graphs and semidefinite optimization,” _Foundations and Trends in Optimization_ , vol. 1, no. 4, pp. 241–433, 2015.
  * [12] Y. Zheng and G. Fantuzzi, “Sum-of-squares chordal decomposition of polynomial matrix inequalities,” _Math. Program._ , pp. 1–38, 2021.
  * [13] E. G. Boman, D. Chen, O. Parekh, and S. Toledo, “On factor width and symmetric H-matrices,” _Linear algebra and its applications_ , vol. 405, pp. 239–248, 2005.
  * [14] A. A. Ahmadi and A. Majumdar, “DSOS and SDSOS optimization: more tractable alternatives to sum of squares and semidefinite optimization,” _SIAM J Appl Math._ , vol. 3, no. 2, pp. 193–230, 2019.
  * [15] D. Bertsimas and R. Cory-Wright, “On polyhedral and second-order cone decompositions of semidefinite optimization problems,” _Operations Research Letters_ , vol. 48, no. 1, pp. 78–85, 2020.
  * [16] A. A. Ahmadi, S. Dash, and G. Hall, “Optimization over structured subsets of positive semidefinite matrices via column generation,” _Discrete Optimization_ , vol. 24, pp. 129–151, 2017.
  * [17] Y. Wang, A. Tanaka, and A. Yoshise, “Polyhedral approximations of the semidefinite cone and their application,” _Computational Optimization and Applications_ , vol. 78, no. 3, pp. 893–913, 2021.
  * [18] A. A. Ahmadi and G. Hall, “Sum of squares basis pursuit with linear and second order cone programming,” _Algebraic and geometric methods in discrete mathematics_ , vol. 685, pp. 27–53, 2017.
  * [19] B. Roig-Solvas and M. Sznaier, “A globally convergent lp and socp-based algorithm for semidefinite programming,” _arXiv preprint arXiv:2202.12374_ , 2022.
  * [20] Y. Zheng, A. Sootla, and A. Papachristodoulou, “Block factor-width-two matrices and their applications to semidefinite and sum-of-squares optimization,” _IEEE Transactions on Automatic Control_ , 2022.
  * [21] A. Sootla, Y. Zheng, and A. Papachristodoulou, “Block factor-width-two matrices in semidefinite programming,” in _2019 18th European Control Conference (ECC)_. IEEE, 2019, pp. 1981–1986.
  * [22] F. Alizadeh and D. Goldfarb, “Second-order cone programming,” _Mathematical programming_ , vol. 95, no. 1, pp. 3–51, 2003.
  * [23] J. F. Sturm, “Using sedumi 1.02, a matlab toolbox for optimization over symmetric cones,” _Optimization methods and software_ , vol. 11, no. 1-4, pp. 625–653, 1999.
  * [24] J. Löfberg, “Dualize it: software for automatic primal and dual conversions of conic programs,” _Optimization Methods & Software_, vol. 24, no. 3, pp. 313–325, 2009.
  * [25] R. M. Karp, “Reducibility among combinatorial problems,” in _Complexity of computer computations_. Springer, 1972, pp. 85–103.
  * [26] L. Lovász, “On the shannon capacity of a graph,” _IEEE Transactions on Information theory_ , vol. 25, no. 1, pp. 1–7, 1979.
  * [27] P. Festa, P. M. Pardalos, M. G. Resende, and C. C. Ribeiro, “Randomized heuristics for the max-cut problem,” _Optimization methods and software_ , vol. 17, no. 6, pp. 1033–1058, 2002.
  * [28] J. Hartmanis, “Computers and intractability: a guide to the theory of np-completeness (michael r. garey and david s. johnson),” _Siam Review_ , vol. 24, no. 1, p. 90, 1982.


absence of a dark flavour symmetry, implying that it does not fall into the
DMFV class [20, 21, 22, 23, 24, 25, 26]. In turn, the DMFV connection between
the coupling matrix $\lambda$ and the DM mass spectrum is lifted in this
model. Further, the two mediator fields interact with the SM Higgs doublet
through the Yukawa coupling $y_{\psi}$.

To examine the structure of the coupling matrix $\lambda$, determine the
model’s viable parameter space and subsequently examine whether it is capable
of generating sizeable effects in the muon anomalous magnetic moment
$a_{\mu}$, we have studied limits from collider searches, flavour experiments,
precision tests of the SM, the DM relic density as well as DM detection
experiments.

In Section 3 we explored constraints from LHC searches for sleptons in the
same-flavour final state $\ell\bar{\ell}+\not{E}_{T}$ with $\ell=e,\mu$. We
found that the interplay between contributions from processes with the two
charged mediators leads to an exclusion of DM masses close to the equal mass
threshold $m_{\phi_{3}}\approx m_{\psi_{2}}$ for values
$0.5\mathrel{\mathchoice{\raise 0.0pt\hbox{\scalebox{0.8}{\raise
0.0pt\hbox{$\displaystyle\lesssim$}}}}{\raise 0.0pt\hbox{\scalebox{0.8}{\raise
0.0pt\hbox{$\textstyle\lesssim$}}}}{\raise 0.0pt\hbox{\scalebox{0.8}{\raise
0.0pt\hbox{$\scriptstyle\lesssim$}}}}{\raise 0.0pt\hbox{\scalebox{0.8}{\raise
0.0pt\hbox{$\scriptscriptstyle\lesssim$}}}}}y_{\psi}\mathrel{\mathchoice{\raise
0.0pt\hbox{\scalebox{0.8}{\raise 0.0pt\hbox{$\displaystyle\lesssim$}}}}{\raise
0.0pt\hbox{\scalebox{0.8}{\raise 0.0pt\hbox{$\textstyle\lesssim$}}}}{\raise
0.0pt\hbox{\scalebox{0.8}{\raise 0.0pt\hbox{$\scriptstyle\lesssim$}}}}{\raise
0.0pt\hbox{\scalebox{0.8}{\raise
0.0pt\hbox{$\scriptscriptstyle\lesssim$}}}}}1.00$, while this near-threshold
exclusion tends to decrease with increasing values
$y_{\psi}\mathrel{\mathchoice{\raise 0.0pt\hbox{\scalebox{0.8}{\raise
0.0pt\hbox{$\displaystyle\gtrsim$}}}}{\raise 0.0pt\hbox{\scalebox{0.8}{\raise
0.0pt\hbox{$\textstyle\gtrsim$}}}}{\raise 0.0pt\hbox{\scalebox{0.8}{\raise
0.0pt\hbox{$\scriptstyle\gtrsim$}}}}{\raise 0.0pt\hbox{\scalebox{0.8}{\raise
0.0pt\hbox{$\scriptscriptstyle\gtrsim$}}}}}1.00$. We obtained the largest
exclusion in the $m_{\psi_{2}}-m_{\phi_{3}}$ plane for vanishing couplings
$|\lambda_{\tau 3}|$ and maximum couplings to electrons and muons
$|\lambda_{\ell 3}|=2.0$. In this case the LHC constraints exclude mediator
masses up to $m_{\psi_{2}}\simeq 750\,\mathrm{GeV}$ and DM masses up to
$m_{\phi_{3}}\simeq 400\,\mathrm{GeV}$.

To determine the flavour structure of $\lambda$ we then studied limits from
LFV decays in Section 4. Due to the contribution with a chirality flip in the
loop governed by the Yukawa coupling $y_{\psi}$, the LFV decays
$\ell_{i}\to\ell_{j}\gamma$ yield stringent bounds. The strongest limit is
placed on the model by the decay $\mu\rightarrow e\gamma$ and we estimated the
resulting constraint on the coupling matrix. Motivated by our goal to solve
the $(g-2)_{\mu}$ anomaly, we satisfied this constraint by suppressing the
DM–electron couplings and choosing
$|\lambda_{ei}|\sim\mathcal{O}(10^{-6}-10^{-1})$. Other LFV decays less
severely constrain the coupling matrix $\lambda$ due to weaker experimental
limits.

We continued to restrict the coupling matrix $\lambda$ in Section 5 by using
constraints from precision tests of the SM. Here we particularly discussed the
electron electric dipole moment $d_{e}$ as well as the electron magnetic
dipole moment $a_{e}$, with the latter having the same sign in our model as
the NP contributions to $a_{\mu}$. We found that once the DM–electron
couplings are suppressed according to the LFV constraints, the EDM constraint
allows for $\mathcal{O}(1)$ imaginary parts of the scaling parameter $\xi$.
Moreover, for accordingly suppressed DM–electron couplings the constraints on
the electron MDM $a_{e}$ are automatically fulfilled.

In Section 6 we studied in which part of our model’s parameter space the
observed DM relic density can be reproduced. We investigated two benchmark
scenarios for the thermal freeze-out: the QDF scenario in which negligible
mass splittings lead to the presence of all dark flavours during freeze-out,
and the SFF scenario where due to a significant mass splitting between the DM
flavours only the lightest state contributes to the freeze-out. For both
scenarios, we studied the two cases of suppressed and non-suppressed left-
handed interactions between DM and the SM with $|\xi|=0.01$ and $|\xi|=1.00$,
respectively. For small left-handed couplings the DM annihilation rate is
$p$-wave suppressed while for sizeable left-handed interactions this
suppression is lifted. Still the relic density constraint allows for large
couplings $|\lambda_{ij}|\sim\mathcal{O}(1)$ in both freeze-out scenarios and
both cases for $\xi$.

The direct detection phenomenology of our model was studied in Section 7.1,
where we used XENON1T data to constrain the coupling matrix $\lambda$. As the
photon penguin that dominates DM–nucleon scattering is proportional to the
logarithm of the mass of the lepton in the loop, the restrictions on $\lambda$
were found to increase for decreasing lepton masses. The largest constraints
were thus found for the DM–muon coupling, since the DM–electron coupling is
already suppressed due to the flavour constraints.

Section 7.2 was dedicated to the limits from indirect detection experiments.
Here we focussed on limits from AMS measurements of the positron flux as well
as measurements of the $\gamma$-ray line and continuum spectrum performed by
the Fermi-LAT satellite and the H.E.S.S. telescope. For non-suppressed left-
handed interactions the constraints from measurements of the positron flux and
the $\gamma$-ray continuum spectrum are restricting for DM masses
$m_{\phi_{3}}\mathrel{\mathchoice{\raise 0.0pt\hbox{\scalebox{0.8}{\raise
0.0pt\hbox{$\displaystyle\lesssim$}}}}{\raise 0.0pt\hbox{\scalebox{0.8}{\raise
0.0pt\hbox{$\textstyle\lesssim$}}}}{\raise 0.0pt\hbox{\scalebox{0.8}{\raise
0.0pt\hbox{$\scriptstyle\lesssim$}}}}{\raise 0.0pt\hbox{\scalebox{0.8}{\raise
0.0pt\hbox{$\scriptscriptstyle\lesssim$}}}}}500\,\mathrm{GeV}$ and
$m_{\phi_{3}}\mathrel{\mathchoice{\raise 0.0pt\hbox{\scalebox{0.8}{\raise
0.0pt\hbox{$\displaystyle\lesssim$}}}}{\raise 0.0pt\hbox{\scalebox{0.8}{\raise
0.0pt\hbox{$\textstyle\lesssim$}}}}{\raise 0.0pt\hbox{\scalebox{0.8}{\raise
0.0pt\hbox{$\scriptstyle\lesssim$}}}}{\raise 0.0pt\hbox{\scalebox{0.8}{\raise
0.0pt\hbox{$\scriptscriptstyle\lesssim$}}}}}700\,\mathrm{GeV}$, respectively.
The $\gamma$-ray line spectrum generally leads to relevant constraints in the
near-degeneracy region $m_{\phi_{3}}\approx m_{\psi_{2}}$. In total,
constraints from indirect detection were still found to be weak in comparison
to other limits.

To obtain our model’s viable parameter space we then performed a combined
analysis in Section 8 by demanding that all constraints are simultaneously
fulfilled at the $2\sigma$ level. The global picture is mainly determined by
flavour, relic density and direct detection constraints. For the SFF scenario
the combination of flavour and relic density constraints forces the allowed
points to lie in a band in the $|\lambda_{\tau 3}|-|\lambda_{\mu 3}|$ plane,
while the direct detection constraint dominates in a small part of the
parameter space over the relic density constraint. In these regions, the outer
edge of the mentioned bands shrinks toward the inner band for growing values
of $|\lambda_{\mu 3}|$. For the QDF scenario we found that for large parts of
the parameter space the direct detection constraint dominates over the relic
density constraint. Consequently the combined analysis also allows for
simultaneously small values of $|\lambda_{\tau 3}|$ and $|\lambda_{\mu 3}|$,
since the relic density constraint in this case can also be fulfilled through
annihilations of the heavier states $\phi_{1}$ and $\phi_{2}$ alone, provided
that the mediator mass is sufficiently small,
$m_{\psi_{2}}\mathrel{\mathchoice{\raise 0.0pt\hbox{\scalebox{0.8}{\raise
0.0pt\hbox{$\displaystyle\lesssim$}}}}{\raise 0.0pt\hbox{\scalebox{0.8}{\raise
0.0pt\hbox{$\textstyle\lesssim$}}}}{\raise 0.0pt\hbox{\scalebox{0.8}{\raise
0.0pt\hbox{$\scriptstyle\lesssim$}}}}{\raise 0.0pt\hbox{\scalebox{0.8}{\raise
0.0pt\hbox{$\scriptscriptstyle\lesssim$}}}}}1500\,\mathrm{GeV}$. Generally the
case of non-suppressed left-handed interactions with $|\xi|=1.00$ allows for
smaller couplings $|\lambda_{\tau 3}|$ and $|\lambda_{\mu 3}|$ than the case
with $|\xi|=0.01$.

Finally, we used our results from Section 8 to examine if our model is able to
account for the discrepancy between the SM and experiment in the muon
anomalous magnetic moment $a_{\mu}$ in Section 9. To this end we calculated
$\Delta a_{\mu}$ in the regions identified as viable in the combined analysis
and compared it with the experimental value. We further calculated
accompanying corrections $\Delta m_{\mu}$ to the muon mass and checked if
sizeable effects in $a_{\mu}$ introduce a fine-tuned muon mass or not. We
found that in both freeze-out scenarios the central value of $\Delta
a_{\mu}^{\text{exp}}$ can be reached within the region of parameter space that
we regard as non-fine-tuned for both cases of $\xi$, requiring different
values for the mediator-Higgs coupling $y_{\psi}$. Noteworthy, for non-
suppressed left-handed interactions larger corrections to the muon mass are
generated for a given value of $\Delta a_{\mu}$ than for $|\xi|=0.01$.

We conclude that lepton-flavoured DM with couplings to both left- and right-
handed leptons accompanied by Higgs portal interactions of the corresponding
mediators elegantly connects the current most convincing hints at NP: the DM
problem and the muon $(g-2)$ anomaly. In spite of exhibiting a very rich
phenomenology spanning over several branches of particle physics and thus
being subject to many constraints, this model still allows for a joint
explanation of both. Hence, it qualifies as an attractive DM candidate waiting
to be further probed with increased sensitivity by future experiments.

#### Acknowledgements

We thank Manuel Egner, Mustafa Tabet and Marco Fedele for useful discussions.
This work is supported by the Deutsche Forschungsgemeinschaft (DFG, German
Research Foundation) under grant 396021762 – TRR 257. P.A. is supported by the
STFC under Grant No. ST/T000864/1. H.A. acknowledges the scholarship and
support he receives from the Avicenna-Studienwerk e.V., the support of the
doctoral school “Karlsruhe School of Elementary and Astroparticle Physics:
Science and Technology (KSETA)” and the funding he received for his academic
visit at the University of Oxford from the “Karlsruhe House of Young
Scientists (KHYS)”. He further acknowledges the hospitality during his
academic visit at the Rudolph Peierls Centre for Theoretical Physics.

##  Appendix A Relic Density

The functions $A_{ijkl},B_{ijkl},C_{kl}$ and $D_{kl}$ from eqs. (6.9) – (6.12)
read

$\displaystyle A_{ijkl}$
$\displaystyle=(m_{\phi_{j}}^{2}-m_{\ell_{l}}^{2}-t)(t+m_{\ell_{k}}^{2}-m_{\phi_{i}}^{2})-t(s-m_{\ell_{k}}^{2}-+m_{\ell_{l}}^{2})\,,$
(A.1) $\displaystyle B_{ijkl}$
$\displaystyle=\xi^{*}m_{\ell_{l}}(m_{\phi_{i}}^{2}-m_{\ell_{k}}^{2}-t)+\xi
m_{\ell_{k}}(m_{\phi_{j}}^{2}-m_{\ell_{l}}^{2}-t)\,,$ (A.2) $\displaystyle
C_{kl}$ $\displaystyle=-2m_{\ell_{k}}m_{\ell_{l}}t\,,$ (A.3) $\displaystyle
D_{kl}$
$\displaystyle=2|\xi|^{2}(s-m_{\ell_{k}}^{2}-m_{\ell_{l}}^{2})-2m_{\ell_{k}}m_{\ell_{l}}\left({\xi^{*}}^{2}+\xi^{2}\right)\,.$
(A.4)

The $p$-wave contribution to the thermally averaged annihilation cross section
from eq. (6.13) for $\xi\neq 0$ is given by

$\displaystyle b=$
$\displaystyle\frac{1}{9}\sum_{ijkl}\frac{|\lambda_{ik}|^{2}|\lambda_{jl}|^{2}}{32\pi
m_{\phi_{3}}^{2}}\Biggl{\\{}\frac{\left(2+\mu_{2}^{2}+\mu_{1}^{2}+\left(\mu_{1}^{2}-\mu_{2}^{2}\right)\cos
2\theta_{\psi}\right)^{2}}{\left(1+\mu_{2}^{2}\right)^{2}\left(1+\mu_{1}^{2}\right)^{2}}$
$\displaystyle-\frac{|\xi|^{2}\sin^{2}2\theta_{\psi}(\mu_{2}-\mu_{1})^{2}}{(1+\mu_{2}^{2})^{4}(1+\mu_{1}^{2})^{4}}\biggr{[}3\left(\mu_{2}^{6}+6\mu_{2}^{4}+\mu_{1}^{2}\right)\mu_{2}^{6}$
$\displaystyle+2\mu_{1}\left(\mu_{1}^{2}-5\right)\left(3\mu_{1}^{2}+1\right)\mu_{2}^{5}+\left(18\mu_{1}^{6}+31\mu_{1}^{4}+4\mu_{1}^{2}+3\right)\mu_{2}^{4}$
$\displaystyle-4\mu_{1}\left(7\mu_{1}^{4}+26\mu_{1}^{2}+7\right)\mu_{2}^{3}+\left(3\mu_{1}^{6}+4\mu_{1}^{4}+31\mu_{1}^{2}+18\right)\mu_{2}^{2}$
$\displaystyle-2\mu_{1}\left(\mu_{1}^{2}+3\right)\left(5\mu_{1}^{2}-1\right)\mu_{2}+3\mu_{1}^{2}\left(\mu_{1}^{2}+6\right)+3\biggl{]}$
$\displaystyle+4|\xi|^{4}\,\Biggl{[}\frac{\cos^{4}\left(\theta_{\psi}\right)}{\left(\mu_{1}^{2}+1\right){}^{2}}+\frac{\sin^{2}\left(\theta_{\psi}\right)}{\left(\mu_{2}^{2}+1\right){}^{2}}\Biggl{(}\frac{2\left(\mu_{2}^{2}+1\right)\cos^{2}\left(\theta_{\psi}\right)}{\mu_{1}^{2}+1}$
$\displaystyle+\sin^{2}\left(\theta_{\psi}\right)\Biggr{)}+\frac{1}{\left(\mu_{0}^{2}+1\right){}^{2}}\Biggr{]}\Biggr{\\}}\,,$
(A.5)

in the limit of equal initial state masses and vanishing final state masses.
Here we have used $\mu_{\alpha}=m_{\psi_{\alpha}}/m_{\phi_{3}}$.

##  Appendix B Direct Detection

The DM–nucleon cross section for $t$-channel scatterings through the Higgs
portal reads [77]

$\sigma_{\text{SI}}^{N,H\phi}=\frac{\lambda_{H\phi}^{2}y_{N}^{2}}{4\pi}\frac{\mu^{2}m_{N}^{2}}{m_{H}^{4}m_{\phi_{3}}^{2}}\,,$
(B.1)

where $m_{N}$ is the nucleon mass and
$\mu=m_{\phi_{3}}m_{N}/(m_{\phi_{3}}+m_{N})$ is the reduced mass of the
DM–nucleon system. In order to estimate in which parts of the parameter space
these contributions grow larger than the photon one-loop penguin from Figure
2(a) that we consider in the numerical analysis, we set the couplings to
$|\lambda_{i3}|=2$ and $|\xi|=1$ as well as $y_{\psi}=0$ in eq. (7.4) for
maximum mixing with $\theta_{\psi}=\pi/4$. Comparing with eq. (B.1) then gives
the maximum allowed value of the Higgs portal coupling $\lambda_{H\phi}$ for
at most equal scattering cross sections. This illustrated by the contours
shown in Figure B.1.

Figure B.1: Maximum allowed values of $\lambda_{H\phi}$ in order to give at
most equal contributions to the DM–nucleon scattering cross section as the
photon penguin diagram.

##  Appendix C Indirect Detection

The expression for the interference term of $\psi_{1}$ and $\psi_{2}$ for the
internal bremsstrahlung process of Figure 3(a) is given by

$\displaystyle\autobreak\langle\sigma
v\rangle_{\ell\bar{\ell}\gamma}^{12}=\sum_{ij}\frac{-\alpha_{\text{em}}|\lambda_{i3}|^{2}|\lambda_{j3}|^{2}\left(c^{2}_{\theta}+|\xi|^{2}s^{2}_{\theta}\right)\left(s^{2}_{\theta}+|\xi|^{2}c^{2}_{\theta}\right)}{128m_{\phi_{3}}^{2}\pi^{2}(\mu_{2}-\mu_{1})^{2}}\Biggl{\\{}-4p_{1}\mu_{2}(1+\mu_{2})^{2}+4p_{2}\mu_{2}(1+\mu_{2})^{2}-2(\mu_{2}-\mu_{1})^{2}-4p_{3}\mu_{1}(1+\mu_{1})^{2}+4p_{4}\mu_{1}(1+\mu_{1})^{2}+p_{5}(\mu_{2}+\mu_{1})(2+\mu_{2}(2+\mu_{2})+\mu_{1}(2+\mu_{1}))-p_{6}(\mu_{2}+\mu_{1})(2+\mu_{2}(2+\mu_{2})+\mu_{1}(2+\mu_{1}))+p_{7}(\mu_{2}+\mu_{1})(2+\mu_{2}(2+\mu_{2})+\mu_{1}(2+\mu_{1}))-p_{8}(\mu_{2}+\mu_{1})(2+\mu_{2}(2+\mu_{2})+\mu_{1}(2+\mu_{1}))+\mu_{2}^{3}(4l_{1}^{2}-l_{2}l_{3}+l_{3}l_{4}-3l_{5}-l_{3}l_{5}+l_{4}l_{5}+4l_{5}l_{6}+l_{1}(3+l_{2}+l_{3}-2l_{4}-4l_{5}-4l_{6}-l_{8})+l_{5}l_{8})+\mu_{2}^{2}(8l_{1}^{2}-2l_{2}(1+l_{3})+2l_{4}(1+l_{3}+l_{5})-2l_{5}(l_{3}-4l_{6})+2l_{1}(l_{2}+l_{3}-2(l_{4}+2(l_{5}+l_{6})))-l_{1}l_{9}+l_{5}l_{9}+(-l_{2}(-2+l_{3})+l_{1}(-1+l_{2}+l_{3}-2l_{4})+(-2+l_{3})l_{4}+(1-l_{3}+l_{4})l_{5})\mu_{1})+\mu_{2}(4l_{1}^{2}-l_{2}(3+2l_{3})+2l_{3}l_{4}-2l_{3}l_{5}+2l_{4}l_{5}\
+3(l_{4}+l_{5})+4l_{5}l_{6}+l_{1}(-3+2l_{2}+2l_{3}-4l_{4}-4l_{5}-4l_{6}-l_{8})+l_{5}l_{8}+\mu_{1}(2(l_{2}-2l_{2}l_{3}+l_{1}(-1+2l_{2}+2l_{3}-4l_{4})-l_{4}+2l_{3}l_{4}+l_{5}-2l_{3}l_{5}+2l_{4}l_{5})+(l_{2}-l_{2}l_{3}+l_{1}(-2+l_{2}+l_{3}-2l_{4})+(-1+l_{3})l_{4}+(2-l_{3}+l_{4})l_{5})\mu_{1}))+\mu_{1}(l_{1}(3+2l_{2}+2l_{3}-4l_{4})+2l_{3}l_{4}+4l_{4}^{2}-2l_{3}l_{5}+2l_{4}l_{5}-3(l_{4}+l_{5})-4l_{4}l_{7}-l_{4}l_{8}+l_{2}(3-2l_{3}-4l_{4}+4l_{7}+l_{8})+\mu_{1}(2l_{1}(1+l_{2}+l_{3}-2l_{4})-2(l_{5}+l_{3}(-l_{4}+l_{5})+l_{2}(l_{3}+4l_{4}-4l_{7})-l_{4}(4l_{4}+l_{5}-4l_{7}))+(l_{2}-l_{4})l_{9}+(l_{1}(l_{3}-2l_{4})+3l_{4}+l_{3}l_{4}+4l_{4}^{2}-l_{3}l_{5}+l_{4}l_{5}-4l_{4}l_{7}-l_{4}l_{8}+l_{2}(-3+l_{1}-l_{3}-4l_{4}+4l_{7}+l_{8}))\mu_{1}))\Biggr{\\}}\,,$
(C.1)

with the logarithms $l_{i}$ and polylogarithms $p_{i}$ defined as

$\displaystyle l_{1}$ $\displaystyle=\log(1+\mu_{2})\,,\quad$ $\displaystyle
l_{2}$ $\displaystyle=\log(\mu_{1}-1)\,,\quad$ $\displaystyle l_{3}$
$\displaystyle=\log(\mu_{2}+\mu_{1})\,,$ $\displaystyle l_{4}$
$\displaystyle=\log(1+\mu_{1})\,,\quad$ $\displaystyle l_{5}$
$\displaystyle=\log(\mu_{2}-1)\,,\quad$ $\displaystyle l_{6}$
$\displaystyle=\log(\mu_{2})\,,$ $\displaystyle l_{7}$
$\displaystyle=\log(\mu_{1})\,,\phantom{+1}$ $\displaystyle l_{8}$
$\displaystyle=\log(16)\,,\phantom{+11}$ $\displaystyle l_{9}$
$\displaystyle=\log(256)\,,$ (C.2)

and

$\displaystyle p_{1}$
$\displaystyle=\text{Li}_{2}\left(\frac{\mu_{2}-1}{2\mu_{2}}\right)\,,$
$\displaystyle p_{2}$
$\displaystyle=\text{Li}_{2}\left(\frac{1+\mu_{2}}{2\mu_{2}}\right)\,,$
$\displaystyle p_{3}$
$\displaystyle=\text{Li}_{2}\left(\frac{\mu_{1}-1}{2\mu_{1}}\right)\,,$
$\displaystyle p_{4}$
$\displaystyle=\text{Li}_{2}\left(\frac{1+\mu_{1}}{2\mu_{1}}\right)\,,$
$\displaystyle p_{5}$
$\displaystyle=\text{Li}_{2}\left(\frac{\mu_{2}-1}{\mu_{2}+\mu_{1}}\right)\,,\quad$
$\displaystyle p_{6}$
$\displaystyle=\text{Li}_{2}\left(\frac{1+\mu_{2}}{\mu_{2}+\mu_{1}}\right)\,,$
$\displaystyle p_{7}$
$\displaystyle=\text{Li}_{2}\left(\frac{\mu_{1}-1}{\mu_{2}+\mu_{1}}\right)\,,\quad$
$\displaystyle p_{8}$
$\displaystyle=\text{Li}_{2}\left(\frac{1+\mu_{1}}{\mu_{2}+\mu_{1}}\right)\,.$
(C.3)

The constraint coming from indirect detection experiments for the case of
suppressed left-handed interactions is shown in Figure C.1.

(a) constraints from the positron flux

(b) constraints from the $\gamma$ continuum spectrum

(c) constraints from the $\gamma$ line spectrum

Figure C.1: Restrictions on the model parameters from indirect detection
experiments for suppressed left-handed interactions. In all three plots we
have assumed maximum mixing with $\theta_{\psi}=\pi/4$. The area included by
the white dashed line and the equal mass diagonal indicates in which mass
regime the constraints are relevant.

## References

  * [1] G. Bertone, D. Hooper and J. Silk, _Particle dark matter: Evidence, candidates and constraints_ , _Phys. Rept._ 405 (2005) 279 [hep-ph/0404175].
  * [2] Muon g-2 collaboration, _Measurement of the Positive Muon Anomalous Magnetic Moment to 0.46 ppm_ , _Phys. Rev. Lett._ 126 (2021) 141801 [2104.03281].
  * [3] T. Aoyama et al., _The anomalous magnetic moment of the muon in the Standard Model_ , _Phys. Rept._ 887 (2020) 1 [2006.04822].
  * [4] J. Kile and A. Soni, _Flavored Dark Matter in Direct Detection Experiments and at LHC_ , _Phys. Rev. D_ 84 (2011) 035016 [1104.5239].
  * [5] J. F. Kamenik and J. Zupan, _Discovering Dark Matter Through Flavor Violation at the LHC_ , _Phys. Rev. D_ 84 (2011) 111502 [1107.0623].
  * [6] B. Batell, J. Pradler and M. Spannowsky, _Dark Matter from Minimal Flavor Violation_ , _JHEP_ 08 (2011) 038 [1105.1781].
  * [7] P. Agrawal, S. Blanchet, Z. Chacko and C. Kilic, _Flavored Dark Matter, and Its Implications for Direct Detection and Colliders_ , _Phys. Rev. D_ 86 (2012) 055002 [1109.3516].
  * [8] B. Batell, T. Lin and L.-T. Wang, _Flavored Dark Matter and R-Parity Violation_ , _JHEP_ 01 (2014) 075 [1309.4462].
  * [9] J. Kile, _Flavored Dark Matter: A Review_ , _Mod. Phys. Lett. A_ 28 (2013) 1330031 [1308.0584].
  * [10] J. Kile, A. Kobach and A. Soni, _Lepton-Flavored Dark Matter_ , _Phys. Lett. B_ 744 (2015) 330 [1411.1407].
  * [11] L. Lopez-Honorez and L. Merlo, _Dark matter within the minimal flavour violation ansatz_ , _Phys. Lett. B_ 722 (2013) 135 [1303.1087].
  * [12] A. Kumar and S. Tulin, _Top-flavored dark matter and the forward-backward asymmetry_ , _Phys. Rev. D_ 87 (2013) 095006 [1303.0332].
  * [13] Y. Zhang, _Top Quark Mediated Dark Matter_ , _Phys. Lett. B_ 720 (2013) 137 [1212.2730].
  * [14] A. J. Buras, P. Gambino, M. Gorbahn, S. Jager and L. Silvestrini, _Universal unitarity triangle and physics beyond the standard model_ , _Phys. Lett. B_ 500 (2001) 161 [hep-ph/0007085].
  * [15] G. D’Ambrosio, G. F. Giudice, G. Isidori and A. Strumia, _Minimal flavor violation: An Effective field theory approach_ , _Nucl. Phys. B_ 645 (2002) 155 [hep-ph/0207036].
  * [16] A. J. Buras, _Minimal flavor violation_ , _Acta Phys. Polon. B_ 34 (2003) 5615 [hep-ph/0310208].
  * [17] R. S. Chivukula and H. Georgi, _Composite Technicolor Standard Model_ , _Phys. Lett. B_ 188 (1987) 99.
  * [18] L. J. Hall and L. Randall, _Weak scale effective supersymmetry_ , _Phys. Rev. Lett._ 65 (1990) 2939.
  * [19] V. Cirigliano, B. Grinstein, G. Isidori and M. B. Wise, _Minimal flavor violation in the lepton sector_ , _Nucl. Phys. B_ 728 (2005) 121 [hep-ph/0507001].
  * [20] P. Agrawal, M. Blanke and K. Gemmler, _Flavored dark matter beyond Minimal Flavor Violation_ , _JHEP_ 10 (2014) 072 [1405.6709].
  * [21] M.-C. Chen, J. Huang and V. Takhistov, _Beyond Minimal Lepton Flavored Dark Matter_ , _JHEP_ 02 (2016) 060 [1510.04694].
  * [22] M. Blanke and S. Kast, _Top-Flavoured Dark Matter in Dark Minimal Flavour Violation_ , _JHEP_ 05 (2017) 162 [1702.08457].
  * [23] M. Blanke, S. Das and S. Kast, _Flavoured Dark Matter Moving Left_ , _JHEP_ 02 (2018) 105 [1711.10493].
  * [24] T. Jubb, M. Kirk and A. Lenz, _Charming Dark Matter_ , _JHEP_ 12 (2017) 010 [1709.01930].
  * [25] H. Acaroğlu and M. Blanke, _Tasting flavoured Majorana dark matter_ , _JHEP_ 05 (2022) 086 [2109.10357].
  * [26] H. Acaroğlu, P. Agrawal and M. Blanke, _Lepton-Flavoured Scalar Dark Matter in Dark Minimal Flavour Violation_ , 2211.03809.
  * [27] Y. Bai and J. Berger, _Lepton Portal Dark Matter_ , _JHEP_ 08 (2014) 153 [1402.6696].
  * [28] C.-J. Lee and J. Tandean, _Lepton-Flavored Scalar Dark Matter with Minimal Flavor Violation_ , _JHEP_ 04 (2015) 174 [1410.6803].
  * [29] A. Hamze, C. Kilic, J. Koeller, C. Trendafilova and J.-H. Yu, _Lepton-Flavored Asymmetric Dark Matter and Interference in Direct Detection_ , _Phys. Rev. D_ 91 (2015) 035009 [1410.3030].
  * [30] J. Kawamura, S. Okawa and Y. Omura, _Current status and muon $g-2$ explanation of lepton portal dark matter_, _JHEP_ 08 (2020) 042 [2002.12534].
  * [31] ALEPH collaboration, _Search for charginos nearly mass degenerate with the lightest neutralino in e+ e- collisions at center-of-mass energies up to 209-GeV_ , _Phys. Lett. B_ 533 (2002) 223 [hep-ex/0203020].
  * [32] DELPHI collaboration, _Searches for supersymmetric particles in e+ e- collisions up to 208-GeV and interpretation of the results within the MSSM_ , _Eur. Phys. J. C_ 31 (2003) 421 [hep-ex/0311019].
  * [33] CMS collaboration, _Search for new physics in the lepton plus missing transverse momentum final state in proton-proton collisions at $\sqrt{s}=$ 13 TeV_, _JHEP_ 07 (2022) 067 [2202.06075].
  * [34] ATLAS collaboration, _Search for a new heavy gauge boson resonance decaying into a lepton and missing transverse momentum in 36 fb -1 of $pp$ collisions at $\sqrt{s}=$ 13 TeV with the ATLAS experiment_, _Eur. Phys. J. C_ 78 (2018) 401 [1706.04786].
  * [35] ATLAS collaboration, _Search for chargino–neutralino pair production in final states with three leptons and missing transverse momentum in $\sqrt{s}=13$ TeV pp collisions with the ATLAS detector_, _Eur. Phys. J. C_ 81 (2021) 1118 [2106.01676].
  * [36] ATLAS collaboration, _Search for direct stau production in events with two hadronic $\tau$-leptons in $\sqrt{s}=13$ TeV $pp$ collisions with the ATLAS detector_, _Phys. Rev. D_ 101 (2020) 032009 [1911.06660].
  * [37] CMS collaboration, _Search for supersymmetry in final states with two oppositely charged same-flavor leptons and missing transverse momentum in proton-proton collisions at $\sqrt{s}=$ 13 TeV_, _JHEP_ 04 (2021) 123 [2012.08600].
  * [38] CMS collaboration, _Search for supersymmetric partners of electrons and muons in proton-proton collisions at $\sqrt{s}=$ 13 TeV_, _Phys. Lett. B_ 790 (2019) 140 [1806.05264].
  * [39] ATLAS collaboration, _Search for electroweak production of charginos and sleptons decaying into final states with two leptons and missing transverse momentum in $\sqrt{s}=13$ TeV $pp$ collisions using the ATLAS detector_, _Eur. Phys. J. C_ 80 (2020) 123 [1908.08215].
  * [40] ATLAS collaboration, _Search for direct production of charginos, neutralinos and sleptons in final states with two leptons and missing transverse momentum in $pp$ collisions at $\sqrt{s}=$ 8 TeV with the ATLAS detector_, _JHEP_ 05 (2014) 071 [1403.5294].
  * [41] G. Alguero, J. Heisig, C. K. Khosa, S. Kraml, S. Kulkarni, A. Lessa et al., _Constraining new physics with SModelS version 2_ , _JHEP_ 08 (2022) 068 [2112.00769].
  * [42] A. Alloul, N. D. Christensen, C. Degrande, C. Duhr and B. Fuks, _FeynRules 2.0 - A complete toolbox for tree-level phenomenology_ , _Comput. Phys. Commun._ 185 (2014) 2250 [1310.1921].
  * [43] C. Degrande, C. Duhr, B. Fuks, D. Grellscheid, O. Mattelaer and T. Reiter, _UFO - The Universal FeynRules Output_ , _Comput. Phys. Commun._ 183 (2012) 1201 [1108.2040].
  * [44] J. Alwall, R. Frederix, S. Frixione, V. Hirschi, F. Maltoni, O. Mattelaer et al., _The automated computation of tree-level and next-to-leading order differential cross sections, and their matching to parton shower simulations_ , _JHEP_ 07 (2014) 079 [1405.0301].
  * [45] Z. Chacko and G. D. Kribs, _Constraints on lepton flavor violation in the MSSM from the muon anomalous magnetic moment measurement_ , _Phys. Rev. D_ 64 (2001) 075015 [hep-ph/0104317].
  * [46] J. Kersten, J.-h. Park, D. Stöckinger and L. Velasco-Sevilla, _Understanding the correlation between $(g-2)_{\mu}$ and $\mu\rightarrow e\gamma$ in the MSSM_, _JHEP_ 08 (2014) 118 [1405.2972].
  * [47] MEG collaboration, _Search for the lepton flavour violating decay $\mu^{+}\rightarrow\mathrm{e}^{+}\gamma$ with the full dataset of the MEG experiment_, _Eur. Phys. J. C_ 76 (2016) 434 [1605.05081].
  * [48] BaBar collaboration, _Searches for Lepton Flavor Violation in the Decays tau+- — $>$ e+- gamma and tau+- —$>$ mu+- gamma_, _Phys. Rev. Lett._ 104 (2010) 021802 [0908.2381].
  * [49] Belle collaboration, _Search for lepton-flavor-violating tau-lepton decays to $\ell\gamma$ at Belle_, _JHEP_ 10 (2021) 19 [2103.12994].
  * [50] Particle Data Group collaboration, _Review of Particle Physics_ , _PTEP_ 2020 (2020) 083C01.
  * [51] K. Cheung, O. C. W. Kong and J. S. Lee, _Electric and anomalous magnetic dipole moments of the muon in the MSSM_ , _JHEP_ 06 (2009) 020 [0904.4352].
  * [52] M. E. Pospelov and I. B. Khriplovich, _Electric dipole moment of the W boson and the electron in the Kobayashi-Maskawa model_ , _Sov. J. Nucl. Phys._ 53 (1991) 638.
  * [53] M. Pospelov and A. Ritz, _Electric dipole moments as probes of new physics_ , _Annals Phys._ 318 (2005) 119 [hep-ph/0504231].
  * [54] S. P. Martin and J. D. Wells, _Muon Anomalous Magnetic Dipole Moment in Supersymmetric Theories_ , _Phys. Rev. D_ 64 (2001) 035003 [hep-ph/0103067].
  * [55] T. Ibrahim and P. Nath, _CP Violation From Standard Model to Strings_ , _Rev. Mod. Phys._ 80 (2008) 577 [0705.2008].
  * [56] Muon (g-2) collaboration, _An Improved Limit on the Muon Electric Dipole Moment_ , _Phys. Rev. D_ 80 (2009) 052008 [0811.1207].
  * [57] Belle collaboration, _Search for the electric dipole moment of the tau lepton_ , _Phys. Lett. B_ 551 (2003) 16 [hep-ex/0210066].
  * [58] ACME collaboration, _Improved limit on the electric dipole moment of the electron_ , _Nature_ 562 (2018) 355.
  * [59] DELPHI collaboration, _Study of tau-pair production in photon-photon collisions at LEP and limits on the anomalous electromagnetic moments of the tau lepton_ , _Eur. Phys. J. C_ 35 (2004) 159 [hep-ex/0406010].
  * [60] ATLAS collaboration, _Observation of the $\gamma\gamma\to\tau\tau$ process in Pb+Pb collisions and constraints on the $\tau$-lepton anomalous magnetic moment with the ATLAS detector_, 2204.13478.
  * [61] D. Hanneke, S. Fogwell and G. Gabrielse, _New measurement of the electron magnetic moment and the fine structure constant_ , _Phys. Rev. Lett._ 100 (2008) 120801.
  * [62] R. H. Parker, C. Yu, W. Zhong, B. Estey and H. Müller, _Measurement of the fine-structure constant as a test of the standard model_ , _Science_ 360 (2018) 191.
  * [63] T. Aoyama, T. Kinoshita and M. Nio, _Theory of the anomalous magnetic moment of the electron_ , _Atoms_ 7 (2019) .
  * [64] L. Morel, Z. Yao, P. Cladé and S. Guellati-Khélifa, _Determination of the fine-structure constant with an accuracy of 81 parts per trillion_ , _Nature_ 588 (2020) 61.
  * [65] T. Aoyama, M. Hayakawa, T. Kinoshita and M. Nio, _Tenth-Order QED Contribution to the Electron g-2 and an Improved Value of the Fine Structure Constant_ , _Phys. Rev. Lett._ 109 (2012) 111807 [1205.5368].
  * [66] Planck collaboration, _Planck 2018 results. VI. Cosmological parameters_ , _Astron. Astrophys._ 641 (2020) A6 [1807.06209].
  * [67] H. Acaroğlu, M. Blanke, J. Heisig, M. Krämer, M. Mühlleitner and L. Rathmann, _Phenomenological Details of Flavoured Majorana Dark Matter_ , _in preparation_ (2023) .
  * [68] M. Srednicki, R. Watkins and K. A. Olive, _Calculations of Relic Densities in the Early Universe_ , _Nucl. Phys. B_ 310 (1988) 693.
  * [69] P. Gondolo and G. Gelmini, _Cosmic abundances of stable particles: Improved analysis_ , _Nucl. Phys. B_ 360 (1991) 145.
  * [70] J. D. Wells, _Annihilation cross-sections for relic densities in the low velocity limit_ , hep-ph/9404219.
  * [71] F. Giacchino, L. Lopez-Honorez and M. H. G. Tytgat, _Scalar Dark Matter Models with Significant Internal Bremsstrahlung_ , _JCAP_ 10 (2013) 025 [1307.6480].
  * [72] T. Toma, _Internal Bremsstrahlung Signature of Real Scalar Dark Matter and Consistency with Thermal Relic Density_ , _Phys. Rev. Lett._ 111 (2013) 091301 [1307.6181].
  * [73] G. Steigman, B. Dasgupta and J. F. Beacom, _Precise Relic WIMP Abundance and its Impact on Searches for Dark Matter Annihilation_ , _Phys. Rev. D_ 86 (2012) 023506 [1204.3622].
  * [74] G. Steigman, _CMB Constraints On The Thermal WIMP Mass And Annihilation Cross Section_ , _Phys. Rev. D_ 91 (2015) 083538 [1502.01884].
  * [75] J. Kopp, V. Niro, T. Schwetz and J. Zupan, _DAMA/LIBRA and leptonically interacting Dark Matter_ , _Phys. Rev. D_ 80 (2009) 083502 [0907.3159].
  * [76] D. V. Nguyen, D. Sarnaaik, K. K. Boddy, E. O. Nadler and V. Gluscevic, _Observational constraints on dark matter scattering with electrons_ , _Phys. Rev. D_ 104 (2021) 103521 [2107.12380].
  * [77] J. M. Cline, K. Kainulainen, P. Scott and C. Weniger, _Update on scalar singlet dark matter_ , _Phys. Rev. D_ 88 (2013) 055025 [1306.4710].
  * [78] XENON collaboration, _XENON1T results from 1 tonne $\times$ year WIMP search_, _PoS_ NOW2018 (2018) 094.
  * [79] S. Tulin, H.-B. Yu and K. M. Zurek, _Three Exceptions for Thermal Dark Matter with Enhanced Annihilation to $\gamma\gamma$_, _Phys. Rev. D_ 87 (2013) 036011 [1208.0009].
  * [80] L. Bergstrom, T. Bringmann and J. Edsjo, _New Positron Spectral Features from Supersymmetric Dark Matter - a Way to Explain the PAMELA Data?_ , _Phys. Rev. D_ 78 (2008) 103520 [0808.3725].
  * [81] T. Bringmann, L. Bergstrom and J. Edsjo, _New Gamma-Ray Contributions to Supersymmetric Dark Matter Annihilation_ , _JHEP_ 01 (2008) 049 [0710.3169].
  * [82] P. Ciafaloni, M. Cirelli, D. Comelli, A. De Simone, A. Riotto and A. Urbano, _On the Importance of Electroweak Corrections for Majorana Dark Matter Indirect Detection_ , _JCAP_ 06 (2011) 018 [1104.2996].
  * [83] V. Barger, W.-Y. Keung and D. Marfatia, _Bremsstrahlung in dark matter annihilation_ , _Phys. Lett. B_ 707 (2012) 385 [1111.4523].
  * [84] A. Ibarra, T. Toma, M. Totzauer and S. Wild, _Sharp Gamma-ray Spectral Features from Scalar Dark Matter Annihilations_ , _Phys. Rev. D_ 90 (2014) 043526 [1405.6917].
  * [85] AMS collaboration, _First Result from the Alpha Magnetic Spectrometer on the International Space Station: Precision Measurement of the Positron Fraction in Primary Cosmic Rays of 0.5–350 GeV_ , _Phys. Rev. Lett._ 110 (2013) 141102.
  * [86] T. Bringmann, X. Huang, A. Ibarra, S. Vogl and C. Weniger, _Fermi LAT Search for Internal Bremsstrahlung Signatures from Dark Matter Annihilation_ , _JCAP_ 07 (2012) 054 [1203.1312].
  * [87] H.E.S.S. collaboration, _Search for Photon-Linelike Signatures from Dark Matter Annihilations with H.E.S.S._ , _Phys. Rev. Lett._ 110 (2013) 041301 [1301.1173].
  * [88] A. Ibarra, A. S. Lamperstorfer and J. Silk, _Dark matter annihilations and decays after the AMS-02 positron measurements_ , _Phys. Rev. D_ 89 (2014) 063539 [1309.2570].
  * [89] M. Tavakoli, I. Cholis, C. Evoli and P. Ullio, _Constraints on Dark Matter Annihilations from Diffuse Gamma-Ray Emission in the Galaxy_ , _JCAP_ 01 (2014) 017 [1308.4135].
  * [90] M. Garny, A. Ibarra, M. Pato and S. Vogl, _Internal bremsstrahlung signatures in light of direct dark matter searches_ , _JCAP_ 12 (2013) 046 [1306.6342].
  * [91] Muon g-2 collaboration, _Final Report of the Muon E821 Anomalous Magnetic Moment Measurement at BNL_ , _Phys. Rev. D_ 73 (2006) 072003 [hep-ex/0602035].
  * [92] T. Aoyama, M. Hayakawa, T. Kinoshita and M. Nio, _Complete Tenth-Order QED Contribution to the Muon g-2_ , _Phys. Rev. Lett._ 109 (2012) 111808 [1205.5370].
  * [93] T. Aoyama, T. Kinoshita and M. Nio, _Theory of the Anomalous Magnetic Moment of the Electron_ , _Atoms_ 7 (2019) 28.
  * [94] A. Czarnecki, W. J. Marciano and A. Vainshtein, _Refinements in electroweak contributions to the muon anomalous magnetic moment_ , _Phys. Rev. D_ 67 (2003) 073006 [hep-ph/0212229].
  * [95] C. Gnendiger, D. Stöckinger and H. Stöckinger-Kim, _The electroweak contributions to $(g-2)_{\mu}$ after the Higgs boson mass measurement_, _Phys. Rev. D_ 88 (2013) 053005 [1306.5546].
  * [96] M. Davier, A. Hoecker, B. Malaescu and Z. Zhang, _Reevaluation of the hadronic vacuum polarisation contributions to the Standard Model predictions of the muon $g-2$ and ${\alpha(m_{Z}^{2})}$ using newest hadronic cross-section data_, _Eur. Phys. J. C_ 77 (2017) 827 [1706.09436].
  * [97] A. Keshavarzi, D. Nomura and T. Teubner, _Muon $g-2$ and $\alpha(M_{Z}^{2})$: a new data-based analysis_, _Phys. Rev. D_ 97 (2018) 114025 [1802.02995].
  * [98] G. Colangelo, M. Hoferichter and P. Stoffer, _Two-pion contribution to hadronic vacuum polarization_ , _JHEP_ 02 (2019) 006 [1810.00007].
  * [99] M. Hoferichter, B.-L. Hoid and B. Kubis, _Three-pion contribution to hadronic vacuum polarization_ , _JHEP_ 08 (2019) 137 [1907.01556].
  * [100] M. Davier, A. Hoecker, B. Malaescu and Z. Zhang, _A new evaluation of the hadronic vacuum polarisation contributions to the muon anomalous magnetic moment and to $\mathbf{\boldsymbol{\alpha}(m_{Z}^{2})}$_, _Eur. Phys. J. C_ 80 (2020) 241 [1908.00921].
  * [101] A. Keshavarzi, D. Nomura and T. Teubner, _$g-2$ of charged leptons, $\alpha(M^{2}_{Z})$ , and the hyperfine splitting of muonium_, _Phys. Rev. D_ 101 (2020) 014029 [1911.00367].
  * [102] A. Kurz, T. Liu, P. Marquard and M. Steinhauser, _Hadronic contribution to the muon anomalous magnetic moment to next-to-next-to-leading order_ , _Phys. Lett. B_ 734 (2014) 144 [1403.6400].
  * [103] K. Melnikov and A. Vainshtein, _Hadronic light-by-light scattering contribution to the muon anomalous magnetic moment revisited_ , _Phys. Rev. D_ 70 (2004) 113006 [hep-ph/0312226].
  * [104] P. Masjuan and P. Sanchez-Puertas, _Pseudoscalar-pole contribution to the $(g_{\mu}-2)$: a rational approach_, _Phys. Rev. D_ 95 (2017) 054026 [1701.05829].
  * [105] G. Colangelo, M. Hoferichter, M. Procura and P. Stoffer, _Dispersion relation for hadronic light-by-light scattering: two-pion contributions_ , _JHEP_ 04 (2017) 161 [1702.07347].
  * [106] M. Hoferichter, B.-L. Hoid, B. Kubis, S. Leupold and S. P. Schneider, _Dispersion relation for hadronic light-by-light scattering: pion pole_ , _JHEP_ 10 (2018) 141 [1808.04823].
  * [107] A. Gérardin, H. B. Meyer and A. Nyffeler, _Lattice calculation of the pion transition form factor with $N_{f}=2+1$ Wilson quarks_, _Phys. Rev. D_ 100 (2019) 034520 [1903.09471].
  * [108] J. Bijnens, N. Hermansson-Truedsson and A. Rodríguez-Sánchez, _Short-distance constraints for the HLbL contribution to the muon anomalous magnetic moment_ , _Phys. Lett. B_ 798 (2019) 134994 [1908.03331].
  * [109] G. Colangelo, F. Hagelstein, M. Hoferichter, L. Laub and P. Stoffer, _Longitudinal short-distance constraints for the hadronic light-by-light contribution to $(g-2)_{\mu}$ with large-$N_{c}$ Regge models_, _JHEP_ 03 (2020) 101 [1910.13432].
  * [110] T. Blum, N. Christ, M. Hayakawa, T. Izubuchi, L. Jin, C. Jung et al., _Hadronic Light-by-Light Scattering Contribution to the Muon Anomalous Magnetic Moment from Lattice QCD_ , _Phys. Rev. Lett._ 124 (2020) 132002 [1911.08123].
  * [111] G. Colangelo, M. Hoferichter, A. Nyffeler, M. Passera and P. Stoffer, _Remarks on higher-order hadronic corrections to the muon g $-$2_, _Phys. Lett. B_ 735 (2014) 90 [1403.7512].
  * [112] M. Cè et al., _Window observable for the hadronic vacuum polarization contribution to the muon $g-2$ from lattice QCD_, 2206.06582.
  * [113] S. Borsanyi et al., _Leading hadronic contribution to the muon magnetic moment from lattice QCD_ , _Nature_ 593 (2021) 51 [2002.12347].
  * [114] G. Colangelo, A. X. El-Khadra, M. Hoferichter, A. Keshavarzi, C. Lehner, P. Stoffer et al., _Data-driven evaluations of Euclidean windows to scrutinize hadronic vacuum polarization_ , _Phys. Lett. B_ 833 (2022) 137313 [2205.12963].
  * [115] C. Alexandrou et al., _Lattice calculation of the short and intermediate time-distance hadronic vacuum polarization contributions to the muon magnetic moment using twisted-mass fermions_ , 2206.15084.
  * [116] A. Crivellin, M. Hoferichter, C. A. Manzari and M. Montull, _Hadronic Vacuum Polarization: $(g-2)_{\mu}$ versus Global Electroweak Fits_, _Phys. Rev. Lett._ 125 (2020) 091801 [2003.04886].
  * [117] A. Keshavarzi, W. J. Marciano, M. Passera and A. Sirlin, _Muon $g-2$ and $\Delta\alpha$ connection_, _Phys. Rev. D_ 102 (2020) 033002 [2006.12666].
  * [118] G. Colangelo, M. Hoferichter and P. Stoffer, _Constraints on the two-pion contribution to hadronic vacuum polarization_ , _Phys. Lett. B_ 814 (2021) 136073 [2010.07943].
  * [119] P. Athron, C. Balázs, D. H. J. Jacob, W. Kotlarski, D. Stöckinger and H. Stöckinger-Kim, _New physics explanations of a μ in light of the FNAL muon g $-$ 2 measurement_, _JHEP_ 09 (2021) 080 [2104.03691].
  * [120] D. Stöckinger and H. Stöckinger-Kim, _On the role of chirality flips for the muon magnetic moment and its relation to the muon mass_ , _Front. in Phys._ 10 (2022) 944614.