Tropical Fréchet Means: a polyhedral approach to exact optimization

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 $\mathbb{R}[x_1,\dots ,x_n]$ 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.