Derivative-Free Algorithms for Nonlinear Optimisation Problems

Background

Optimisation – that is, finding local maxima or minima of an ‘objective’ function – is one of the most common numerical tasks encountered in academia and industry. Almost all numerical methods for solving optimisation problems require the ability to compute derivatives of the objective function – these are used to determine both directions in which we expect the function to increase or decrease, and when to terminate the method. However, when the objective has stochastic noise or is expensive to compute, we may be unable to calculate or estimate derivatives.

Derivative-Free Optimisation (DFO) is the area of optimisation devoted to the development of algorithms which do not require any derivative information. Interest in DFO has been growing over the last 15-20 years. NAG, a British technology company, sells mathematical software via the NAG Library, and wishes to improve their current offering of DFO methods.

The aim of this project is to develop new DFO techniques in order to improve the performance of DFO for problems with stochastic noise, and large-scale problems.

Progress

We are primarily working on improving on existing DFO algorithms for nonlinear least-squares minimisation (where the objective function is a sum of squares of nonlinear functions). These problems are very common, and there are many applications where the objective is noisy or expensive, such as: data assimilation for weather and climate forecasting and parameter estimation for complex physical models.

We are using a new framework for building internal approximations of the objective, which improves on existing methods (typically based on polynomial interpolation) in two key ways. Firstly, it uses simpler approximations, similar to the classical Gauss-Newton method, which speeds up the algorithm substantially without sacrificing performance [1]. Secondy, we use multiple restarts and sample averaging to help the method make progress through noisy landscapes [2]. 

For example, in Figure 1, we compare our new method (black/blue) against other state-of-the-art methods. We show the proportion of test problems solved for a given number of objective evaluations when we have added stochastic noise to the objective. Our method performs similarly for small computational budgets, but is much more robust, ultimately solving a greater proportion of the problems as the computational budget increases.

Figure 1: Comparison of two variants of our new method (DFO-LS in black and blue) to other state-of-the-art DFO solvers for least-squares problems (DFBOLS and DFO-GN).

Future Work

Future work will focus on improving these methods for high-dimensional problems by using techniques from approximation theory and derivative-based optimisation. 

Publications

[1] Coralia Cartis and Lindon Roberts. A Derivative-Free Gauss-Newton Method. arXiv preprint arXiv:1710.11005 (2017).

[2] Coralia Cartis, Jan Fiala, Benjamin Marteau and Lindon Roberts. Improving the Flexibility and Robustness of Model-Based Derivative-Free Optimization Solvers. arXiv preprint arXiv:1804.00154 (2018).