Benchmarking Optimization Algorithms with Quality Profiles and Test Set Profiles

技术摘要：利用质量剖面图与测试集剖面图对优化算法进行基准测试

问题陈述
对优化算法进行基准测试是一项具有挑战性的任务，特别是当比较的求解器在测试集上可能收敛到不同的解点时。现有的基准测试工具，如性能剖面图（Dolan and Moré）和数据剖面图（Moré and Wild），主要关注效率（计算量）和可靠性（成功率）。虽然性能剖面图是衡量收敛努力程度（如 CPU 时间、迭代次数）的标准方法，但为了确保计算负担比较的公平性，它们通常会排除那些求解器收敛到不同解的问题。因此，目前缺乏专门用于评估和比较最终目标函数值“质量”（精度）的工具，特别是在将精确方法与启发式方法进行比较，或者当求解器收敛到不同的局部极小值时。此外，文献对于定量评估测试集本身相对于被基准测试算法的适当性和一致性的关注也相对有限。

方法论
作者提出了两种新型图形化工具：质量剖面图（Quality Profiles）和测试集剖面图（Test Set Profiles）。

1. 质量剖面图：

   • 定义： 对于一组求解器 $S$ 和测试问题 $P$，质量剖面 $Q_s(\tau)$ 表示求解器 $s$ 在特定精度阈值 $\tau$ 内达到解的比例。精度的衡量是相对于参考值 $f_L^{(p)}$（通常是集合中任何求解器找到的最佳解）和初始点 $x_0^{(p)}$。
   • 核心不等式： 该剖面基于以下不等式构建：
     $$f_s^{(p)}(x^*) - f_L^{(p)} \leq \tau [f^{(p)}(x_0^{(p)}) - f_L^{(p)}]$$
     其中 $\tau \in [0, 1]$。
   • 弱与强： “弱”剖面在归一化中使用初始点 $x_0^{(p)}$，而“强”剖面则使用求解器找到的最差解。
   • 可视化增强： 为了解决难以区分密集排列轨迹的问题，作者引入了缩放参数 $r_1$ 和 $r_2$。这些参数允许对横轴（精度）和纵轴（百分比）进行非线性压缩或扩张。这有助于在不丢弃数据的情况下，对特定的精度范围（例如 $\tau=0$ 附近的高精度区域）进行缩放观察。
   • 属性： 证明了这些剖面对目标函数的任何一致仿射变换都是不变的，并且是单调不减的。与性能剖面图不同，它们不需要预先进行可能引入偏差的参数识别，尽管它们依赖于每个求解器的固定计算预算（停止准则）。

2. 测试集剖面图：

   • 目的： 评估基准测试结论的稳健性以及测试集 $P$ 的一致性。
   • 方法论： 该工具应用了自助法（bootstrapping）技术。通过对测试集 $P$ 进行重复抽样（有放回抽样）来生成多个子集 $\hat{P}$。随后计算每个子集的质量剖面图。
   • 输出： 将各个自助循环中质量剖面值的方差 $\sigma_s^2(\tau)$ 绘制在 $\tau$ 轴上。低方差表明求解器的排名和性能对于测试集的组成变化是稳健的；高方差则表明基准测试的结论对所选问题的特定性较为敏感。

核心贡献

• 新型基准测试工具： 质量剖面的引入提供了一种基于解的精度而非计算努力程度来比较求解器的确定性程序。这使得包含那些在性能剖面图中通常会被排除的、收敛到不同解的问题成为可能。
• 互补性质： 作者将质量剖面定位为性能剖面图或数据剖面图的补充工具，而非替代品。它们填补了文献中的空白，提供了解质量的浓缩图形表示，在比较精确方法与启发式方法时尤为有用。
• 测试集诊断： 测试集剖面的引入提供了一种定量、事后的方法来评估测试集的可靠性和判别能力，解决了基准测试中经常被忽视的一个维度。
• 可视化的灵活性： 使用缩放参数（$r_1, r_2$）和半对数尺度，可以实现对不同数量级精度的详细分析，这是标准性能剖面或数据剖面难以实现的特性。

实验结果
论文通过广泛的数值实验验证了这些工具：

• 光滑优化：
  • 在对 166 个 CUTEst 问题上的四种大规模无约束求解器（L-BFGS, CG+, TRON, CG DESCENT）的比较中，质量剖面显示 TRON 在低到中等精度区间表现优于其他求解器，而 CG+ 则表现出稍好的稳健性（失败次数更少）。实验证明，缩放参数（$r_1 > 1$）对于区分在其他情况下难以辨别的轨迹至定的高精度区域至关重要。
  • 第二个实验比较了采用不同负曲率方向策略的截断牛顿法（Truncated Newton methods）。质量剖面有效地凸显了 TN-NC3 策略（选择第一个负特征值）是最有效的，证实了理论预期，并展示了该工具衡量特定算法特征的能力。
• 无导数优化：
  • 作者将质量剖面应用于 145 个问题上的七种无导数求解器（包括 NEWUOA、Nelder-Mead 和模式搜索方法）。
  • 结果证明了其与数据剖面的互补性：数据剖面展示的是固定精度下的性能随计算预算的变化，而质量剖面展示的是固定计算预算下的性能随精度的变化。
  • 实验确认，即使在适度预算下，基于模型的模型（如 NEWUOA）通常也能产生比模式搜索方法更高的精度，且缩放参数对于可视化这些差异至关重要。
• 测试集分析：
  • 通过使用合成数据并改变测试集的大小（$|P|$），测试集剖面显示较小的测试集会导致求解器排名的方差增大，从而证实了基准测试对测试集组成的敏感性。

意义与主张
作者声称，质量剖面图和测试集剖面图通过提供更完整的求解器行为图景，增强了基准测试过程。具体而言：

• 它们允许比较收敛到不同解的算法，而在这种场景下，传统的性能剖面图往往力不从心或需要剔除数据。
• 它们提供了一种评估求解器稳健性的“另一面”的方法：即测试集本身的适当性。
• 该方法是建设性的而非公理化的；它并不声称解决了所有关于排序的悖论（例如 Liu 等人讨论的悖论），而是提供了一个测量特定性能维度（解质量）的实用、数据驱动的工具。
• 这些工具在无导数优化和黑盒优化领域特别有价值，因为在这些领域，固定函数评价次数的计算预算非常普遍，且解质量是核心关注的指标。

论文总结道，这些工具应被视为更广泛基准测试生态系统的一部分，作为实例空间分析、严谨实验设计和无悖论比较规则的补充，而非取代现有的方法论。