Tropical Fréchet means: a polyhedral approach to exact optimization
File(s)
Published version
Author(s)
Ferry, Kamillo
Lin, Bo
Améndola, Carlos
Monod, Anthea
Yoshida, Ruriko
Type
Journal Article
Abstract
The Fréchet mean is a fundamental notion of central tendency defined as a minimizer of a sum of squared distances in a general metric space. In this paper, we study Fréchet means in tropical geometry—a piecewise linear, combinatorial, and polyhedral variant of algebraic geometry—by formulating and solving the associated
tropical quadratic optimization problem. We give a geometric characterization of the collection of all tropical Fréchet means as a bounded set that is simultaneously tropically and classically convex, hence a polytrope. We establish the existence of positivity certificates for maxima of finitely many quadratic polynomials in R[x1,...,xn] whose homogeneous quadratic components are sums of squares, which provides a symbolic framework for exact
optimization. Using this structure, we develop algorithms for computing tropical Fréchet means and the associated Fréchet mean polytrope. We further describe a combinatorial type decomposition of the objective function induced by braid arrangements, yielding a piecewise quadratic representation and a fully symbolic method
for exact computation.
tropical quadratic optimization problem. We give a geometric characterization of the collection of all tropical Fréchet means as a bounded set that is simultaneously tropically and classically convex, hence a polytrope. We establish the existence of positivity certificates for maxima of finitely many quadratic polynomials in R[x1,...,xn] whose homogeneous quadratic components are sums of squares, which provides a symbolic framework for exact
optimization. Using this structure, we develop algorithms for computing tropical Fréchet means and the associated Fréchet mean polytrope. We further describe a combinatorial type decomposition of the objective function induced by braid arrangements, yielding a piecewise quadratic representation and a fully symbolic method
for exact computation.
Date Issued
2026-11-01
Date Acceptance
2026-03-16
Citation
Journal of Symbolic Computation, 2026, 137
ISSN
0747-7171
Publisher
Elsevier BV
Journal / Book Title
Journal of Symbolic Computation
Volume
137
Copyright Statement
©2026 The Author(s). Published by Elsevier Ltd. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
License URL
Publication Status
Published
Article Number
102572
Date Publish Online
2026-03-18