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

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.**D. Bates and D. Watts,*Nonlinear regression analysis and its applications*, John Wiley, 1988. MR**92f:62002****2.**Å. Björck,*Numerical methods for least squares problems*, SIAM, 1996.MR**97g:65004****3.**L. Elden,*Algorithms for the regularization of ill conditioned least squares problems*, BIT**17**(1977), 134-145. MR**57:14541****4.**-,*A weighted pseudoinverse, generalized singular values and constrained least squares problems*, BIT**22**(1982), 487-502. MR**84g:65048****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 pseudoinverses and nonlinear least squares problems whose variables separate*, SIAM J. Num. Anal.**10**(1973), 413-432. MR**49:1753****8.**M. E. Gulliksson,*KKT-conditions for exactly rank deficient nonlinear least squares with exactly rank deficient nonlinear constraints*, Journal of Optmization Theory and Application (JOTA)**100**(1999), no. 1, 145-160.MR**99m:93057****9.**M. E. Gulliksson, I. Söderkvist, and P.-Å. Wedin,*Algorithms for constrained and weighted nonlinear least squares*, SIAM J. Opt.**7**(1997), no. 1, 208-224. MR**97m:90063****10.**P.C. Hansen,*Rank-deficient and discrete ill-posed problems. Numerical aspects of linear inversion*, SIAM, Philadelphia, 1997. MR**99a:65037****11.**R. J. Hanson and C. L. Lawson,*Solving least squares problems*, Prentice Hall, Englewood Cliffs, N. J., 1974. MR**51:2270****12.**Sabine Van Huffel and Joos Vandewalle,*The total least squares problem - computational aspects and analysis*, SIAM, 1991. MR**93b:65001****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.**J. J. More,*The Levenberg-Marquardt algorithm: implementation and theory*, Proceedings of the 1977 Dundee conference on numerical analysis (Berlin, Heidelberg, New York, Tokyo) (G. A. Watson, ed.), Lecture notes in mathematics 630, Springer Verlag, 1978, pp. 105-116. MR**58:3446****15.**J. M. Ortega and W. C. Rheinboldt,*Iterative solution of nonlinear equations in several variables*, Academic Press, New York, 1970. MR**42:8686****16.**H. F. Walker,*Newton-like methods for underdetermined systems*, Lectures in Applied Mathematics**26**(1990), 679-699. MR**91h:65086****17.**P.-Å. Wedin,*Perburbation theory for pseudo-inverses*, BIT**13**(1973), 217-232. MR**49:1755****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