Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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
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 $\min_{x} 1/2\Vert f_{2}(x) \Vert _{2}^{2}$subject to the constraints $f_{1}(x) = 0$, the Jacobian $J_{1} = \partial f_{1}/ \partial x$ and/or the Jacobian $J = \partial f/ \partial x$, $f = [f_{1};f_{2}]$, may be ill conditioned at the solution.

We analyze the important special case when $J_{1}$ and/or $J$ 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 $\mathbb{R} ^{n}$.

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.

References [Enhancements On Off] (What's this?)

  • 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.

Similar Articles

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

Mårten E. Gulliksson
Affiliation: Department of Engineering, Physics, and Mathematics, Mid-Sweden University, Sundsvall, Sweden

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

American Mathematical Society