Quadratic and Superlinear Convergence of the Huschens Method for Nonlinear Least Squares Problems

This paper is concerned with quadratic and superlinear convergence of structured quasi-Newton methods for solving nonlinear least squares problems. These methods make use of a special structure of the Hessian matrix of the objective function. Recently, Huschens proposed a new kind of structured quasi-Newton methods and dealt with the convex class of the structured Broyden family, and showed its quadratic and superlinear convergence properties for zero and nonzero residual problems, respectively. In this paper, we extend the results by Huschens to a wider class of the structured Broyden family. We prove local convergence properties of the method in a way different from the proof by Huschens.     

A Hybrid Method for Nonlinear Least Squares Problems

A negative curvature method is applied to nonlinear least squares problems with indefinite Hessian approximation matrices. With the special structure of the method, a new switch is proposed to form a hybrid method. Numerical experiments show that this method is feasible and effective for zero-residual, small-residual and large-residual problems.     

Quasi-Newton Methods for Nonlinear Least Squares Focusing on Curvatures

A new quasi-Newton method for nonlinear least squares problems is proposed. Two advantages of the method are accomplished by utilizing special geometrical properties in the problem class. First, fast convergence is established for well-conditioned problems by interpolating both the current and the previous step in each iteration. Second, high accuracy is achieved for certain difficult problems, such as ill-conditioned problems and problems with large curvatures in the tangent space. Numerical results for artificial problems and standard test problems are presented and discussed.     

基于修正拟牛顿方程的两阶段非单调稀疏对角变尺度梯度投影算法

基于修正拟牛顿方程,利用Goldstein-Levitin-Polyak(GLP)投影技术,建立了求解带凸集约束的优化问题的两阶段步长非单调变尺度梯度投影算法,证明了算法的全局收敛性和一定条件下的Q超线性收敛速率.数值结果表明新算法是有效的,适合求解大规模问题.     

求解非线性互补问题的逐次逼近拟牛顿法的收敛性分析

提出了求解非线性互补问题的一个逐次逼近拟牛顿算法。在适当的假设下,证明了该算法的全局收敛性和局部超线性收敛性。     

用神经网络解非线性最小二乘问题

提出了一种求解非线性最小二乘问题的神经网络方法 ,并证明了该神经网络方法的稳定性和收敛性     

Analysis of the Structured Total Least Squares Problem for Hankel/Toeplitz Matrices

The Structured Total Least Squares (STLS) problem is a natural extension of the Total Least Squares (TLS) approach when structured matrices are involved and a similarly structured rank deficient approximation of that matrix is desired. In many of those cases the STLS approach yields a Maximum Likelihood (ML) estimate as opposed to, e.g., TLS.In this paper we analyze the STLS problem for Hankel matrices (the theory can be extended in a straightforward way to Toeplitz matrices, block Hankel and block Toeplitz matrices). Using a particular parametrisation of rank-deficient Hankel matrices, we show that this STLS problem suffers from multiple local minima, the properties of which depend on the parameters of the new parametrisation. The latter observation makes initial estimates an important issue in STLS problems and a new initialization method is proposed. The new initialization method is applied to a speech compression example and the results confirm the improved performance compared to other previously proposed initialization methods.     

基于Armijo线搜索的对角三阶拟柯西法

通过引入基于最小改变的对角修正策略,结合三阶拟牛顿方程,提出了基于Armijo线搜索的对角三阶拟柯西法.在适当的假设下,算法保证了修正矩阵的非奇异性,并证明了算法的线性收敛性.数值试验表明该算法是有效的.     

Solving Quadratically Constrained Least Squares Problems Using a Differential-Geometric Approach

A quadratically constrained linear least squares problem is usually solved using a Lagrange multiplier for the constraint and then solving iteratively a nonlinear secular equation for the optimal Lagrange multiplier. It is well-known that, due to the closeness to a pole for the secular equation, standard methods for solving the secular equation can be slow, and sometimes it is not easy to select a good starting value for the iteration. The problem can be reformulated as that of minimizing the residual of the least squares problem on the unit sphere. Using a differential-geometric approach we formulate Newton's method on the sphere, and thereby avoid the difficulties associated with the Lagrange multiplier formulation. This Newton method on the sphere can be implemented efficiently, and since it is easy to find a good starting value for the iteration, and the convergence is often quite fast, it has a clear advantage over the Lagrange multiplier method. A numerical example is given.     

求解加权线性最小二乘问题的预处理迭代方法

给出了求解一类加权线性最小二乘问题的预处理迭代方法,也就是预处理的广义加速超松弛方法（GAOR）,得到了一些收敛和比较结果．比较结果表明当原来的迭代方法收敛时,预处理迭代方法会比原来的方法具有更好的收敛率．而且,通过数值算例也验证了新预处理迭代方法的有效性．     

Backward Error Bounds for Constrained Least Squares Problems

We derive an upper bound on the normwise backward error of an approximate solution to the equality constrained least squares problem min _Bx=d b – Ax₂. Instead of minimizing over the four perturbations to A, b, B and d, we fix those to B and d and minimize over the remaining two; we obtain an explicit solution of this simplified minimization problem. Our experiments show that backward error bounds of practical use are obtained when B and d are chosen as the optimal normwise relative backward perturbations to the constraint system, and we find that when the bounds are weak they can be improved by direct search optimization. We also derive upper and lower backward error bounds for the problem of least squares minimization over a sphere: .     

无约束优化问题的对角稀疏拟牛顿法

对无约束优化问题提出了对角稀疏拟牛顿法,该算法采用了Armijo非精确线性搜索,并在每次迭代中利用对角矩阵近似拟牛顿法中的校正矩阵,使计算搜索方向的存贮量和工作量明显减少,为大型无约束优化问题的求解提供了新的思路．在通常的假设条件下,证明了算法的全局收敛性,线性收敛速度并分析了超线性收敛特征。数值实验表明算法比共轭梯度法有效,适于求解大型无约束优化问题．     

On Least Squares Estimation for Stable Nonlinear AR Processes

Following a Markov chain approach, this paper establishes asymptotic properties of the least squares estimator in nonlinear autoregressive (NAR) models. Based on conditions ensuring the stability of the model and allowing the use of a strong law of large number for a wide class of functions, our approach improves some known results on strong consistency and asymptotic normality of the estimator. The exact convergence rate is established by a law of the iterated logarithm. Based on this law and a generalized Akaike's information criterion, we build a strongly consistent procedure for selection of NAR models. Detailed results are given for familiar nonlinear AR models like exponential AR models, threshold models or multilayer feedforward perceptions.     

The Superlinear Convergence of a Modified BFGS-Type Method for Unconstrained Optimization

The BFGS method is the most effective of the quasi-Newton methods for solving unconstrained optimization problems. Wei, Li, and Qi [16] have proposed some modified BFGS methods based on the new quasi-Newton equation B _k+1 s _k = y* _k , where y* _k is the sum of y _k and A _k s _k, and A _k is some matrix. The average performance of Algorithm 4.3 in [16] is better than that of the BFGS method, but its superlinear convergence is still open. This article proves the superlinear convergence of Algorithm 4.3 under some suitable conditions.     

A Smoothing Newton Method for General Nonlinear Complementarity Problems

Smoothing Newton methods for nonlinear complementarity problems NCP(F) often require F to be at least a P ₀-function in order to guarantee that the underlying Newton equation is solvable. Based on a special equation reformulation of NCP(F), we propose a new smoothing Newton method for general nonlinear complementarity problems. The introduction of Kanzow and Pieper's gradient step makes our algorithm to be globally convergent. Under certain conditions, our method achieves fast local convergence rate. Extensive numerical results are also reported for all complementarity problems in MCPLIB and GAMSLIB libraries with all available starting points.     

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.     

一类新拟牛顿非单调信赖域算法

提出了一类新的求解无约束最优化问题的新拟牛顿非单调信赖域算法.采用加权的r_k用以调整信赖域半径,在适当的条件下,证明了算法的全局收敛性.数值结果表明算法的有效性.     

A Sequential Least Squares Method for Elliptic Equations in Non-Divergence Form

We develop a new least squares method for solving the second-order elliptic equations in non-divergence form. Two least-squares-type functionals are proposed for solving the equation in two sequential steps. We first obtain a numerical approximation to the gradient in a piecewise irrotational polynomial space. Then together with the numerical gradient, we seek a numerical solution of the primitive variable in the continuous Lagrange finite element space. The variational setting naturally provides an a posteriori error which can be used in an adaptive refinement algorithm. The error estimates under the $L^2$ norm and the energy norm for both two unknowns are derived. By a series of numerical experiments, we verify the convergence rates and show the efficiency of the adaptive algorithm.     

A Modified Quasi-Newton Method for Structured Optimization with Partial Information on the Hessian

This paper develops a modified quasi-Newton method for structured unconstrained optimization with partial information on the Hessian, based on a better approximation to the Hessian in current search direction. The new approximation is decided by both function values and gradients at the last two iterations unlike the original one which only uses the gradients at the last two iterations. The modified method owns local and superlinear convergence. Numerical experiments show that the proposed method is encouraging comparing with the methods proposed in [4] for structured unconstrained optimization Presented at the 6th International Conference on Optimization: Techniques and Applications, Ballarat, Australia, December 9–11, 2004     

关于K-S方程的非线性伽辽金方法(英文)

该文讨论了关于 K- S方程的伽辽金方法和非线性伽辽金方法的收敛性和 L2 误差估计 ,并得出误差阶一致的结论