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.     

Operations research and optimization (ORO)

We have recently proposed a structured algorithm for solving constrained nonlinear least-squares problems and established its local two-step Q-superlinear convergence rate. The approach is based on an earlier adaptive structured scheme due to Mahdavi-Amiri and Bartels of the exact penalty method. The structured adaptation makes use of the ideas of Nocedal and Overton for handling quasi-Newton updates of projected Hessians and adapts a structuring scheme due to Engels and Martinez. For robustness, we have employed a specific nonsmooth line search strategy, taking account of the least-squares objective. Numerical results also confirm the practical relevance of our special considerations for the inherent structure of the least squares. Here, we establish global convergence of the proposed algorithm using a weaker condition than the one used by the exact penalty method of Coleman and Conn for general nonlinear programs.     

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.     

等式约束不定最小二乘问题的双曲MGS消去算法

众所周知,加权法是解等式约束不定最小二乘问题的方法之一.通过探讨极限意义下,双曲MGS算法解对应加权问题的本质,得到一类消去算法.实验表明,该算法以和文献中现有的GHQR算法达到一样的精度,但实际计算量只需要GHQR算法的一半.     

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

Real structure-preserving algorithm for quaternion equality constrained least squares problem

Quaternion equality constrained least squares problem is an extremely effective tool in studying quantum mechanics and quantum field theory. However, the computation of the quaternion equality constrained least squares problem is extremely complex. In this paper, we first prove that quaternion equality constrained least squares problem is equivalent to weighted quaternion least squares problem when the parameter $\tau \to +\infty$. Then, for weighted quaternion least squares problem, applying the special structure of real representation of quaternion, we propose real structure–preserving algorithm to obtain the solution of quaternion equality contained least squares problem. At last, we give numerical examples to illustrate the effectiveness of our method.     

Model reduction for large-scale dynamical systems via equality constrained least squares

In this paper, we present a new method of model reduction for large-scale dynamical systems, which belongs to the SVD-Krylov based method category. It is a two-sided projection where one side reflects the Krylov part and the other side reflects the SVD (observability gramian) part. The reduced model matches the first r+i Markov parameters of the full order model, and the remaining ones approximate in a least squares sense without being explicitly computed, where r is the order of the reduced system, and i is a nonnegative integer such that 1≤i<r. The reduced system minimizes a weighted ?₂ error. By the definition of a shift operator, the proposed approximation is also obtained by solving an equality constrained least squares problem. Moreover, the method is generalized for moment matching at arbitrary interpolation points. Several numerical examples verify the effectiveness of the approach.     

Nonlinear conjugate gradient methods with structured secant condition for nonlinear least squares problems

In this paper, we deal with conjugate gradient methods for solving nonlinear least squares problems. Several Newton-like methods have been studied for solving nonlinear least squares problems, which include the Gauss-Newton method, the Levenberg-Marquardt method and the structured quasi-Newton methods. On the other hand, conjugate gradient methods are appealing for general large-scale nonlinear optimization problems. By combining the structured secant condition and the idea of Dai and Liao (2001) [20], the present paper proposes conjugate gradient methods that make use of the structure of the Hessian of the objective function of nonlinear least squares problems. The proposed methods are shown to be globally convergent under some assumptions. Finally, some numerical results are given.     

A superlinearly convergent projection method for constrained systems of nonlinear equations

In this paper, a new projection method for solving a system of nonlinear equations with convex constraints is presented. Compared with the existing projection method for solving the problem, the projection region in this new algorithm is modified which makes an optimal stepsize available at each iteration and hence guarantees that the next iterate is more closer to the solution set. Under mild conditions, we show that the method is globally convergent, and if an error bound assumption holds in addition, it is shown to be superlinearly convergent. Preliminary numerical experiments also show that this method is more efficient and promising than the existing projection method. This work was done when Yiju Wang visited Chongqing Normal University.     

A globally convergent method for nonlinear programming

Recently developed Newton and quasi-Newton methods for nonlinear programming possess only local convergence properties. Adopting the concept of the damped Newton method in unconstrained optimization, we propose a stepsize procedure to maintain the monotone decrease of an exact penalty function. In so doing, the convergence of the method is globalized.This research was supported in part by the National Science Foundation under Grant No. ENG-75-10486.     

约束最优化的一个使用非单调线搜索的超线性收敛算法

Abstract. In the paper, a new mixed algorithm combined with schemes of nonmonotone line search, the systems of linear equations for higher order modification and sequential quadratic programming for constrained optimizations is presented. Under some weaker assumptions,without strict complementary condition, the algorithm is globally and superlinearly convergent.     

Algebraic methods for equality constrained least squares problems in commutative quaternionic theory

This paper, by means of two matrix representations of a commutative quaternion matrix, studies the relationship between the solutions of commutative quaternion equality constrained least squares (LSE) problems and that of complex and real LSE problems and derives two algebraic methods for finding the solutions of equality constrained least squares problems in commutative quaternionic theory.     

A negative-norm least squares method for Reissner-Mindlin plates

In this paper a least squares method, using the minus one norm developed by Bramble, Lazarov, and Pasciak, is introduced to approximate the solution of the Reissner-Mindlin plate problem with small parameter , the thickness of the plate. The reformulation of Brezzi and Fortin is employed to prevent locking. Taking advantage of the least squares approach, we use only continuous finite elements for all the unknowns. In particular, we may use continuous linear finite elements. The difficulty of satisfying the inf-sup condition is overcome by the introduction of a stabilization term into the least squares bilinear form, which is very cheap computationally. It is proved that the error of the discrete solution is optimal with respect to regularity and uniform with respect to the parameter . Apart from the simplicity of the elements, the stability theorem gives a natural block diagonal preconditioner of the resulting least squares system. For each diagonal block, one only needs a preconditioner for a second order elliptic problem.

     

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.     

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.     

Perturbation theory for generalized and constrained linear least squares

The perturbation analysis of weighted and constrained rank‐deficient linear least squares is difficult without the use of the augmented system of equations. In this paper a general form of the augmented system is used to get simple perturbation identities and perturbation bounds for the general linear least squares problem both for the full‐rank and rank‐deficient problem. Perturbation identities for the rank‐deficient weighted and constrained case are found as a special case. Interesting perturbation bounds and condition numbers are derived that may be useful when considering the stability of a solution of the rank‐deficient general least squares problem. Copyright © 2000 John Wiley & Sons, Ltd.     

A new technique of quaternion equality constrained least squares problem

By means of complex representation of a quaternion matrix, we study the relationship between the solutions of the quaternion equality constrained least squares problem and that of complex equality constrained least squares problem, and obtain a new technique of finding a solution of the quaternion equality constrained least squares problem.     

The structured total least‐squares approach for non‐linearly structured matrices

In this paper, an extension of the structured total least‐squares (STLS) approach for non‐linearly structured matrices is presented in the so‐called ‘Riemannian singular value decomposition’ (RiSVD) framework. It is shown that this type of STLS problem can be solved by solving a set of Riemannian SVD equations. For small perturbations the problem can be reformulated into finding the smallest singular value and the corresponding right singular vector of this Riemannian SVD. A heuristic algorithm is proposed. Some examples of Vandermonde‐type matrices are used to demonstrate the improved accuracy of the obtained parameter estimator when compared to other methods such as least squares (LS) or total least squares (TLS). Copyright © 2002 John Wiley & Sons, Ltd.