×

zbMATH — the first resource for mathematics

A derivative-free Gauss-Newton method. (English) Zbl 1461.65136
Summary: 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).

MSC:
65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
90C56 Derivative-free methods and methods using generalized derivatives
90-04 Software, source code, etc. for problems pertaining to operations research and mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aoki, Y., Hayami, B., De Sterck, H., Konagaya, A.: Cluster Newton method for sampling multiple solutions of underdetermined inverse problems: application to a parameter identification problem in pharmacokinetics. SIAM J. Sci. Comput. 36(1), B14-B44 (2014) · Zbl 1290.65062
[2] Arter, W., Osojnik, A., Cartis, C., Madho, G., Jones, C., Tobias, S.: Data assimilation approach to analysing systems of ordinary differential equations. In: 2018 IEEE International Symposium on Circuits and Systems (ISCAS) (2018)
[3] Bergou, E., Gratton, S., Vicente, L.N.: Levenberg-Marquardt methods based on probabilistic gradient models and inexact subproblem solution, with application to data assimilation. SIAM/ASA J. Uncertain. Quantif. 4(1), 924-951 (2016) · Zbl 1358.90156
[4] Cartis, C., Roberts, L.: A Derivative-Free Gauss-Newton Method. Tech. rep., University of Oxford, Mathematical Institute (2017). Available on Optimization Online
[5] Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-Region Methods. MPS-SIAM Series on Optimization. MPS/SIAM, Philadelphia (2000)
[6] Conn, A.R., Scheinberg, K., Toint, P.L.: Recent progress in unconstrained nonlinear optimization without derivatives. Math. Program. 79, 397-414 (1997) · Zbl 0887.90154
[7] Conn, A.R., Scheinberg, K., Vicente, L.N.: Geometry of interpolation sets in derivative free optimization. Math. Program. 111(1-2), 141-172 (2007) · Zbl 1163.90022
[8] Conn, A.R., Scheinberg, K., Vicente, L.N.: Global convergence of general derivative-free trust-region algorithms to first- and second-order critical points. SIAM J. Optim. 20(1), 387-415 (2009) · Zbl 1187.65062
[9] Conn, A.R., Scheinberg, K., Vicente, L.N.: Introduction to Derivative-Free Optimization, MPS-SIAM Series on Optimization, vol. 8. MPS/SIAM, Philadelphia (2009) · Zbl 1163.49001
[10] Conn, AR; Toint, PL; Pillo, G. (ed.); Gianessi, F. (ed.), An Algorithm using Quadratic Interpolation for Unconstrained Derivative Free Optimization, 27-47 (1996), New York
[11] Custódio, AL; Scheinberg, K.; Vicente, LN; Terlaky, T. (ed.); Anjos, MF (ed.); Ahmed, S. (ed.), Methodologies and Software for Derivative-free Optimization (2017), Philadelphia
[12] Garmanjani, R., Júdice, D., Vicente, L.N.: Trust-region methods without using derivatives: worst case complexity and the nonsmooth case. SIAM J. Optim. 26(4), 1987-2011 (2016) · Zbl 1348.90572
[13] Gould, N.I.M., Orban, D., Toint, P.L.: CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization. Comput. Optim. Appl. 60(3), 545-557 (2015) · Zbl 1325.90004
[14] Gould, N.I.M., Porcelli, M., Toint, P.L.: Updating the regularization parameter in the adaptive cubic regularization algorithm. Comput. Optim. Appl. 53(1), 1-22 (2012) · Zbl 1259.90134
[15] Grapiglia, G.N., Yuan, J., Yuan, Yx: A derivative-free trust-region algorithm for composite nonsmooth optimization. Comput. Appl. Math 35(2), 475-499 (2016) · Zbl 1371.49014
[16] Júdice, D.: Trust-Region Methods without using Derivatives: Worst-Case Complexity and the Non-Smooth Case. Ph.D. thesis, University of Coimbra (2015)
[17] Kolda, T.G., Lewis, R.M., Torczon, V.: Optimization by direct search: new perspectives on some classical and modern methods. SIAM Rev. 45(3), 385-482 (2003) · Zbl 1059.90146
[18] Lukšan, L.: Hybrid methods for large sparse nonlinear least squares. J. Optim. Theory Appl. 89(3), 575-595 (1996) · Zbl 0851.90118
[19] Moré, J.J., Garbow, B.S., Hillstrom, K.E.: Testing unconstrained optimization software. ACM Trans. Math. Softw. 7(1), 17-41 (1981) · Zbl 0454.65049
[20] Moré, J.J., Wild, S.M.: Benchmarking derivative-free optimization algorithms. SIAM J. Optim. 20(1), 172-191 (2009) · Zbl 1187.90319
[21] Nocedal, J., Wright, S.J.: Numerical Optimization, Springer Series in Operations Research and Financial Engineering., 2nd edn. Springer, New York (2006)
[22] Oeuvray, R., Bierlaire, M.: BOOSTERS: a derivative-free algorithm based on radial basis functions. Int. J. Model. Simul. 29(1), 26-36 (2009)
[23] Powell, M. J. D., A Direct Search Optimization Method That Models the Objective and Constraint Functions by Linear Interpolation, 51-67 (1994), Dordrecht · Zbl 0826.90108
[24] Powell, M.J.D.: Direct search algorithms for optimization calculations. Acta Numer. 7, 287-336 (1998) · Zbl 0911.65050
[25] Powell, M.J.D.: UOBYQA: Unconstrained optimization by quadratic approximation. Math. Program. 92(3), 555-582 (2002) · Zbl 1014.65050
[26] Powell, M.J.D.: On trust region methods for unconstrained minimization without derivatives. Math. Program. 97(3), 605-623 (2003) · Zbl 1106.90382
[27] Powell, M.J.D.: Least Frobenius norm updating of quadratic models that satisfy interpolation conditions. Math. Program. 100(1), 183-215 (2004) · Zbl 1146.90526
[28] Powell, M.J.D.: A view of algorithms for optimization without derivatives. Tech. Rep. DAMTP 2007/NA03, University of Cambridge (2007)
[29] Powell, M.J.D.: The BOBYQA algorithm for bound constrained optimization without derivatives. Tech. Rep. DAMTP 2009/NA06, University of Cambridge (2009)
[30] Ralston, M.L., Jennrich, R.I.: Dud, a derivative-free algorithm for nonlinear least squares. Technometrics 20(1), 7-14 (1978) · Zbl 0422.65006
[31] Scheinberg, K., Toint, P.L.: Self-correcting geometry in model-based algorithms for derivative-free unconstrained optimization. SIAM J. Optim. 20(6), 3512-3532 (2010) · Zbl 1209.65017
[32] Tange, O.: GNU Parallel: the command-line power tool. ;login USENIX Mag. 36(1), 42-47 (2011)
[33] Wild, S.M.: POUNDERS in TAO: solving derivative-free nonlinear least-squares problems with POUNDERS. In: Adv. Trends Optim. with Eng. Appl., chap. 40, pp. 529-539. SIAM, Philadelphia, PA (2017)
[34] Wild, S.M., Regis, R.G., Shoemaker, C.A.: ORBIT: optimization by radial basis function interpolation in trust-regions. SIAM J. Sci. Comput. 30(6), 3197-3219 (2008) · Zbl 1178.65065
[35] Wild, S.M., Shoemaker, C.A.: Global convergence of radial basis function trust-region algorithms for derivative-free optimization. SIAM Rev. 55(2), 349-371 (2013) · Zbl 1270.65028
[36] Winfield, D.: Function minimization by interpolation in a data table. IMA J. Appl. Math. 12(3), 339-347 (1973) · Zbl 0274.90060
[37] Zhang, H., Conn, A.R.: On the local convergence of a derivative-free algorithm for least-squares minimization. Comput. Optim. Appl. 51(2), 481-507 (2012) · Zbl 1268.90043
[38] Zhang, H., Conn, A.R., Scheinberg, K.: A derivative-free algorithm for least-squares minimization. SIAM J. Optim. 20(6), 3555-3576 (2010) · Zbl 1213.65091
[39] Zhang, Z.: Software by Professor M. J. D. Powell. http://mat.uc.pt/ zhang/software.html (2017)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.