精读笔记

Problem Setting

这篇论文实际解决的是优化算法比较中的“最终解质量不可见”问题。传统 performance profile 问的是谁更快，data profile 问的是在给定精度下谁用更少预算，但在非凸局部优化、heuristic/exact solver 混合比较、或 derivative-free 场景中，solver 往往并不收敛到同一个解。此时只比较 CPU time、iteration、function evaluations 甚至是不公平的，因为快到一个更差局部点和慢到一个更好局部点不是同一类行为。

真正困难点是：objective value 不是天然可比的。不同 problem 的 scale、offset、符号、初始点、已知最优值缺失都会破坏直接比较。performance profile 若直接把 final objective value 当作 performance measure，会遇到负值、零值、接近零值导致 ratio 不稳定的问题。accuracy profile 又通常需要 fixed-cost setting 或预设精度阈值，且对不同预算 solver 容易有偏。

关键矛盾是：benchmarking 需要一个压缩的大图形化总结，但 solution quality 本身依赖 problem-specific reference、solver set、test set composition。本文的目标不是消除这种依赖，而是把它显式化、规范化，并让读者能在同一张 profile 中看到质量-覆盖率关系。

Motivation

已有路线不够的根本原因是它们默认主要性能维度是 computational burden。对于许多 smooth optimization benchmark，这个假设只有在 solver 找到可比较解时才成立；一旦 solver 收敛到不同局部点，效率比较就可能失去语义。derivative-free 场景虽然有 data profiles，但它们以给定 accuracy level 下的预算为横轴，不能直接回答固定预算后哪类 solver 更可能达到更好 objective value。

作者的核心观察是：solution quality 应该作为与 efficiency 并列的 profiling 维度，而不是在实验表格中附带报告。尤其在 exact methods 与 heuristics 同台比较时，最终 objective value 的排序经常比运行时间更能解释 solver 行为。

另一个动机是 test set 本身的可靠性。优化 benchmarking 中常见做法是默认 CUTEst 或某个 benchmark suite 足够代表，但算法相对排名可能高度依赖实例组成。本文试图补上一个 ex post diagnostic：不是问 solver 是否 robust，而是问这个 test set 对当前 solver family 的结论是否稳定。

Core Idea

核心思想很直接：对每个 problem p，取一个参考 objective value f_L^(p)，通常是所有 solver 在该 problem 上找到的最好值；再用初始点 objective value f^(p)(x0)-f_L^(p) 作为 scale。solver s 的最终值若满足 f_s^(p)(x*)-f_L^(p) <= tau [f^(p)(x0)-f_L^(p)]，则认为它在阈值 tau 下达到了相应质量。扫描 tau in [0,1]，统计满足条件的问题比例，就得到 quality profile。

这个建模方式改变的是横轴语义：从“花了多少资源”变成“离参考质量还有多近”。它引入的 inductive bias 是相对改善而不是绝对 objective value，也就是说每个 problem 的难度和 scale 被初始差距归一化，最终曲线表达的是 solver 在 test set 上达到不同质量等级的覆盖率。

与 prior 的本质区别在于：performance/data profiles 把预算或效率作为主信号，quality profiles 把 final objective quality 作为主信号。它不是更一般的 profile，而是把 benchmarking 的信息流重新组织为 quality threshold -> solved fraction。test set profiles 则进一步把 test set perturbation -> profile variance 作为诊断信号，把 benchmark suite 的稳定性变成可视化对象。

Method

第一，reference normalization 解决 objective value 不可比的问题。直接比较 f_s^(p)(x*) 没有意义，因为不同 problem 的 scale、offset、符号都不同；用 f_s-f_L 除以 f(x0)-f_L 后，比较变成“相对初始差距消除了多少”。这也是 quality profile 能跨 problem 聚合的必要条件。

第二，weak quality profile 保留初始点作为参照，回答 solver 从共同 starting point 出发取得了多少相对进展。strong quality profile 用 solver set 中最差 final value 替代初始值，更强调 solver 之间的相互差距。前者更适合一般 benchmark，后者更适合 solver 最终值接近、需要放大相对差异的场景。

第三，tau 扫描把单点 ranking 变成曲线。tau=0 近似表示达到当前最佳参考值的问题比例；tau 接近 1 则反映失败率或低精度覆盖。曲线位置越高，表示在该质量阈值下覆盖的问题越多。这个机制避免了单一阈值排名的脆弱性。

第四，r1/r2 是可视化缩放机制。r1 调整横轴上低 tau 或高 tau 区域的分辨率，r2 调整纵轴可分辨性。它们不改变点对点排序，但会改变可读性和面积解释。严格说这不是新的 benchmarking principle，而是 profile visualization 的工程增强。

第五，test set profiles 使用 bootstrap resampling 生成多个扰动 test sets，重复计算 quality profiles，并对每个 tau 估计方差。它解决的问题不是 solver quality，而是 benchmark conclusion stability：如果重采样后曲线波动大，说明当前 test set 对该 solver 的质量判断不稳。

Key Insight / Why It Works

最核心的有效性来自一个简单但强的归一化：用每个 problem 的初始差距 f(x0)-f_L 作为单位，把 heterogeneous objective landscapes 压到同一尺度上。这样 profile 的每个点都有明确解释：在多少比例的问题上，solver 把初始 optimality gap 的剩余比例压到 tau 以下。这个解释比直接 objective ranking、ratio of final values 或 runtime ranking 都更稳定。

真正的贡献不是公式复杂，而是把“最终解质量”从表格中的附属指标提升为 profile 的主轴。对于非凸局部优化，这一点很关键：不同 solver 找到不同 basin 时，速度不是第一问题，最终 objective value 才是对用户有意义的比较对象。

r1/r2 的作用更像 visualization/scaling，而不是理论贡献。它们能让曲线在高精度区间更可读，但并不增加信息，只是重新分配视觉分辨率。若后续用 area under quality profile 作为 scalar ranking，r1/r2 会变成实质权重选择，这时“只是可视化参数”的说法就不够严谨。

test set profiles 的 insight 是值得迁移的：benchmark 不应只输出 solver ranking，还应输出 ranking 对 test set perturbation 的敏感性。这里的 bootstrap 不是新统计方法，核心新意是把 profile 的方差当作 test set adequacy 的诊断对象。这个想法比具体公式更重要。

需要直接指出：默认 f_L=min_s f_s 会带来 solver-set dependence。新增一个强 solver 会改变所有人的 reference，删除一个 solver 也可能改变曲线。因此它并不天然 paradox-free，也不完全独立于 benchmark design。方法有效的前提是读者接受这种相对比较语义，而不是把 profile 当成绝对 solver quality。

Relation To Prior Work

最接近的是 Dolan-More performance profiles、More-Wild data profiles、accuracy profiles，以及 EAF/AOCC 一类 attainment-function 视角。本文属于 profiling-based benchmarking 工具谱系，不属于新优化算法，也不是 axiomatic ranking framework。

与 performance profiles 的本质差异是 measure 的方向反了：performance profile 比较达到目标所需资源，quality profile 比较给定最终结果下达到的质量覆盖。performance profiles 对 solver-set 的 best performance 有依赖，且不适合直接把 objective value 当 ratio；quality profiles 则专门处理 final objective value，但同样可能依赖 reference construction。

与 data profiles 的差异是信息组织方式。data profile 固定精度，看预算增长下 solved fraction；quality profile 可固定预算，看精度阈值变化下 solved fraction。在 derivative-free optimization 中二者尤其互补：前者回答“达到某精度要多少函数评估”，后者回答“给定预算后质量分布如何”。

与 accuracy profiles 的关系最近。二者都关注 solution quality 和相对精度，但本文强调无需预设离散阈值、可以连续扫描 tau，并通过 r1/semilog 在任意精度范围放大观察。这里的新意更多是 profile construction 和 visualization generalization，而不是全新的统计原则。

与 Liu et al. 的 paradox-free comparison 路线不同，本文不是从公理出发定义比较规则，而是构造一个实用 profile。作者也承认默认 weak/strong reference 可能不满足 paradox-free 条件。实质创新是质量维度的 profile 化和 test set stability 的 profile 化，而不是解决所有 ranking paradox。

Dataset / Evaluation

实验覆盖了两个合理场景：大规模 smooth unconstrained CUTEst problems，以及 derivative-free optimization 中较小到中等维度的 CUTEst selection。前者展示了 quality profiles 能区分经典 solver 和不同 negative-curvature strategies 的最终 objective quality；后者展示了在不同 function-evaluation budgets 下，model-based 与 pattern/simplex search 方法在质量区间上的行为差异。

这些实验支持的 claim 是有限但清楚的：quality profiles 确实能提供 performance/data profiles 不直接呈现的解质量视角，并且在 solver 曲线接近时，缩放参数能改善可读性。它们没有证明 quality profiles 是更“正确”的 ranking 方法，也没有证明 test set profiles 能判定 benchmark 的真实代表性。

benchmark 主要是 CUTEst 和已有 DFO test selections，属于标准离线数值优化实验。没有真实 deployment，也不需要真机系统实验。评价更偏工具展示，而非统计显著性严格验证。test set profiles 的实验使用随机生成数据和 bootstrap 说明概念，缺少在真实 benchmark suite 上系统展示“发现不可靠 test set”的案例，这是证据链中较弱的一环。

Limitation

最重要限制是 reference value f_L 的语义不稳。若 f_L 来自 solver set 内最优结果，那么 profile 是相对当前比较集合定义的；加入或删除 solver 会改变其他 solver 的曲线。这意味着质量 profile 不是绝对指标，也不能直接跨论文或跨 solver set 比较。

第二，方法依赖共同 starting point 和 f(x0) >= f_s(x*) >= f_L 这类隐含前提。若 solver 使用不同 initialization、多 start、随机重启、不同 feasibility restoration，或问题含约束且可行性质量与 objective quality 冲突，当前定义需要额外规则。文中未充分说明这些实际 benchmarking 细节。

第三，r1/r2 被定位为缩放参数，但它们可能影响研究者的判断。尤其是用曲线下面积做 scalar ranking 时，r1 实际上决定了强调低精度还是高精度区间。这里的增益部分来自 visualization/scaling，不是新的可证比较能力。

第四，test set profiles 只能评估对经验 test set 重采样的稳定性，不能评估真实问题分布覆盖。bootstrap 方差低只说明当前集合内部扰动下结论稳定，不说明 test set representative。若原始 test set 有系统性偏置，bootstrap 不会自动暴露。

第五，方法把 benchmarking 难点从“怎么比较 solver”部分转移到“怎么选 reference、怎么选 test set、怎么解释 profile 区间”。这不是缺陷，但需要明确：quality profiles 是诊断工具，不是最终裁判。

Takeaway

• 第一，solution quality 应该被 profile 化，而不是只作为表格末列。
• 对非凸优化和 heuristic/exact solver 混合比较，这比单纯 runtime profile 更接近用户真正关心的问题。
• 第二，相对初始 gap 的归一化是可迁移 insight。
• 很多 benchmark 中，只要任务结果有 scale/offset 问题，都可以考虑用“相对初始状态到 reference 的进展比例”来构造跨实例可比曲线。

一句话总结

这篇论文在优化算法 benchmarking 谱系中补上了“最终解质量 profile”和“test set 稳定性 profile”两个实用诊断工具，实质贡献是重新组织比较信号而不是提出新的优化或排名理论。