Adaptive Metrics for Norm-Minimization-Based Outer Approximation in Convex Vector Optimization

技术摘要：凸向量优化中基于范数最小化的外逼近自适应度量

问题陈述
本文研究了有界凸向量优化问题（CVOPs）中上像 $P := \Gamma(X) + C$ 的逼近问题，其中 $X$ 是紧凸集，$\Gamma$ 是连续 $C$-凸映射，$C$ 是闭、实心、点状多面体锥。目标是构造 $P$ 的多面体外逼近，并保证豪斯多夫距离下的误差界限。虽然由范数最小化标量化驱动的外逼近算法已被证明具有有限终止性和收敛速率，但关于这些速率对标量化范数选择的依赖性仍存在空白。具体而言，Ararat 等人 [4] 之前的工作证明了标准欧几里得（$\ell_2$）范数具有改进的收敛速率 $O(k^{2/(1-q)})$，而任意范数的通用速率为 $O(k^{1/(1-q)})$。目前尚不清楚这种改进是欧几里得结构的特例，还是更一般的希尔伯特几何性质的体现，以及动态调整度量是否能进一步提升性能。

方法论
本文通过以下三种主要机制建立了理论框架并提出了一种自适应算法以解决上述问题：

1. 线性等距与不变性：作者证明，任何内积范数 $\|y\|_M = \sqrt{y^\top M y}$（其中 $M \succ 0$）均可通过线性变换 $T = M^{1/2}$ 与欧几里得范数等距。他们证明了基于范数最小化的外逼近算法在该变换下具有不变性。因此，算法在任意内积空间中的行为等价于其在欧几里得空间中针对变换后问题的行为。这使得收敛性分析可以从欧几里得情形推广到任意内积范数。

2. 自适应度量框架：作者提出了一种算法，其中标量化范数在每次迭代 $k$ 时根据切割法向量的历史进行变化。具体而言，度量 $M_k$ 被构造为归一化切割法向量外积的正则化平均值：$M_k = \varepsilon_0 I + \frac{1}{k} \sum_{i=1}^k u_i u_i^\top$。虽然标量化使用该自适应度量 $M_k$，但逼近误差的测量和停止准则的强制执行仍使用固定的欧几里得范数。

3. 弥散定理：为确保自适应度量保持良好条件（即条件数不爆炸），本文引入了“弥散”条件。该条件要求切割法向量序列在目标空间中充分分散。作者证明，如果上像截面的有效前沿是曲率有界的严格凸超曲面（假设 3），则切割法向量会自然弥散。这一几何性质保证了法向量经验协方差矩阵的最小特征值保持远离零，从而确保自适应度量在整个执行过程中保持良好条件。

主要贡献
本文做出了五项 distinct 贡献：

• 收敛速率的扩展：证明了先前仅针对欧几里得范数已知的改进收敛速率 $O(k^{2/(1-q)})$ 可扩展至所有内积范数。这是通过利用内积空间与欧几里得空间之间的线性等距实现的，表明该速率取决于希尔伯特几何而非特定的欧几里得结构。
• 显式收敛界限：作者推导了原始坐标下的显式收敛界限，量化了内积矩阵 $M$ 的谱性质如何影响误差估计中的常数。
• 自适应度量收敛性：建立了自适应度量变体的正确性及欧几里得收敛性。在自适应度量具有均匀谱界限的条件下，他们提供了显式界限，表明更好的度量条件（更好的弥散）会导致更锐利的收敛常数。
• 弥散定理：核心理论结果（定理 15）提供了充分的几何条件（有效前沿的严格凸性及有界曲率），在此条件下自适应度量保持良好条件。这填补了固定范数理论与实际观察（即适应问题几何可加速收敛）之间的空白。
• 数值验证：本文在三个测试问题（包括球体和椭球可行集）上进行了数值实验，验证了理论速率并展示了自适应方法的实际有效性。

结果

• 理论速率：实验证实了固定内积范数的理论速率 $O(k^{2/(1-q)})$。对于自适应度量，虽然理论保证是通用速率 $O(k^{1/(1-q)})$（定理 18），但实证结果显示了一致的性能提升。
• 迭代节省：在具有弯曲帕累托前沿的问题（示例 1 和 2）上，与固定欧几里得范数相比，自适应度量方法将达到特定容差所需的迭代次数减少了 31–33%。
• 度量条件：实验在经验上验证了弥散条件。经验协方差矩阵 $\Sigma_k$ 的最小特征值保持远离零（例如 $\approx 0.15$），且度量质量参数 $\theta_k$ 稳定在 $[0.41, 0.54]$ 范围内，证实度量始终保持良好条件。
• 高维策略：对于 $q \ge 4$ 的维度，全顶点枚举在计算上不可行，本文评估了"LP 探测”和“混合”策略。在测试的高维情况（$q=4$）中，结合 LP 探测策略的自适应度量实现了最快的收敛（最少的迭代次数）。
• 局限性：在一个具有抛物线帕累托前沿且迭代次数极少的问题（示例 3）中，自适应度量未提供加速，这归因于数据积累不足，导致适应机制无法有效发挥作用。

意义与主张
本文声称基于范数最小化的凸向量优化中，为使用几何感知和自适应内积度量提供了严谨的基础。其主要意义在于：

1. 阐明几何起源：证明了改进的收敛指数是希尔伯特几何（内积空间）的性质，而非特定的欧几里得范数，从而解决了理论上的模糊性。
2. 论证自适应的合理性：首次为此类自适应度量选择提供了严谨的论证，证明在自然几何条件（严格凸性）下，算法能够自我修正以维持良好条件的度量，从而避免收敛常数的退化。
3. 实际效率：结果表明，对于具有弯曲帕累托前沿的问题，根据切割历史调整标量化度量可以显著减少计算工作量（迭代次数），而不会显著增加每次迭代的成本。

作者对自适应度量本身的收敛速率保持谦逊；虽然他们观察到了迭代次数的节省，但指出证明自适应情形下改进的 $O(k^{2/(1-q)})$ 速率仍然是一个未解决的问题，因为当度量在每次迭代都发生变化时，标准的等距论证失效。他们还指出，当前的理论依赖于严格凸性和全顶点枚举，将其直接应用范围限制在非光滑边界和近似顶点查找策略上。