Tim Mitchell

betaRMP

betaRMP is an open-source benchmarking visualization tool written in Matlab for creating β-Relative Minimization Profiles (β-RMPs), which are plots for concisely comparing optimization methods evaluated on large heterogenous sets of test problems. β-RMPs are designed to highlight the interplay and trade-offs between the following three pertinent performance attributes:

Like performance profiles and data profiles, β-RMPs can also be used in other contexts outside of optimization, such as assessing numerical accuracy of solvers under different computational budget limits.

A note about heterogenous test sets

In general, we assume that the difficulty of each test problem varies somewhat proportionally with the computational cost to solve it. Note that test problems of different types, such as linear versus non-linear, should not necessarily be grouped together in a single test set.

How Relative Minimization Profiles work

Each solver in a comparison has what is called its RMP curve. A point (a,b) on a given solver's RMP curve indicates that, for b% of the test problems, the solver was able to find feasible solutions such that the best (lowest) objective values attained at these feasible points were either equal to given per-problem target values or, at worst, were only higher by at most a relative difference of 10a.

Sample β-RMPs for β equal to 1, 5, 10, and infinity, where the fixed per-problem computational budgets are defined as the costs to run Method 3 for each test problem. Note that for this particular set of β-RMPs, the target values are not fixed across plots; the target values are defined as the best values that are attainable within the given computational budgets determined by each value of β.

Per-problem target values, if known a priori, can be supplied by the user but, by default, target values are automatically extracted from the collected benchmarking data itself. In general, each per-problem target value is defined as the best (lowest) objective value known to be achievable at a feasible point, which is determined by taking the best feasible solution encountered over all the methods being compared. Feasibility is generally defined in terms of a tolerance (particularly for equality constraints, since it is unrealistic to expect them to be perfectly satisfied).

To do a comparison of methods with respect to computational budgets, we generalize the concept of the aforementioned RMP curve to a so called β-RMP curve. When β is infinity, a β-RMP curve is equivalent to the RMP curve described above, that is, the solvers are judged without any imposed per-problem computational budgets. However, when β is less than infinity, a solver's β-RMP curve is defined only in terms of the iterates that the solver was able to reach within certain per-problem budgets, specifically β times a fixed set of per-problem computational budgets.

Like the target values, the fixed per-problem computational budgets can be explicitly supplied by the user if desired. However, as the difficulty of each problem in the test set may vary significantly and it can be difficult to predict to appropriate budgets, by default, the per-problem budgets are automatically determined from the collected benchmarking data itself. The set of observed costs for running each method on a given problem can be used to estimate an appropriate budget for that problem. These fixed per-problem budget estimates can be constructed in various ways, depending on what aspect one wishes to highlight in an β-RMP benchmark; see the betaRMP documentation for more info.

For more details and discussion on β-RMPs, such as their motivation and exact definition, we refer the interested reader to the paper mentioned below.

How to install and use betaRMP

  1. Download the latest version of betaRMP on GitLab (v1.0).
  2. The only installation task is to add the desired location of the extracted betaRMP folder to the search path in Matlab.
  3. To recreate the β-RMP benchmark shown above, run the following commands and run the following commands: cd your_betaRMP_install_directory
    load('betaRMP_sample_data.mat');
    betaRMP(sample_data.method_data,sample_data.opts);
  4. To read the betaRMP documentation on how to properly collect and format new benchmark data and learn how the various betaRMP options can be used, enter: help betaRMP
  5. To create any RMP benchmark, a "history of iterates" is required for every problem, for all methods in the comparison. For each problem method pair, one needs to record the following data for every iterate of the given method:

    • the value of the objective (whether it be a minimization goal, a stationarity measure, etc)
    • the value(s) of the constraint and/or violation functions (assuming the problem has constraints; if not, this data is not required).

  6. To create a β-RMP benchmark, where computational budgets are also considered, the cumulative cost (elapsed wall-clock time, number of gradient evaluations, etc) to obtain each iterate for every problem method pair must also be collected.

    Note if this cost data cannot be collected, it may be okay to estimate it (though one must proceed with caution). For example, if elapsed wall-clock time is the cost metric and all the methods typically take many iterations before terminating, then it may then be adequate to simply record the total elapsed time and the number of iterations incurred for every problem method pair and use the average elapsed time per iterate to construct an approximation to the actual cumulative cost data.

Citing

If you publish work that either refers to or makes use of β-RMPs, please cite the following paper:

When referring to this software, please also include which version was used, e.g. betaRMP v1.0. Note that betaRMP, in monospaced font, refers to the command/routine, not the name of the software package.

License

betaRMP is licensed under the GNU Affero General Public License, version 3.