Local analysis of a spectral correction for the Gauss-Newton model applied to quadratic residual problems.

*(English)*Zbl 1357.90152This paper is a helpful contribution to nonlinear programming at its interface with data mining, statistics and the theory of inverse problems, being a “classical” and yet challenging field of modern operational research (OR), but also of economics, medicine, engineering, etc. There, smart inventions are appreciated very much to cope with problems of complexity, of convergence and to further provide qualitative theory. In fact, in today’s OR, the strongly emerging area of data mining is often named under “big data”, “data analytics”, “business analytics”, or just “analytics”. This paper is rigorous and based on it, future research can be raised and so many real-world applications made.

In fact, the authors present a simple – smart – spectral correction for the famous Gauss-Newton model from nonlinear regression theory, namely, from the optimization of nonlinear least squares. That correction consists in the addition of a sign-free multiple of the unit (or identity) matrix to the Gauss-Newton model’s Hessian, namely, the multiple that bases on spectral approximations for the Hessians of the residual functions. For the resulting method, an analysis of local convergence is provided in detail and applied on the class of quadratic residual problems. Given some mild assumptions, the proposed technique is demonstrated to converge for problems where convergence of the Gauss-Newton procedure might not be guaranteed. Furthermore, for a class of non-zero residue problems the rate of linear convergence is shown to be better than the one of the Gauss-Newton method. With the help of numerical examples on quadratic and non-quadratic residual problems, these theoretical results are illustrated in the article.

This valuable article is well-structured, mathematically deep, well exemplified and illustrated, related to rank-deficiency, etc., also, and written well.

The five sections of this work are as follows: 1. Introduction, 2. The spectral approximation, 3. Local analysis: quadratic residual case, 4. Illustrative numerical examples, and 5. Conclusions and future perspectives.

In the future, theoretical and algorithmic refinements and generalizations, strong results and codes could be expected in the research community, initiated by this research article. Those could be made in terms of nonlinear optimization, semi-infinite optimization, robust optimization, optimal control, image processing, pattern recognition, shape detection, tomography and information Theory.

Such a process could foster progress in science and engineering, finance, business administration, economics, earth-sciences, neuroscience and medicine.

In fact, the authors present a simple – smart – spectral correction for the famous Gauss-Newton model from nonlinear regression theory, namely, from the optimization of nonlinear least squares. That correction consists in the addition of a sign-free multiple of the unit (or identity) matrix to the Gauss-Newton model’s Hessian, namely, the multiple that bases on spectral approximations for the Hessians of the residual functions. For the resulting method, an analysis of local convergence is provided in detail and applied on the class of quadratic residual problems. Given some mild assumptions, the proposed technique is demonstrated to converge for problems where convergence of the Gauss-Newton procedure might not be guaranteed. Furthermore, for a class of non-zero residue problems the rate of linear convergence is shown to be better than the one of the Gauss-Newton method. With the help of numerical examples on quadratic and non-quadratic residual problems, these theoretical results are illustrated in the article.

This valuable article is well-structured, mathematically deep, well exemplified and illustrated, related to rank-deficiency, etc., also, and written well.

The five sections of this work are as follows: 1. Introduction, 2. The spectral approximation, 3. Local analysis: quadratic residual case, 4. Illustrative numerical examples, and 5. Conclusions and future perspectives.

In the future, theoretical and algorithmic refinements and generalizations, strong results and codes could be expected in the research community, initiated by this research article. Those could be made in terms of nonlinear optimization, semi-infinite optimization, robust optimization, optimal control, image processing, pattern recognition, shape detection, tomography and information Theory.

Such a process could foster progress in science and engineering, finance, business administration, economics, earth-sciences, neuroscience and medicine.

##### MSC:

90C30 | Nonlinear programming |

65K05 | Numerical mathematical programming methods |

49M37 | Numerical methods based on nonlinear programming |

##### Keywords:

nonlinear least squares; quadratic residues; spectral parameter; Gauss-Newton method; local convergence
PDF
BibTeX
XML
Cite

\textit{D. S. Gonçalves} and \textit{S. A. Santos}, Numer. Algorithms 73, No. 2, 407--431 (2016; Zbl 1357.90152)

Full Text:
DOI

##### References:

[1] | Bartholomew-Biggs, MC, The estimation of the Hessian matrix in nonlinear least squares problems with non-zero residuals, Math. Program., 12, 67-80, (1977) · Zbl 0365.65043 |

[2] | Barzilai, J; Borwein, J, Two-point step size gradient methods, IMA J. Numer. Anal., 8, 141-148, (1988) · Zbl 0638.65055 |

[3] | Behling, R; Fischer, A, A unified local convergence analysis of inexact constrained Levenberg-Marquardt methods, Optim. Lett, 6, 927-940, (2012) · Zbl 1279.90159 |

[4] | Bellavia, S; Cartis, C; Gould, N; Morini, B; Toint, Ph, L.: convergence of a regularized Euclidean residual algorithm for nonlinear least-squares, SIAM J. Numer. Anal., 48, 1-29, (2010) · Zbl 1218.90182 |

[5] | Bellavia, S; Morini, B, Strong local convergence properties of adaptive regularized methods for nonlinear least squares, IMA J. Numer. Anal., 35, 947-968, (2015) · Zbl 1316.65061 |

[6] | Birgin, E.G., Martínez, J.M., Raydan, M.: Nonmonotone spectral projected gradient methods on convex sets. SIAM J. Optim., 1196-1211 (2000). doi:10.1.1.145.9706 · Zbl 1047.90077 |

[7] | Brown, KM; Dennis Jr., JE, Derivative free analogues of the Levenberg-Marquardt and Gauss algorithms for nonlinear least squares approximation, Numer. Math., 18, 289-297, (1971) · Zbl 0235.65043 |

[8] | Chen, P, Hessian matrix vs. Gauss-Newton Hessian matrix, SIAM J. Numer. Anal, 49, 1417-1435, (2011) · Zbl 1228.65087 |

[9] | Dennis Jr., J.E.: Non-linear least squares and equations, pp 269-312. Academic Press, London (1977) · Zbl 1064.65037 |

[10] | Dennis Jr., J.E., Schnabel, R.B.: Numerical methods for unconstrained optimization and nonlinear equations, Classics in Applied Mathematics, vol. 16. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA. doi:10.1137/1.9781611971200, Corrected reprint of the 1983 original (1996) · Zbl 0847.65038 |

[11] | Dennis Jr., JE; Song-Bai, S; Vu, PA, A memoryless augmented Gauss-Newton method for nonlinear least-squares problems, J. Comput. Math, 6, 355-374, (1988) · Zbl 0662.65054 |

[12] | Ferreira, OP; Gonçalves, MLN; Oliveira, PR, Local convergence analysis of the Gauss-Newton method under a majorant condition, J. Complex., 27, 111-125, (2011) · Zbl 1216.65070 |

[13] | Ferreira, OP; Gonçalves, MLN; Oliveira, PR, Convergence of the Gauss-Newton method for convex composite optimization under a majorant condition, SIAM J. Optim., 23, 1757-1783, (2013) · Zbl 1277.49036 |

[14] | Gill, PE; Murray, W, Algorithms for the solution of the nonlinear least-squares problem, SIAM J. Numer. Anal., 15, 977-992, (1978) · Zbl 0401.65042 |

[15] | Gould, NIM, Ph.l.toint: FILTRANE, a Fortran 95 filter-trust-region package for solving nonlinear least-squares and nonlinear feasibility problems, ACM Trans. Math. Softw., 33, 23, (2007) |

[16] | Gratton, S; Lawless, AS; Nichols, NK, Approximate Gauss-Newton methods for nonlinear least squares problems, SIAM J. Optim, 18, 106-132, (2007) · Zbl 1138.65046 |

[17] | Kanzow, C; Yamashita, N; Fukushima, M, Levenberg-Marquardt methods with strong local convergence properties for solving nonlinear equations with convex constraints, J. Comput. Appl. Math., 172, 375-397, (2004) · Zbl 1064.65037 |

[18] | Levenberg, K, A method for the solution of certain non-linear problems in least squares, Q. Appl. Math., 2, 164-168, (1944) · Zbl 0063.03501 |

[19] | Marquardt, D, An algorithm for least-squares estimation of nonlinear parameters, SIAM J. Appl. Math., 11, 431-441, (1963) · Zbl 0112.10505 |

[20] | McKeown, J, Specialised versus general purpose algorithms for minimising functions that are sums of squared terms, Math. Program., 9, 57-68, (1975) · Zbl 0315.68036 |

[21] | Meyer, C.D.: Matrix analysis and applied linear algebra. SIAM philadelphia (2000) · Zbl 0898.90119 |

[22] | Morrison, DD; Lorell, J (ed.); Yagi, F (ed.), Methods for nonlinear least squares problems and convergence proofs, 1-9, (1960), USA |

[23] | Nesterov, Y, Modified Gauss-Newton scheme with worst-case guarantees for global performance, Optim. Methods Softw., 22, 469-483, (2007) · Zbl 1136.65051 |

[24] | Nocedal, J., Wright, S.J.: Numerical optimization. Springer Series in Operations Research. Springer, New York (1999). doi:10.1007/b98874 |

[25] | Raydan, M, The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem, SIAM J. Optim., 7, 26-33, (1997) · Zbl 0898.90119 |

[26] | Salzo, S; Villa, S, Convergence analysis of a proximal Gauss-Newton method, Comput. Optim. Appl, 53, 557-589, (2012) · Zbl 1282.90236 |

[27] | Smith, FB; Shanno, DF, An improved Marquardt procedure for nonlinear regressions, Technometrics, 13, 63-74, (1971) · Zbl 0216.22402 |

[28] | Wilkinson, J.H.: The algebraic eigenvalue problem. Oxford university press new york (1988) · Zbl 0626.65029 |

[29] | Yuan, YX, Recent advances in numerical methods for nonlinear equations and nonlinear least squares, Numer. Algebra Control Optim., 1, 15-34, (2011) · Zbl 1226.65045 |

[30] | Zhang, HC; Conn, AR, On the local convergence of a derivative-free algorithm for least-squares minimization, Comput. Optim. Appl., 51, 481-507, (2012) · Zbl 1268.90043 |

[31] | Zhang, HC; Conn, AR; Scheinberg, K, A derivative-free algorithm for the least-squares minimization, SIAM J. Optim., 20, 3555-3576, (2010) · Zbl 1213.65091 |

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.