# Tropical convexity in location problems

Andrei Comăneci  Institut für Mathematik, Technische Universität Berlin
<EMAIL_ADDRESS>
###### Abstract.

We investigate location problems whose optimum lies in the tropical convex
hull of the input points. Firstly, we study geodesically star-convex sets
under the asymmetric tropical distance and introduce the class of tropically
quasiconvex functions whose sub-level sets have this shape. The latter are
related to monotonic functions. Then we show that location problems whose
distances are measured by tropically quasiconvex functions as before give an
optimum in the tropical convex hull of the input points. We also show that a
similar result holds if we replace the input points by tropically convex sets.
Finally, we focus on applications to phylogenetics presenting properties of
consensus methods arising from our class of location problems.

###### Key words and phrases:

tropical convexity; tropically quasiconvex function; monotonic norms; tropical
$L^{p}$-norm; tropically convex consensus trees

###### 2020 Mathematics Subject Classification:

14T90, 26B25, 52A30, 90B85, 92B10

##  1\. Introduction

There is a recent interest in studying location problems in tropical geometry,
especially in the use of tropical methods to data analysis. Maybe the first
article to promote such problems with a view towards “tropical statistics” is
the work of Lin et al. [27]. They showed that tropical convexity in tree
spaces has some better properties than the geometry of Billera, Holmes, and
Vogtmann (BHV) [7]. This encouraged them to propose location estimators based
on the symmetric tropical distance that could potentially exploit tropical
convexity. In particular, this would give a tropical approach to the consensus
problem from phylogenetics [9].

The connection for the proposed location statistics to tropical convexity was
not well understood. For example, they noticed that tropical Fermat–Weber
points can lie outside the tropical convex hull of the input points [27,
Example 26], although it was found later that one can find Fermat–Weber points
inside the tropical convex hull [34, Lemma 3.5]. However, the unclear
connection makes it difficult to obtain solutions that can be interpreted in
the phylogenetic setting; see also [28].

Recently, we could show that studying the Fermat–Weber problem using an
_asymmetric_ distance function leads to a better explanation in terms of
tropical convexity [12]. In particular, it provides a clear approach based on
tropical convexity to the consensus problem from phylogenetics. Moreover,
various desirable properties of consensus methods were obtained by exploiting
tropical convexity. In fact, the good properties were solely due to tropical
convexity and not the particular distance function which motivates the search
for other methods with similar properties.

In this paper, we focus on location problems that have the potential of
exploiting tropical convexity. More specifically, we care of those location
estimators that will belong to the tropical convex hull of the input points.
Such estimators are based on distances that reflect the tropical structure of
the space and can be seen as a counterpart to similar studies regarding
location problems and ordinary convexity.

Significant work was done for understanding geometric properties of location
problems and their relationship to ordinary convexity. The case of Chebyshev
centers dates back to the 60s in the work of Garkavi [20] and Klee [25]. More
general location problems in a normed space were studied by Wendell and Hurter
[41], while a focus on geometric properties of Fermat–Weber problems with
varying distances is covered by Durier and Michelot [16]. What is more, it was
shown that finding an optimal solution in the (ordinary) convex hull for every
set of points is equivalent to having an inner product space in three
dimensions or more; a general form of this result was obtained by Durier [14,
15].

The results mentioned above show a strong relationship between ordinary
convexity and a Euclidean structure. Tropical convexity, on the other hand, it
is related to the lattice structure of $({\mathbb{R}}^{n},\leq)$. Hence, we
have to focus on “monotonic” distances. To interpret geometrically monotonic
functions in the quotient space ${\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$,
we notice that all sub-level sets share a similarity: they are geodesically
star-convex with respect to the asymmetric tropical distance. The latter can
be seen by remarking that geodesic segments are images of order segments in
$({\mathbb{R}}^{n},\leq)$. The resulting sets, called $\triangle$-star-convex,
and functions, called $\triangle$-star-quasiconvex, are discussed in sections
3 and 4, respectively.

In section 5 we focus on location problems in which distances to the sites are
measured by $\triangle$-star-quasiconvex functions. We show that this setting
guarantees optimal locations in the tropical convex hull of the input. We will
see that the triangle inequality does not play any role, which emphasizes the
differences between tropical and ordinary convexity. Further, this setting
allows for very general location problems where dissimilarities are not
necessarily distances; triangle inequality is generally assumed in location
science when dealing with geographic location [26], but it is not reasonable
for more general data [40] and never assumed in the construction of
M-estimators [23, §3.2].

We have further a few examples of location problems from the literature that
end in our setting. In particular, location problems involving the symmetric
and asymmetric tropical distances. However, the former case might contain
cases where some optima are outside the tropical convex hull of the input. So
what is the precise distinction between the symmetric and the asymmetric
tropical distances that causes the above behaviour? We show that _strict_
$\triangle$-star-convexity is the answer. This motivates that study of
regularized versions discussed in §5.2.

We briefly show in section 6 that we can extend the results to the case when
the sites are tropically convex sets. Then section 7 deals with the main
application to phylogenetics: the tropical approach to consensus methods. Our
general setting provides a large class of tropically convex consensus methods
as defined in [12, §5]. Furthermore, we enlarge the list of desirable
properties of these consensus methods that were given in the previously cited
work. Finally, we conclude with section 8 consisting of highlights and
possible directions for future research.

##  2\. Tropical convexity

The purpose of this section is to fix the notation and emphasize the basic
properties of tropically convex sets that will be used later. One can consult
the book of Joswig [24] for more details. We will use both semirings
${\mathbb{T}}^{\min}=\left({\mathbb{R}}\cup\\{\infty\\},\wedge,+\right)$ and
${\mathbb{T}}^{\max}=\left({\mathbb{R}}\cup\\{-\infty\\},\vee,+\right)$ where
$x\wedge y=\min(x,y)$ and $x\vee y=\max(x,y)$. They are isomorphic under the
map $x\mapsto-x$, but it is better to be seen as dual to each other. This
duality will play an important role later similar to the relationship between
$\max$-tropical polytopes and $\min$-tropical hyperplanes [24, Chapter 6].

Since our applications deal with points of finite entry, we will define
tropical geometric objects in ${\mathbb{R}}^{n}$ and
${\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$. It also exploits the common set
of ${\mathbb{T}}^{\max}$ and ${\mathbb{T}}^{\min}$ and we can make use of the
vector space structure.

A _$\min$ -tropical cone_ $K\subset{\mathbb{R}}^{n}$ is a set closed under
$\min$-tropical linear combinations:
$(x+\lambda{\mathbf{1}})\wedge(y+\mu{\mathbf{1}})\in K$ for all $x,y\in K$ and
$\lambda,\mu\in{\mathbb{R}}$. The image of a $\min$-tropical cone in
${\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$ is called a _$\min$ -tropically
convex set_. A common example is the $\min$-tropical hyperplane with apex $v$
which is the set
$H^{\min}_{v}=\left\\{x\in{\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}:|\operatorname{arg\,min}_{j}(x_{j}-v_{j})|\geq
2\right\\}$. The $\max$-tropical cones and $\max$-tropically convex sets are
defined similarly, replacing $\min$ by $\max$ in the previous definitions. One
can also see them as images of $\min$-tropical cones and $\min$-tropically
convex sets under $x\mapsto-x$.

The $\min$-tropical convex hull of two points
$a,b\in{\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$ will be denoted by
$[a,b]_{\max}$ and is called the _$\min$ -tropical segment_ between $a$ and
$b$. We will also use the notation
$(a,b)_{\min}=[a,b]_{\min}\setminus\\{a,b\\}$ for the _open_ $\min$-tropical
segment between $a$ and $b$. Similarly, we define $[a,b]_{\max}$ and
$(a,b)_{\max}$.

The _$\min$ -tropical convex hull_ of a set
$A\subset{\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$ is the smallest
$\min$-tropically convex set containing $A$ and we denote it by
$\operatorname{tconv}^{\min}(A)$. It can be related to the $\max$-tropical
semiring by [24, Proposition 5.37]. For this we need to introduce the
$\max$-tropical sector
$S_{i}^{\max}=\\{x\in{\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}:x_{i}\geq
x_{j}\ \forall
j\in[n]\\}=\\{x\in{\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}:i\in\operatorname{arg\,min}_{j}x_{j}\\}$.
Then [24, Proposition 5.37] says that $x$ belongs to
$\operatorname{tconv}^{\min}(A)$ if and only if for each $i\in[n]$ there
exists $a_{i}\in A$ such that $x\in a_{i}+S_{i}^{\max}$. For the case of
$\max$-tropically convex hull just reverse $\min$ with $\max$.

We say that a point $a$ of a $\min$-tropically convex set $A$ is _$i$
-exposed_ if $\left(a+S_{i}^{\min}\right)\cap A=\\{a\\}$. If a point is
$i$-exposed for some $i\in[n]$, then we simply call it _exposed_.

Since the order $\leq$ on ${\mathbb{R}}^{n}$ is strongly related to tropical
convexity, we will focus on monotonic function. We say that a function
$f:X\to{\mathbb{R}}$, defined on a subset $X$ of ${\mathbb{R}}^{n}$, is
_increasing_ if for every $x,y\in X$ with $x\leq y$ we have $f(x)\leq f(y)$.
We call $f$ _strictly increasing_ if $f(x)<f(y)$ whenever $x\leq y$ and $x\neq
y$.

For $a,b\in{\mathbb{R}}^{n}$ and $a\leq b$, we denote by $[a,b]_{\leq}$ the
set of points $x\in{\mathbb{R}}^{n}$ such that $a\leq x\leq b$ and call it the
_order segment_ between $a$ and $b$. It can also be written as a box:
$[a,b]_{\leq}=[a_{1},b_{1}]\times\dots\times[a_{n},b_{n}]$. Its image in
${\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$ is a _polytrope_ , i.e. it is both
$\min$\- and $\max$-tropically convex [24, §6.5], which we call a _box
polytrope_. A particular case is presented in the following example.

Consider the asymmetric distance
$d_{\triangle}(a,b)=\sum_{i}(b_{i}-a_{i})-n\min_{j}(b_{j}-a_{j})$ defined on
${\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$ [12]. We are interested in
geodesic segments under this distance, which are portrayed in Figure 1. This
is different from the geodesic convexity discussed in [24, §5.3] which focuses
on the symmetric tropical distance.

######  Definition 1.

For two points $a,b\in{\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$ we define the
(oriented) _geodesic segment_ between $a$ and $b$ under $d_{\triangle}$ as
$[a,b]_{\triangle}:=\left\\{x\in{\mathbb{R}}^{n}:d_{\triangle}(a,x)+d_{\triangle}(x,b)=d_{\triangle}(a,b)\right\\}$.

######  Remark 2.

[width=0.35]triangleSeg

Figure 1. The geodesic segment $[a,b]_{\triangle}$ is marked with grey

The geodesic segment $[a,b]_{\triangle}$ is a (box) polytrope. To see this, we
point out that $[a,b]_{\triangle}=(a+S_{i}^{\min})\cap(b+S_{i}^{\max})$ where
$i$ is any index from $\operatorname{arg\,min}_{j}(b_{j}-a_{j})$; the equality
can be also seen in Figure 1. What is more, if we choose representatives $a$
and $b$ such that $\min_{j}(b_{j}-a_{j})=0$, then $[a,b]_{\triangle}$ is the
image of $[a,b]_{\leq}$ in ${\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$. The
$\min$-tropical vertices $[a,b]_{\triangle}$ are of the form
$v_{j}=b-(b_{j}-b_{i}+a_{i}-a_{j})e_{j}=b-\left(b_{j}-a_{j}-\min_{\ell}(b_{\ell}-a_{\ell})\right)e_{j}$
for $j\in[n]$

######  Remark 3.

The set $[a,b]_{\triangle}$ contains the ordinary segment $[a,b]$ but also the
$\min$\- and $\max$-tropical segments between $a$ and $b$. What is more, for
every $c\in{\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$ the $\min$-tropical
segment between $a$ and $b$ is contained in
$[c,a]_{\triangle}\cup[c,b]_{\triangle}$.

To see the latter statement, we take arbitrary representatives modulo
${\mathbb{R}}{\mathbf{1}}$ for $a$ and $b$ and show that $a\wedge
b\in[c,a]_{\triangle}\cup[c,b]_{\triangle}$. Let
$i\in\operatorname{arg\,min}_{j}[(a_{j}\wedge b_{j})-c_{j}]$. Without loss of
generality, we can assume that $a_{i}\wedge b_{i}=a_{i}$. Thus, $a\wedge
b\in(c+S_{i}^{\min})\cap(a+S_{i}^{\max})=[c,a]_{\triangle}$.

The _canonical coordinates_ of a point
$x\in{\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$ are the entries of the
$\widehat{x}\in{\mathbb{R}}^{n}$ defined by
$\widehat{x}=x-\left(\min_{j}x_{j}\right){\mathbf{1}}$. This is a
representative of $x$ modulo ${\mathbb{R}}{\mathbf{1}}$ such that all its
entries are non-negative and at least one entry is $0$.

######  Definition 4.

We say that $K$ is a _strictly $\min$-tropically convex cone_ if $K$ is a
$\min$-tropically convex cone and for every $a,b\in K$ such that $a\wedge b$
is different from $a$ and $b$ modulo ${\mathbb{R}}{\mathbf{1}}$, then $a\wedge
b$ belongs to the interior of $K$.

We say that a subset of ${\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$ is
_strictly $\min$-tropically convex_ if it is the image of a strictly
$\min$-tropically convex cone under the canonical projection
${\mathbb{R}}^{n}\to{\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$.

######  Remark 5.

A subset $L$ of ${\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$ is strictly
$\min$-tropically convex if all the points of the open $\min$-tropical segment
$(a,b)_{\min}$ belong to the interior of $L$, where $a$ and $b$ are distinct
points in $L$.

######  Proposition 6.

Any strictly $\min$-tropically convex set is a singleton or its closure
coincides with the closure of its interior. Moreover, all of its boundary
points are exposed.

###### Proof.

The first part results from Remark 5. For the second part, consider $v$ which
is not exposed. Then there exist $p,q$ in the strictly $\min$-tropically
convex set such that $v\in(p,q)_{\min}$. According to the same remark, $v$ is
an interior point. ∎

##  3\. $\triangle$-star-convex sets

######  Definition 7.

A _$\triangle$ -star-convex_ set with kernel $v$ is a non-empty set
$K\subseteq{\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$ such that for every
point $w\in K$ we have $[v,w]_{\triangle}\subseteq K$. We call $K$ _strictly_
$\triangle$-star-convex if $[v,w]_{\triangle}\setminus\\{w\\}$ belongs to the
interior of $K$ for every $w\in K$.

Since $[v,w]_{\triangle}$ contains the ordinary segment $[v,w]$, we conclude
that $\triangle$-star-convex sets are also star-convex in the ordinary sense.
We show now that $\triangle$-star-convex sets are $\min$-tropically convex.

######  Proposition 8.

Any $\triangle$-star-convex set is $\min$-tropically convex.

###### Proof.

Let $K$ be a $\triangle$-star-convex set with kernel $v$ and $a,b$ arbitrary
points in $K$. According to Remark 3, we have
$[a,b]_{\min}\subseteq[v,a]_{\triangle}\cup[v,b]_{\triangle}$. The latter set
is contained in $K$ due to its $\triangle$-star-convexity. ∎

However, $\triangle$-star-convex sets might not be $\max$-tropically convex.
For example, the image of the regular simplex
$\Delta_{n}=\operatorname{conv}\\{e_{1},\dots,e_{n}\\}$ in
${\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$ is $\triangle$-star-convex but not
$\max$-tropically convex.

######  Example 9.

[width=0.3]tropicalHyperplane |  [width=0.3]tropical_Lp_balls |  [width=0.3]complicatedTriangStar
---|---|---
(a) $\min$-tropical hyperplane |  (b) Tropical $L^{p}$ balls for ${p\in\\{1/4,1,2,\infty\\}}$ |  (c) More complicated $\triangle$-star-convex set
Figure 2. $\triangle$-star-convex sets

One can find examples of $\triangle$-star-convex sets in Figure 2. Picture (a)
shows a $\min$-tropical hyperplane $H^{\min}_{v}$ which is $\triangle$-star-
convex with kernel $v$—the apex.

Picture (b) displays the unit balls for tropical $L^{p}$ norms, which will be
defined in Example 14. They are nested increasingly with respect to $p$; the
outer one corresponds to the tropical $L^{\infty}$ norm and is the only one
that is not strictly $\triangle$-star-convex. One can recognize the triangle
as the unit ball for the asymmetric tropical distance $d_{\triangle}$. The
$\min$-tropical hyperplane with apex at the origin (the kernel of the
$\triangle$-star-convex sets) is dotted.

Picture (c) shows a more complicated $\triangle$-star-convex sets. This case
is not pure dimensional, the tropically exposed points do not form a closed
set. Moreover, it is neither convex in the ordinary sense, nor strictly
$\triangle$-star-convex.

######  Proposition 10.

Let $K$ be a $\triangle$-star-convex set with kernel $v$ such that
$K\neq\\{v\\}$. Then $K$ is strictly $\triangle$-star-convex if and only if
$K$ is strictly $\min$-tropically convex and $v$ is an interior point of $K$.

###### Proof.

Firstly, assume that $K$ is strictly $\triangle$-star-convex. For every
$a,b\in K$ the $\min$-tropical segment $[a,b]_{\min}$ is a subset of
$[v,a]_{\triangle}\cup[v,b]_{\triangle}$. Therefore, all of the points of
$[a,b]_{\min}$ with the exception of $a$ and $b$ must be in the interior of
$K$. Hence, $K$ is strictly $\min$-tropically convex. The fact that $v$ is an
interior point is clear from the definition and our assumption that
$K\neq\\{v\\}$.

Conversely, assume that $K$ is strictly $\min$-tropically convex and $v$ is an
interior point of $K$. We consider $w\in K\setminus\\{v\\}$ and we show that
all points of $[v,w]_{\triangle}\setminus\\{w\\}$ are in the interior of $K$.
The result is clear for non-exposed points of $[v,w]_{\triangle}$ as we
assumed $K$ is strictly $\min$-tropically convex. Hence, let $u$ be an exposed
point of $[v,w]_{\triangle}$ distinct from $w$. According to the discussion
from Remark 2, $u=w-(w_{j}-w_{i})e_{j}$ where
$i\in\operatorname{arg\,min}_{k}w_{k}$ and
$j\notin\operatorname{arg\,min}_{k}w_{k}$. Since $(u+w)/2$ belongs to the
interior of the tropical segment $[u,w]_{\min}$ and $K$ is strictly
$\min$-tropically convex, then $(u+w)/2$ is an interior point of $K$. Thus,
for small $\delta>0$, the point $c=(u+w)/2-\delta e_{i}$ belongs to $K$.

However, $u\in[v,c]_{\triangle}=S_{i}^{\min}\cap(c+S_{i}^{\max})$ as
$c-u=(w-u)/2-\delta e_{i}=({w_{j}-w_{i}})e_{j}/2-\delta e_{i}$. But $u$ cannot
be an exposed point of $[v,c]_{\triangle}$ as $c-u$ is not parallel to a
vector $e_{k}$ for $k\in[n]$ unless $n=2$. Consequently, $u$ must be an
interior point of $K$ from the strict $\min$-tropical convexity of $K$, when
$n\geq 3$.

For the case $n=2$, we could have noticed that the exposed points of
$[v,w]_{\triangle}$ are $v$ and $w$, so $u$ can only be equal to $v$. But $v$
was already assumed to be interior. ∎

######  Remark 11.

The proof above shows that the assumption that $v$ is an interior point of $K$
is superfluous for the converse when $n\geq 3$.

######  Lemma 12.

If $K$ is strictly $\triangle$-star-convex with kernel $v$, then any exposed
point of $K$ from $v+S_{i}^{\min}$ is $i$-exposed.

###### Proof.

If $a\in v+S_{i}^{\min}$ and it is not $i$-exposed, then there exists
$b\in(a+S_{i}^{\min})\cap K$ with $b\neq a$. In particular,
$a\in[v,b]_{\triangle}\setminus\\{b\\}$. But the strict $\triangle$-star-
convexity of $K$ implies that $a$ must be an interior point. ∎

##  4\. Tropically quasiconvex functions

A function $f:{\mathbb{R}}^{n}\to{\mathbb{R}}$ whose sub-level sets
$L_{\leq\alpha}(f):=\\{x:f(x)\leq\alpha\\}$ are convex is called
_quasiconvex_. This is a purely geometric definition, but some other sources
define them as functions satisfying $f(\lambda
x+({1-\lambda})y)\leq\max\\{f(x),f(y)\\}$ for every $x,y\in{\mathbb{R}}^{n}$
and $\lambda\in[0,1]$. The latter can be more convenient in checking
quasiconvexity. See [4, Chapter 3] for more details.

We will be interested in specific _tropically quasiconvex_ functions. Before
we introduce them, we need some notation. For a function
$\gamma:{\mathbb{R}}^{n}_{\geq 0}\to{\mathbb{R}}$ we associate the function
$\widehat{\gamma}:{\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}\to{\mathbb{R}}$
defined by $\widehat{\gamma}(x)=\gamma(\widehat{x})$. We recall that
$\widehat{x}=x-\left(\min_{i}x_{i}\right){\mathbf{1}}$ are the canonical
coordinates of $x$.

######  Definition 13.

We call a function
$f:{\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}\to{\mathbb{R}}$ _$\triangle$
-star-quasiconvex_ with kernel $v$ if $f(x)=\widehat{\gamma}(x-v)$ for some
increasing function $\gamma:{\mathbb{R}}^{n}_{\geq 0}\to{\mathbb{R}}$.
Moreover, if $\gamma$ is strictly increasing, we call $f$ _strictly
$\triangle$-star-quasiconvex_.

We will give a geometric interpretation of $\triangle$-star-quasiconvex in
Theorem 17. However, we prefer the definition above because it easier to check
in practice.

######  Example 14.

Considering $\gamma$ a monotonic norm [6], $f$ measures the distance to the
kernel. If $v={\mathbf{0}}$, then $f$ is a _gauge_ which are commonly used in
convex analysis [36] and location science [32]. Gauges are sometimes dubbed
“asymmetric norms” as they satisfy all the properties of a norm with the
exception that $f(x)$ need not be equal to $f(-x)$.

A famous class of monotonic norms are the $L^{p}$ norms. They give rise to
$\triangle$-star-quasiconvex gauges whose expression is

$\gamma_{p}(x)=\left\\{\begin{array}[]{ll}\sqrt[p]{\sum_{i\in[n]}\left(x_{i}-\min_{j\in[n]}x_{j}\right)^{p}}&\text{if
}p\in[1,\infty)\\\ \max_{i\in[n]}x_{i}-\min_{j\in[n]}x_{j}&\text{if
}p=\infty\\\ \end{array}\right..$

We call them _tropical $L^{p}$ norms_. They appeared in the work of Luo [29]
under the name “$B^{p}$-pseudonorms”.

One can recognize the tropical $L^{\infty}$ norm as the tropical norm defined
in [22, §5]. The relationship to the $L^{\infty}$ norm is stressed in [22,
Lemma 5.2.1]. The tropical $L^{1}$ norm gives rise to the asymmetric tropical
distance $d_{\triangle}$; this relationship is implicit in [12, §6].

######  Remark 15.

The function $\widehat{\gamma}$ depends only on the values on
$\partial{\mathbb{R}}^{n}_{\geq 0}$, so we could have considered only
$\partial{\mathbb{R}}^{n}_{\geq 0}$ as the domain of $\gamma$. However, this
does not increase the generality since every (strictly) increasing function
defined on $\partial{\mathbb{R}}^{n}_{\geq 0}$ can be extended to a (strictly)
increasing function on ${\mathbb{R}}^{n}_{\geq 0}$, according to the following
lemma.

######  Lemma 16.

Every (strictly) increasing function $\gamma:\partial{\mathbb{R}}^{n}_{\geq
0}\to{\mathbb{R}}$ can be extended to a (strictly) increasing function
$\tilde{\gamma}:{\mathbb{R}}^{n}_{\geq 0}\to{\mathbb{R}}$. Moreover, if
$\gamma$ is continuous, then the extension can also be made continuous.

###### Proof.

Consider
$\tilde{\gamma}(x)=\max_{i\in[n]}\gamma(x_{-i},0_{i})+\prod_{i\in[n]}x_{i}$.
Clearly, this is continuous if $\gamma$ is, as being a composition of
continuous functions. Moreover, $\tilde{\gamma}(x)=\gamma(x)$ for every
$\mathbf{x}\in\partial{\mathbb{R}}^{n}_{\geq 0}$, due to monotonicity of
$\gamma$ and the fact that $x_{1}x_{2}\dots x_{n}=0$ for
$x\in\partial{\mathbb{R}}^{n}_{\geq 0}$.

If $x\leq y$, then $x_{-i}\leq y_{-i}$ for all $i\in[n]$, where $x_{-i}$ is
obtained from $x$ by removing the $i$th entry. Therefore,
$\gamma(x_{-i},0_{i})\leq\gamma(y_{-i},0_{i})$ for every $i\in[n]$, which
implies $\tilde{\gamma}(x)\leq\tilde{\gamma}(y)$ after using
$\prod_{j}x_{j}\leq\prod_{j}y_{j}$. In other words, $\tilde{\gamma}$ is
increasing.

Moreover, if $\gamma$ is strictly increasing and $x\neq y$ we have two cases.
On the one hand, if $y\in\partial{\mathbb{R}}^{n}_{\geq 0}$, then
$x\in\partial{\mathbb{R}}^{n}_{\geq 0}$ so
$\tilde{\gamma}(x)=\gamma(x)<\gamma(y)=\tilde{\gamma}(y)$.

On the other hand, if $y\in{\mathbb{R}}^{n}_{>0}$, then
$\prod_{j}x_{j}<\prod_{j}y_{j}$. Using the last inequality with
$\max_{i\in[n]}\gamma(x_{-i},0_{i})\leq\max_{i\in[n]}\gamma(y_{-i},0_{i})$, we
obtain $\tilde{\gamma}(x)<\tilde{\gamma}(y)$. Accordingly, $\tilde{\gamma}$ is
strictly increasing if $\gamma$ is strictly increasing. ∎

The following result explains why the functions from Definition 13 deserve the
name “$\triangle$-star-quasiconvex”.

######  Theorem 17.

Let $f:{\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}\to{\mathbb{R}}$ be a
continuous function. Then $f$ is (strictly) $\triangle$-star-quasiconvex if
and only if all of its non-empty sub-level sets are (strictly)
$\triangle$-star convex with the same kernel.

###### Proof.

After an eventual translation, we can assume that the kernel is
${\mathbf{0}}$.

Firstly, assume $f$ is $\triangle$-star-quasiconvex and let
$\alpha\in{\mathbb{R}}^{n}$ arbitrary such that $L_{\leq\alpha}(f)$ is non-
empty. Let $\gamma:{\mathbb{R}}^{n}\to{\mathbb{R}}$ increasing such that
$f(x)=\widehat{\gamma}(x)$.

Let $w\in L_{\leq\alpha}(f)$ and choose $i\in[n]$ such that $w\in
S_{i}^{\min}$. Since $\gamma$ is increasing, the points $x\in{\mathbb{R}}^{n}$
satisfying ${\mathbf{0}}\leq x\leq\widehat{w}$ belong to
$L_{\leq\alpha}(\gamma)$. This set projects onto
$[{\mathbf{0}},w]_{\triangle}$ showing that
$[{\mathbf{0}},w]_{\triangle}\subseteq L_{\leq\alpha}(f)$. Since $w$ was
selected arbitrarily, $L_{\leq\alpha}(f)$ must be $\triangle$-star convex with
kernel ${\mathbf{0}}$.

If $f$ is strictly $\triangle$-star-quasiconvex, then the points satisfying
${\mathbf{0}}\leq x\leq\widehat{w}$ different from $\widehat{w}$ actually
belong to $L_{<\alpha}(f)$. Due to the continuity of $f$, this coincides with
the interior of $L_{\leq\alpha}(f)$. This shows that $L_{\leq\alpha}(f)$ is
strictly $\triangle$-star-convex.

Conversely, assume that $L_{\leq\alpha}(f)$ is $\triangle$-star-convex with
kernel ${\mathbf{0}}$ for every $\alpha\geq f({\mathbf{0}})$. Take
$\gamma:\partial{\mathbb{R}}^{n}_{\geq 0}\to{\mathbb{R}}$ defined as
$\gamma(x)=f(\widehat{x})$ for $x\in\partial{\mathbb{R}}^{n}_{\geq 0}$. Using
Lemma 16 it is enough to show that $\gamma$ is increasing.

Let $x$ and $y$ arbitrary points of $\partial{\mathbb{R}}^{n}_{\geq 0}$ such
that $x\leq y$. The order segment $[{\mathbf{0}},y]_{\leq}$ projects onto
$[{\mathbf{0}},y]_{\triangle}$ which belongs to $L_{\leq f(y)}(f)$. Due to the
$\triangle$-star-convexity of sub-level sets, we obtain $\gamma(x)=f(x)\leq
f(y)=\gamma(y)$.

If we have strict $\triangle$-star-convexity, then
$[0,y]_{\triangle}\setminus\\{y\\}$ is contained in the interior of $L_{\leq
f(y)}(f)$ which coincides to $L_{<f(y)}(f)$. Hence, we obtain
$\gamma(x)<\gamma(y)$ for this case. ∎

######  Remark 18.

The continuity of $f$ is relevant only for strictly $\triangle$-star-
quasiconvex functions. Without continuity, only the strict $\triangle$-star-
convexity of the sub-level sets is not sufficient for $f$ to be strictly
$\triangle$-star-quasiconvex. This is similar to the case of ordinary
quasiconvex functions; cf. [4, Proposition 3.28] and [4, Example 3.3].

We will see that convexity, in the ordinary sense, will also be helpful for
our applications. We give a simple criterion for checking when a
$\triangle$-star-quasiconvex function is convex.

######  Lemma 19.

If $\gamma$ is increasing and (strictly) convex, then $\widehat{\gamma}$ is
(strictly) convex.

###### Proof.

Let $x,y\in{\mathbb{R}}^{n}$ and $\lambda\in[0,1]$.

We have $\min_{j}\left(\lambda
x_{i}+(1-\lambda)y_{i}\right)\geq\lambda\min_{i}x_{i}+(1-\lambda)\min_{i}y_{i}$
as $\lambda,1-\lambda\geq 0$. Hence, $\lambda
x+(1-\lambda)y-\min_{j}\left(\lambda
x_{i}+(1-\lambda)y_{i}\right){\mathbf{1}}\leq\lambda(x-\min_{i}x_{i}{\mathbf{1}})+(1-\lambda)(y-\min_{i}y_{i}{\mathbf{1}})$.
Since $\gamma$ is convex and increasing, we obtain

(1) $\begin{split}\widehat{\gamma}\left(\lambda
x+(1-\lambda)y\right)&\leq\gamma\left(\lambda(x-\min_{i}x_{i}{\mathbf{1}})+(1-\lambda)(y-\min_{i}y_{i}{\mathbf{1}})\right)\\\
&\leq\lambda\,\gamma(x-\min_{i}x_{i}{\mathbf{1}})+(1-\lambda)\,\gamma(y-\min_{i}y_{i}{\mathbf{1}})\\\
&=\lambda\widehat{\gamma}(x)+(1-\lambda)\widehat{\gamma}(y).\end{split}$

If $\gamma$ is strictly convex and $x\neq y$ modulo
${\mathbb{R}}{\mathbf{1}}$, then the second inequality from (1) is strict, so
$\widehat{\gamma}\left(\lambda
x+(1-\lambda)y\right)<\lambda\widehat{\gamma}(x)+(1-\lambda)\widehat{\gamma}(y)$.
Thus, $\widehat{\gamma}$ is strictly convex if $\gamma$ is strictly convex. ∎

##  5\. Tropically convex location problems

We will consider some input points $v_{1},\dots,v_{m}$ in
${\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$. We measure the distance (or
dissimilarity) from $x\in{\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$ to a point
$v_{i}$ using a $\triangle$-star-quasiconvex function $f_{i}$ having kernel
$v_{i}$. We consider increasing functions
$\gamma_{i}:{\mathbb{R}}^{n}\to{\mathbb{R}}$ such that
$f_{i}(x)=\widehat{\gamma}_{i}(x-v_{i})$. Without loss of generality, we
assume $\gamma_{i}({\mathbf{0}})=0$, so that all dissimilarities are non-
negative.

The purpose of location problems is to find a point as close (or similar) as
possible to the input points, depending on some criterion; usually, the
optimal location is a minimum of an objective function
$h:{\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}\to{\mathbb{R}}$. The function $h$
is constructed using an increasing function $g:{\mathbb{R}}^{m}_{\geq
0}\to{\mathbb{R}}$, which aggregates the distances to the input points.
Formally, we define $h(x)=g\left(f_{1}(x),\dots,f_{m}(x)\right)$.

Since $f_{i}$ measures the distance or dissimilarity from $x$ to $v_{i}$ and
$g$ is increasing, the minima of $h$ record a global closeness to the input
points. In most studied location problems, we would have a distance $d$ on
${\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$ and set $f_{i}(x)=d(x,v_{i})$.
Common choices of $g$ are $g(x)=x_{1}+\dots+x_{m}$, for the median or
Fermat–Weber problem, $g(x)=\max_{i\in[m]}x_{i}$ for the center problem [26],
or $g(x)=x_{1}^{2}+\dots+x_{m}^{2}$, for defining the Fréchet mean [18].
Nevertheless, we will allow $g$ to be an arbitrary increasing function. We
will assume that $h$ has a minimum, which happens, e.g., when $h$ is lower
semi-continuous.

######  Theorem 20.

Let $h$ be as above. Then there is a minimum of $h$ belonging to
$\operatorname{tconv}^{\max}(v_{1},\dots,v_{m})$. Moreover, if $g$ is strictly
increasing and at least one of $f_{1},\dots,f_{m}$ is strictly
$\triangle$-star-quasiconvex, then all the minima of $h$ are contained in
$\operatorname{tconv}^{\max}(v_{1},\dots,v_{m})$.

###### Proof.

Consider $x\notin\operatorname{tconv}^{\max}(v_{1},\dots,v_{m})$ which is a
minimum of $h$. Thus there exists $k\in[n]$ such that
$k\notin\operatorname{arg\,min}_{j}(x_{j}-v_{ij})$ for all $i\in[m]$. Set
$\delta_{i}:=x_{k}-v_{ik}-\min_{j}(x_{j}-v_{ij})$ for all $i$, and
$\delta=\min_{i}\delta_{i}$, which is strictly positive by the consideration
of $k$.

Note that $f_{i}(x-\delta e_{k})=\gamma_{i}\left(x-v_{i}-\delta
e_{k}-\min_{j}({x_{j}-v_{ij}){\mathbf{1}}}\right)\leq\gamma_{i}(x-v_{i}-{\min_{j}(x_{j}-v_{ij}){\mathbf{1}}})=f_{i}(x)$
for all $i\in[n]$. Hence $h(x-\delta e_{k})\leq h(x)$.

Note that the inequality above is strict if $g$ and some $\gamma_{\ell}$ are
strictly increasing. Indeed, in that case, we must have $f_{\ell}(x-\delta
e_{k})<f_{\ell}(x)$, so we use the strict increase of $g$ in the $\ell$th
entry. That would contradict the optimality of $x$, so the second statement of
the theorem holds.

For the first statement, we can only infer that $x-\delta e_{k}$ is also a
minimum of $h$. Hence, we can find an optimum of $h$ in
$\operatorname{tconv}^{\max}(v_{1},\dots,v_{m})$ by moving $x$ in directions
$-e_{k}$ for indices $k$ as above.

To be more precise, we collect in $D(x)$ the possible elementary descent
directions from $x$; formally
$D(x):=\bigcap_{i\in[m]}\left([n]\setminus\operatorname{arg\,min}_{j\in[n]}(x_{j}-v_{ij})\right)$.
Notice that $k\in D(x)$, but $k\notin D(x-\delta e_{k})$. Moreover,
$D(x-\delta e_{k})\subsetneq D(x)$, as the $\operatorname{arg\,min}$ functions
only increase by our move in a descent direction. Thus, replacing $x$ by
$x-\delta e_{k}$, we find a minimum with smaller $D(x)$. We can repeat the
procedure to construct a minimum $x^{\star}$ of $h$ with
$D(x^{\star})=\emptyset$. The last condition is equivalent to
$x^{\star}\in\operatorname{tconv}^{\max}(v_{1},\dots,v_{m})$ due to [24,
Proposition 5.37]. ∎

######  Remark 21.

The regions of $f_{i}$ where it looks like a monotonic function are induced by
the $\min$-tropical hyperplane based at $v_{i}$. Those hyperplanes defined the
$\max$-tropical polytope generated by the input points, explaining why we look
at the $\max$-tropical convex hull, instead of the $\min$ analogue.

The following lemma presents cases when there is a unique optimum location. We
recall that a gauge $\gamma$ is called _strictly convex_ if $\gamma(\lambda
x+(1-\lambda)y)<1$ for every $\lambda\in(0,1)$ and
$x,y\in{\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$ with
$\gamma(x)=\gamma(y)=1$, although they are not strictly convex functions.

######  Lemma 22.

Assume that $g,f_{1},\dots,f_{m}$ are convex, $g$ is strictly increasing, and
at least one of the following conditions holds:

  * a)

at least one $f_{i}$ is strictly convex; or

  * b)

all $f_{i}$ are strictly convex gauges and the points $v_{1},\dots,v_{m}$ are
not collinear.

Then $h$ is strictly convex. In particular, it has a unique minimum.

###### Proof.

Consider arbitrary distinct points
$x,y\in{\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$ and a scalar
$\lambda\in(0,1)$.

For case a), we have $f_{i}(\lambda x+(1-\lambda)y-v_{i})<\lambda
f_{i}(x-v_{i})+(1-\lambda)f_{i}(x-v_{i})$. Since $g$ is convex and strictly
increasing and the functions $f_{j}$ convex, we obtain $h(\lambda
x+(1-\lambda)y)<\lambda h(x)+(1-\lambda)h(y)$. So $h$ must be strictly convex.

For case b), at least one of the points $v_{i}$ is not on the line through $x$
and $y$. Then $x-v_{i}$ and $y-v_{i}$ they are not parallel and the strict
convexity of the unit ball defined by $f_{i}$ implies that $f_{i}(\lambda
x+(1-\lambda)y-v_{i})<\lambda f_{i}(x-v_{i})+(1-\lambda)f_{i}(x-v_{i})$. The
rest of the proof is identical to case a). ∎

###  5.1. Examples

Here we review the tropical location problems from literature that fall in our
category, i.e. an optimum belongs to the tropical convex hull of the input.

######  Example 23 (Tropical Fermat–Weber and Fréchet problems).

To the best of our knowledge, the first one-point location problems in
tropical geometry are proposed by Lin et al. [27]. They suggest the study of
Fermat–Weber points and Fréchet means under the symmetric tropical distance
$d_{\text{trop}}$. The goal was to relate them to tropical convexity for
applications in phylogenetics.

However, they noticed that tropical Fermat–Weber points might lie outside the
tropical convex hull of the input points leading to medians that cannot be
interpreted easily in biological applications [27, Example 27]. However,
Theorem 20 says that it is possible to find an optimum in the tropical convex
hull. This was already noticed for the tropical Fermat–Weber points [34, Lemma
3.5] but it was unknown, until now, for tropical Fréchet means.

######  Example 24 (Tropical center).

Consider the case $f_{i}(x)=d_{\triangle}(v_{i},x)$ and
$g(y)=\max(y_{1},\dots,y_{m})$. This can be interpreted as the center of the
minimum $\max$-tropical $L^{1}$ ball enclosing the points $v_{1},\dots,v_{m}$.
The tropical center appears in [12, Example 23], but the details are omitted.

If we choose representatives of the input points in
${\mathcal{H}}=\\{x\in{\mathbb{R}}^{n}:{x_{1}+\dots+x_{n}=0}\\}$, the optimum
can be obtained by solving the linear program:

(2) $\begin{array}[]{ll@{}ll}\text{minimize}&\displaystyle n\cdot t&\\\
\text{subject to}&\displaystyle v_{ij}-x_{j}\ \leq\ t\,,&\quad\text{for
}i\in[m]\text{ and }j\in[n]\\\ &\displaystyle x_{1}+\dots+x_{n}\ =\
0&\end{array}.$

Note that the $x$-coordinates of the optimal solutions are equal, modulo
${\mathbb{R}}{\mathbf{1}}$, to the $x$-coordinates of the linear program

(3) $\begin{array}[]{ll@{}ll}\text{minimize}&\displaystyle n\cdot
t+\sum_{j=1}^{n}x_{j}&\\\ \text{subject to}&\displaystyle v_{ij}-x_{j}\ \leq\
t\,,&\quad\text{for }i\in[m]\text{ and }j\in[n]\end{array}.$

Let $(t^{\star},x^{\star})$ an optimal solution of (3). For any solution of
(3) we have $t+x_{j}\geq\max_{i\in[m]}v_{ij}=:V_{j}$. In particular,
$x^{\star}$ will have the smallest entries if we actually have equality:
$t^{\star}+x^{\star}_{j}=V_{j}$, otherwise we can replace $x^{\star}$ by some
$x^{\star}-\varepsilon e_{i}$ to minimize the objective function. This implies
$x^{\star}=V$ modulo ${\mathbb{R}}{\mathbf{1}}$; in particular, the solution
is unique in ${\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$.

Even if we do not have $g$ strictly increasing, the uniqueness and Theorem 20
ensures that the optimum is in the tropical convex hull. However, this could
have been noticed from the closed form $V=\bigvee_{i}v_{i}$ for
$v_{1},\dots,v_{m}\in{\mathcal{H}}$.

######  Example 25 (Transportation problems).

Consider $\lambda_{1},\dots,\lambda_{n}>0$ and $\triangle(\lambda)$ the
simplex in ${\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$ whose vertices are
$e_{i}/\lambda_{i}$. Then
$\gamma_{\triangle(\lambda)}(x)=\sum_{i}\lambda_{i}x_{i}-\left(\sum_{i}\lambda_{i}\right)\min_{j}x_{j}$
is the gauge on ${\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$ whose unit ball is
$\triangle(\lambda)$.

The (weighted) Fermat–Weber problem
$\sum_{i\in[m]}w_{i}\gamma_{\triangle(\lambda)}(x-v_{i})$ is equivalent to a
transportation problem and every transportation problem can be reduced to this
case; to see this better, write it as a linear program after scaling the
weights $w_{i}$ such that $\sum_{i}w_{i}=\sum_{j}\lambda_{j}$ (this change
does not influence the optimum). This was firstly noticed in [12], where the
authors focused on the case $\lambda_{1}=\dots=\lambda_{n}$. The corresponding
optimum is called a _tropical median_ in the work cited.

The optimal point is called a $\lambda$-splitter by Tokuyama and Nakano [39],
but no metric interpretation was mentioned. The authors gave a condition of
partitioning the space in $n$ region in an equal fashion with some weights
coming from $\lambda$ and $w$; this can be seen as a reinterpretation of the
first-order optimality condition for the corresponding Fermat–Weber problem.
As a $\lambda$-splitter, it appeared in statistics [19] and as a particular
case of Minkowski partition problems [3].

######  Example 26 (Locating tropical hyperplanes).

The tropical hyperplanes are parametrized by
${\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$ by their identification with their
apex. Moreover, we have
$d_{\text{trop}}(a,H_{x}^{\max})=(x-a)_{(2)}-(x-a)_{(1)}$. For a vector $y$,
we denote by $y_{(k)}$ the $k$th smallest entry, also known as the $k$th order
statistic. Note that the aforementioned distance is $\triangle$-star-
quasiconvex with apex $a$; the easiest to see this is noticing that the second
order statistic is increasing. Therefore, our general location problems cover
the case of locating tropical hyperplanes.

The best-fit tropical hyperplane with with $L^{1}$ error, i.e. $g$ is the
$L^{1}$ norm, was considered by Yoshida, Zhang, and Zhang as part of _tropical
principal component analysis_ [43].

The case of $L^{\infty}$ error was considered by Akian et al. [1] for
applications to auction theory and called _tropical linear regression_. They
also show that the problem is polynomial-time equivalent to mean-payoff games
[1, Corollary 4.15] and, using
$d_{\text{trop}}(a,H_{x}^{\max})=d_{\text{trop}}(x,H_{a}^{\min})$, that it is
dual to the problem of finding the largest inscribed ball in the tropical
convex hull of the input points [1, Theorem 4.6].

[width=0.5]tropical_locations

Figure 3. Input points (purple) with their convex hull (black boundary) and
various locations from the examples of §5.1; see the discussion after the
examples

To end this subsection, we compute the optimal location from the examples
above for specific input points. We consider the points from [1, §4] which are
given by the columns of the matrix

$V\ =\ \begin{pmatrix}0&1&3&2\\\ 1&0&2&3\\\ 1&1&0&0\\\ \end{pmatrix}.$

For this input, there is a unique tropical Fréchet point, $(1,1,0)$, but the
set of tropical Fermat–Weber points is a hexagon, marked with grey in Figure
3. We remark that $V$ has two axes of symmetry and $(1,1,0)$ is their
intersection.

The point $(1,1,0)$ is also the tropical center of $V$, while the tropical
median is $(0,0,0)$. The latter point is the also the unique apex of the best-
fit tropical hyperplane with $L^{1}$ error of [43]. It is also a solution of
the tropical linear regression, but not the unique one. The apices of the
best-fit tropical hyperplanes with $L^{\infty}$ error are of the form
$(\lambda,\lambda,0)$ with $\lambda\leq 1$ and their set is pictured with
green in Figure 3.

###  5.2. Regularization

In some cases, we cannot expend $g$ to be strictly increasing or all the
dissimilarity functions $f_{i}$ to be strictly $\triangle$-star-quasiconvex.
Hence, a minimization algorithm might return a point outside the
$\max$-tropical convex hull of the input points, when there are multiple
solutions. In this subsection, we show how we could try to arrive to a
solution belonging to $\operatorname{tconv}^{\max}(v_{1},\dots,v_{m})$ through
a regularized formulation.

The idea of regularization is to consider a small parameter $\lambda>0$ and a
nicely behaved function
$f_{m+1}:{\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}\to{\mathbb{R}}_{\geq 0}$
and try to solve the optimization problem

$\text{minimize }g\left(f_{1}(x),\dots,f_{m}(x)\right)+\lambda f_{m+1}(x).$

For our purposes, $f_{m+1}$ is nicely behaved if it is strictly
$\triangle$-star-quasiconvex with a kernel from
$\operatorname{tconv}^{\max}(v_{1},\dots,v_{m})$. An easy choice for $v$ is
the tropical center from Example 24.

This is also a location problem with $g_{\lambda}:{\mathbb{R}}^{m+1}_{\geq
0}\to{\mathbb{R}}$ given by
$g_{\lambda}(x_{1},\dots,x_{m},x_{m+1})=g(x_{1},\dots,x_{m})+\lambda x_{m+1}$
and the optimality criterion is the function
$h_{\lambda}:{\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}\to{\mathbb{R}}$ given
by $h_{\lambda}(x)=g_{\lambda}(f_{1}(x),\dots,f_{m+1}(x))$ Note that
$g_{\lambda}$ is strictly increasing in the $(m+1)$-st entry for every
$\lambda>0$.

Checking more carefully the proof of Theorem 20, the second statement holds if
$f_{\ell}$ is strictly $\triangle$-star-quasiconvex and $g$ strictly
increasing in its $\ell$-th entry. We use this property for the
regularization. Therefore, we obtain the following direct consequence of
Theorem 20.

######  Corollary 27.

For every $\lambda>0$, all the minima of $h_{\lambda}$ lie in
$\operatorname{tconv}^{\max}(v_{1},\dots,v_{m})$.

The influence of the term $f_{m+1}$ decreases as $\lambda$ goes to $0$. If the
functions are regular enough, we expect that a collection of optima
$x^{\star}_{\lambda}$ of $h_{\lambda}$ to converge to an optimum of $h$. In
fact, $x^{\star}_{\lambda}$ will be an optimum of $h$ for $\lambda$
sufficiently small if $h$ is polyhedral convex and $f_{m+1}$ is Lipschitz
continuous.

######  Proposition 28.

If $h$ is polyhedral convex and $f_{m+1}$ is a convex function with sub-linear
growth, then there exists $\lambda_{0}>0$ such that all minima of
$h_{\lambda}$ are also minima of $h$ for every $\lambda<\lambda_{0}$.

The proof is quite technical using the differential theory from convex
analysis so it is given in the appendix. We stress that Proposition 28 can be
useful for studying the tropical Fermat–Weber problem from [28]. Without
regularization, it has undesirable behaviour for applications to biology; cf.
[12, §5.2].

##  6\. Location problems with tropically convex sites

Location problems can appear also when facilities are regions of the ambient
space and not only points. Here, we consider such a generalization where the
sites are tropically convex sets.

In the previous section, we used different distances to the input points.
Here, we will measure our dissimilarities in a uniform way, by fixing an
increasing function $\gamma:{\mathbb{R}}^{n}_{\geq 0}\to{\mathbb{R}}$ and
considering $d_{\gamma}(x,y)=\widehat{\gamma}(y-x)$. We than say that
$d_{\gamma}$ is $\triangle$-star-quasiconvex; if $\gamma$ is strictly
increasing we say that $d_{\gamma}$ is strictly $\triangle$-star-quasiconvex.
This allows a clear definition of a distance from a region to a point:
$d_{\gamma}(A,x):=\inf_{y\in A}d_{\gamma}(y,x)$.

For a closed $\max$-tropical cone $K\subseteq{\mathbb{R}}^{n}$ we define the
projection $\pi_{K}:{\mathbb{R}}^{n}\to K$ as $\pi_{K}(x)=\max\\{y\in K:y\leq
x\\}$. We note that
$\pi_{K}(x+\lambda{\mathbf{1}})=\pi_{K}(x)+\lambda{\mathbf{1}}$ for every
$x\in{\mathbb{R}}^{n}$ and $\lambda\in{\mathbb{R}}$, so it induces a well-
defined function
$\pi_{K/{\mathbb{R}}{\mathbf{1}}}:{\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}\to
K/{\mathbb{R}}{\mathbf{1}}$ called the _tropical projection_ onto the
$\max$-tropically convex set $K/{\mathbb{R}}{\mathbf{1}}$.

The following lemma gives an explicit formula for the tropical projection and
it characterizes it as a closest point under $d_{\gamma}$. We omit the proof,
as it is a classical result, shown when $\gamma$ is the maximum norm in [10,
§3] and for a general tropical $L^{p}$ norm in [29, Theorem 4.6].

######  Lemma 29.

Let $A$ be a closed $\max$-tropically convex set. Then the tropical projection
$\pi_{A}(x)$ of a point $x$ has the entries

(4) $\pi_{A}(x)_{i}=\max_{a\in
A}\left(a_{i}+\min_{j\in[n]}(x_{j}-a_{j})\right).$

Moreover, $d_{\gamma}(A,x)=d_{\gamma}(\pi_{A}(x),x)$ and $\pi_{A}(x)$ is the
unique point whose distance to $x$ equals $d_{\gamma}(A,x)$ if $d_{\gamma}$ is
strictly $\triangle$-star-quasiconvex.

######  Remark 30.

In fact, the maximum expression of the tropical projection from Lemma 29 can
be taken over the extremal points, in the case of tropical polytopes [24,
Propositon 5.24]. A similar result seems similar for general convex sets, but
the form above is sufficient for our purposes.

From now on, our given sites are closed $\max$-tropically convex sites
$A_{1},\dots,A_{m}$ in ${\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$. Similar to
section 5, the objective function is
$h=g\left(d_{\gamma}(A_{1},x),\dots,d_{\gamma}(A_{m},x)\right)$, where
$g:{\mathbb{R}}^{m}_{\geq 0}\to{\mathbb{R}}_{\geq 0}$ is increasing.

######  Theorem 31.

There exists an minimum of $h$ lying in the tropical convex hull of the input
$\operatorname{tconv}^{\max}(A_{1}\cup\dots\cup A_{m})$. Moreover, if $g$ and
$\gamma$ are strictly increasing, then all the minima of $h$ lie in
$\operatorname{tconv}^{\max}(A_{1}\cup\dots\cup A_{m})$.

###### Proof.

If $x\notin\operatorname{tconv}^{\max}(A_{1}\cup\dots\cup A_{m})$, then [24,
Proposition 5.37] entails the existence of an index $\ell\in[n]$ such that
$\min_{j\neq\ell}({x_{j}-a_{j}})<{x_{\ell}-a_{\ell}}$ for every
$a\in\operatorname{tconv}^{\max}(A_{1}\cup\dots\cup A_{m})$. Since
$A_{1},\dots,A_{m}$ are closed sets, then there exists an open ball around $x$
not intersecting the union of these sets. Thus, for $\delta>0$ sufficiently
small and $y=x-\delta e_{\ell}$ we have
$\min_{j}(y_{j}-a_{j})=\min_{j}(x_{j}-a_{j})$ for every
$a\in\operatorname{tconv}^{\max}(A_{1}\cup\dots\cup A_{m})$. Therefore,
equation (4) implies $\pi_{A_{i}}(y)=\pi_{A_{i}}(x)$ for all $i\in[m]$.

Note that $y-\pi_{A_{i}}(y)=x-\pi_{A_{i}}(x)-\delta e_{\ell}\leq
x-\pi_{A_{i}}(x)$. Since $\gamma$ is increasing, we have
$d_{\gamma}(A_{i},y)=\gamma(y-\pi_{A_{i}}(y))\leq\gamma(x-\pi_{A_{i}}(x))=d_{\gamma}(A_{i},x)$
for every $i\in[m]$. Moreover, if $\gamma$ is strictly increasing we get
$d_{\gamma}(A_{i},y)<d_{\gamma}(A_{i},x)$.

In other words, going from $x$ in the direction $-e_{\ell}$ we obtain a
decrease in all the distances $d_{\gamma}(A_{i},x)$; in particular, a decrease
of $h$. Using this observation, the rest of the proof is identical to the
proof of Theorem 20. ∎

##  7\. Tropically convex consensus methods

In this section, we focus on applications to phylogenetics—the study of
evolutionary history of species [17, 37]. The information is represented as an
evolutionary tree, or phylogeny, which are trees whose leaves are labeled by
the name of the species. In this paper, we will deal only with trees that
encode the evolution from a common ancestor and possess a molecular clock.

To be more formal, we have a finite set ${\mathsf{X}}$ containing the names of
the species and a rooted tree whose leaves are in bijection with
${\mathsf{X}}$; the root corresponds to the most recent ancestor of all the
species into consideration. The time is represented as positive weights on the
edges, which gives a way to measure distances between nodes in the trees. What
is more we assume that the distance from the root to any leaf is the same; it
means that the same time is measured from the evolution of the most recent
common ancestor (MRCA) of all species and any element of ${\mathsf{X}}$. Such
trees are called _equidistant_.

To a rooted phylogeny $T$ we associate a distance matrix
$D\in{\mathbb{R}}^{{\mathsf{X}}\times{\mathsf{X}}}$ where the entry $D_{ij}$
represents the distance between the leaves labelled $i$ and $j$ in $T$. It is
known that $T$ is equidistant if and only if $D$ is ultrametric [37, Theorem
7.2.5], i.e.

(5) $D_{ij}\leq\max(D_{ik},D_{kj})\quad\forall\,i,j,k\in{\mathsf{X}}.$

Hence, we will not distinguish between equidistant trees and ultrametric
matrices in the rest of the paper.

Because $D$ is symmetric and has zero entries on the diagonal, we can see it
as a point of ${\mathbb{R}}^{\binom{{\mathsf{X}}}{2}}$. We define the _tree
space_ ${\mathcal{T}}_{\mathsf{X}}$ as the image of space of all ultrametrics
in ${\mathbb{R}}^{\binom{{\mathsf{X}}}{2}}/{\mathbb{R}}{\mathbf{1}}$. Due to
[2, Proposition 3], this is homeomorphic to the BHV space defined in [7]. We
note that the ultrametric condition (5) implies that
${\mathcal{T}}_{\mathsf{X}}$ is $\max$-tropically convex.

We are interested in _consensus methods_ : given as input multiple phylogenies
on ${\mathsf{X}}$, find an evolutionary tree on ${\mathsf{X}}$ being as
similar as possible to the input trees. This is a common problem in
evolutionary biology, as multiple distinct trees arise from the statistical
procedures or from the multiple methods to reconstruct phylogenies from
different data; see [9] or [17, Chapter 30] for details.

A consensus method can be seen as a location statistic in the tree space.
Since the latter is $\max$-tropically convex, there were many attempts to
exploit this geometric structure to obtain relevant information [12, 27, 28,
34]. We are interested in tropically convex consensus methods, defined in
[12].

######  Definition 32.

A consensus method $c$ is _tropically convex_ if
$c(T_{1},\dots,T_{m})\in\operatorname{tconv}^{\max}(T_{1},\dots,T_{m})$ for
every $m\geq 1$ and $T_{1},\dots,T_{m}\in{\mathcal{T}}_{\mathsf{X}}$.

The location problems discussed in the previous section give rise to
tropically convex consensus methods. Note that we do not need to impose the
restriction that the optimum to lie in ${\mathcal{T}}_{\mathsf{X}}$. It is
automatically satisfied from the tropical convexity of
${\mathcal{T}}_{\mathsf{X}}$ and Theorem 20. This observation ensured that
tropical median consensus methods are fast to compute [12, §5.3].

Tropically convex consensus methods are particularly interesting because they
preserve relationships from the input trees. To explain this more clearly, we
firstly need some terminology: two subsets of taxa $A,B$ form a _nesting_ in
$T$, and we denote it by $A<B$, if the MRCA of $A$ in $T$ is a strict
descendant of the MRCA of $A\cup B$. If $D$ is the ultrametric associated to
$T$, then we can write the condition as

(6) $\max_{i,j\in A}D_{ij}<\max_{k,\ell\in A\cup B}D_{k\ell}.$

We say that a consensus method $c$ is _Pareto on nestings_ if
$c(T_{1},\dots,T_{m})$ displays the nesting $A<B$ whenever $A<B$ appears in
all input trees $T_{1},\dots,T_{m}$. The consensus method $c$ is called _co-
Pareto on nestings_ if $c(T_{1},\dots,T_{m})$ does not display the nesting
$A<B$ unless $A<B$ appears in some input tree $T_{i}$. These conditions are
desirable for consensus methods [9, 42].

######  Remark 33.

It is useful to see these properties from a geometric point of view. Consider
${\mathcal{T}}_{\mathsf{X}}(A<B)$ the subset of ${\mathcal{T}}_{\mathsf{X}}$
consisting of trees displaying the nesting $A<B$; it is described by (6). We
also make the notation ${\mathcal{T}}_{\mathsf{X}}(A\not<B)$ for the
complement
${{\mathcal{T}}_{\mathsf{X}}\setminus{\mathcal{T}}_{\mathsf{X}}({A<B})}$,
which is the set of trees not displaying $A<B$.

Then $c$ is Pareto on nestings if and only if for every nesting $A<B$ and
trees $T_{1},\dots,T_{m}\in{\mathcal{T}}_{\mathsf{X}}(A<B)$ we have
$c(T_{1},\dots,T_{m})\in{\mathcal{T}}_{\mathsf{X}}(A<B)$. We also note that
$c$ is co-Pareto on nestings if and only if for every nesting $A<B$ and trees
$T_{1},\dots,T_{m}\in{\mathcal{T}}_{\mathsf{X}}(A\not<B)$ we have
$c(T_{1},\dots,T_{m})\in{\mathcal{T}}_{\mathsf{X}}(A\not<B)$.

The next result shows that tropically convex consensus methods have both
Pareto and co-Pareto properties, being an improved version of [12, Proposition
22]. Thus, we have a large class of consensus methods satisfying both
properties. This is remarkable, as no such consensus method is listed in the
surveys [9, 42].

######  Proposition 34.

Tropically convex consensus methods are Pareto and co-Pareto on nestings.

###### Proof.

For every nesting $A<B$, the set ${\mathcal{T}}_{\mathsf{X}}(A<B)$ is
$\max$-tropically convex as (6) describes an open $\max$-tropical halfspace.
Whence, Remark 33 implies that tropically convex consensus methods are Pareto
on nestings.

Similarly, the set ${\mathcal{T}}_{\mathsf{X}}(A\not<B)$ is $\max$-tropically
convex as it is the intersection of ${\mathcal{T}}_{\mathsf{X}}$ with the
tropical halfspace defined by the inequality $\max_{i,j\in
A}D_{ij}\geq\max_{k,\ell\in A\cup B}D_{k\ell}$. Remark 33 implies also the co-
Pareto property. ∎

The Pareto property gives a unanimity rule: nestings present in all the trees
are also present in the consensus. One may wonder if this rule can be relaxed
as there exist (super)majority-rule consensus trees commonly used for the
unweighted case; they are denoted $M_{\ell}$ by Felsenstein in [17, Chapter
30]. Indeed, one can find such a rule for tropical medians [12].

######  Proposition 35.

A nesting appears in the tropical median consensus tree if it appears in a
proportion of the input trees greater than $1-1/\binom{n}{2}$. Moreover, a
nesting will not appear in the tropical median consensus tree if it occurs in
a proportion less than $1/\binom{n}{2}$ of the input trees.

###### Proof.

The tropical median corresponds to the Fermat–Weber problem whose gauge
distance is given by the regular simplex. Therefore, the essential hull of a
finite set $A$ defined in [13] coincides with the $\max$-tropical convex hull
of $A$. Then the conclusion follows from [13, Proposition 5.6] and Remark 33,
as in the proof of Proposition 34. ∎

######  Remark 36.

Note that a consensus method is not well-defined when there are multiple
minimum points. Most problematic is the situation when different tree
topologies are possible, when it is unclear how to resolve incompatible
optimum trees. Yet, this is not the case when the set of optimal locations is
convex [11, Proposition 6]: separating the tree space in cones of trees having
a tree topology gives rise to a convexly disjoint collection in the sense of
[21, Definition 1.15].

Nonetheless, the aforementioned proposition applies when the set of all optima
in ${\mathbb{R}}^{\binom{n}{2}}/{\mathbb{R}}{\mathbf{1}}$ is contained in
${\mathcal{T}}_{\mathsf{X}}$; guaranteed for strictly $\triangle$-star-
quasiconvex dissimilarities. Otherwise, one might still have problems in
defining consistently a consensus method; see [12, Example 24] for the
symmetric tropical Fermat–Weber problem. For this reason, one has to consider
the regularized versions discussed in §5.2.

##  8\. Conclusion and future perspectives

We provided a large class of location estimators whose value lies in the
$\max$-tropical convex hull of the input with the purpose of obtaining
consensus methods with good properties. The first direction would be to obtain
methods to obtain the optima efficiently. On the other hand, searching for
extra properties of specific location problems could be helpful for
applications; more details are provided below.

###  8.1. Comparison to consensus methods based on the BHV distance

We have exploited tropical convexity to obtain consensus methods with good
properties. More precisely, we focused on (co-)Pareto properties that can be
interpreted in a purely geometric way. The associated spaces are also
$\max$-tropically convex so the aforesaid properties are immediate for the
tropical approach.

Although the BHV geometry of the tree space is more studied than its tropical
counterpart, there are few consensus methods proposed for this geometry. A
first proposal was given in the pioneering paper by Billera, Holmes, and
Vogtmann [7], but a few drawbacks were already pointed out: e.g., doubling
every input tree changes the output. An approach based on Fréchet means was
proposed by Miller et al. [31] and Bačák [5]. It is also Pareto and co-Pareto
on splits [31, Lemma 5.1], but the result is more intricate. The same
properties hold for Fermat–Weber and center problems in the BHV space [8,
Chapter 3]. The approach is again analytical, but similar for all the cases.
One could try a geometric approach, as in the tropical case, as it could lead
faster to identification of self-consistent properties for consensus methods.

###  8.2. Majority rules in consensus methods

Proposition 35 provides a supermajority rule for tropical median consensus
with respect to nestings. This can be a step towards understanding the
relationship between median weighted trees and the widely used majority-rule
consensus for unweigthed trees. In fact, the majority-rule consensus can be
interpreted as a median [30], but it is unclear if this can be extended to
weighted phylogenies.

However, Proposition 35 provides a large threshold for a majority rule in the
case of tropical median consensus trees, indicating that they are quite
conservative. This seems to be owing to the low breakdown point of the
tropical median caused by asymmetry; check [13] for more details. Therefore,
an investigation of location estimators with higher breakdown point could
provide a better connection to the majority-rule consensus.

###  8.3. Compositional data

A different application of our location estimators could be to compositional
data [35]. That is, the data can be seen as points in a simplex; our methods
would be applied to the centered logratio transform of the input. Note that
$\triangle$-star-quasiconvex sets are defined with respect to special
directions, which correspond to the vertices of the simplex.

What is more, the motivation of Tokuyama and Nakano in studying algorithms for
transportation problem came from splitting the points from a simplex in
multiple regions [39]. Moreover, Nielsen and Sun analyzed clustering methods
with the symmetric tropical distance on compositional data showing a better
performance than other more commonly used dissimilarity measures [33]. These
results suggest that $\triangle$-star-quasiconvex dissimilarities could be
useful in compositional data analysis.

### Acknowledgments

I am indebted to Michael Joswig for discussing different aspects of this
paper. I thank Günter Rote for bringing [3] to my attention. The author was
supported by “Facets of Complexity” (GRK 2434, project-ID 385256563).

## References

  * [1] Marianne Akian, Stéphane Gaubert, Yang Qi and Omar Saadi  “Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria”  In _SIAM J. Discrete Math._ 37.2, 2023, pp. 632–674  DOI: 10.1137/21M1428297
  * [2] Federico Ardila and Caroline J. Klivans  “The Bergman complex of a matroid and phylogenetic trees”  In _J. Comb. Theory, Ser. B_ 96.1, 2006, pp. 38–49  DOI: 10.1016/j.jctb.2005.06.004
  * [3] F. Aurenhammer, F. Hoffmann and B. Aronov  “Minkowski-type theorems and least-squares clustering”  In _Algorithmica_ 20.1, 1998, pp. 61–76  DOI: 10.1007/PL00009187
  * [4] Mordecai Avriel, Walter E. Diewert, Siegfried Schaible and Israel Zang  “Generalized concavity” 63, Classics Appl. Math.  Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM), 2010  DOI: 10.1137/1.9780898719437
  * [5] Miroslav Bačák  “Computing medians and means in Hadamard spaces”  In _SIAM J. Optim._ 24.3, 2014, pp. 1542–1566  DOI: 10.1137/140953393
  * [6] F. L. Bauer, J. Stoer and C. Witzgall  “Absolute and monotonic norms”  In _Numer. Math._ 3, 1961, pp. 257–264  DOI: 10.1007/BF01386026
  * [7] Louis J. Billera, Susan P. Holmes and Karen Vogtmann  “Geometry of the space of phylogenetic trees”  In _Adv. Appl. Math._ 27.4, 2001, pp. 733–767  DOI: 10.1006/aama.2001.0759
  * [8] Marco Botte  “Facility location in the phylogenetic tree space”  Göttingen: Univ. Göttingen (Diss.), 2019  URL: d-nb.info/1182033555/34
  * [9] David Bryant  “A classification of consensus methods for phylogenetics”  In _Bioconsensus (Piscataway, NJ, 2000/2001)_ 61, DIMACS Ser. Discrete Math. Theoret. Comput. Sci.  Amer. Math. Soc., Providence, RI, 2003, pp. 163–183
  * [10] Guy Cohen, Stéphane Gaubert and Jean-Pierre Quadrat  “Duality and separation theorems in idempotent semimodules.”  In _Linear Algebra Appl._ 379, 2004, pp. 395–422  DOI: 10.1016/j.laa.2003.08.010
  * [11] Andrei Comăneci and Michael Joswig  “Parametric Fermat–Weber and tropical supertrees”, 2022  arXiv:2211.06328 [math.CO]
  * [12] Andrei Comăneci and Michael Joswig  “Tropical medians by transportation”  In _Math. Program._ , 2023  DOI: 10.1007/s10107-023-01996-8
  * [13] Andrei Comăneci and Frank Plastria  “Breakdown points of Fermat–Weber problems under gauge distances”, 2023  arXiv:2306.13424 [math.MG]
  * [14] Roland Durier  “Convex hull properties in location theory”  In _Numer. Funct. Anal. Optim._ 15.5-6, 1994, pp. 567–582  DOI: 10.1080/01630569408816581
  * [15] Roland Durier  “Optimal locations and inner products”  In _J. Math. Anal. Appl._ 207.1, 1997, pp. 220–239  DOI: 10.1006/jmaa.1997.5287
  * [16] Roland Durier and Christian Michelot  “Geometrical properties of the Fermat-Weber problem”  In _Eur. J. Oper. Res._ 20, 1985, pp. 332–343  DOI: 10.1016/0377-2217(85)90006-2
  * [17] Joseph Felsenstein  “Inferring phylogenies”  Sinauer Associates, 2003
  * [18] Maurice Fréchet  “Les éléments aléatoires de nature quelconque dans un espace distancie”  In _Ann. Inst. Henri Poincaré_ 10, 1948, pp. 215–310
  * [19] María Teresa Gallegos and Gunter Ritter  “Using combinatorial optimization in model-based trimmed clustering with cardinality constraints”  In _Comput. Stat. Data Anal._ 54.3, 2010, pp. 637–654  DOI: 10.1016/j.csda.2009.08.023
  * [20] A. L. Garkavi  “On the Čebyšev center and convex hull of a set”  In _Uspehi Mat. Nauk_ 19.6 (120), 1964, pp. 139–145
  * [21] Paul Hacking, Sean Keel and Jenia Tevelev  “Stable pair, tropical, and log canonical compactifications of moduli spaces of del Pezzo surfaces”  In _Invent. Math._ 178.1, 2009, pp. 173–227  DOI: 10.1007/s00222-009-0199-1
  * [22] Simon Hampe  “Tropical linear spaces and tropical convexity”  In _Electron. J. Comb._ 22.4, 2015, pp. research paper p4.43, 20  URL: www.combinatorics.org/ojs/index.php/eljc/article/view/v22i4p43
  * [23] Peter J. Huber  “Robust statistics”, Wiley Ser. Probab. Math. Stat.  John Wiley & Sons, Hoboken, NJ, 1981  DOI: 10.1002/0471725250
  * [24] Michael Joswig  “Essentials of tropical combinatorics” 219, Grad. Stud. Math.  Providence, RI: American Mathematical Society (AMS), 2021  DOI: 10.1090/gsm/219
  * [25] Victor Klee  “Circumspheres and inner products”  In _Math. Scand._ 8, 1960, pp. 363–370  DOI: 10.7146/math.scand.a-10618
  * [26] “Location science”  Cham: Springer, 2019  DOI: 10.1007/978-3-030-32177-2
  * [27] Bo Lin, Bernd Sturmfels, Xiaoxian Tang and Ruriko Yoshida  “Convexity in tree spaces”  In _SIAM J. Discrete Math._ 31.3, 2017, pp. 2015–2038  DOI: 10.1137/16M1079841
  * [28] Bo Lin and Ruriko Yoshida  “Tropical Fermat-Weber points”  In _SIAM J. Discrete Math._ 32.2, 2018, pp. 1229–1245  DOI: 10.1137/16M1071122
  * [29] Ye Luo  “Idempotent Analysis, Tropical Convexity and Reduced Divisors”, 2018  arXiv:1808.01987 [math.CO]
  * [30] T. Margush and F. R. McMorris  “Consensus n-trees”  In _Bull. Math. Biol._ 43, 1981, pp. 239–244
  * [31] Ezra Miller, Megan Owen and J. Scott Provan  “Polyhedral computational geometry for averaging metric phylogenetic trees”  In _Adv. Appl. Math._ 68, 2015, pp. 51–91  DOI: 10.1016/j.aam.2015.04.002
  * [32] Stefan Nickel and Justo Puerto  “Location theory. A unified approach”  Berlin: Springer, 2005  DOI: 10.1007/3-540-27640-8
  * [33] Frank Nielsen and Ke Sun  “Clustering in Hilbert’s projective geometry: the case studies of the probability simplex and the elliptope of correlation matrices”  In _Geometric structures of information. Proceedings of the conference on geometric science of information, GSI 2017_ Cham: Springer, 2019, pp. 297–331  DOI: 10.1007/978-3-030-02520-5˙11
  * [34] Robert Page, Ruriko Yoshida and Leon Zhang  “Tropical principal component analysis on the space of phylogenetic trees”  In _Bioinformatics_ 36.17, 2020, pp. 4590–4598  DOI: 10.1093/bioinformatics/btaa564
  * [35] Vera Pawlowsky-Glahn, Juan José Egozcue and Raimon Tolosana-Delgado  “Modeling and analysis of compositional data”, Statistics in Practice  John Wiley & Sons, Ltd., Chichester, 2015
  * [36] R. Tyrrell Rockafellar  “Convex analysis”  Princeton University Press, 1970
  * [37] Charles Semple and Mike Steel  “Phylogenetics” 24, Oxford Lecture Series in Mathematics and its Applications  Oxford University Press, Oxford, 2003
  * [38] Shai Shalev-Shwartz  “Online learning and online convex optimization”  In _Found. Trends Mach. Learn._ 4.2, 2011, pp. 107–194  DOI: 10.1561/2200000018
  * [39] Takeshi Tokuyama and Jun Nakano  “Efficient algorithms for the Hitchcock transportation problem”  In _SIAM J. Comput._ 24.3, 1995, pp. 563–578  DOI: 10.1137/S0097539792236729
  * [40] Amos Tversky  “Features of Similarity”  In _Psychological Review_ 84.4, 1977, pp. 327–352  DOI: 10.1037/0033-295x.84.4.327
  * [41] Richard E. Wendell and Arthur P. Hurter  “Location theory, dominance, and convexity” Mathematical programming and its applications  In _Operations Res._ 21, 1973, pp. 314–320  DOI: 10.1287/opre.21.1.314
  * [42] Mark Wilkinson, James A. Cotton, François-Joseph Lapointe and Davide Pisani  “Properties of supertree methods in the consensus setting”  In _Systematic Biology_ 56.2, 2007, pp. 330–337  DOI: 10.1080/10635150701245370
  * [43] Ruriko Yoshida, Leon Zhang and Xu Zhang  “Tropical principal component analysis and its application to phylogenetics”  In _Bull. Math. Biol._ 81.2, 2019, pp. 568–597  DOI: 10.1007/s11538-018-0493-4

## Appendix A: Convex analysis on ${\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$

We state and proof a slightly more general form of Proposition 28 and then we
put an Euclidean structure on ${\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$ to
show how we can obtain a quantitative result for the regularized version of
the tropical Fermat–Weber problem.

### The proof of Proposition 28

We will prove the result in a finite-dimensional real vector space $X$. We
will equip it with an inner product $\langle\cdot,\cdot\rangle$ which gives an
isomorphism $X^{*}\cong X$. In this way, we can see the subgradients of a
convex function as elements of $X$. We recall that the subdifferential of a
convex function $f:X\to{\mathbb{R}}$ at a point $x$ is the set

$\partial f(x)=\left\\{c\in X:f(y)-f(x)\geq\langle c,y-x\rangle\ \forall y\in
X\right\\}.$

It will be used to characterize the minima of $f$ through the first-order
minimality condition: $x$ is a minimum of $f$ if and only if
${\mathbf{0}}\in\partial f(x)$. We refer to the book by Rockafellar [36] for
more details on convex analysis.

We are interested in optima of regularized versions of $f$ of the form
$f+\lambda h$ with $h$ having linear growth. More specifically, we care of $h$
being _Lipschitz continuous_ , i.e. there exists a constant $L>0$ such that
$|h(x)-h(y)|\leq L\|x-y\|$ for every $x,y\in X$, where $\|\cdot\|$ is any norm
on $X$.111We assumed that $X$ is finite-dimensional, so every two norms are
equivalent. Thus, the definition does not depend on the specific norm.
Nevertheless, the constant $L$ depends on $\|\cdot\|$.

As a last definition, we say that $h$ is polyhedral convex if it is the
maximum of finitely many affine functions on $X$. Now we can state and proof a
slight generalization of Proposition 28.

######  Proposition 37.

Let $h:X\to{\mathbb{R}}$ be a polyhedral convex function and
$f:X\to{\mathbb{R}}$ convex and Lipschitz continuous. Then there exists a
constant $\lambda_{0}>0$ such that the minima of $h+\lambda f$ are also the
minima of $h$ for every $\lambda\in(0,\lambda_{0})$.

###### Proof.

Consider an arbitrary minimum $m_{\lambda}$ of $h+\lambda f$. The first-order
optimality condition entails ${\mathbf{0}}\in\partial
h(m_{\lambda})+\lambda\partial f(m_{\lambda})$. What is more, since $f$ is
Lipschitz continuous, [38, Lemma 2.6] yields the existence of a bounded set
$B$ such that ${\partial f(x)\subset B}$ for all $x\in X$.

If ${\mathbf{0}}\notin\partial h(x)$, then ${\mathbf{0}}\notin\partial
h(x)+\lambda B$ for $\lambda$ sufficiently small, as $\partial h(x)$ is
closed. We also know that there are finitely many values for $\partial h(x)$,
as we assumed $h$ is a polyhedral convex function. Accordingly, there exists
$\lambda_{0}>0$ such that ${\mathbf{0}}\notin\partial h(x)+\lambda B$ for
every $\lambda\in(0,\lambda_{0})$. The last relation implies that
${\mathbf{0}}\in\partial h(m_{\lambda})$ if $\lambda<\lambda_{0}$, which is
equivalent to $m_{\lambda}$ being a minimum of $h$. ∎

######  Remark 38.

If we know the bounded set $B$ from the proof of Proposition 37, then we can
set $\lambda_{0}=\sup\\{\lambda>0:{\mathbf{0}}\notin P+\lambda B,\ \forall
P\in{\mathcal{P}}\\}$ where ${\mathcal{P}}$ is the set of all possible values
of $\partial h(x)$ such that ${\mathbf{0}}\notin\partial h(x)$. The infimum is
positive, as $\mathcal{P}$ is a finite collection of closed convex sets.

If $h$ is a gauge $\gamma$, then [38, Lemma 2.6] says that we can set
$B=\\{x\in X:{\gamma^{\circ}(x)\leq r}\\}=:rB_{\gamma^{\circ}}$ for some $r>0$
where $\gamma^{\circ}(y):=\sup_{x:\gamma(x)\leq 1}\langle x,y\rangle$ is the
dual gauge. Hence, $P+\lambda B$ represents the set of points at distance at
most $\lambda r$ from $P$ measured by the distance $d_{\gamma^{\circ}}$
induced from $\gamma^{\circ}$, i.e.
$d_{\gamma^{\circ}}(x,y)=\gamma^{\circ}(y-x)$. Consequently, we have
$\lambda_{0}=\inf_{P\in{\mathcal{P}}}d_{\gamma^{\circ}}(P,{\mathbf{0}})/r$.

### Euclidean structure on ${\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$

We just conclude with explaining how we can put a Euclidean structure on
${\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$ in a natural way. The idea is to
identify the tropical projective torus with a hyperplane of ${\mathbb{R}}^{n}$
with the regular Euclidean structure. Using this idea, by factoring with
${\mathbb{R}}{\mathbf{1}}$, one can identify
${\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}$ with the orthogonal subspace to
${\mathbf{1}}$, which is
${\mathcal{H}}=\\{x\in{\mathbb{R}}:x_{1}+\dots+x_{n}=0\\}$. This
identification is natural as we obtain the same subdifferentials of a convex
function $f:{\mathbb{R}}^{n}/{\mathbb{R}}{\mathbf{1}}\to{\mathbb{R}}$ as in
the case when we consider it as a function on ${\mathbb{R}}^{n}$ such that
$f(x+\lambda{\mathbf{1}})=f(x)$ for each $x\in{\mathbb{R}}^{n}$ and
$\lambda\in{\mathbb{R}}$.

Having fixed this structure, we search for $\lambda_{0}$ as in Proposition 37
for $h(x)=\sum_{i}\gamma_{\infty}({x-v_{i}})$ and $f(x)=\gamma_{1}(x-v)$ where
$v\in\operatorname{tconv}^{\max}(v_{1},\dots,v_{m})$. This is, we want
quantitative results for regularizations of tropical Fermat–Weber problems.

In this case, the subdifferentials of $h$ are integer polytopes in
${\mathcal{H}}$. Moreover, one can check that the dual gauge of $\gamma_{1}$
has the expression $\gamma_{1}^{\circ}(x)=\gamma_{1}(-x)/n$ which takes
integer values at each point of ${\mathcal{H}}\cap{\mathbb{Z}}^{n}$.
Consequently,
$\lambda_{0}=\inf_{P\in{\mathcal{P}}}d_{\gamma_{1}^{\circ}}(P,{\mathbf{0}})\geq
1$ as it is a positive integer. Whence, the minima of $h+\lambda f$ are also
minima of $h$ for every $\lambda\in(0,1)$.