Local results for the Gauss-Newton method on constrained rank-deficient nonlinear least squares

Authors:
Jerry Eriksson and Mårten E. Gulliksson

Journal:
Math. Comp. **73** (2004), 1865-1883

MSC (2000):
Primary 65F22, 65K05

DOI:
https://doi.org/10.1090/S0025-5718-03-01611-9

Published electronically:
September 26, 2003

MathSciNet review:
2059740

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A nonlinear least squares problem with nonlinear constraints may be ill posed or even rank-deficient in two ways. Considering the problem formulated as subject to the constraints , the Jacobian and/or the Jacobian , , may be ill conditioned at the solution.

We analyze the important special case when and/or do not have full rank at the solution. In order to solve such a problem, we formulate a nonlinear least norm problem. Next we describe a truncated Gauss-Newton method. We show that the local convergence rate is determined by the maximum of three independent Rayleigh quotients related to three different spaces in .

Another way of solving an ill-posed nonlinear least squares problem is to regularize the problem with some parameter that is reduced as the iterates converge to the minimum. Our approach is a Tikhonov based local linear regularization that converges to a minimum norm problem. This approach may be used both for almost and rank-deficient Jacobians.

Finally we present computational tests on constructed problems verifying the local analysis.

**1.**Douglas M. Bates and Donald G. Watts,*Nonlinear regression analysis and its applications*, Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics, John Wiley & Sons, Inc., New York, 1988. MR**1060528****2.**Åke Björck,*Numerical methods for least squares problems*, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. MR**1386889****3.**Lars Eldén,*Algorithms for the regularization of ill-conditioned least squares problems*, Nordisk Tidskr. Informationsbehandling (BIT)**17**(1977), no. 2, 134–145. MR**0474912****4.**Lars Eldén,*A weighted pseudoinverse, generalized singular values, and constrained least squares problems*, BIT**22**(1982), no. 4, 487–502. MR**688717**, https://doi.org/10.1007/BF01934412**5.**J. Eriksson,*Optimization and regularization of nonlinear least squares problems*, Tech. Report UMINF 96.09 (Ph.D. Thesis), Dept. of Comp. Science, Umeå University, Umeå, Sweden, 1996.**6.**J. Eriksson, M. E. Gulliksson, P. Lindström, and P.-Å. Wedin,*Regularization tools for training feed-forward neural networks part I: Theory and basic algorithms*, Tech. Report UMINF 96.05, Dept. of Comp. Science, 1996.**7.**G. H. Golub and V. Pereyra,*The differentiation of pseudo-inverses and nonlinear least squares problems whose variables separate*, SIAM J. Numer. Anal.**10**(1973), 413–432. Collection of articles dedicated to the memory of George E. Forsythe. MR**0336980**, https://doi.org/10.1137/0710036**8.**M. Gulliksson,*KKT conditions for rank-deficient nonlinear least-square problems with rank-deficient nonlinear constraints*, J. Optim. Theory Appl.**100**(1999), no. 1, 145–160. MR**1673493**, https://doi.org/10.1023/A:1021721132282**9.**Mårten Gulliksson, Inge Söderkvist, and Per-Åke Wedin,*Algorithms for constrained and weighted nonlinear least squares*, SIAM J. Optim.**7**(1997), no. 1, 208–224. MR**1430564**, https://doi.org/10.1137/S1052623493248809**10.**Per Christian Hansen,*Rank-deficient and discrete ill-posed problems*, SIAM Monographs on Mathematical Modeling and Computation, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1998. Numerical aspects of linear inversion. MR**1486577****11.**Charles L. Lawson and Richard J. Hanson,*Solving least squares problems*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1974. Prentice-Hall Series in Automatic Computation. MR**0366019****12.**Sabine Van Huffel and Joos Vandewalle,*The total least squares problem*, Frontiers in Applied Mathematics, vol. 9, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1991. Computational aspects and analysis; With a foreword by Gene H. Golub. MR**1118607****13.**P. Lindström and P.-Å. Wedin,*Methods and software for nonlinear least squares problems*, Tech. Report UMINF-133.87, Inst. of Info. Proc., Univ. of Umeå, Umeå, Sweden, 1988.**14.**Jorge J. Moré,*The Levenberg-Marquardt algorithm: implementation and theory*, Numerical analysis (Proc. 7th Biennial Conf., Univ. Dundee, Dundee, 1977), Springer, Berlin, 1978, pp. 105–116. Lecture Notes in Math., Vol. 630. MR**0483445****15.**J. M. Ortega and W. C. Rheinboldt,*Iterative solution of nonlinear equations in several variables*, Academic Press, New York-London, 1970. MR**0273810****16.**Homer F. Walker,*Newton-like methods for underdetermined systems*, Computational solution of nonlinear systems of equations (Fort Collins, CO, 1988) Lectures in Appl. Math., vol. 26, Amer. Math. Soc., Providence, RI, 1990, pp. 679–699. MR**1066307****17.**Per-È¦ke Wedin,*Perturbation theory for pseudo-inverses*, Nordisk Tidskr. Informationsbehandling (BIT)**13**(1973), 217–232. MR**0336982****18.**-,*Notes on the constrained linear least squares problem. A new approach based on generalized inverses*, Technical Report UMINF 75.79, Inst. of Info. Proc., Univ. of Umeå, 1979.**19.**-,*Perturbation theory and condition numbers for generalized and constrained linear least squares problems*, Tech. Report UMINF 125.85, Inst. of Info. Proc., Univ. of Umeå, Umeå, Sweden, 1985.**20.**-,*On the use of a quadratic merit function for constrained nonlinear least squares*, Tech. report, Inst. of Info. Proc., Univ. of Umeå, Umeå, Sweden, 1987.

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
65F22,
65K05

Retrieve articles in all journals with MSC (2000): 65F22, 65K05

Additional Information

**Jerry Eriksson**

Affiliation:
Department of Computing Science, Umeå, Sweden

Email:
jerry@cs.umu.se

**Mårten E. Gulliksson**

Affiliation:
Department of Engineering, Physics, and Mathematics, Mid-Sweden University, Sundsvall, Sweden

Email:
marten@fmi.mh.se

DOI:
https://doi.org/10.1090/S0025-5718-03-01611-9

Keywords:
Nonlinear least squares,
nonlinear constraints,
optimization,
regularization,
Gauss-Newton method

Received by editor(s):
March 29, 2002

Received by editor(s) in revised form:
February 12, 2003

Published electronically:
September 26, 2003

Article copyright:
© Copyright 2003
American Mathematical Society