Jorge Moré
Derivative-Free Optimization Solvers: A Shootout

Mathematics and Computer Science Division
Argonne National Laboratory
9700 S Cass Ave
Argonne
Illinois 60439-4844
more@mcs.anl.gov
Stefan Wild

Derivative-Free Optimization Solvers: A Shootout

Jorge J. Moré¹and Stefan M. Wild²

Derivative-free optimization has experienced a renewed interest over the past decade that has encouraged a new wave of theory and algorithms. While this research includes computational experiments that compare and explore the properties of these algorithms, most of these experiments do not provide useful information for users of derivative-free algorithms with computationally expensive problems. In our experience, these users want solvers that deliver the most reduction in function value within a given computational budget.

We explore benchmarking procedures for derivative-free optimization algorithms when there is a limited computational budget. The focus of our work is the unconstrained optimization problem

$$\min \left \{ f(x) : x \in \mbox{${\mathbb{R}}$}^n \right \} ,$$

where $f :$   $\mbox{${\mathbb{R}}$}$$^n \to$   $\mbox{${\mathbb{R}}$}$ may be noisy or non-differentiable and, in particular, in the case where the evaluation of $f$ is computationally expensive. These expensive optimization problems arise in science and engineering because evaluation of the function $f$ often requires a complex deterministic simulation based on solving the equations (for example, nonlinear eigenvalue problems, ordinary or partial differential equations) that describe the underlying physical phenomena. The computational noise associated with these complex simulations means that obtaining derivatives is difficult and unreliable. Moreover, these simulations often rely on legacy or proprietary codes and hence must be treated as black-box functions, necessitating a derivative-free optimization algorithm.

Several comparisons have been made of derivative-free algorithms on noisy optimization problems that arise in applications. In particular, we mention [2,3,4,6,7]. The most ambitious work in this direction [2] is a comparison of six derivative-free optimization algorithms on two variations of a groundwater problem specified by a simulator. This work compares algorithms by their trajectories (plot of the best function value against the number of evaluations) until the solver satisfies a convergence test based on the resolution of the simulator.

Benchmarking derivative-free algorithms on selected applications with trajectory plots provides useful information to users with related applications. In particular, users can find the solver that delivers the largest reduction within a given computational budget. However, the conclusions in these computational studies do not readily extend to other applications.

We use data [5] and performance profiles [1] to analyze the performance of six derivative-free solvers on benchmark sets of smooth, noisy, and piecewise-smooth problems. We use performance measures that evaluate the progress of the algorithm in terms of the function value, and thus avoid unrealistic convergence tests. We consider geometry-based solvers (APPSPACK, for example) and model-based solvers (NEWUOA, for example). Our results show that on these problems, model-based solvers performs better than geometry-based solvers, even for noisy and piecewise-smooth problems.

Our results also show that data and performance profiles provide complementary information that measures the strengths and weaknesses of optimization solvers as a function of the computational budget. Data profiles are useful, in particular, to assess the short-term behavior of the algorithms.