Exact Uniform L1 Spacing for Solow-Polasky Diversity on Lines and Ordered Pareto Fronts

技术摘要：Solow–Polasky 多样性在线性及有序 Pareto 前沿上的精确均匀 L1 间距

问题陈述
本文针对特定度量结构上的固定基数 Solow–Polasky 多样性度量（等价于指数核的有限度量幅值）的最大化问题。给定度量空间 $(X, d)$、尺度参数 $\beta > 0$ 和整数 $k$，目标是选择一个大小为 $k$ 的子集 $S \subset X$，使其最大化多样性 $D_\beta(S) = \mathbf{1}^\top Z_S^{-1} \mathbf{1}$，其中 $Z_S$ 是指数相似性矩阵，其元素为 $e^{-\beta d(x_i, x_j)}$。虽然这通常是一个组合优化问题，但作者聚焦于一维有序结构及其等距等价结构，具体包括实数线区间 $[0, 1]$ 和有序 $\ell_1$（曼哈顿）曲线，例如单调双目标 Pareto 前沿。

方法论与理论框架
分析通过利用域的有序结构，将多样性目标分解为连续间隙的函数之和来进行。

1. 线公式推导：对于点 $0 \le x_1 < \dots < x_k \le 1$，其连续间隙为 $\delta_i = x_{i+1} - x_i$，作者利用了幅值理论（Leinster 和 Willerton）及 Solow–Polasky 文献中的已知结果。多样性目标简化为：
   $$D_\beta(S) = 1 + \sum_{i=1}^{k-1} \tanh\left(\frac{\beta \delta_i}{2}\right)$$
   这一简化将矩阵求逆问题转化为受限于 $\sum \delta_i \le 1$ 的间隙分配问题。

2. 基于 Jensen 不等式的优化：函数 $f(t) = \tanh(\beta t / 2)$ 被识别为在 $(0, \infty)$ 上严格递增且严格凹。作者将这些间隙贡献之和应用 Jensen 不等式。由于间隙之和受限于区间长度（1），当且仅当所有间隙相等（$\delta_i = 1/(k-1)$）时，最大值被唯一地达到。

3. 核特征（逆命题）：为了确立指数核对此行为的必要性，作者证明了一个逆命题。他们表明，在归一化的非增距离核中，要求基线校正后的超额多样性（$D_\beta(S) - 1$）对任意三点集的相邻间隙具有可加性，这迫使核属于指数族 $K(t) = e^{-\beta t}$。

4. 到 $\ell_1$ 曲线的等距转移：本文将这些结果扩展到 $\mathbb{R}^m$ 中的有序 $\ell_1$ 曲线。通过定义一个标量坐标 $\phi(t)$ 表示沿曲线累积的 $\ell_1$ 长度，作者证明了此类曲线与实数区间等距。因此，均匀间距定理直接转移：最优子集是那些在累积 $\ell_1$ 长度上均匀分布的点。

主要结果

• 定理 1（区间上的均匀间距）：对于任意 $k \ge 2$ 和 $\beta > 0$，最大化 Solow–Polasky 多样性的 $[0, 1]$ 的唯一子集是等间距集合 $S^\star_k = \{0, \frac{1}{k-1}, \dots, 1\}$。最大多样性值为 $1 + (k-1)\tanh\left(\frac{\beta}{2(k-1)}\right)$。
• 命题 1（指数核的唯一性）：超额多样性在相邻间隙中具有可加性的性质，在归一化非增核中唯一地刻画了指数核族。
• 定理 2（曲线上的均匀 $\ell_1$ 间距）：对于总长度为 $L$ 的连续有序 $\ell_1$ 曲线，最大化 $k$ 点子集由在累积 $\ell_1$ 距离上均匀分布的点组成。
• 推论 1（Pareto 前沿）：对于连续双目标 Pareto 前沿，其中目标函数是单调的（一个非递减，一个非递增），该前沿在 $\ell_1$ 度量下与直线等距。因此，Solow–Polasky 多样性的最优有限近似由在目标值累积变化中均匀分布的点组成。

在有限候选集上的应用
本文承认，对于离散候选集（连续前沿的有限近似），精确的均匀间距可能无法实现。然而，等距性将问题简化为从直线上的有限有序集中选择子集。作者指出，这种特定的有序情况允许使用多项式时间的动态规划算法（参考文献 [1]）来寻找精确的最优子集，这与一般度量空间中的 NP 难子集选择问题区分开来。文中提供了两个数值示例：

1. 一个具有 70 个候选项的密集连通前沿（$f_2 = 1 - f_1^2$），其中最优的 10 点子集紧密近似于连续均匀间距。
2. 一个具有 100 个候选项的不连通 ZDT3 前沿，其中算法选择的点既尊重了不连通结构，又在诱导的 $\ell_1$ 坐标中保持了近均匀间距。

意义与主张
本文声称为有序一维度量结构上的 Solow–Polasky 多样性提供了一种“精确且透明的间距原则”。其主要贡献是严格证明了在指数核下，连续固定基数的最优解恰好由均匀连续距离刻画，而不仅仅是在非正式意义上“分布良好”。

作者将这项工作定位为对多目标优化中先前观察的理论澄清，在这些观察中，Solow–Polasky 指标被注意到倾向于网格状或均匀配置。通过建立有序 Pareto 前沿与线区间之间的等距性，本文为使用目标空间变化的累积均匀间距作为连续 Pareto 前沿的表示策略提供了数学依据。该工作还划定了可处理的有序情况（可通过动态规划求解）与一般 NP 难子集选择问题之间的界限。