Tropical Fréchet means: a polyhedral approach to exact optimization 中文标题 热带Fréchet均值：一种精确优化的多面体方法

《Journal of Symbolic Computation》：Tropical Fréchet means: a polyhedral approach to exact optimization

　　

Fréchet均值是度量空间中定义为中心趋势基本概念的最小化平方和距离的极小值点。研究人员在本文中研究热带几何（tropical geometry）——代数几何的分段线性、组合和多面体变体——中的Fréchet均值，通过公式化并求解相关的热带二次优化问题。研究人员给出了所有热带Fréchet均值集合的几何刻画，将其表征为同时具有热带凸性和经典凸性的有界集合，因此是一个多面体（polytrope）。研究人员建立了R[x1,…,xn]中有限多个二次多项式的最大值的正性证书的存在性，这些多项式的齐次二次分量是平方和，这为精确优化提供了符号框架。利用这一结构，研究人员开发了计算热带Fréchet均值及相关Fréchet均值多面体（Fréchet mean polytrope）的算法。研究人员进一步描述了由辫子排列（braid arrangements）诱导的目标函数的组合类型分解，产生了分段二次表示和用于精确计算的完全符号方法。

研究背景方面，Fréchet均值作为度量空间中中心趋势的基本定义，是平方和距离的最小化点，在欧氏空间有闭式解，但在一般度量空间定义为优化问题的隐式解且不一定唯一，缺乏光滑性与唯一性使理论与精确计算具挑战性。热带几何以极大代数替代经典运算，形成分段线性多面体几何设定，在系统发生学与代数统计等领域有应用，其计算对应非光滑优化问题且结构具组合性。热带Fréchet目标函数为平方和热带距离之和，每个热带距离为有限多个二次函数的最大值，导致全局目标为指数区域数的分段二次函数，标准光滑优化技术不适用，且经典Fréchet均值算法如Sturm算法因热带射影环面的曲率性质在热带设定中失效。因此需开展热带Fréchet均值的几何表征与精确符号计算研究，以解决非光滑度量空间优化问题。论文发表于《Journal of Symbolic Computation》。

主要关键技术方法包括：热带度量几何与热带凸性理论分析，用于刻画热带射影环面与多面体结构；正性证书理论基于Farkas引理，处理非负齐次分量二次多项式最大值的最优性验证；辫子排列（braid arrangements）的类型分解，将目标函数按腔室划分为分段二次结构；符号算法设计，枚举可行余向量、计算仿射临界点并与组合区域相交；数值实验采用Clarabel.jl与Ipopt求解器对比验证，样本为随机生成维度n∈{5,10,15,20}与样本量m∈{n,2n,3n}的数据集。

研究结果部分，各小节结论如下：

1. 2.
   Tropical metric spaces中，研究人员定义热带射影环面Rⁿ/R1与热带度量d_tr，证明其为良定义度量，热带度量球为多面体，给出矩阵C表示的不等式刻画及Kleene星计算热带顶点。

2.1. The tropical projective torus and the tropical metric中，明确热带数运算⊕为max、⊙为+，等价关系定义商空间，d_tr表示为坐标差的最大减最小，举例验证度量计算。

2.2. Tropical convexity中，区分经典多面体与热带多面体tconv(A)，定义多面体（polytrope）为同时具热带与经典凸性的集合，由矩阵C的不等式Q(C)表示，Kleene星C^?关联热带与经典描述，Theorem 5表明热带线段为至多n-1段普通线段，Corollary 6给出伪顶点计算时间O(n³log n)。

1. 3.
   Defining tropical Fréchet means中，Definition 8定义有限点集P的热带Fréchet均值为最小化∑d_tr²(x?,p^(ν))的点，Lemma 9证明确存在性，Lemma 10证平方热带距离对凸组合满足凸性不等式，Theorem 11证明所有Fréchet均值到各样本点的热带距离为常数d_ν。

3.1. The Fréchet mean polytrope中，Definition 12定义Fréchet均值多面体（FM polytrope）P￣，Theorem 13证明其为有界多面体，等于各点为中心d_ν为半径的热带球B_tr(p^(ν),d_ν)的交集。

3.2. Case study: two points中，Proposition 15证明两点间热带测地线中点为Fréchet均值，反之亦然，关联热带线段Γ_x,y^tr与中点定义。

1. 4.
   Computing tropical Fréchet means中，提出先计算单Fréchet均值再求交集的三步法，Proposition 16给出面描述计算时间O(mn²)、热带顶点O(mn²+n³)、经典顶点O(mn²+n³log n)。

4.1. Exact quadratic optimization中，将问题转化为带约束二次规划，Theorem 18证明具非负二次齐次分量的二次多项式最大值存在非负权重下界证书，例Example 17展示3点最小平方和186的证书计算，指出Sturm算法因曲率失效如Example 19的负曲率三角形收敛错误。

4.2. Reduced gradient algorithm中，基于目标函数分段二次凸性设计贪婪Algorithm 1，Remark 20说明有理输入保留有理坐标，收敛率亚线性。

1. 5.
   A type decomposition for the objective function中，Definition 22定义辫子排列B_n与平移B_n(p)，腔室对应余向量（covector），Definition 24定义点相对于点的类型type(x,p)为最大化差的指标对，Lemma 26证同腔室类型相同，Proposition 27推广至有限集S，Example 28展示4点类型分解与临界点交腔室得FM polytrope为线段，Example 29展示临界点在腔室外时用拉格朗日乘子得边界最优，Algorithm 2枚举余向量计算FM polytrope，Lemma 30算类型O(mn³)，Lemma 31腔内最小值O(2ⁿ)，Theorem 32总复杂度O(2^mn2+n·(mn³))。
2. 6.
   Numerical experiments中，用Clarabel.jl与Ipopt计算，Example 33中3点数值解误差约10^?5，精确解和为182/25=7.28，证书验证顶点为Fréchet均值；随机数据实验维度n=5,10,15,20与样本量m=n,2n,3n，平均运行时间随维度与样本量增长，实现发布于Zenodo。

讨论部分总结：研究人员表征热带Fréchet均值集合为经典与热带凸多面体，证正性证书存在性，提出精确计算算法并数值测试。未来方向包括FM polytrope维数预测与唯一性准则、ε误差下的ε-增厚热带球交集、q-Fréchet均值（q≠1,2）的凸性与推广、样本点条件致FM polytrope正维数的梯度分析。研究将热带Fréchet均值问题纳入精确二次优化与多面体符号框架，关联热带几何与度量代数几何（metric algebraic geometry），为分段线性几何的度量优化提供组合符号范式。

研究结论翻译：在本文中，研究人员研究了热带射影环面下热带度量中Fréchet均值计算的优化问题。热带Fréchet均值通常不唯一；研究人员将所有热带Fréchet均值的集合刻画为经典与热带凸多面体，并证明了热带Fréchet均值计算的正非负证书的存在性。研究人员研究了热带Fréchet均值与热带Fréchet均值多面体的精确计算；提出并实现计算热带Fréchet均值的算法并进行了数值测试。研究人员还提出一种局部方法，将热带Fréchet均值的优化问题分解为大量小型线性问题。尽管具组合需求，该方法适用于能产生精确解的计算机代数系统。这也作为热带几何与度量代数几何（metric algebraic geometry）关联的起点。未来工作可能的方向包括研究样本点使FM polytrope为正维数的条件。如Example 28所示，该问题与目标函数分片梯度恒为零相关联。总之，本文表明热带Fréchet均值问题容许完全符号与多面体公式化，其中解集合的几何与目标函数的结构均可组合描述。研究人员的工作将热带Fréchet均值置于精确二次优化问题于多面体空间的更广泛背景中，并提出了用符号方法处理热带与其他分段线性几何中度量优化问题的一般范式。