Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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 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 $\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. 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 (92f:62002)
  • 2. Åke Björck, Numerical methods for least squares problems, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. MR 1386889 (97g:65004)
  • 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 (57 #14541)
  • 4. Lars Eldén, A weighted pseudoinverse, generalized singular values, and constrained least squares problems, BIT 22 (1982), no. 4, 487–502. MR 688717 (84g:65048), http://dx.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 (49 #1753)
  • 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 (99m:93057), http://dx.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 (97m:90063), http://dx.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 (99a:65037)
  • 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 (51 #2270)
  • 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 (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. 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 (58 #3446)
  • 15. J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York, 1970. MR 0273810 (42 #8686)
  • 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 (91h:65086)
  • 17. Per-Ȧke Wedin, Perturbation theory for pseudo-inverses, Nordisk Tidskr. Informationsbehandling (BIT) 13 (1973), 217–232. MR 0336982 (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
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: http://dx.doi.org/10.1090/S0025-5718-03-01611-9
PII: S 0025-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