DFO-GN: A Derivative-Free Gauss-Newton Solver

Release: 1.0.2

Date: 08 July 2019

Author: Lindon Roberts (Mathematical Institute, University of Oxford)

DFO-GN is a Python package for finding local solutions to nonlinear least-squares minimization problems (with optional bound constraints), without requiring any derivatives of the objective. DFO-GN stands for Derivative-Free Optimization using Gauss-Newton, and is applicable to problems such as

  • Parameter estimation/data fitting;

  • Solving systems of nonlinear equations (including under- and over-determined systems); and

  • Inverse problems, including data assimilation.

DFO-GN is a derivative-free algorithm, meaning it does not require any information about the derivative of the objective, nor does it attempt to estimate such information (e.g. by using finite differencing). This means that it is particularly useful for solving noisy problems; i.e. where evaluating the objective function several times for the same input may give different results.

Mathematically, DFO-GN solves

\[\begin{split}\min_{x\in\mathbb{R}^n} &\quad f(x) := \sum_{i=1}^{m}r_{i}(x)^2 \\ \text{s.t.} &\quad a \leq x \leq b\end{split}\]

where the functions \(r_i(x)\) may be nonlinear and even nonconvex. Full details of the DFO-GN algorithm are given in our paper: A Derivative-Free Gauss-Newton Method, C. Cartis and L. Roberts, Mathematical Programming Computation (2019). A preprint of the paper is available here.

DFO-GN is released under the open source GNU General Public License, a copy of which can be found in LICENSE.txt. Please contact NAG for alternative licensing. It is compatible with both Python 2 and Python 3.

Note: we have released a newer package, called DFO-LS, which is an upgrade of DFO-GN to improve its flexibility and robustness to noisy problems. See here for details.

If you have any questions or suggestsions about the code, or have used DFO-GN for an interesting application, we would very much like to hear from you: please contact Lindon Roberts (alternative email).

Citation To cite DFO-GN, please use

@Article{DFOGN,
  Title    = {A derivative-free {G}auss-{N}ewton method},
  Author   = {Cartis, Coralia and Roberts, Lindon},
  Journal  = {Mathematical Programming Computation},
  Year     = {2019},
  Doi      = {10.1007/s12532-019-00161-7},
  Url      = {https://doi.org/10.1007/s12532-019-00161-7}
}

Acknowledgements

This software was developed under the supervision of Coralia Cartis (Mathematical Institute, University of Oxford), and was supported by the EPSRC Centre For Doctoral Training in Industrially Focused Mathematical Modelling (EP/L015803/1) at the University of Oxford’s Mathematical Institute, in collaboration with the Numerical Algorithms Group.

DFO-GN was developed using techniques from DFBOLS (Zhang, Conn & Scheinberg, 2010) and BOBYQA (Powell, 2009). The structure of this documentation is from oBB by Jari Fowkes.