[1]Jan Rolfes These authors contributed equally to this work.

These authors contributed equally to this work.

These authors contributed equally to this work.

[1]Optimization and System Theory, KTH - Royal Institute of Technology,
Lindtstedtsvägen 25, Stockholm, 114 28, Sweden

2]Institute for Mathematics, University of Rostock, Universitätsplatz 1,
Rostock, 18051 Rostock, Germany

3]Abteilung Mathematik, Universität zu Köln, Weyertal 86-90, Köln, 50931,
Germany

# Bounds on polarization problems on compact sets via mixed integer
programming

<EMAIL_ADDRESS>Robert Schüler<EMAIL_ADDRESS>Marc Christian
Zimmermann<EMAIL_ADDRESS>*  [  [

###### Abstract

Finding point configurations, that yield the maximum polarization (Chebyshev
constant) is gaining interest in the field of geometric optimization. In the
present article, we study the problem of unconstrained maximum polarization on
compact sets. In particular, we discuss necessary conditions for local
optimality, such as that a locally optimal configuration is always contained
in the convex hull of the respective darkest points. Building on this, we
propose two sequences of mixed-integer linear programs in order to compute
lower and upper bounds on the maximal polarization, where the lower bound is
constructive. Moreover, we prove the convergence of these sequences towards
the maximal polarization.

###### keywords:

maximal polarization, potentials, mixed integer programming, geometric
optimization

###### pacs:

[

MSC Classification]31C20, 51-08, 90C11

##  1 Introduction

Suppose you were given a set $A$ and $N$ lamps you are to place such that the
darkest point in $A$ is as bright as possible. In less descriptive terms this
max-min problem is known as the maximal polarization problem, which we now
state in mathematical language.

Let $A,D\subset\mathds{R}^{n}$ be nonempty sets and let $K:A\times
D\rightarrow\mathds{R}\cup\\{+\infty\\}$ be a function bounded from below. An
$N$-point multiset $C\subseteq D$ will be refered to as _point configuration
(of $N$ points)_ and the set of all $N$-point configurations supported on $D$
will be denoted by $\mathcal{C}$. We assign the discrete $K$-potential
associated with $C$ to every point $p\in A$ as

$U_{K,A}(p,C)=\sum_{c\in C}K(p,c).$

To any point configuration we associate its _polarization_

$P_{K,A}(C)=\inf_{p\in A}U_{K,A}(p,C).$

It is then natural to consider the _(maximal) polarization problem_ :

$\mathcal{P}_{K}(A)=\sup_{C\in\mathcal{C}}P_{K,A}(C).$ (1)

For a broader context and overview of this formulation of the polarization
problem we refer to the recent monograph [1, CH. $14$]. Problems of this kind
have been extensively studied. In particular the case of $A=D=S^{n-1}$ being a
unit sphere and $K(x,y)=\|x-y\|^{-s}$ being related to a Riesz potential is
rich in results on explicit optimal configurations of few points (eg. [2],
[3], [4], [5], [6], [7] [8]), bounds on maximal polarization (eg. [4], [7])
and asymptotic results (eg. [9], [10], [11], [12]). Asymptotic results are
also available for more general choices of $A$, such as rectifiable sets.

Moreover, the polarization problem as stated in (1) is closely related to the
well-studied covering problem, i.e. the question, whether $A$ can be covered
by balls of radius $r>0$. In particular, let
$K(x,y)=\mathbbm{1}_{[0,r]}(\|x-y\|)$, then, a covering with $N$ balls exists
if and only if $1\leq\mathcal{P}_{K}(A)$. General discussions of covering
problems can be found, for example in the seminal book by Conway and Sloane
[13]. For covering problems on compact metric spaces we refer to [14] for an
overview, whereas constructive methods have been developed, e.g. in [15] and
[16].

In this paper we consider polarization problems of the following kind. The set
$A\subset\mathds{R}^{n}$ will be a compact set and we will impose no
restrictions on the point configurations, i.e. $D=\mathds{R}^{n}$.
Furthermore, we restrict to functions $K(x,y)=f(\|x-y\|)$ for some continuous
strictly monotone decreasing function
$f:\mathds{R}_{+}\rightarrow\mathds{R}_{+}$ and use the notation
$U_{f,A}(p,C)$, $P_{f,A}(C),\mathcal{P}_{f}(A)$. If the subscript parameters
are clear from context we omit them.

Under the above assumptions, we therefore consider the optimization problem

$\mathcal{P}_{f}(A)=\sup_{C\subset\mathcal{C}}P_{f,A}(C).$ (2)

For explicit computations we choose Gaussians $f(x)=e^{-ax^{2}}$. These
functions appear rather naturally in the context of universal optimality (cf.
[17]): Recall that a function $g:(0,\infty)\rightarrow\mathds{R}$ is
_completely monotonic_ if it is infinitely differentiable and the derivatives
satisfy $(-1)^{k}g^{(k)}\geq 0$ for all $k$. The functions $g(x)=e^{-\alpha
x}$ are completely monotonic and we can write $f(\|x-y\|)=g(\|x-y\|^{2})$. In
this context functions $f(x)=g(x^{2})$ are called completely monotonic
functions of squared distance.

A Theorem of Bernstein (cf. [18, Thm. 9.16]) asserts that every completely
monotonic function can be written as a convergent integral

$g(x)=\int e^{-\alpha x}d\mu(\alpha).$

From this one obtains that the set of completely monotonic functions of
squared distance is the cone spanned by the gaussians and the constant
function $x\mapsto 1$.

In particular the commonly used Riesz potentials can be written in this way.

We fix some more notation for the case that the infimum $P_{f,A}$ is in fact a
minimum, i.e. the minimizers of this function are points in $A$. In this case,
any such minimizer will be called a _darkest point_ of $A$. Moreover,

$\operatorname{Dark}_{A}(C)=\\{p\in A\ :\ \sum_{c\in
C}f(\|p-c\|)=P_{f,A}(C)\\}$

will be called the _set of darkest points_ of $C$. To explain this wording we
invite the reader to recall the interpretation of the problem we gave in the
beginning: we center lamps at the points in $C$ which now illuminate $A$. The
polarization of $A$ is then the lowest level of brightness any point in $A$
can have, any point realizing this is a “darkest point”.

Note, that requiring $A$ to be compact is rather natural. Indeed if $A$ were
unbounded, then the value of the polarization would always tend to $N\cdot\inf
f$. If $A$ were not closed, darkest points need not exist. Consider for
example $A$ to be the open disc and $C$ only containing the origin. In this
case, $P_{f,A}(C)$ is not attained at any point in $A$.

In Section 2 we provide some results connecting a locally optimal
configuration to the set of its respective darkest points. Theorem 2.1 states
that the points of such a configuration are contained in the convex hull of
the darkest points while on the other hand Theorem 2.5 states that the darkest
points are located either on the boundary of $A$ or in the interior of the
convex hull of the configuration. These restrictions provide necessary
conditions for optimality.

In Section 3 we investigate mixed-integer approximations of the polarization
problem providing upper and lower bounds. These are collected in Theorem 3.5.
We then prove that these bounds indeed converge to $\mathcal{P}_{f}(A)$ in
Theorems 3.8 and 3.9.

In Section 4 we illustrate capabilities and limitations of the approach on
some benchmark instances.

##  2 Darkest points and necessary conditions

In this section, we investigate structural properties an optimal configuration
needs to satisfy in order to potentially falsify the optimality of a given
polarization and reduce the search space of optimal configurations.

In particular, we have the following necessary condition that relates local
optimality of a configuration to the set of its darkest points:

######  Theorem 2.1.

If $C$ is a locally optimal solution of (2), then

$C\subset\operatorname{conv}\operatorname{Dark}_{A}(C).$

###### Proof.

Suppose $C$ is a configuration for which we have $c\in C$ such that
$c\notin\operatorname{conv}(\operatorname{Dark}_{A}(C))$. In the following, we
discuss how to construct a new configuration $C^{\prime}$ in an arbitrary
neighbourhood of $C$ such that $P(C^{\prime})>P(C)$. Thus $C$ can not be
locally optimal. Since $f$ is continuous, the niveau line

$S=\\{p\in\mathds{R}^{n}\ :\ U(p,C)=P(C)\\}$

containing the darkest points is closed and thus
$\operatorname{Dark}_{A}(C)=A\cap S$ is compact. Therefore,
$\operatorname{conv}(\operatorname{Dark}_{A}(C))$ is a compact convex set and
we can find a hyperplane $H=\\{x\ :\ a^{\top}x=b\\}$ strictly separating this
set from $c$ such that $a^{\top}c<b$. For $\varepsilon>0$ small enough
$c^{\prime}=c+\varepsilon a$ still satisfies $a^{\top}c^{\prime}<b$. We obtain
a new configuration $C^{\prime}=C\cup\\{c^{\prime}\\}\setminus\\{c\\}$. Note,
that for every neighbourhood of $C$, there is a sufficiently small
$\varepsilon$ such that $C^{\prime}$ is contained in said neighbourhood.
Obviously $|c^{\prime}-p|<|c-p|$ for all points $p$ in the non-negative
halfspace of $H$. In particular $c^{\prime}$ is closer to all of the darkest
points than $c$ and since $f$ is monotonously decreasing

$U(p,C^{\prime})>U(p,C)\geq P(C)$

for all points $p$ in the non-negative halfspace of $H$.

It remains to assert this also on the negative halfspace. Since all the
darkest points are on the positive side of $H$, a point $p\in A\cap(H\cup
H_{-})$ satisfies

$U(p,C)>P(C).$

Since $A\cap(H\cup H_{-})$ is compact this yields

$U(p,C)\geq\delta>P(C)$

for some constant $\delta$. By continuity of $f$, for $\varepsilon$ small
enough, we can guarantee that

$U(p,C^{\prime})>P(C)$

for all $p\in A\cap(H\cup H_{-})$. Altogether,

$P(C^{\prime})=\inf_{p\in A}U(p,C^{\prime})>P(C).$

∎

The formulated condition is very “unstable” in the following sense:

######  Proposition 2.2.

Let $C$ be a configuration such that
$C\subset\operatorname{conv}\operatorname{Dark}_{A}(C)$. Let $c\in C$ and
$c^{\prime}\neq c$ and $C^{\prime}=C\cup\\{c^{\prime}\\}\setminus\\{c\\}$.
Then

  1. 1.

$P(C^{\prime})<P(C)$ and

  2. 2.

$C^{\prime}\nsubseteq\operatorname{conv}\operatorname{Dark}_{A}(C^{\prime})$.

###### Proof.

  1. 1.

Consider the hyperplane $H$ with outer normal $c-c^{\prime}$ through $c$,
oriented such that $c^{\prime}$ is on the negative side. Since
$c\in\operatorname{conv}\operatorname{Dark}_{A}(C)$ there has to be a darkest
point $d\in\operatorname{Dark}_{A}(C)$ in the non-negative halfspace of $H$
(it might be in $H$). Then $\|c-d\|<\|c^{\prime}-d\|$ and by monotonicity
$f(\|c-d\|)>f(\|c^{\prime}-d\|)$. The potentials $U(d,C^{\prime})$ and
$U(d,C)$ differ by $f(\|c^{\prime}-d\|)-f(\|c-d\|)$, therefore the above
implies

$P(C^{\prime})\leq U(d,C^{\prime})<U(d,C)=P(C).$

  2. 2.

Suppose
$C^{\prime}\subset\operatorname{conv}\operatorname{Dark}_{A}(C^{\prime})$.
Then we can apply 1. to $C^{\prime}$ with the roles of $c,c^{\prime}$
reversed. But this would give $P(C^{\prime})<P(C)<P(C^{\prime}),$ which is a
contradiction.

∎

Optimization methods which only consider single components (like pattern
search) or move single configuration points therefore possibly converge to a
configuration contained in the convex hull of the darkest points which is not
locally optimal. Therefore it seems reasonable to only use optimization
methods which are able to move several points at once. Another conclusion is
the following, which seems to suggest that the number of optimization
variables can be reduced to only $m-1$ vectors.

######  Corollary 2.3.

For given points $C^{\prime}$ with $|C^{\prime}|=N-1$ there is _at most_ one
point $c$ such that $\\{c\\}\cup
C^{\prime}\subset\operatorname{conv}\operatorname{Dark}_{A}(\\{c\\}\cup
C^{\prime})$.

We can use Theorem 2.1 to study the structure of the darkest points even more.
First, we discuss a way to find certificates for
$p\notin\operatorname{Dark}_{A}(C)$.

######  Lemma 2.4.

Let $C$ be a configuration and $p\in\mathds{R}^{n}$ be an arbitrary point. Let

$N(p,C)=\\{p+v\ :\ v\neq 0\text{ and }v^{\top}w\geq 0\text{ for all
}w\in\operatorname{cone}\\{p-c\ :\ c\in C\\}\\}.$

  1. 1.

For all $q\in N(p,C)$ we have $U(q,C)<U(p,C)$,

  2. 2.

if $N(p,C)\cap A\neq\emptyset$ then $p\notin\operatorname{Dark}_{A}(C)$.

###### Proof.

Write $q=p+v\in N(p,C)$ with $v\neq 0$. Then for all $c\in C$ we have

$|c-(p+v)|^{2}=|c-p|^{2}+2(p-c)^{\top}v+|v|^{2}>|c-p|^{2}.$

Since $f$ is strictly monotone decreasing, we have $U(q,C)<U(p,C)$. From this,
the second claim follows immediately. ∎

The above definition of $N(p,C)$ of a point $p$ contains only points at which
the potential is strictly smaller than at $p$ itself, as we just showed. We
think this object will be useful beyond the scope of the previous lemma and
subsequent theorem, but in the present work we only need it here.

If we recall the visualization of the polarization problem as placing light
sources $C$ to illuminate $A$ the above definition of $N(p,C)$ of a point $p$
contains only points that are illuminated less than $p$ itself. It is (by cone
duality) somewhat related to the idea of a physical shadow (which would be
resembled most closely by $-\operatorname{cone}\\{p-c:c\in C\\}$). With this
we prove the following result which further restricts the location of the
darkest points:

######  Theorem 2.5.

Let $C$ be a feasible configuration for (2). Then the points of
$\operatorname{Dark}_{A}(C)$ are either in the interior of
$\operatorname{conv}(C)$ or in $\delta A$, i.e.
$\operatorname{Dark}_{A}(C)\subset\operatorname{int}\operatorname{conv}(C)\cup\delta
A$. Moreover, if $C$ is locally optimal for (2), then
$\operatorname{Dark}_{A}(C)\cap\delta A\neq\emptyset$.

###### Proof.

Let $p\in\operatorname{Dark}_{A}(C)$ and assume
$p\notin\operatorname{int}\operatorname{conv}(C)$. Furthermore, let $N(p,C)$
be defined as in Lemma 2.4. We can find a hyperplane $H=\\{x\in\mathds{R}^{n}\
:\ a^{\top}x=\beta\\}$ through $p$ separating $C$ from $p$, in particular
$a^{\top}c\leq\beta$ for all $c\in C$. Then for all $c\in C$

$a^{\top}(p-c)=a^{\top}p-a^{\top}c=\beta-a^{\top}c\geq 0,$

which shows that $p+\lambda a\in N(p,C)$ for arbitrary $\lambda>0$. If
$p\in\operatorname{int}A$, so is $p+\lambda a$ for $\lambda$ sufficiently
small. Then $A\cap N(p,C)\neq\emptyset$ in contradiction to Lemma 2.4. Thus
$p\in\partial A$ as claimed.

In addition, if $C$ is also locally optimal for (2) by Theorem 2.1 we
immediately obtain that
$C\subset\operatorname{conv}\operatorname{Dark}_{A}(C)$. Now, assume
$\operatorname{Dark}_{A}(C)\cap\delta A=\emptyset$, then as seen above
$\operatorname{Dark}_{A}(C)\subseteq\operatorname{int}\operatorname{conv}C$
and we obtain

$C\subseteq\operatorname{conv}\operatorname{Dark}_{A}(C)\subseteq\operatorname{int}\operatorname{conv}C,$

which is a contradiction since $C$ is finite. ∎

Figure 1: Illustration of Theorems 2.1 and 2.5. $A$ is depicted in red,
$\operatorname{Dark}_{A}$ in black and the configuration $C$ in orange. The
dashed lines depict the convex hulls $\operatorname{conv}C$ and
$\operatorname{conv}\operatorname{Dark}_{A}(C)$, whereas the black line
depicts all points $p\in\mathds{R}^{2}$, such that $U(p,C)=P(C)$.

To summarize, locally optimal configurations $C$ of (2) and its corresponding
darkest points $\operatorname{Dark}_{A}(C)$ share a similar containment
property as is illustrated in Figure 1.

##  3 An MIP approach to polarization

The current section is dedicated to the development of two hierarchies of
mixed-integer linear programs (MIP) that approximate the maximal polarization
of a compact set $A$ with respect to a monotonically decreasing and continuous
function $f:\ \mathds{R}_{+}\rightarrow\mathds{R}_{+}$. The MIP, that computes
the lower bounds is constructive, i.e. solutions to this MIP are
configurations whose polarization is lower bounded by the value of the MIP.
The actual polarization of these configurations may very well exceed this
lower bound by a significant margin, cf. Figure 3 for some numerical evidence.

First we give an equivalent description of problem (2). For this we observe
that by Theorem 2.1 any locally optimal point configuration is necessarily
supported on $\operatorname{conv}(A)$. Furthermore we can get rid of the
infimum by adding new constraints. The resulting optimization problem is then

$\displaystyle\mathcal{P}_{f}(A)=\max_{x,C}\ $ $\displaystyle x$ (3)
$\displaystyle C\in\left[\begin{array}[]{cc}\operatorname{conv}(A)\\\
N\end{array}\right]$ (6) $\displaystyle x\leq U_{f,A}(p,C)$
$\displaystyle\text{ for all }p\in A,$

where $\left[\begin{array}[]{cc}X\\\ N\end{array}\right]$ describes the set of
all multisets of size $N$ with elements in $X$. It is now clear, that the
$\sup$ is actually a $\max$, since the feasible region can easily be made
compact by bounding $x$ from below (e.g. $x\geq 0$) without changing the value
of the program.

###  3.1 MIP Hierarchies

We observe that Problem (3) is an optimization problem with finitely many
variables (namely $x,C$), but infinitely many constraints - it is a
semiinfinite program (SIP) - and therefore not solvable using standard
solvers. In the remainder of this section we introduce two hierarchies of
(tractable) MIPs, that approximate $\mathcal{P}(A)$ from above and below (see
Theorem 3.5). For this we make use of the following concept of functions which
“control” the difference of two values of $f$.

######  Definition 3.1.

We call a family of functions
$g_{c,p}:\mathds{R}_{+}\rightarrow\mathds{R}_{+}$ for
$c\in\operatorname{conv}(A)$, $p\in A$ a _family of control functions_ (with
respect to $f$, $A$) if for all $c\in\operatorname{conv}(A)$, $p\in A$:

  1. 1.

$g_{c,p}(0)=0$,

  2. 2.

$g_{c,p}$ is continuous and non-decreasing,

  3. 3.

$|f(\|c-p\|)-f(\|c^{\prime}-p\|)|\leq g_{c,p}(\|c-c^{\prime}\|)$ for all
$c^{\prime}\in\operatorname{conv}(A)$,

  4. 4.

$|f(\|c-p\|)-f(\|c-p^{\prime}\|)|\leq g_{c,p}(\|p-p^{\prime}\|)$ for all $p\in
A$,

where $\|\cdot\|$ denotes the standard Euclidean norm.

Note that $f$ is related to a function $K$ taking two points $c,p$ as
arguments: $K(c,p)=f(\|c-p\|)$. A family of control functions allows us to
control the way $K$ changes as we vary either $c$ or $p$.

This control will be an important ingredient of the proof of Theorem 3.5. For
continuous functions this is related to bounding the slope of $K$ as can be
illustrated by the following example: Suppose the function
$K(c,\cdot)=f(\|c-\cdot\|)$ is Lipschitz-continous with Lipschitz constant $L$
for all $p\in A$. Then, $g_{c,p}(\varepsilon)=L\cdot\varepsilon$ is a valid
control function for $f$.

However, applying global Lipschitz-continuity is not a very precise
approximation as it ignores local information around specific points $c,p$.
Therefore we provide a more suitable family of control functions.

######  Proposition 3.2.

For $f$ monotonously decreasing and continuous the following is a family of
control functions:

$g_{c,p}(\varepsilon)=\max(\hat{g}_{c,p}(\varepsilon),\hat{g}_{c,p}(-\varepsilon))$

where

$\hat{g}_{c,p}(x)=\begin{cases}f(0)-f(\|c-p\|)\text{ if }x<-\|c-p\|\\\
\left|f(\|c-p\|+x)-f(\|c-p\|)\right|\text{ otherwise}\end{cases}$

###### Proof.

We fix $c,p$ and write $g=g_{c,p}$ and $\hat{g}=\hat{g}_{c,p}.$ Clearly
$g(0)=\hat{g}(0)=0$. Since $f$ is continuous, so is $g$.

For $x\in(-\infty,-\|c-p\|)$ the function $\hat{g}(x)$ is constant. For
$x\in(-\|c-p\|,0)$ we have

$\hat{g}(x)=f(\|c-p\|+x)-f(\|c-p\|)$

which is decreasing since $f$ is decreasing. For $x\in(0,\infty)$ we have

$\hat{g}(x)=f(\|c-p\|)-f(\|c-p\|+x)$

which is increasing since $f$ is decreasing. Overall
$g(\varepsilon)=\max(\hat{g}(\varepsilon),\hat{g}(-\varepsilon))$ is an
increasing function on $\mathds{R}_{+}$.

By symmetry, it is sufficient to prove that $g$ provides an upper bound for
$\Delta=|f(\|c-p\|)-f(\|c-p^{\prime}\|)|$ for all
$p^{\prime}\in\operatorname{conv}(A)$. To this end, we use the triangle
inequalities

$\|c-p\|-\|p^{\prime}-p\|\leq\|c-p^{\prime}\|\leq\|c-p\|+\|p^{\prime}-p\|$

and that $f$ is a decreasing function. Then, on the one hand if
$\|c-p\|\leq\|c-p^{\prime}\|$, we have

$\displaystyle\Delta$ $\displaystyle=f(\|c-p\|)-f(\|c-p^{\prime}\|)$
$\displaystyle\leq
f(\|c-p\|)-f(\|c-p\|+\|p^{\prime}-p\|)=\hat{g}(\|p^{\prime}-p\|)\leq
g(\|p^{\prime}-p\|).$

On the other hand, if $\|c-p\|\geq\|c-p^{\prime}\|$, we obtain

$\displaystyle\Delta$ $\displaystyle=-f(\|c-p\|)+f(\|c-p^{\prime}\|)$
$\displaystyle\leq-f(\|c-p\|)+f(\|c-p\|-\|p-p^{\prime}\|)=\hat{g}(-\|p-p^{\prime}\|)\leq
g(\|p-p^{\prime}\|).$

∎

For explicit computations we need to discretize two aspects of the problem.
Firstly, we discretize the set of possible point configurations. For this we
choose a finite sample $\Lambda\subset\operatorname{conv}(A)$ and only
optimize over

$C\in\left[\begin{array}[]{cc}\Lambda\\\ N\end{array}\right].$ (7)

Secondly, we replace the infinite number of constraints, parameterized by $A$,
by a finite subcollection. For this we again choose a finite sample
$\Gamma\subset A$, and only consider the inequalities

$x\leq U(p,C)\text{ for all }p\in\Gamma.$ (8)

However, this naively sampled problem is not necessarily connected to the
original problem, since we enforce only a subset of the infinitely many
constraints and allow only a finite number of configurations. Either one of
these changes would provide valid bounds but they unfortunately work in
different directions. We will now show how to overcome this problem by
utilizing the above family of control functions to obtain lower and upper
bounds on the original problem.

Let us first consider lower bounds on (3). It is clear that we can restrict
the choice of configurations to be supported on a finite sample $\Lambda$ of
$\operatorname{conv}(A)$ as in (7) and obtain a program that computes a lower
bound.

Discretizing the constraints is the harder part, since removing constraints
lets the maximum grow. The following lemma shows how a slight variation of
discretized constraints for some fintie sample $\Gamma$ of $A$ imply the
validity of all of the infinitely many original constraints.

######  Lemma 3.3.

Let $g_{c,p}$ be a family of control functions. Let $\varepsilon>0$, $\Lambda$
be an arbitrary finite sample of $\operatorname{conv}(A)$ and $\Gamma$ be an
$\varepsilon$-net of $A$. Furthermore, suppose
$x\in\mathds{R},C\subset\left[\begin{array}[]{cc}\Lambda\\\
N\end{array}\right]$ satisfy

$x\leq\sum_{c\in\Lambda}\mathbbm{1}_{C}(c)\cdot\left(f(\|c-p\|)-g_{c,p}(\varepsilon)\right)\text{
for all }p\in\Gamma.$

Then,

$x\leq\sum_{c\in\Lambda}\mathbbm{1}_{C}(c)\cdot f(\|c-p\|)\text{ for all }p\in
A.$

###### Proof.

Let $p\in A$ be arbitrary and
$n(p)=\operatorname{argmin}_{\bar{p}\in\Gamma}\\{\|p-\bar{p}\|\\}$ denote the
closest sample point to $p\in A$. Note that $\|p-n(p)\|<\varepsilon$ since
$\Gamma$ is an $\varepsilon$-net. Then,

$\displaystyle\sum_{c\in\Lambda}\mathbbm{1}_{C}(c)f(\|c-p\|)$
$\displaystyle=\sum_{c\in\Lambda}\mathbbm{1}_{C}(c)\cdot\left(f(\|c-p\|)-f(\|c-n(p)\|)\right)$
$\displaystyle\qquad+\sum_{c\in\Lambda}\mathbbm{1}_{C}(c)\cdot\left(f(\|c-n(p)\|)-g_{c,n(p)}(\varepsilon)\right)$
$\displaystyle\qquad+\sum_{c\in\Lambda}\mathbbm{1}_{C}(c)\cdot
g_{c,n(p)}(\varepsilon)$
$\displaystyle\geq-\sum_{v\in\Lambda}\mathbbm{1}_{C}(c)\cdot
g_{c,n(p)}(\|p-n(p)\|)$ $\displaystyle\qquad+x$
$\displaystyle\qquad+\sum_{c\in\Lambda}\mathbbm{1}_{C}(c)\cdot
g_{c,n(p)}(\varepsilon),$

which is larger than $x$ since $g_{c,n(p)}$ is non-decreasing and
$\|p-n(p)\|<\varepsilon$. ∎

Conversely, if we consider upper bounds on (3), we now cannot simply choose a
finite sample $\Lambda$ of $\operatorname{conv}(A)$ to approximate the above
SIP. Indeed this would restrict the set of feasible solutions of (3) and
thereby lower the maximum instead. Again, the following lemma provides a way
around this problem using a variation of the constraints.

######  Lemma 3.4.

Let $g_{c,p}$ be a family of control functions. Let $\varepsilon>0$ and
$\Lambda$ be an $\varepsilon$-net of $\operatorname{conv}(A)$. Furthermore,
suppose $C\in\left[\begin{array}[]{cc}\operatorname{conv}(A)\\\
N\end{array}\right]$ and $x$ satisfy

$x\leq U(p,C)=\sum_{c\in C}f(\|c-p\|)\text{ for all }p\in\Gamma.$

Then, there exists a configuration
$C^{\prime}\in\left[\begin{array}[]{cc}\Lambda\\\ N\end{array}\right]$ such
that

$x\leq\sum_{c\in C^{\prime}}f(\|c-p\|)+g_{c,p}(\varepsilon)\text{ for all
}p\in\Gamma.$

###### Proof.

Let $C^{\prime}=\\{\\{n(c)\ :\ c\in C\\}\\}$ where
$n(c)=\operatorname{argmin}_{c^{\prime}\in\Lambda}\|c-c^{\prime}\|$. Then

$\displaystyle\sum_{c\in C^{\prime}}f(\|c-p\|)+g_{c,p}(\varepsilon)$
$\displaystyle=\sum_{c\in C}f(\|n(c)-p\|)-f(\|c-p\|)$
$\displaystyle\qquad+\sum_{c\in C}f(\|c-p\|)+\sum_{c\in
C}g_{n(c),p}(\varepsilon)$ $\displaystyle\geq-\sum_{c\in
C}g_{n(c),p}(\|c-n(c)\|)+x+\sum_{c\in C}g_{n(c),p}(\varepsilon)\geq x,$

where the last inequality holds since $g_{n(c),p}$ is non-decreasing and
$\|c-n(c)\|<\varepsilon$ as $\Lambda$ is an $\varepsilon$-net of
$\operatorname{conv}(A)$. ∎

Now we can prove the main result of this section.

######  Theorem 3.5.

Let $\varepsilon_{\Lambda},\varepsilon_{\Gamma}>0$ and $\Lambda$ be an
$\varepsilon_{\Lambda}$-net of $\operatorname{conv}(A)$ and $\Gamma$ be an
$\varepsilon_{\Gamma}$-net of $A$. Furthermore, let $g_{c,p}$ be a family of
control functions. Then we have the following:

$\displaystyle\max\ $ $\displaystyle x$ (9a) $\displaystyle
y\in\\{0,\ldots,N\\}^{\Lambda}$ $\displaystyle\mathbbm{1}^{\top}y=N$
$\displaystyle
x\leq\sum_{c\in\Lambda}y_{c}\cdot(f(\|c-p\|)-g_{c,p}(\varepsilon_{\Gamma}))$
$\displaystyle\text{ for all }p\in\Gamma$ $\displaystyle\leq\max\ $
$\displaystyle x$ (9b) $\displaystyle y\in\\{0,\ldots,N\\}^{\Lambda}$
$\displaystyle\mathbbm{1}^{\top}y=N$ $\displaystyle
x\leq\sum_{v\in\Lambda}y_{c}\cdot f(\|c-p\|)$ $\displaystyle\text{ for all
}p\in A$ $\displaystyle\leq\mathcal{P}(A)$ (9c) $\displaystyle\leq\max\ $
$\displaystyle x$ (9d) $\displaystyle
C\in\left[\begin{array}[]{cc}\operatorname{conv}(A)\\\ N\end{array}\right]$
(9g) $\displaystyle x\leq\sum_{c\in C}f(\|c-p\|)$ $\displaystyle\text{ for all
}p\in\Gamma$ $\displaystyle\leq\max\ $ $\displaystyle x$ (9h) $\displaystyle
y\in\\{0,\ldots,N\\}^{\Lambda}$ $\displaystyle\mathbbm{1}^{\top}y=N$
$\displaystyle
x\leq\sum_{c\in\Lambda}y_{c}\cdot(f(\|c-p\|)+g_{c,p}(\varepsilon_{\Lambda}))$
$\displaystyle\text{ for all }p\in\Gamma$

###### Proof.

We show, that feasible solutions of the left hand sides are also feasible for
the right hand sides with the same objective value justifying the asserted
inequalities. First, observe that Lemma 3.3 implies that a feasible solution
$x,y$ of (9a) is also feasible for (9b) and the objective values coincide.
Next, we consider a feasible solution $x,y$ of (9b) and observe that $y$
encodes a multiset $C\in\left[\begin{array}[]{cc}\Lambda\\\
N\end{array}\right]\subseteq\left[\begin{array}[]{cc}\operatorname{conv}(A)\\\
N\end{array}\right]$. Moreover, $x,C$ satisfy the constraints in (2) and with
the same objective value $x$. The next inequality follows rather immediately
since (9d) is a relaxation of (2) due to dropping constraints for $p\in
A\setminus\Gamma$. Lastly, if $x,C$ is a feasible solution of (9d), we apply
Lemma 3.4 to obtain a set $C^{\prime}\in\left[\begin{array}[]{cc}\Lambda\\\
N\end{array}\right]$ satisfying the constraints of (9h). Then, by encoding
$C^{\prime}$ through $y\in\\{0,\ldots,N\\}^{\Lambda}$ with
$\mathbbm{1}^{\top}y=N$ we obtain a feasible solution to (9h) with the same
objectve value $x$. ∎

Let us briefly comment on the computational complexity of the mixed-integer
programs (9a) and (9h). It is worth noting, that mixed-integer linear
programming usually refers to optimization problems that include binary
variables, which run significantly faster. We would like to note that the
integral variables $y\in\\{0,\ldots,N\\}^{\Lambda}$ in both (9a) and (9h) can
be replaced by $|\Lambda|\cdot\log(N)$ binary variables.

Moreover, in the lower bound of Theorem 3.5 the vector $y$ can be chosen as
$y\in\\{0,1\\}^{\Lambda}$, which still provides a (potentially worse) lower
bound and reduces the number of binary variables significantly. Unfortunately,
a similar simplification is not immediately possible for the upper bound.
However, we introduce another concept which aims to reduce the computational
complexity in a similar fashion in the upper bound case.

######  Definition 3.6.

A finite subset $\Lambda\subset\mathds{R}^{n}$ is called an
$(\varepsilon,k)$-net of $A$ if

  1. 1.

$\Lambda\subset A$,

  2. 2.

For every $p\in A$ there are at least $k$ distinct points
$p_{1},\dots,p_{k}\in\Lambda$ such that $|p_{i}-p|<\varepsilon$.

Using an $(\varepsilon_{\Lambda},N)$-net we obtain a hierarchy similar to
Theorem 3.5 restricting the possible entries of $y$ to $\\{0,1\\}$.

######  Proposition 3.7.

Let $\varepsilon_{\Lambda},\varepsilon_{\Gamma}>0$ and $\Lambda$ be an
$(\varepsilon_{\Lambda},N)$-net of $\operatorname{conv}(A)$ and $\Gamma$ be an
$\varepsilon_{\Gamma}$-net of $A$. Furthermore, let $g_{c,p}$ be a family of
control functions. Then,

$\displaystyle\eqref{prob:upper_bound_inter}\leq\max\ $ $\displaystyle x$
$\displaystyle y\in\\{0,1\\}^{\Lambda}$ $\displaystyle\mathbbm{1}^{\top}y=N$
$\displaystyle
x\leq\sum_{c\in\Lambda}y_{c}\cdot(f(\|c-p\|)+g_{c,p}(\varepsilon_{\Lambda}))$
$\displaystyle\text{ for all }p\in\Gamma$

###### Proof.

The proof works similar to the proof of Theorem 3.5 by replacing
$C^{\prime}=\\{\\{n(c)\ :c\in C\\}\\}$ in the proof of Lemma 3.4 by a set
$C^{\prime}$ of $N$ distinct points of $\Lambda$. This is possible since
$\Lambda$ is an $(\varepsilon_{\Lambda},N)$-net (see Definition 3.6). ∎

A trivial example of an $(\varepsilon,N)$-net can basically be obtained by a
multiset consisting of $N$ copies of an $\varepsilon$-net. However, in
practise there are usually solutions that need fewer points, albeit more than
a classical $\varepsilon$-net.

###  3.2 Convergence Results

After establishing upper and lower bounds to $\mathcal{P}(A)$ through the
hierarchies presented in Theorem 3.5, we study the quality of these bounds. To
this end, we show in this section, that solutions of the bounding problems
(9a) and (9h) converge, as $\varepsilon_{\Lambda},\varepsilon_{\Gamma}$ both
tend to $0$, to a solution of the original problem (3). Both proofs rely in
large parts on the proof of Lemma 6.1 in [19], which proves similar
convergence for more general semiinfinite programs, but include minor
necessary modifications. At first, we focus on the lower bounds, i.e., we
show, that (9a) converges to (9b) as $\varepsilon_{\Gamma}\rightarrow 0$:

######  Theorem 3.8.

Let $(\varepsilon_{k})$ be a non-negative sequence converging towards $0$.
Furthermore, for every $k\in\mathds{N}$ choose an $\varepsilon_{k}$ net
$\Gamma_{k}$ of $A$. Then, any accumulation point of a sequence
$(x_{k},y_{k})_{k\in\mathds{N}}$ of optimal solutions of (9a) w.r.t.
$\Gamma_{k}$ and $\varepsilon_{k}$ is an optimal solution of (9b).

###### Proof.

Let $(\bar{x},\bar{y})$ be an accumulation point of $(x_{k},y_{k})$. By
passing to a subsequence we can assume that
$(x_{k},y_{k})\rightarrow(\bar{x},\bar{y})$ if $k\rightarrow\infty$. We are
now going to prove, that $(\bar{x},\bar{y})$ is feasible and in fact optimal
for (9b):

Consider an arbitrary $p\in A$ and observe that since $\Gamma_{k}$ is an
$\varepsilon_{k}$-net of $A$, there exists a sequence $(p_{k})$ with
$p_{k}\in\Gamma_{k}$ such that $p_{k}\rightarrow p$ as $k\rightarrow\infty$.
We observe further, that for all $k$ we have

$x_{k}\leq\sum_{c\in\Lambda}(y_{k})_{c}\cdot(f(\|c-p_{k}\|)-g_{c,p_{k}}(\varepsilon_{k}))\leq\sum_{c\in\Lambda}(y_{k})_{c}\cdot
f(\|c-p_{k}\|)$

and by taking limits

$\bar{x}\leq\sum_{c\in\Lambda}\bar{y}_{c}\cdot f(\|c-p\|).$

Hence, $(\bar{x},\bar{y})$ is feasible for (9b).

Now, let $(x,y)$ be an arbitrary solution to (9b). Since $A$ is compact and
$\varepsilon_{k}>0$, we know that $g_{c}=\max_{p\in A}g_{c,p}$ is a
continuous, monotonously non-decreasing function with $g_{c}(0)=0$. We now
observe, that

$(x-\sum_{c\in\Lambda}y_{c}\cdot g_{c}(\varepsilon_{k}),y)$

is feasible for (9a) with respect to $\Gamma_{k}$. Since $(x_{k},y_{k})$ is an
optimal solution to (9a), we have $x_{k}\geq x-\sum_{c\in\Lambda}y_{c}\cdot
g_{c}(\varepsilon_{k})$. Consequently, as $g_{c}(0)=0$, in the limit we obtain
that $\bar{x}\geq x$. Since $x$ was chosen arbitrarily, we conclude, that
$(\bar{x},\bar{y})$ is indeed optimal for (9b). ∎

Note that the convergence of (9b) to (9c) as $\varepsilon_{\Lambda}\rightarrow
0$ follows directly since the utility function and $f$ are continuous. Thus,
Theorem 3.8 implies the convergence of (9a) to (9c), i.e. the value of (9a)
tends to $\mathcal{P}(A)$, as
$\varepsilon_{\Lambda},\varepsilon_{\Gamma}\rightarrow 0$.

Moreover, with the same arguments, we conclude the convergence of (9d) to (9c)
as $\varepsilon_{\Gamma}\rightarrow 0$ and thus only one proof of convergence
remains, namely that (9h) converges to (9d) as
$\varepsilon_{\Lambda}\rightarrow 0$.

One difficulty of the following theorem is the different kinds of feasible
solutions when altering the sample $\Lambda$. Feasible solutions of (9h) have
the form $y\in\\{1,\dots,N\\}^{\Lambda}$ with $\mathbbm{1}^{\top}y=N$ while
feasible solutions of (9d) are $N$-point multisets supported on
$\operatorname{conv}(A)$. Note that these objects do not permit an easy
discussion of convergence. However, both notions can be translated into an
element $\omega\in(\operatorname{conv}(A))^{N}$ which is independent of
$\Lambda$ and allows a discussion of convergence. Note that $\omega$ can
canonically be translated back into a multiset.

######  Theorem 3.9.

Let $(\varepsilon_{k})$ be a non-negative sequence converging towards $0$.
Furthermore, for every $k\in\mathds{N}$ choose an $\varepsilon_{k}$-net
$\Lambda_{k}$ of $\operatorname{conv}(A)$. Let $(x_{k},y_{k})$ be a sequence
of optimal solutions of (9h) w.r.t. $\Lambda_{k}$, $\varepsilon_{k}$.
Identifying each $y_{k}$ with $\omega_{k}\in(\operatorname{conv}(A))^{N}$, any
accumulation point $(\bar{x},\bar{\omega})$ of this sequence corresponds to an
optimal solution of (9d) by identification of $\bar{\omega}$ with a multiset.

###### Proof.

The proof is similiar to the proof of Theorem 3.8. Note that, since order of
elements is not important for the discussed problems, we can regard to
elements of $(\operatorname{conv}(A))^{N}$ either as tuples or as multisets
depending on the context. Suppose $(x_{k},\omega_{k})$ with has an
accumulation point $(\bar{x},\bar{\omega})$. By passing to a subsequence we
can assume that $(x_{k},\omega_{k})\rightarrow(\bar{x},\bar{\omega})$.
Consider the continuous function
$g_{p}=\max_{c\in\operatorname{conv}(A)}g_{c,p}$ with $g_{p}(0)=0$. Then, we
have for all $k$ and $p\in\Gamma$:

$\displaystyle x_{k}$
$\displaystyle\leq\sum_{c\in\Lambda_{k}}(y_{k})_{c}\cdot(f(\|c-p\|)+g_{c,p}(\varepsilon_{k}))$
$\displaystyle\leq\sum_{i=1}^{N}f(\|(\omega_{k})_{i}-p\|)+g_{p}(\varepsilon_{k})$

By taking limits we obtain

$\bar{x}\leq\sum_{i=1}^{N}f(\|\bar{\omega}_{i}-p\|)$

for all $p\in\Gamma$. Thus $\bar{x},\bar{\omega}$ is feasible for (9d).

Now suppose $x,\omega$ is an arbitrary solution of (9d). Then by Lemma 3.4
there exists $\omega_{k}^{\prime}$ such that $x,\omega_{k}^{\prime}$ is a
feasible solution for (9d). Since $(x_{k},\omega_{k})$ is an optimal solution,
we have $x_{k}\geq x$ and by taking limits $\bar{x}\geq x$. Therefore
$\bar{x}$ is also optimal for (9h). ∎

Note, that the proofs of Theorems 3.8, 3.9 still work if we restrict $y$ to be
binary as was discussed at the end of Section 3.1.

Combining Theorems 3.8 and 3.9, we conclude that by choosing a suitable
sequence $(\varepsilon_{\Gamma})_{k},(\varepsilon_{\Lambda})_{k}$, we can in
theory bound the value of $\mathcal{P}(A)$ as tightly as we need. However,
solving the respective mixed-integer linear problems in practice will pose a
computational challenge.

##  4 Computational results

This section presents numerical experiments illustrating the capabilities and
limits of the MIP approach presented in this paper. All computations have been
performed using Gurobi on a HP DL380 Gen9 server with two Intel(R) Xeon(R) CPU
<EMAIL_ADDRESS>(each with 14 cores) and 256 GB RAM. We first focus on a
simple illustrative example, where $A$ is an equilateral triangle and the size
of the configuration is $N=3$. In addition, we chose $f(x)=e^{-5\|x\|^{2}}$
for our potential function and
$\varepsilon_{\Gamma}=0.014,\varepsilon_{\Lambda}=\varepsilon_{\Gamma}/3$ as
the respective discretization widths of $\Gamma\subseteq A$ and
$\Lambda\subseteq\operatorname{conv}(A)$. Lastly, we restrict both, (9a) and
(9h) to binary variables $y\in\\{0,1\\}^{\Lambda}$ instead of integral
$y\in\\{0,\ldots,N\\}^{\Lambda}$ as discussed below Theorem 3.5. Since we
expect the resulting configuration to consist of three separate points, this
should not significantly impact the quality of the bounds.

We illustrate the configuration given by (9a) in Figure 2. It was obtained
after approximately $10$ hours.

Figure 2: Optimal configuration for (9a) with $\varepsilon=0.014$ and a
heatmap of the respective $f$-potential (from dark blue over green to yellow).
The points of the configuration are represented by orange circles.

We continue by assessing the numerical evidence on the convergence for the
above example. To this end, we illustrate the quality of the binary versions
of both, (9a) and (9h) for decreasing values of $\varepsilon_{\Lambda}$ and
$\varepsilon_{\Gamma}$. Here, the binary variant of (9h) was derived from
Proposition 3.7. To be precise, for every
$\varepsilon\in\\{0.04,0.038,\dots,0.014\\}$ we computed the lower bound using
$\varepsilon_{\Lambda}=\varepsilon/3$, $\varepsilon_{\Gamma}=\varepsilon$ and
the upper bound using
$\varepsilon_{\Gamma}=\varepsilon_{\Lambda}=\varepsilon$. We chose these
scalings for a better comparability, since the $(\varepsilon_{\Lambda},3)$-net
in the upper-bound case contains more sample points and therefore yields more
variables than an $(\varepsilon_{\Lambda},1)$-net. Furthermore, we used scaled
versions of the $A_{2}$ lattice complemented with additional sample points on
the boundary to generate the samples $\Lambda$ and $\Gamma$. This construction
ensures that both, $\Lambda$ and $\Gamma$ are indeed $\varepsilon_{\Lambda}$
and $\varepsilon_{\Gamma}$-nets respectively. The obtained bounds are
visualized in Figure 3.

It is apparent, that lower values of $\varepsilon$ do not always yield better
bounds although there is a clearly visible trend to close the gap between the
bounds as can be expected from our convergence results established in Theorems
3.8 and 3.9. A drawback of this approach is the computational runtime of the
respective MIPs, which vastly increases with the sample size of $\Gamma$ and
$\Lambda$ from a few seconds if $\varepsilon=0.04$ to $10$ hours for
$\varepsilon=0.014$.

Figure 3: Upper and lower bounds computed with decreasing values of
$\varepsilon$ and the respective running optimum (dashed lines) as well as an
approximate polarization of the lower bound configuration.

As an additional academic example, we use the same approach for different
suitable choices of $\varepsilon=\varepsilon_{\Lambda}=\varepsilon_{\Gamma}$
and different convex, non-convex or even non-connected $A$ to showcase the
wide applicability of our approach. We illustrate the polarizations derived by
the binary approximation of our lower bound MIP (9a) in Figure 4.

Figure 4:  Optimal configurations of (9a) for different $A$ in orange with a
heatmap of the respective potential (from dark blue over green to yellow). The
border of the respective shape $A$ is highlighted in blue (from left to right:
ball, triangles, non-convex shape).

Moreover, we briefly summarize the computational results on these additional
shapes $A$ in Table 4 below. The respective sample widths were chosen such
that the corresponding MIPs could be solved in reasonable time.

$A$ | Ball | Two twisted triangles | Non-convex shape
---|---|---|---
$N$ | 7 | 6 | 7
lower bound | 0.391063 | 0.381283 | 0.918088
$\varepsilon=\varepsilon_{\Lambda}=\varepsilon_{\Gamma}$ | 0.0625 | 0.025 | 0.025
| computation time
---
in seconds
6145 | 1238 | 2020
upper bound | 0.942982 | 0.506328 | 1.12719
$\varepsilon=\varepsilon_{\Lambda}=\varepsilon_{\Gamma}$ | 0.0875 | 0.0375 | 0.03125
| computation time
---
in seconds
6741 | 858 | 879
gap | ca. $59\%$ | ca. $25\%$ | ca $19\%$

We note, that the shape of $A$ significantly impacts the runtime of our MIP
approach. It seems that the large symmetry group of the ball may contribute to
a larger runtime as good solutions may be found everywhere in the branch-and-
bound tree used by solvers such as Gurobi. If true, symmetry reduction
techniques may lead to substantial improvements.

##  5 Outlook

We have seen in Section 2 that the location of the darkest points and the
location of the points of a locally optimal configuration are intertwined. We
suspect that these results can be extended, in particular by utilizing
symmetries of $A$ or requiring $A$ to be convex or even a polytope.
Furthermore, it would be interesting to extend these results to other choices
of $D$.

However, it is clear that there will be limitations to these kinds of results.
Consider for example $A=D=S^{n-1}$ the unit sphere. In this case, no obvious
variant of Theorem 2.1 holds.

In this paper, we have not dealt with explicit computations of locally or
globally optimal point configurations, even on simple sets such as $n$-gons or
the unit ball. However, numerical experiments suggest that such configurations
show some structure and we hope that extensions of the results in Section 2
can be utilized to obtain proof of optimality for some configurations. Here,
we would like to highlight one result in this direction we are aware of,
namely that for certain Riesz potentials of modest decay and $A$ equals the
closed $d$-dimensional unit ball, the optimal point configuration consists of
$N$ copies of the origin (see [1, Theorem 14.2.6]). We were able to observe
similar effects in numerical experiments on regular polytopes.

The MIP hierarchies presented in Section 3 give provable upper and lower
bounds converging to the optimal solution. However, unsurprisingly computing
these bounds for sufficiently fine samples is very time consuming since MIP is
NP-complete. A natural question is, whether well known techniques from
mathematical programming - such as convex relaxations, inner approximations,
column generation or local refinement, that speed up the computations can be
utilized to achieve results for finer samples. However, most of these
techniques only provide approximations of the discussed MIP hierarchies, which
might limit the gain achieved through the finer samples.

Moreover, it might be helpful to carefully fit the choice of the samples to
the specific instance of the problem. For example, if one has a conjecture for
an optimal configuration and/or the correct location of the darkest points,
this information can be fitted into the samples while retaining the
$\varepsilon$-net property of the samples. Furthermore, these ideas might
provide a way to use our bounds for analytic proofs of optimality in highly
structured situations.

Data Availability Data sharing not applicable to this article as no datasets
were generated oranalysed during the current study.

Acknowledgments

The authors like to thank Frank Vallentin for useful suggestions. M.C.Z. is
partially supported “Spectral bounds in extremal discrete geometry” (project
number 414898050) funded by the DFG.

## References

  *   * Borodachov et al. [2019] Borodachov, S.V., Hardin, D.P., Saff, E.B.: Discrete Energy on Rectifiable Sets. Springer Monographs in Mathematics. Springer, ??? (2019). https://books.google.se/books?id=Eie7DwAAQBAJ
  * Stolarsky [1975] Stolarsky, K.: The sum of the distances to certain pointsets on the unit circle. Pacific Journal of Mathematics 59(1), 241–251 (1975)
  * Ambrus [2009] Ambrus, G.: Analytic and probabilistic problems in discrete geometry. PhD thesis, University College London (2009)
  * Ambrus et al. [2013] Ambrus, G., Ball, K.M., Erdélyi, T.: Chebyshev constants for the unit circle. Bull. Lond. Math. Soc. 45(2), 236–248 (2013) https://doi.org/10.1112/blms/bds082
  * Nikolov and Rafailov [2011] Nikolov, N., Rafailov, R.: On the sum of powered distances to certain sets of points on the circle. Pacific journal of mathematics 253(1), 157–168 (2011)
  * Hardin et al. [2013] Hardin, D.P., Kendall, A.P., Saff, E.B.: Polarization optimality of equally spaced points on the circle for discrete potentials. Discrete & Computational Geometry 50, 236–243 (2013)
  * Erdélyi and Saff [2013] Erdélyi, T., Saff, E.B.: Riesz polarization inequalities in higher dimensions. Journal of Approximation Theory 171, 128–147 (2013)
  * Borodachov [2022] Borodachov, S.: Polarization problem on a higher-dimensional sphere for a simplex. Discrete Comput Geom 67, 525–542 (2022) https://doi.org/%****␣sn-article.bbl␣Line␣150␣****10.1007/s00454-021-00308-1
  * Borodachov and Bosuwan [2014] Borodachov, S.V., Bosuwan, N.: Asymptotics of discrete riesz d-polarization on subsets of d-dimensional manifolds. Potential Analysis 41(1), 35–49 (2014)
  * Borodachov et al. [2018] Borodachov, S., Hardin, D., Reznikov, A., Saff, E.: Optimal discrete measures for riesz potentials. Transactions of the American Mathematical Society 370(10), 6973–6993 (2018)
  * Hardin et al. [2020] Hardin, D.P., Petrache, M., Saff, E.B.: Unconstrained polarization (chebyshev) problems: basic properties and riesz kernel asymptotics. Potential Analysis, 1–44 (2020)
  * Anderson et al. [2022] Anderson, A., Reznikov, A., Vlasiuk, O., White, E.: Polarization and covering on sets of low smoothness. Advances in Mathematics 410, 108720 (2022)
  * Conway et al. [2013] Conway, J.H., Sloane, N.J.A., Bannai, E., Borcherds, R.E., Leech, J., Norton, S.P., Odlyzko, A.M., Parker, R.A., Queen, L., Venkov, B.B.: Sphere Packings, Lattices and Groups. Grundlehren der mathematischen Wissenschaften. Springer, ??? (2013). https://books.google.se/books?id=hoTjBwAAQBAJ
  * Naszódi [2018] Naszódi, M.: In: Ambrus, G., Bárány, I., Böröczky, K.J., Fejes Tóth, G., Pach, J. (eds.) Flavors of Translative Coverings, pp. 335–358. Springer, Berlin, Heidelberg (2018). https://doi.org/%****␣sn-article.bbl␣Line␣250␣****10.1007/978-3-662-57413-3_14 . https://doi.org/10.1007/978-3-662-57413-3_14
  * Naszódi [2016] Naszódi, M.: On some covering problems in geometry. Proc. Amer. Math. Soc. 144(8), 3555–3562 (2016) https://doi.org/10.1090/proc/12992
  * Rolfes and Vallentin [2017] Rolfes, J.H., Vallentin, F.: Covering compact metric spaces greedily. Acta Mathematica Hungarica 155, 130–140 (2017)
  * Cohn and Kumar [2007] Cohn, H., Kumar, A.: Universally optimal distribution of points on spheres. Journal of the American Mathematical Society 20(1), 99–148 (2007)
  * Simon [2011] Simon, B.: Convexity: an Analytic Viewpoint vol. 187. Cambridge University Press, ??? (2011)
  * Shapiro [2009] Shapiro, A.: Semi-infinite programming, duality, discretization and optimality conditions. Optimization 58(2), 133–161 (2009)


††thanks: This work was supported by the National Key Research and Development
Program of China (2018YFE0103100), the National Natural Science Foundation of
China (12125508, 11935020), Program of Shanghai Academic/Technology Research
Leader (21XD1404100), and Shanghai Pilot Program for Basic Research – Chinese
Academy of Science, Shanghai Branch (JCYJ-SHFY-2021-010).

# Design and Commissioning of Beam Distribution Line at the SXFEL User
Facility

Si Chen<EMAIL_ADDRESS>Shanghai Advanced Research Institute, Chinese
Academy of Sciences, Shanghai 201210, China  Shanghai Synchrotron Radiation
Facility, Chinese Academy of Sciences, Shanghai 201204, China  Kaiqing Zhang
Shanghai Advanced Research Institute, Chinese Academy of Sciences, Shanghai
201210, China  Shanghai Synchrotron Radiation Facility, Chinese Academy of
Sciences, Shanghai 201204, China  Zheng Qi  Shanghai Advanced Research
Institute, Chinese Academy of Sciences, Shanghai 201210, China  Shanghai
Synchrotron Radiation Facility, Chinese Academy of Sciences, Shanghai 201204,
China  Tao Liu  Shanghai Advanced Research Institute, Chinese Academy of
Sciences, Shanghai 201210, China  Shanghai Synchrotron Radiation Facility,
Chinese Academy of Sciences, Shanghai 201204, China  Chao Feng  Shanghai
Advanced Research Institute, Chinese Academy of Sciences, Shanghai 201210,
China  Shanghai Synchrotron Radiation Facility, Chinese Academy of Sciences,
Shanghai 201204, China  Haixiao Deng  Shanghai Advanced Research Institute,
Chinese Academy of Sciences, Shanghai 201210, China  Shanghai Synchrotron
Radiation Facility, Chinese Academy of Sciences, Shanghai 201204, China  Bo
Liu  Shanghai Advanced Research Institute, Chinese Academy of Sciences,
Shanghai 201210, China  Shanghai Synchrotron Radiation Facility, Chinese
Academy of Sciences, Shanghai 201204, China  Zhentang Zhao
<EMAIL_ADDRESS>Shanghai Advanced Research Institute, Chinese
Academy of Sciences, Shanghai 201210, China  Shanghai Synchrotron Radiation
Facility, Chinese Academy of Sciences, Shanghai 201204, China

###### Abstract

As an important measure of improving the efficiency and usability of X-ray
free electron laser facilities, simultaneous operation of multiple undulator
lines realized by a beam distribution system has become a standard
configuration in the recent built XFEL facilities. In Shanghai, SXFEL-UF, the
first soft X-ray free electron laser user facility in China, has finished
construction and started commissioning recently. Electron beam from linac is
alternately distributed between the two parallel undulator beam lines by a
beam distribution system with a $6\text{\,}\mathrm{\SIUnitSymbolDegree}$
deflection line. The beam distribution system is designed to keep the beam
properties like low emittance, high peak charge and small bunch length from
being spoiled. Beam collective effects such as the dispersion, coherent
synchrotron radiation and micro-bunching instability should be well suppressed
to guarantee the beam quality. In this work, the detailed physics design of
the beam distribution system is described and the recent commissioning result
is reported.

X-ray free electron laser, Beam distribution system, Double bend achromat,
coherent synchrotron radiation

##  I Introduction

In the recent few decades, with the rapid development of high-gain Free
Electron Lasers (FELs), X-ray FEL facilities based on the high-performance RF
linear accelerator, have become a powerful platform for extensive research
areas including but not limited to the bioscience, material science,
chemistry, etc.Huang2021 . To satisfy the growing thirsty of various users in
various communities, several X-ray Free Electron Laser user facilities have
been built world wide, including several hard X-ray FEL facilities such as the
LCLSEmma2010 , SACLAIshikawa2012 , PAL-FELKang2017 , European XFELDecking2020
, and Swiss-FELPrat2020 , and several soft X-ray FEL facilities such as the
FLASHAckermann2007  and Fermi-FELAllaria2012 . In China, several X-ray FEL
facilities have been built or under construction, including the Shanghai Soft
X-ray FEL Facility (SXFEL)Zhao2017 ; Liu2022  and the High repetition rate
hard X-ray FEL facility, which is named as SHINEZhao2017shine .

With the rapidly growing number of users and their various experiment
requirement, it naturally arises a demond of building more XFEL facilities
with various parameters of light. However, unlike the storage-ring based
sychrotron light sources that can run tens of beamlines simultaneously, linac
based XFEL facilities are typically single-user facility in the early stage.
Meanwhile, the number of XFEL facilities is limited by the high cost of
building one. As a more efficient and economical approach, in the recent built
XFEL facilities, the beam distribution system is becoming a standard
configuration in order to accommodate multiple undulator lines with various
X-ray parameters for feeding more beamlinesHara2016 ; Hara2018 ; Beukers2019 ;
Balandin2011 ; Milas2012 ; DiMitri2013 . In such a beam distribution system,
electrons from linear accelerator are separated by switching magnets and
delivered alternately to each undulator line on a predetermined model, either
pulsed or bunch-by-bunch. At the mean time, the beam quality should be well
maintained during the beam distribution process, especially when the beam
current is high, which is usualy a necessary for high-gain XFEL.

As the first X-ray FEL facility in China, the SXFEL user facility is also
designed to be a multi-beamline facility. Two undulator lines are fed by a
single linac with 50 Hz bunch repetition rate and more undulator lines can be
accommodated in the future. In this work, the detailed design of a beam
distribution system to realize multi-beamline operation of the SXFEL-UF is
described. The commissioning of the beam distribution system has started in
late 2021 and the main results are also presented in this work.

##  II The SXFEL Facility

Figure 1: Schematic view of the SXFEL-UF.

The SXFEL facility is aimed to open up the enormous field related to XFEL in
China and to accumulate the indispensable technical experience for
constructing and utilizing the future hard x-ray FEL facility. It is developed
in phases. First a test facility (SXFEL-TF) with a
$840\text{\,}\mathrm{M}\mathrm{e}\mathrm{V}$ linac is built for generation of
$8.8\text{\,}\mathrm{nm}$ full coherent soft X-ray radiation and demonstration
of various seeded FEL mechanisms. In 2020, it has achieved its goal with the
demonstration of two-stage HGHG-HGHG cascade and two-stage EEHG-HGHG cascade
schemes.

Soon afterwards, the SXFEL-TF has been upgraded and integrated to the user
facility (SXFEL-UF)Liu2022 . It is designed to cover the whole water window
range. To accomplish this, the beam energy is upgraded to about
$1.5\text{\,}\mathrm{G}\mathrm{e}\mathrm{V}$ by adding more C-band RF
structures to the linac. Two individual undulator lines are parallelly
installed in the newly built undulator hall. Directly downstream of the linac
it is a brand new SASE-FEL line with radiation wavelength about
$2\text{\,}\mathrm{nm}$. The existing seeded-FEL line of SXFEL-TF is moved to
about $3\text{\,}\mathrm{m}$ aside of the SASE-FEL line with an upgrade of
more undulator sections for a radiation wavelength about
$3\text{\,}\mathrm{nm}$. The schematic layout of the SXFEL-UF is shown in Fig.
1. Some main beam parameters of SXFEL-UF are shown in Table 1.

Table 1: Main Parameters of SXFEL Linac Parameters |  Values |  Units
---|---|---
E |  1.5$\sim$1.6 |  $\mathrm{G}\mathrm{e}\mathrm{V}$
$\sigma_{E}$/$E$ (rms) |  $\leq$$0.1\text{\,}\mathrm{\char 37\relax}$ |
$\varepsilon_{n}$ (rms) |  $\leq$1.5 |  mm$\cdot$mrad
$l_{b}$ (FWHM) |  $\leq$0.7 |  $\mathrm{ps}$
$Q$ |  500 |  $\mathrm{pC}$
${I_{pk}}$ |  $\geq$700 |  $\mathrm{A}$
${f_{rep}}$ |  50 |  $\mathrm{Hz}$

For the parallel operation of the two FEL lines, a beam distribution system is
located between the linac and undulator section. The
$50\text{\,}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{t}\mathrm{z}$ electron bunch
train from linac is distributed in two directions, either to the SASE-FEL line
or to the seeding-FEL line. Because of the high requirement of the seeded FEL,
the beam distribution system should be able to guarantee a stable, precise
transportation of the electron beam with a well maintained beam quality
properties, such as the low emittance, high peak charge and small bunch
length. The detailed physics design of the switchyard is described below.

##  III Beam Distribution System Design of SXFEL-UF

###  III.1 General Layout

Figure 2: Schematic layouts of the beam distribution system of SXFEL-UF. The
total bending angle of the beam distribution dog-leg is about
$6\text{\,}\mathrm{\SIUnitSymbolDegree}$ with the limitation of total
available space for beam distribution system. A pulsed kicker magnet acts as
the first bending magnet of the dog-leg with the ability of bunch-by-bunch
distribution between the two FEL lines.

The beam distribution system uses a fast switching kicker magnet for bunch-by-
bunch distribution of the
$50\text{\,}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{t}\mathrm{z}$ electron bunch
train from the linac. It is also designed to be programmable for an arbitrary
separation model. When the kicker magnet is on, the electron bunch is
deflected horizontally to the seeding-FEL line through a deflection line,
otherwise it goes straight to the SASE-FEL line downstream of the linac
without any deflection.

Since the two FEL lines lie parallel in the undulator hall, the deflection
line uses a dog-leg structure to bring the kicked beam to the entrance of the
seeding-FEL line. Due to the limitation of the longitudinal distance, the
total deflection angle of the dog-leg is about
$6\text{\,}\mathrm{\SIUnitSymbolDegree}$. The most immediate effect of the
dog-leg is the dispersion function. When electron bunch with non-zero energy
spread passes through a bending magnet, dispersion effect introduces a
coupling between the transverse position and the energy of each electron in
the bunch so that the electrons spread transversely afterwards. The transverse
phase space can be severely destroyed by this effect. In order to cancel the
dispersion of beam distribution dog-leg, its entrance and exit bending magnets
are replaced by two identical double-bend-achromat (DBA) sections,
respectively. With this configuration, both the dispersion element ($R_{16}$)
and the dispersion prime element ($R_{26}$) are cancelled locally after each
DBA and globally after the whole dog-leg. The dispersion evolution along the
dog-leg is shown in Fig. 3 as the dashed lines. Between the two DBA sections,
several quadruples are inserted for beam matching. The position of the
elements is adjusted carefully to avoid conflict between the straight line and
the deflected line. The total projected length of the dog-leg is about
$39\text{\,}\mathrm{m}$. A schematic view of such a dog-leg is shown in Fig.
2.

###  III.2 Optics for CSR & MBI Suppression

For high-gain XFEL facilities, typically a high peak current, low emittance
electron beam is necessary for obtaining as higher gain in as shorter gain
length. However, when such a electron beam passes through the deflection line
of the beam distribution system, several kinds beam collective effect may
spoil both the transverse and longitudinal phase space of the electron beam,
thus reduces the performance of XFEL. Those collective effects should be
carefully suppressed in the deflection dog-leg of the beam distribution
system.

Figure 3: Twiss functions ($\beta_{x,y}$) and dispersion functions
($\eta_{x,y}$) evolution along the dog-leg. The $\beta_{x}$ at the entrance
kicker magnet is optimize to be around 1.6 m so that all the bending magnets
have the similar value with the symmetrical optics. The maximum values of
$\beta$ and $|\eta|$ are also optimized for smaller beam stay-clear area.

Coherent synchrotron radiation (CSR) introduced emittance growth is one of the
critical beam dynamic issues of the beam distribution dog-leg. When the
electron bunch passes through the bending magnet, synchrotron radiation is
emitted. If the bunch length is short enough that it is comparable with the
radiation spectral components, the synchrotron radiation becomes coherent. CSR
from the bunch tail part may catch up with the head part and interact with the
electrons inside as the bunch goes by. Both the transverse and longitudinal
phase space distribution can be changed by this process. In longitudinal
direction, the CSR field introduces a energy modulation along the longitudinal
coordinate of the bunch so that the energy spread increases. In transverse
direction, the CSR field mainly acts as a special term of dispersion due to
the longitudinal energy variation ans thus the emittance in the bending
direction grows. To avoid CSR induced emittance growth in the distribution
dog-leg of SXFEL-UF, it is necessary to cancel the transverse effect of CSR.
For this purpose, the so called ”optics balance method is used. The lattice of
the dog-leg is designed to be mirror symmetrical with a small beam waist at
each bending magnet to keep the CSR kick small but the same at each bending
magnet. Meanwhile, the betatron phase advance between the two DBA sections is
matched to be an odd multiple of $\pi$ so that both the CSR kick and the CSR
dispersion are cancelled at the end of the distribution dog-leg. The lattice
functions of such a dog-leg is shown in Fig. 3 as the solid lines.

Another critical beam dynamic issue of the beam distribution system is the
micro-bunching instability (MBI). It results from an interplay of various
collective effects such as longitudinal space charge (LSC) effect, coherent
synchrotron radiation (CSR) in dipole magnets, and the energy-dispersion
correlation in magnetic bunch length compressors. An energy modulation is
introduced in the beam longitudinal phase space and it is easily being
converted to a density modulation while passing through a dispersive magnetic
optics section with non-zero $R_{56}$. The amplified density modulation
further drives even larger energy and density modulations downstream, thus the
beam quality is significantly downgraded. Micro-bunching gain should be well
suppressed in the beam distribution system with multi-bend deflection line to
guarantee a high spectral brilliance, especially at output radiation
wavelengths in EUV and soft x-ray range. For this purpose, a small bending
magnet (micro-bend) is inserted in the middle of the DBA cell with a small
angle reverse to the DBA deflection angle. With this design, the $R_{56}$ of
each DBA becomes zero. Apply this design to both of the DBA cells of the
switchyard, it becomes globally isochronous, as is shown in Fig. 4. With the
isochronous configuration, the deflection line of the beam distribution system
is substantially transparent to any incoming modulation induced by micro-
bunching instability in the linac.

Figure 4: $R_{56}$ evolution along the dog-leg. Without micro-bend, the global
$R_{56}$ is over 700 $\mu m$ while with the micro-bend, the $R_{56}$ is
eliminated to less than 1 $\mu m$, which is negligible for micro-bunching
growth.

###  III.3 S2E Tracking Results

The start-to-end tracking from the linac end throughout the beam distribution
section is performed by the code Elegantelegant . The longitudinal phase space
at the linac exit is shown in Fig. 5. Two stage compression bring the 500 pC
electron bunch from 10 ps after the injector to less than 0.7 ps at the exit
of linac with a long flat top in the longitudinal phase space, which is
necessary for multi-stage energy modulation in some complex seeding-FEL
mechanisms. Laser heater is used for smoothing the longitudinal phase space
and a slice energy spread of about $1\times 10^{-4}$ is obtained at last. The
peak current on the flat top part is about 800 A and the normalized emittance
is about 1.0 $mm\cdot mrad$.

Figure 5: Longitudinal phase space at the linac exit. Beam central energy is
about 1.5 GeV, bunch length (FWHM) is about 700 fs, peak current is about 800
A on the flat top and the normalized emittance is about 1.0 mm$\cdot$ mrad.

Fig. 5 shows the normalized emittance growth
($\varepsilon_{x,f}/\varepsilon_{x,o}$) with respect to the betatron phase
advance ($\phi$) between the two DBA cells, where the $f$ and $o$ denoted in
the subscripts indicate the values at the end of linac and the beam
distribution dog-leg respectively. It is clear that the emittance growth is
almost completely eliminated with the $\pi$ phase advance, which indicates
that the current optics well satisfies the requirement of suppressing the CSR
introduced emittance growth.

Figure 6: Normalized emittance growth with respect to the betatron phase
advance between the two DBA cells. Minimum emittance growth appears at
$\phi\sim\pi$, which is much less than the expected $10\text{\,}\mathrm{\char
37\relax}$.

As is seen in Fig. 5, although the laser-heater is used, some residual micro-
bunching structures still appear in the longitudinal phase space. Besides,
there is a horn with peak current over 1.5 kA in the bunch head part. A
comparison of the t-x phase space and current profile before and after the
switchyard is shown in Fig. 7. For the case that $R_{56}\neq$0, it shows an
obvious growth of the microbunching structure in the longitudinal phase space,
especially on the head horn part. For the isochronous case with micro-bend,
only imperceptible microbunching gain can be observed. The longitudinal phase
space is well preserved after the distribution dog-leg.

Figure 7: Comparison of the t-x phase space and the current profile at linac
exit (upper), BD exit without micro-bend (middle) and BD exit with micro-bend
(lower).

###  III.4 Trajectory Jitter Analysis

For sufficient and stable interaction between beam and seed laser, the seeded
FEL line requires a transverse beam position jitter less than $0.1\sigma_{x}$.
The major sources of the horizontal trajectory jitter comes from the magnet
power fluctuation especially the kicker magnet power jitter. The vertical
jitter mainly comes from the quadrupole misalignment jitter due to ground
vibration.

A simulation of the trajectory jitter of the beam distribution system is done
with the kicker power jitter $\sim$ 100 ppm, bending magnet power jitter
$\sim$ 50 ppm and ground vibration amplitude $\sim$ $200\text{\,}\mathrm{nm}$
in both horizontal and vertical direction (all in RMS). Fig. 8 shows the
transverse trajectory jitter along the beam distribution dog-leg of 200 random
seeds of the jitter source. The horizontal position jitter (RMS) at the exit
of dog-leg is less than $0.1\sigma_{x}$ and the vertical position jitter (RMS)
is less than $1\text{\,}\mathrm{\char 37\relax}$ of $\sigma_{y}$. However, a
further simulation shows that the trajectory jitter is dominated by the kicker
jitter and grows almost linearly with it. In a word, 100 ppm is the criteria
amplitude of the acceptable kicker power jitter.

Figure 8: Transverse trajectory jitter of 200 cases of jitter source. The
horizontal trajectory jitter is less than $10\text{\,}\mathrm{\char 37\relax}$
with respect to the beam size $\sigma_{x}$ and $<1\text{\,}\mathrm{\char
37\relax}$ in vertical direction

##  IV Commissioning Results

The beam distribution system of SXFEL-UF has been installed in the front part
of the newly built undulator hall in late 2020. The commissioning of the
Switchyard and Seeding FEL line has started at the beginning of November 2021.
However, since the power supply of the kicker magnet hasn’t reach the expected
stability requirement, as is described in the upper section, it is not
acceptable for stable operation of seeding-FEL line. So the kicker magnet is
absent in this stage of commissioning until it is stable enough and it’s
function is instead of a DC bending magnet temporary.

The dispersion function measurement is based on measuring the orbit change at
each cavity BPM with different beam energy. As is seen in Eq. 1, if the
dispersion is closed, the orbit data will not change with the energy change,
otherwise there will be an orbit vs. relative energy change slope observed. By
fitting the slope the dispersion function and even higher order dispersion
terms can be obtained.

$x=x_{0}+R_{16}\frac{\Delta{E}}{E}+T_{166}(\frac{\Delta{E}}{E})^{2}+...$ (1)

Figure 9: The transverse dispersion is measured by monitoring the position
variation on CBPM while varying the bending angle as an equivalence of varying
beam energy.

Fig. 9 shows the measurement result of horizontal dispersion at the exit of
distribution dog-leg. The residual horizontal dispersion after the dog-leg is
cancelled to less than $1\text{\,}\mathrm{mm}$ which is much smaller than the
required $10\text{\,}\mathrm{mm}$ value. In order to make sure the
$\eta_{x}^{\prime}$ is also also well cancelled, dispersion is measured at
more CBPMs downstream. Fig. 10 shows the measured dispersion at all the CBPMs
from the beam distribution system to the entrance of the FEL line as a
comparison with the theoretical value. The result not only confirms the
reliability of measurement but also confirms a well cancellation of
$\eta_{x}^{\prime}$.

Figure 10: The dispersion is measured on all the CBPMs along and downstream
the beam distribution line and the data shows a good consistency with the
theoretical value.

The betatron matching of beam distribution system is done by keeping the
theoretical configuration of magnets while matching the entrance parameter
from the linac. The emittance and twiss parameters are measured by varying the
quadrupole and fitting the beam spot variation on a downstream OTR screen.
Then the beam is matched from linac exit to the entrance of beam distribution
system by an automatic algorism based on the code Ocelot. Fig. 11 shows the
comparison between the observed beam spot on each screen and the theoretical
beam spot after matching, which shows a well agreement. With such an optics,
the emittance is measured after the dog-leg. In order to reduce the
fluctuation of emittance measurement, an average of multi-times measurement
has been down and the result shows a emittance growth only about
$3\text{\,}\mathrm{\char 37\relax}$, which is well below the requested
$10\text{\,}\mathrm{\char 37\relax}$ emittance growth.

Figure 11: The beam spot at each beam profile monitor as a comparison with the
theoretical beam spot. With the well cancelled CSR induced emittance growth,
the beam envelop is well sustained along the beam distribution line.

A comparison of the transverse position jitter before and after the dog-leg is
shown in Fig. 12. As the well cancelled dispersion and suppressed CSR effect,
the growth of transverse position jitter after the dog-leg is less than
$10\text{\,}\mathrm{\char 37\relax}$ as is required. The longitudinal phase
space at the end of the seeding-FEL line is shown in Fig. 13. The longitudinal
phase space structure is well preserved with negligible micro-bunching growth
observed.

Figure 12: A comparison of the transverse beam central position jitter between
the entrance and exit of the BD section. Only imperceptible micro-bunching
structure is observed. Figure 13: Longitudinal phase space distribution of the
electron beam after BD section.

##  V Summary

A beam distribution system of SXFEL-UF is designed to perform a bunch-by-bunch
separation of the $50\text{\,}\mathrm{Hz}$ electron beam to the two undulator
lines respectively. With properly optimized optics, some beam collective
effects that may spoil the beam quality can be well suppressed. The beam
distribution has been installed in the undulator tunnel and started
commissioning in Nov. 2021. The commissioning results show that the beam
quality after passing through the beam distribution system is well preserved
with the present design. The electron beam passes through the beam
distribution has been delivered to the downstream FEL line and an exponential
FEL power growth in $3\text{\,}\mathrm{nm}$ has been obtained, which indicates
the beam quality after the beam distribution system well satisfies the
requirement of soft X-ray FEL. And beyond that, it provides an important
reference to the beam distribution system of the future hard X-ray free
electron laser facility.

##  VI Acknowledgment

The author would like to thank all the colleagues working on the SXFEL-UF.
Special thanks to Duan Gu and Zhen Wang for providing the electron
distributions used for this study. Many useful discussions with Bart Fattz and
other members of the physics and commissioning team are also gratefully
acknowledged.

## References

  * (1) Z.T. Zhao. Storage Ring Light Sources. Reviews of Accelerator Science and Technology. Vol. 03, No. 01, pp. 57-76 (2010). https://doi.org/10.1142/S1793626810000361
  * (2) Huang N., et al., Features and Futures of X-ray Free-Electron Lasers. The Innovation. 2(2), 100097. https://doi.org/10.1016/j.xinn.2021.100097
  * (3) Emma, P., Akre, R., Arthur, J. et al. First lasing and operation of an ångstrom-wavelength free-electron laser. Nature Photon 4, 641–647 (2010). https://doi.org/10.1038/nphoton.2010.176
  * (4) Ishikawa, T., Aoyagi, H., Asaka, T. et al. A compact X-ray free-electron laser emitting in the sub-ångström region. Nature Photon 6, 540–544 (2012). https://doi.org/10.1038/nphoton.2012.141
  * (5) Kang, HS., Min, CK., Heo, H. et al. Hard X-ray free-electron laser with femtosecond-scale timing jitter. Nature Photon 11, 708–713 (2017). https://doi.org/10.1038/s41566-017-0029-8
  * (6) Prat, E., Abela, R., Aiba, M. et al. A compact and cost-effective hard X-ray free-electron laser driven by a high-brightness and low-energy electron beam. Nature Photonics 14, 748–754 (2020). https://doi.org/10.1038/s41566-020-00712-8
  * (7) Decking, W., Abeghyan, S., Abramian, P. et al. A MHz-repetition-rate hard X-ray free-electron laser driven by a superconducting linear accelerator. Nature Photonics 14, 391–397 (2020). https://doi.org/10.1038/s41566-020-0607-z
  * (8) Ackermann, W., Asova, G., Ayvazyan, V. et al. Operation of a free-electron laser from the extreme ultraviolet to the water window. Nature Photon 1, 336–342 (2007). https://doi.org/10.1038/nphoton.2007.76
  * (9) Allaria, E., Appio, R., Badano, L. et al. Highly coherent and stable pulses from the FERMI seeded free-electron laser in the extreme ultraviolet. Nature Photon 6, 699–704 (2012). https://doi.org/10.1038/nphoton.2012.233
  * (10) Z.T. Zhao, et al., SXFEL: A Soft X-ray Free Electron Laser in China. Synchrotron Radiation News, Vol.30(2017) 6, pp.29-33. https://doi.org/10.1080/08940886.2017.1386997
  * (11) Liu, B.; Feng, C.; Gu, D.; Gao, F.; Deng, H.; Zhang, M.; Sun, S.; Chen, S.; Zhang, W.; Fang, W.; et al. The SXFEL Upgrade: From Test Facility to User Facility. Appl. Sci. 2022,12,176. https://doi.org/10.3390/app12010176
  * (12) Z.T. Zhao, D. Wang, Z.H. Yang, and L. Yin, “SCLF: An 8-GeV CW SCRF Linac-Based X-Ray FEL Facility in Shanghai”, in Proc. 38th Int. Free Electron Laser Conf. (FEL’17), Santa Fe, NM, USA, Aug. 2017, paper MOP055, pp. 182-184, ISBN: 978-3-95450-179-3, https://doi.org/10.18429/JACoW-FEL2017-MOP055, 2018.
  * (13) Toru Hara, et al., Pulse-by-pulse multi-beam-line operation for x-ray free-electron lasers. Phys. Rev. Accel. Beams 19, 020703 (2016). http://dx.doi.org/10.1103/PhysRevAccelBeams.19.020703
  * (14) Toru Hara, et al., High peak current operation of x-ray free-electron laser multiple beam lines by suppressing coherent synchrotron radiation effects. Phys. Rev. Accel. Beams 21, 040701 (2018). https://doi.org/10.1103/PhysRevAccelBeams.21.040701
  * (15) T. Beukers, et al., A Beam Spreader System for LCLS-II. SLAC-PUB-17468, https://www.slac.stanford.edu/pubs/slacpubs/17250/slac-pub-17468.pdf
  * (16) V. Balandin, et al., Optics for the Beam Switchyard at the European XFEL. in Proceedings of IPAC2011, San Sebastián, Spain, WEPC008. https://accelconf.web.cern.ch/IPAC2011/papers/wepc008.pdf
  * (17) N. Milas, et al., Switchyard Design: ATHOS, in Proceedings of FEL2012, Nara, Japan, MOPD37. https://accelconf.web.cern.ch/FEL2012/papers/mopd37.pdf
  * (18) S. Di Mitri, et al., Cancellation of Coherent Synchrotron Radiation Kicks with Optics Balance. Phys. Rev. Lett. 110, 014801 (2013). https://doi.org/10.1103/PhysRevLett.110.014801
  * (19) M. Borland, elegant: A Flexible SDDS-Compliant Code for Accelerator Simulation, Advanced Photon Source LS-287, September 2000.