Numerical experiments with variations of the Gauss-Newton algorithm for nonlinear least squares

In this paper, the classical Gauss-Newton method for the unconstrained least squares problem is modified by introducing a quasi-Newton approximation to the second-order term of the Hessian. Various quasi-Newton formulas are considered, and numerical experiments show that most of them are more efficient on large residual problems than the Gauss-Newton method and a general purpose minimization algorithm based upon the BFGS formula. A particular quasi-Newton formula is shown numerically to be superior. Further improvements are obtained by using a line search that exploits the special form of the function.     

An efficient line search for nonlinear least squares

The line search subproblem in unconstrained optimization is concerned with finding an acceptable steplength which satisfies certain standard conditions. Prototype algorithms are described which guarantee finding such a step in a finite number of operations. This is achieved by first bracketing an interval of acceptable values and then reducing this bracket uniformly by the repeated use of sectioning in a systematic way. Some new theorems about convergence and termination of the line search are presented.Use of these algorithms to solve the line search subproblem in methods for nonlinear least squares is considered. We show that substantial gains in efficiency can be made by making polynomial interpolations to the individual residual functions rather than the overall objective function. We also study modified schemes in which the Jacobian matrix is evaluated as infrequently as possible, and show that further worthwhile savings can be made. Numerical results are presented.This work was supported by the award of a Syrian Ministry of Higher Education Scholarship.     

Hybrid methods for large sparse nonlinear least squares

Hybrid methods are developed for improving the Gauss-Newton method in the case of large residual or ill-conditioned nonlinear least-square problems. These methods are used usually in a form suitable for dense problems. But some standard approaches are unsuitable, and some new possibilities appear in the sparse case. We propose efficient hybrid methods for various representations of the sparse problems. After describing the basic ideas that help deriving new hybrid methods, we are concerned with designing hybrid methods for sparse Jacobian and sparse Hessian representations of the least-square problems. The efficiency of hybrid methods is demonstrated by extensive numerical experiments.This work was supported by the Czech Republic Grant Agency, Grant 201/93/0129. The author is indebted to Jan Vlek for his comments on the first draft of this paper and to anonymous referees for many useful remarks.     

Circle fitting by linear and nonlinear least squares

The problem of determining the circle of best fit to a set of points in the plane (or the obvious generalization ton-dimensions) is easily formulated as a nonlinear total least-squares problem which may be solved using a Gauss-Newton minimization algorithm. This straight-forward approach is shown to be inefficient and extremely sensitive to the presence of outliers. An alternative formulation allows the problem to be reduced to a linear least squares problem which is trivially solved. The recommended approach is shown to have the added advantage of being much less sensitive to outliers than the nonlinear least squares approach.This work was completed while the author was visiting the Numerical Optimisation Centre, Hatfield Polytechnic and benefitted from the encouragement and helpful suggestions of Dr. M. C. Bartholomew-Biggs and Professor L. C. W. Dixon.     

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

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.

     

A two-step superlinearly convergent projected structured BFGS method for constrained nonlinear least squares

We present an exact penalty approach for solving constrained non-linear least-squares problems, when the projected structured Hessian is approximated by a projected version of the structured BFGS formula and prove its local two-step Q-superlinear convergence. The numerical results obtained in an extensive comparative testing experiment confirm the approach to be reliable and efficient.     

A continuation method for solving separable nonlinear least squares problems

Given the data (x_i, y_i), i=1, 2, …, n, the problem is to find the values of the linear and nonlinear parameters â and b? which minimize the nonlinear functional |F(b)a?y|₂² over $\text{a ?}\text{R}{}^{\mathrm{p}}\text{, b ?}\text{R}{}^{\mathrm{q}}\text{,}\text{where}\text{F ?}\text{R}{}^{\mathrm{n\times p}}$ is a variable matrix and assumed to be of full rank, and $\text{y ?}\text{R}{}^{\mathrm{n}}$ is a constant vector.In this paper, we present a method for solving this problem by imbedding it into a one-parameter family of problems and by following its solution path using a predictor-corrector algorithm. In the course of iterations, the original problem containing p+q+1 variables is transformed into a problem with q+1 nonlinear variables by taking the separable structure of the problem into account. By doing so, the method reduces to solving a series of equations of smaller size and a considerable saving in the storage is obtained.Results of numerical experiments are reported to demonstrate the effectiveness of the proposed method.     

The rate of convergence for the least squares estimator in nonlinear regression model with dependent errors

We study the parameter estimation in a nonlinear regression model with a general error's structure,strong consistency and strong consistency rate of the least squares estimator are obtained.     

Algorithms for separable nonlinear least squares with application to modelling time-resolved spectra

The multiexponential analysis problem of fitting kinetic models to time-resolved spectra is often solved using gradient-based algorithms that treat the spectral parameters as conditionally linear. We make a comparison of the two most-applied such algorithms, alternating least squares and variable projection. A numerical study examines computational efficiency and linear approximation standard error estimates. A new derivation of the Fisher information matrix under the full Golub-Pereyra gradient allows a numerical comparison of parameter precision under variable projection variants. Under the criteria of efficiency, quality of standard error estimates and parameter precision, we conclude that the Kaufman variable projection technique performs well, while techniques based on alternating least squares have significant disadvantages for application in the problem domain.     

Factorized quasi-Newton methods for nonlinear least squares problems

This paper provides a modification to the Gauss—Newton method for nonlinear least squares problems. The new method is based on structured quasi-Newton methods which yield a good approximation to the second derivative matrix of the objective function. In particular, we propose BFGS-like and DFP-like updates in a factorized form which give descent search directions for the objective function. We prove local and q-superlinear convergence of our methods, and give results of computational experiments for the BFGS-like and DFP-like updates.This work was supported in part by the Grant-in-Aid for Encouragement of Young Scientists of the Japanese Ministry of Education: (A)61740133 and (A)62740137.     

Convergence theory for the structured BFGS secant method with an application to nonlinear least squares

In 1981, Dennis and Walker developed a convergence theory for structured secant methods which included the PSB and the DFP secant methods but not the straightforward structured version of the BFGS secant method. Here, we fill this gap in the theory by establishing a convergence theory for the structured BFGS secant method. A direct application of our new theory gives the first proof of local andq-superlinear convergence of the important structured BFGS secant method for the nonlinear least-squares problem, which is used by Dennis, Gay, and Welsh in the current version of the popular and successful NL2SOL code.This research was sponsored by SDIO/IST/ARO, AFOSR-85-0243, and DOE-DEFG05-86 ER-25017.A portion of this work is contained in the second author's doctoral thesis under the supervision of the other two authors in the Department of Mathematical Sciences, Rice University. The second author would like to thank Universidad del Valle, Cali, Columbia, for support during his graduate studies.An early draft of this work was presented at the SIAM 35th Anniversary Meeting, October 12–15, 1987, Denver, Colorado.     

Second-order nonlinear least squares estimation

The ordinary least squares estimation is based on minimization of the squared distance of the response variable to its conditional mean given the predictor variable. We extend this method by including in the criterion function the distance of the squared response variable to its second conditional moment. It is shown that this “second-order” least squares estimator is asymptotically more efficient than the ordinary least squares estimator if the third moment of the random error is nonzero, and both estimators have the same asymptotic covariance matrix if the error distribution is symmetric. Simulation studies show that the variance reduction of the new estimator can be as high as 50% for sample sizes lower than 100. As a by-product, the joint asymptotic covariance matrix of the ordinary least squares estimators for the regression parameter and for the random error variance is also derived, which is only available in the literature for very special cases, e.g. that random error has a normal distribution. The results apply to both linear and nonlinear regression models, where the random error distributions are not necessarily known.     

On nonlinear weighted total least squares parameter estimation problem for the three-parameter Weibull density

The three-parameter Weibull density function is widely employed as a model in reliability and lifetime studies. Estimation of its parameters has been approached in the literature by various techniques, because a standard maximum likelihood estimate does not exist. In this paper we consider the nonlinear weighted total least squares fitting approach. As a main result, a theorem on the existence of the total least squares estimate is obtained, as well as its generalization in the total _lq$l_q$ norm (q?1$q?1$). Some numerical simulations to support the theoretical work are given.     

Nonlinear approximation of functions based on nonnegative least squares solver

In computational practice, most attention is paid to rational approximations of functions and approximations by the sum of exponents. We consider a wide enough class of nonlinear approximations characterized by a set of two required parameters. The approximating function is linear in the first parameter; these parameters are assumed to be positive. The individual terms of the approximating function represent a fixed function that depends nonlinearly on the second parameter. A numerical approximation minimizes the residual functional by approximating function values at individual points. The second parameter's value is set on a more extensive set of points of the interval of permissible values. The proposed approach's key feature consists in determining the first parameter on each separate iteration of the classical nonnegative least squares method. The computational algorithm is used to rational approximate the function . The second example concerns the approximation of the stretching exponential function at $x\ge 0$ by the sum of exponents.     

An algorithm for least squares analysis of spectroscopic data

This paper describes a variant of the Gauss-Newton-Hartley algorithm for nonlinear least squares, in which aQR implementation is used to solve the linear least squares problem. We follow Grey's idea of updating variables at intermediate stages of the orthogonalization. This technique, applied in partitions identified with known or suspected spectral lines, appears to be especially suited to the analysis of spectroscopic data. We suggest that this algorithm is an attractive candidate for the optimization role in Ekenberg's interactive computer graphics curve fitting program.     

A primal-dual interior-point algorithm for nonlinear least squares constrained problems

This paper extends prior work by the authors on solving nonlinear least squares unconstrained problems using a factorized quasi-Newton technique. With this aim we use a primal-dual interior-point algorithm for nonconvex nonlinear programming. The factorized quasi-Newton technique is now applied to the Hessian of the Lagrangian function for the transformed problem which is based on a logarithmic barrier formulation. We emphasize the importance of establishing and maintaining symmetric quasi-definiteness of the reduced KKT system. The algorithm then tries to choose a step size that reduces a merit function, and to select a penalty parameter that ensures descent directions along the iterative process. Computational results are included for a variety of least squares constrained problems and preliminary numerical testing indicates that the algorithm is robust and efficient in practice.     

Interpolation of functions by the least squares method

We study the norm of a best quadratic trigonometric approximation operator on a finite uniform grid. Dedicated to the memory of my scientific adviser, Professor S. B. Stechkin Translated fromMatematicheskie Zametki, Vol. 66, No. 3, pp. 372–379, September, 1999.     

Asymptotic theory of least squares estimator in a nonregular nonlinear regression model

The asymptotic properties of the least squares estimator are derived for a nonregular nonlinear model via the study of weak convergence of the least squares process. This approach was adapted earlier by the author in the smooth case. The model discussed here is not amenable to analysis via the normal equations and Taylor expansions used by earlier authors.     

Minimax estimation and the least squares method

This paper is devoted to the problem of minimax estimation of parameters in linear regression models with uncertain second order statistics. The solution to the problem is shown to be the least squares estimator corresponding to the least favourable matrix of the second moments. This allows us to construct a new algorithm for minimax estimation closely connected with the least squares method. As an example, we consider the problem of polynomial regression introduced by A. N. Kolmogorov     

Perturbation analysis for mixed least squares–total least squares problems

In many linear parameter estimation problems, one can use the mixed least squares–total least squares (MTLS) approach to solve them. This paper is devoted to the perturbation analysis of the MTLS problem. Firstly, we present the normwise, mixed, and componentwise condition numbers of the MTLS problem, and find that the normwise, mixed, and componentwise condition numbers of the TLS problem and the LS problem are unified in the ones of the MTLS problem. In the analysis of the first‐order perturbation, we first provide an upper bound based on the normwise condition number. In order to overcome the problems encountered in calculating the normwise condition number, we give an upper bound for computing more effectively for the MTLS problem. As two estimation techniques for solving the linear parameter estimation problems, interesting connections between their solutions, their residuals for the MTLS problem, and the LS problem are compared. Finally, some numerical experiments are performed to illustrate our results.