Benchmarking Optimization Algorithms with Quality Profiles and Test Set Profiles

Technical Summary: Benchmarking Optimization Algorithms with Quality Profiles and Test Set Profiles

Problem Statement
Benchmarking optimization algorithms presents a significant challenge, particularly when comparing solvers that may converge to different solution points on a test set. Existing benchmarking tools, such as performance profiles (Dolan and Moré) and data profiles (Moré and Wild), primarily focus on efficiency (computational effort) and reliability (success rates). While performance profiles are standard for measuring convergence effort (e.g., CPU time, iterations), they often exclude problems where solvers converge to different solutions to ensure a fair comparison of computational burden. Consequently, there is a lack of tools specifically designed to assess and compare the quality (accuracy) of the final objective function values obtained by different solvers, especially in scenarios where exact methods and heuristics are compared, or where solvers converge to distinct local minima. Furthermore, the literature has paid limited attention to quantitatively assessing the appropriateness and consistency of the test set itself regarding the solvers being benchmarked.

Methodology
The authors propose two novel graphical tools: Quality Profiles and Test Set Profiles.

1. Quality Profiles:

   • Definition: For a set of solvers $S$ and test problems $P$, a quality profile $Q_s(\tau)$ represents the proportion of problems where a solver $s$ achieves a solution within a specific accuracy threshold $\tau$. The accuracy is measured relative to a reference value $f_L^{(p)}$ (typically the best solution found by any solver in the set) and the initial point $x_0^{(p)}$.
   • Core Inequality: The profile is constructed based on the inequality:
     $$f_s^{(p)}(x^*) - f_L^{(p)} \leq \tau [f^{(p)}(x_0^{(p)}) - f_L^{(p)}]$$
     where $\tau \in [0, 1]$.
   • Weak vs. Strong: "Weak" profiles use the initial point $x_0^{(p)}$ in the normalization, while "Strong" profiles use the worst solution found by the solvers.
   • Visualization Enhancements: To address the difficulty of distinguishing closely packed tracks, the authors introduce scaling parameters $r_1$ and $r_2$. These allow for the non-linear compression or expansion of the abscissa (precision) and ordinate (percentage of problems) axes, respectively. This facilitates zooming into specific accuracy ranges (e.g., high precision near $\tau=0$) without discarding data.
   • Properties: The profiles are proven to be invariant under consistent affine transformations of the objective function and are non-decreasing. Unlike performance profiles, they do not require a priori parameter identification that could introduce bias, though they rely on a fixed computational budget (stopping criterion) per solver.

2. Test Set Profiles:

   • Purpose: To assess the robustness of the benchmarking conclusions and the consistency of the test set $P$.
   • Methodology: This tool applies a bootstrapping technique. It repeatedly resamples the test set $P$ (with replacement) to generate multiple subsets $\hat{P}$. Quality profiles are computed for each subset.
   • Output: The variance $\sigma_s^2(\tau)$ of the quality profile values across the bootstrap cycles is plotted against $\tau$. Low variance indicates that the solver's ranking and performance are robust to changes in the test set composition, while high variance suggests that the benchmarking conclusions are sensitive to the specific problems chosen.

Key Contributions

• Novel Benchmarking Tool: The introduction of Quality Profiles provides a deterministic procedure to compare solvers based on solution accuracy rather than computational effort. This allows for the inclusion of problems where solvers converge to different points, which are typically excluded from performance profile comparisons.
• Complementary Nature: The authors position Quality Profiles not as a replacement for performance or data profiles, but as a complementary tool. They fill a gap in the literature by offering a condensed graphical representation of solution quality, particularly useful when comparing exact methods with heuristics.
• Test Set Diagnostics: The introduction of Test Set Profiles offers a quantitative, post-hoc method to evaluate the reliability and discriminative power of a test set, addressing a dimension of benchmarking often overlooked.
• Flexibility in Visualization: The use of scaling parameters ($r_1, r_2$) and semilogarithmic scales allows for detailed analysis of solver performance across different orders of magnitude in accuracy, a feature not easily extendable to standard performance or data profiles.

Results
The paper presents extensive numerical experiments to validate the tools:

• Smooth Optimization:
  • In a comparison of four large-scale unconstrained solvers (L-BFGS, CG+, TRON, CG DESCENT) on 166 CUTEst problems, Quality Profiles revealed that TRON outperformed others in low-to-medium accuracy intervals, while CG+ showed slightly better robustness (fewer failures). The scaling parameters ($r_1 > 1$) were shown to be essential for distinguishing solvers in high-accuracy regions where tracks were otherwise indistinguishable.
  • A second experiment compared Truncated Newton methods with different negative curvature direction strategies. Quality Profiles effectively highlighted that the TN-NC3 strategy (selecting the first negative eigenvalue) was the most effective, confirming theoretical expectations and demonstrating the tool's ability to gauge specific algorithmic features.
• Derivative-Free Optimization:
  • The authors applied Quality Profiles to seven derivative-free solvers (including NEWUOA, Nelder-Mead, and pattern search methods) on 145 problems.
  • The results demonstrated the complementarity with Data Profiles: while Data Profiles show performance vs. computational budget for fixed accuracy, Quality Profiles show performance vs. accuracy for fixed computational budgets.
  • The experiments confirmed that model-based methods (NEWUOA) generally yield higher accuracy than pattern-search methods, even with modest budgets, and that the scaling parameters are crucial for visualizing these differences.
• Test Set Analysis:
  • Using synthetic data and varying the cardinality of the test set ($|P|$), the Test Set Profiles showed that smaller test sets lead to higher variance in solver rankings, confirming the sensitivity of benchmarking to test set composition.

Significance and Claims
The authors claim that Quality Profiles and Test Set Profiles enhance the benchmarking process by providing a more complete picture of solver behavior. Specifically:

• They allow for the comparison of algorithms that converge to different solutions, a scenario where traditional performance profiles are often inadequate or require excluding data.
• They offer a way to assess the "flip side" of solver robustness: the appropriateness of the test set itself.
• The approach is constructive rather than axiomatic; it does not claim to resolve all paradoxes in ranking (such as those discussed by Liu et al.) but provides a practical, data-driven tool for measuring a specific dimension of performance (solution quality).
• The tools are particularly valuable in derivative-free and black-box optimization, where fixed budgets of function evaluations are common, and solution quality is the primary metric of interest.

The paper concludes that these tools should be viewed as part of a broader benchmarking ecosystem, complementing instance-space analysis, sound experimental design, and paradox-free comparison rules, rather than replacing existing methodologies.