Dolan-Moré performance profiles

In order to compare different solvers, we employ the Dolan-Moré performance profile plot.

Let us briefly introduce the Dolan-Moré performance profile plot.

Let $P$ be a finite set of problems used as benchmarks and $S$ be a set of solvers we want to compare to one another.

Let $t_{p,s}$ be the cost (e.g., runtime or flops) to solve a problem $p$ using a solver $s$ .

We define the ration between $t_{p,s}$ and the lowest observed cost to solve this problem using some solver $s\in S$ :

$\begin{eqnarray*} r_{p,s} = \frac{t_{p,s}}{\min_{s \in S} t_{p,s}}. \end{eqnarray*}$

If a solver $s$ does not solve a problem $p$ , then we assign to $r_{p,s}$ a very high value $r_M > r_{p,s}$ for all other $p,s$ .

The cumulative distribution of the performance ratio is the Dolan-Moré performance profile plot.

In particular, define

$\begin{eqnarray*} \rho_s(\tau) = \frac{1}{n_p}\#\{p\in P: r_{p,s}\leq \tau\}, \end{eqnarray*}$

for $\tau\geq 1$ and where $n_p$ is the number of problems.

The Dolan-Moré performance profile is the plot of $\rho_s$ vs $\tau$ , typically on a logarithmic x-axis.

Benchmark results

Benchmarking parameters

In all benchmark results presented below we set the tolerance to $10^{-4}$ .

The maximum number of iterations was set to a very high value above which we may confidently tell the problem is unlikely to be solved (e.g., $10^6$ ).

Given that different algorithms (SCS, SuperSCS using Broyden directions and SuperSCS using Anderson's acceleration) have a different per-iteration cost, we allow every algorithm to run for a give time (see max_time_milliseconds).

After that maximum time has passed, if the algorithm has not converged we consider that it has failed to solve the problem.

In Broyden's method we deactivated the K0 steps.