Benchmarking Optimization Algorithms with Quality Profiles and Test Set Profiles

Abstract

We propose a couple of novel tools for benchmarking optimization algorithms which possibly converge to different solutions on a test set: the quality profiles and the test set profiles. Their aim is to assess and compare algorithms in terms of quality (i.e. value of the objective function) of the obtained solutions, as well as to assess the consistency of the test set. A key distinguishing feature of the quality profiles we propose is its comparative deterministic procedure that emphasizes the accuracy of the solution, rather than the computational burden of solvers. In this regard, several test set--dependent approaches for both comparing and ranking algorithms have already been proposed in the literature, representing widely used benchmarking procedures. We believe that the joint use of such procedures, along with the novel quality profiles detailed here, should enhance the benchmarking process, in all those cases where the comparison encompasses exact methods as well as heuristics. Moreover, the literature on numerical optimization seems to have paid less attention, in the last decade, to determining how appropriate a test set used for benchmarking the selected solvers may be. This motivates the introduction of test set profiles, which assess the appropriateness of a test set and represent the flip side of evaluating the robustness of the solvers on that test set. This paper also includes extensive numerical experiments, showing the usefulness of quality profiles in both smooth and nonsmooth (derivative--free) optimization, along with the reference to a MATLAB code for plotting quality profiles and test set profiles.