DFO-LS: Derivative-Free Optimizer for Least-Squares Minimization

Release: 1.5.3

Date: 30 October 2024

DFO-LS is a flexible package for finding local solutions to nonlinear least-squares minimization problems (with optional regularizer and constraints), without requiring any derivatives of the objective. DFO-LS stands for Derivative-Free Optimizer for Least-Squares.

That is, DFO-LS solves

\[\begin{split}\min_{x\in\mathbb{R}^n} &\quad f(x) := \sum_{i=1}^{m}r_{i}(x)^2 + h(x) \\ \text{s.t.} &\quad a \leq x \leq b\\ &\quad x \in C := C_1 \cap \cdots \cap C_n, \quad \text{all $C_i$ convex}\\\end{split}\]

The optional regularizer $h(x)$ is a Lipschitz continuous and convex, but possibly non-differentiable function that is typically used to avoid overfitting. A common choice is $h(x)=\lambda \|x\|_1$ (called L1 regularization or LASSO) for $\lambda>0$. Note that in the case of Tikhonov regularization/ridge regression, $h(x)=\lambda\|x\|_2^2$ is not Lipschitz continuous, so should instead be incorporated by adding an extra term into the least-squares sum, $r_{m+1}(x)=\sqrt{\lambda} \|x\|_2$. The (optional) constraint set $C$ is the intersection of multiple convex sets provided as input by the user. All constraints are non-relaxable (i.e. DFO-LS will never ask to evaluate a point that is not feasible), although the general constraints $x\in C$ may be slightly violated from rounding errors.

Full details of the DFO-LS algorithm are given in our papers:

1. Cartis, J. Fiala, B. Marteau and L. 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] .
1. Hough, and L. Roberts, Model-Based Derivative-Free Methods for Convex-Constrained Optimization, SIAM Journal on Optimization, 21:4 (2022), pp. 2552-2579 [preprint].
1. Liu, K. H. Lam and L. Roberts, Black-box Optimization Algorithms for Regularized Least-squares Problems, arXiv preprint arXiv:arXiv:2407.14915, 2024.

DFO-LS is a more flexible version of DFO-GN.

If you are interested in solving general optimization problems (without a least-squares structure), you may wish to try Py-BOBYQA, which has many of the same features as DFO-LS.

DFO-LS is released under the GNU General Public License. Please contact NAG for alternative licensing.

Contents:

Acknowledgements

This software was initially developed under the supervision of Coralia Cartis, and was supported by the EPSRC Centre For Doctoral Training in Industrially Focused Mathematical Modelling (EP/L015803/1) in collaboration with the Numerical Algorithms Group. Development of DFO-LS has also been supported by the Australian Research Council (DE240100006).