A derivative-free Gauss–Newton method

Journal article

We present DFO-GN, a derivative-free version of the Gauss–Newton method for solving nonlinear least-squares problems. DFO-GN uses linear interpolation of residual values to build a quadratic model of the objective, which is then used within a typical derivative-free trust-region framework. We show that DFO-GN is globally convergent and requires at most {\mathcal {O}}(\epsilon ^{-2}) iterations to reach approximate first-order criticality within tolerance \epsilon. We provide an implementation of DFO-GN and compare it to other state-of-the-art derivative-free solvers that use quadratic interpolation models. We demonstrate numerically that despite using only linear residual models, DFO-GN performs comparably to these methods in terms of objective evaluations. Furthermore, as a result of the simplified interpolation procedure, DFO-GN has superior runtime and scalability. Our implementation of DFO-GN is available at https://github.com/numericalalgorithmsgroup/dfogn ( https://doi.org/10.5281/zenodo.2629875)

Authors: Roberts, L; Cartis, C

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Springer Verlag
• Journal: Mathematical Programming Computation
• Volume: 11
• Issue: 4
• Pages: 631–674
• Publication date: 2019-05-20
• Acceptance date: 2019-04-02
• DOI: 10.1007/s12532-019-00161-7
• Keywords: least-squares; derivative-free optimization; trust region methods; worst-case complexity; Gauss–Newton method