Overview
When to use Py-BOBYQA
Py-BOBYQA is designed to solve the nonlinear least-squares minimization problem (with optional bound constraints)
We call \(f(x)\) the objective function.
Py-BOBYQA is a derivative-free optimization algorithm, which means it does not require the user to provide the derivatives of \(f(x)\), nor does it attempt to estimate them internally (by using finite differencing, for instance).
There are two main situations when using a derivative-free algorithm (such as Py-BOBYQA) is preferable to a derivative-based algorithm (which is the vast majority of least-squares solvers).
If the residuals are noisy, then calculating or even estimating their derivatives may be impossible (or at least very inaccurate). By noisy, we mean that if we evaluate \(f(x)\) multiple times at the same value of \(x\), we get different results. This may happen when a Monte Carlo simulation is used, for instance, or \(f(x)\) involves performing a physical experiment.
If the residuals are expensive to evaluate, then estimating derivatives (which requires \(n\) evaluations of \(f(x)\) for every point of interest \(x\)) may be prohibitively expensive. Derivative-free methods are designed to solve the problem with the fewest number of evaluations of the objective as possible.
However, if you have provide (or a solver can estimate) derivatives of \(f(x)\), then it is probably a good idea to use one of the many derivative-based solvers (such as one from the SciPy library).
Details of the Py-BOBYQA Algorithm
Py-BOBYQA is a type of trust-region method, a common category of optimization algorithms for nonconvex problems. Given a current estimate of the solution \(x_k\), we compute a model which approximates the objective \(m_k(s)\approx f(x_k+s)\) (for small steps \(s\)), and maintain a value \(\Delta_k>0\) (called the trust region radius) which measures the size of \(s\) for which the approximation is good.
At each step, we compute a trial step \(s_k\) designed to make our approximation \(m_k(s)\) small (this task is called the trust region subproblem). We evaluate the objective at this new point, and if this provided a good decrease in the objective, we take the step (\(x_{k+1}=x_k+s_k\)), otherwise we stay put (\(x_{k+1}=x_k\)). Based on this information, we choose a new value \(\Delta_{k+1}\), and repeat the process.
In Py-BOBYQA, we construct our approximation \(m_k(s)\) by interpolating a linear or quadratic approximation for \(f(x)\) at several points close to \(x_k\). To make sure our interpolated model is accurate, we need to regularly check that the points are well-spaced, and move them if they aren’t (i.e. improve the geometry of our interpolation points).
Py-BOBYQA is a Python implementation of the BOBYQA solver by Powell [Powell2009]. More details about Py-BOBYQA algorithm are given in our paper [CFMR2018].
References
Coralia Cartis, Jan Fiala, Benjamin Marteau and Lindon Roberts, Improving the Flexibility and Robustness of Model-Based Derivative-Free Optimization Solvers, ACM Transactions on Mathematical Software, 45:3 (2019), pp. 32:1-32:41 [preprint]
Michael J. D. Powell, The BOBYQA algorithm for bound constrained optimization without derivatives, technical report DAMTP 2009/NA06, University of Cambridge, (2009).