A comparison of some algorithms for the nonlinear least squares problem

The problem of minimizing a sum of squares of nonlinear functions is studied. To solve this problem one usually takes advantage of the fact that the objective function is of this special form. Doing this gives the Gauss-Newton method or modifications thereof. To study how these specialized methods compare with general purpose nonlinear optimization routines, test problems were generated where parameters determining the local behaviour of the algorithms could be controlled. The order of 1000 test problems were generated for testing three algorithms: the Gauss-Newton method, the Levenberg-Marquardt method and a quasi-Newton method.     

Accelerated Gauss-Newton algorithms for nonlinear least squares problems

Recent theoretical and practical investigations have shown that the Gauss-Newton algorithm is the method of choice for the numerical solution of nonlinear least squares parameter estimation problems. It is shown that when line searches are included, the Gauss-Newton algorithm behaves asymptotically like steepest descent, for a special choice of parameterization. Based on this a conjugate gradient acceleration is developed. It converges fast also for those large residual problems, where the original Gauss-Newton algorithm has a slow rate of convergence. Several numerical test examples are reported, verifying the applicability of the theory.     

非线性最小二乘法的算法

本给出非线性最小二乘的优化条件和几何特征．     

Decomposition algorithms for the tree edit distance problem

We study the behavior of dynamic programming methods for the tree edit distance problem, such as [P. Klein, Computing the edit-distance between unrooted ordered trees, in: Proceedings of 6th European Symposium on Algorithms, 1998, p. 91–102; K. Zhang, D. Shasha, SIAM J. Comput. 18 (6) (1989) 1245–1262]. We show that those two algorithms may be described as decomposition strategies. We introduce the general framework of cover strategies, and we provide an exact characterization of the complexity of cover strategies. This analysis allows us to define a new tree edit distance algorithm, that is optimal for cover strategies.     

Derivative free analogues of the Levenberg-Marquardt and Gauss algorithms for nonlinear least squares approximation

In this paper we give two derivative-free computational algorithms for nonlinear least squares approximation. The algorithms are finite difference analogues of the Levenberg-Marquardt and Gauss methods. Local convergence theorems for the algorithms are proven. In the special case when the residuals are zero at the minimum, we show that certain computationally simple choices of the parameters lead to quadratic convergence. Numerical examples are included.On leave 1970–71 at Yale UniversityThe work of this author was supported in part by the National Science Foundation under Grant GJ-844.     

Trust region affine scaling algorithms for linearly constrained convex and concave programs

We study a trust region affine scaling algorithm for solving the linearly constrained convex or concave programming problem. Under primal nondegeneracy assumption, we prove that every accumulation point of the sequence generated by the algorithm satisfies the first order necessary condition for optimality of the problem. For a special class of convex or concave functions satisfying a certain invariance condition on their Hessians, it is shown that the sequences of iterates and objective function values generated by the algorithm convergeR-linearly andQ-linearly, respectively. Moreover, under primal nondegeneracy and for this class of objective functions, it is shown that the limit point of the sequence of iterates satisfies the first and second order necessary conditions for optimality of the problem. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.The work of these authors was based on research supported by the National Science Foundation under grant INT-9600343 and the Office of Naval Research under grants N00014-93-1-0234 and N00014-94-1-0340.     

The minimum distance superset problem: formulations and algorithms

The partial digest problem consists in retrieving the positions of a set of points on the real line from their unlabeled pairwise distances. This problem is critical for DNA sequencing, as well as for phase retrieval in X-ray crystallography. When some of the distances are missing, this problem generalizes into a “minimum distance superset problem”, which aims to find a set of points of minimum cardinality such that the multiset of their pairwise distances is a superset of the input. We introduce a quadratic integer programming formulation for the minimum distance superset problem with a pseudo-polynomial number of variables, as well as a polynomial-size integer programming formulation. We investigate three types of solution approaches based on an available integer programming solver: (1) solving a linearization of the pseudo-polynomial-sized formulation, (2) solving the complete polynomial-sized formulation, or (3) performing a binary search over the number of points and solving a simpler feasibility or optimization problem at each step. As illustrated by our computational experiments, the polynomial formulation with binary search leads to the most promising results, allowing to optimally solve most instances with up to 25 distance values and 8 solution points.     

Bounds for the least squares distance using scaled total least squares

Summary. The standard approaches to solving overdetermined linear systems construct minimal corrections to the data to make the corrected system compatible. In ordinary least squares (LS) the correction is restricted to the right hand side c, while in scaled total least squares (STLS) [14,12] corrections to both c and B are allowed, and their relative sizes are determined by a real positive parameter . As , the STLS solution approaches the LS solution. Our paper [12] analyzed fundamentals of the STLS problem. This paper presents a theoretical analysis of the relationship between the sizes of the LS and STLS corrections (called the LS and STLS distances) in terms of . We give new upper and lower bounds on the LS distance in terms of the STLS distance, compare these to existing bounds, and examine the tightness of the new bounds. This work can be applied to the analysis of iterative methods which minimize the residual norm, and the generalized minimum residual method (GMRES) [15] is used here to illustrate our theory. Received July 20, 2000 / Revised version received February 28, 2001 / Published online July 25, 2001     

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.     

Solving the nonlinear least square problem: Application of a general method

An algorithm for solving the general nonlinear least-square problem is developed. An estimate for the Hessian matrix is constructed as the sum of two matrices. The first matrix is the usual first-order estimate used by the Gauss method, while the second matrix is generated recursively using a rank-one formula. Test results indicate that the method is superior to the standard Gauss method and compares favorably with other methods, especially for problems with nonzero residuals at the solution.This work was supported by the US Air Force under Contract No. F04701-73-C-0074.The author expresses his appreciation to Dr. H. E. Pickett and Dr. J. L. Searcy for their continuing support in the theoretical and practical development of the algorithm. The recursive method for generating the estimate of the Hessian matrix was developed jointly with Drs. Pickett and Searcy and is included here with their permission. The author would also like to acknowledge the contribution made by the stimulating environment of an optimal control seminar held at The Aerospace Corporation since 1970. Principle members of the seminar have been H. E. Pickett, J. L. Searcy, R. W. Reid, and the author.     

A smoothing conic trust region filter method for the nonlinear complementarity problem

This paper discusses nonlinear complementarity problems; its goal is to present a globally and superlinearly convergent algorithm for the discussed problems. Filter methods are extensively studied to handle nonlinear complementarity problem. Because of good numerical results, filter techniques are attached. By means of a filter strategy, we present a new trust region method based on a conic model for nonlinear complementarity problems. Under a proper condition, the superlinear convergence of the algorithm is established without the strict complementarity condition.     

Two-stage least squares and indirect least squares algorithms for simultaneous equations models

This paper analyzes the solution of simultaneous equations models. Efficient algorithms for the two-stage least squares method using QR-decomposition are developed and studied. The reduction of the execution time when the structure of the matrices in each equation is exploited is analyzed theoretically and experimentally. An efficient algorithm for the indirect least squares method is developed. Some techniques are used to accelerate the solution of the problem: parallel versions for multicore systems, and extensive use of the MKL library, thus obtaining efficient, portable versions of the algorithms.     

Scaled nonlinear conjugate gradient methods for nonlinear least squares problems

Numerical Algorithms -     

The least solution for the polynomial interpolation problem

Supported by the National Science Foundation under Grant No. DMS-8701275     

A new algorithm for nonlinear least squares

A new algorithm for the nonlinear least-squares problems is introduced and illustrated in this article. It is shown that the new algorithm is relatively more efficient compared to the other algorithms in current use and it works for problems where other methods fail. The new method is illustrated by solving a number of classical test problems. In light of the present method, improvements for some other methods in current use are also suggested in this article. Bibliography: 22 titles. Published inZapiski Nauchnykh Seminarov POMI, Vol. 207, pp. 143–157, 1993.