Local results for the GaussNewton method on constrained rankdeficient nonlinear least squares
Authors:
Jerry Eriksson and Mårten E. Gulliksson
Journal:
Math. Comp. 73 (2004), 18651883
MSC (2000):
Primary 65F22, 65K05
Published electronically:
September 26, 2003
MathSciNet review:
2059740
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: A nonlinear least squares problem with nonlinear constraints may be ill posed or even rankdeficient 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 GaussNewton 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 illposed 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 rankdeficient 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
(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 illconditioned
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 feedforward 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. 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 rankdeficient nonlinear
leastsquare problems with rankdeficient 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, Rankdeficient and discrete illposed
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, PrenticeHall Inc.,
Englewood Cliffs, N.J., 1974. PrenticeHall 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 UMINF133.87, Inst. of Info. Proc., Univ. of Umeå, Umeå, Sweden, 1988.
 14.
Jorge
J. Moré, The LevenbergMarquardt 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, Newtonlike 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 pseudoinverses, 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.
 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), 134145. MR 57:14541
 4.
 , A weighted pseudoinverse, generalized singular values and constrained least squares problems, BIT 22 (1982), 487502. 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 feedforward 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), 413432. MR 49:1753
 8.
 M. E. Gulliksson, KKTconditions for exactly rank deficient nonlinear least squares with exactly rank deficient nonlinear constraints, Journal of Optmization Theory and Application (JOTA) 100 (1999), no. 1, 145160.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, 208224. MR 97m:90063
 10.
 P.C. Hansen, Rankdeficient and discrete illposed 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 UMINF133.87, Inst. of Info. Proc., Univ. of Umeå, Umeå, Sweden, 1988.
 14.
 J. J. More, The LevenbergMarquardt 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. 105116. 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, Newtonlike methods for underdetermined systems, Lectures in Applied Mathematics 26 (1990), 679699. MR 91h:65086
 17.
 P.Å. Wedin, Perburbation theory for pseudoinverses, BIT 13 (1973), 217232. 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
Email:
jerry@cs.umu.se
Mårten E. Gulliksson
Affiliation:
Department of Engineering, Physics, and Mathematics, MidSweden University, Sundsvall, Sweden
Email:
marten@fmi.mh.se
DOI:
http://dx.doi.org/10.1090/S0025571803016119
PII:
S 00255718(03)016119
Keywords:
Nonlinear least squares,
nonlinear constraints,
optimization,
regularization,
GaussNewton 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
