On the local convergence of adjoint Broyden methods

The numerical solution of nonlinear equation systems is often achieved by so-called quasi-Newton methods. They preserve the rapid local convergence of Newton’s method at a significantly reduced cost per step by successively approximating the system Jacobian though low-rank updates. We analyze two variants of the recently proposed adjoint Broyden update, which for the first time combines the classical least change property with heredity on affine systems. However, the new update does require, the evaluation of so-called adjoint vectors, namely products of the transposed Jacobian with certain dual direction vectors. The resulting quasi-Newton method is linear contravariant in the sense of Deuflhard (Newton methods for nonlinear equations. Springer, Heidelberg, 2006) and it is shown here to be locally and q-superlinearly convergent. Our numerical results on a range of test problems demonstrate that the new method usually outperforms Newton’s and Broyden’s method in terms of runtime and iterations count, respectively. Partially supported by the DFG Research Center Matheon “Mathematics for Key Technologies”, Berlin and the DFG grant WA 1607/2-1.     

On the solution of highly structured nonlinear equations

We introduce a quasi-Newton update for nonlinear equations which have a Jacobian with sparse triangular factors and consider its application, through an algorithm of Deuflhard, to the solution of boundary value problems by multiple shooting.     

一种新的修正SR1更新公式及其算法收敛性

SR1更新公式对比其他的拟牛顿更新公式,会更加简单且每次迭代需要更少的计算量。但是一般SR1更新公式的收敛性质是在一致线性无关这一很强的条件下证明的。基于前人的研究成果,提出了一种新的修正SR1公式,并分别证明了其在一致线性无关和没有一致线性无关这两个条件下的局部收敛性,最后通过数值实验验证了提出的更新公式的有效性,以及所作出假设的合理性。根据实验数据显示,在某些条件下基于所提出更新公式的拟牛顿算法会比基于传统的SR1更新公式的算法收敛效果更好一些。     

超越方程的优化解法

针对粒子群算法局部搜索能力差,后期收敛速度慢等缺点,提出了一种改进的粒子群算法,该算法是在粒子群算法后期加入拟牛顿方法,充分发挥了粒子群算法的全局搜索性和拟牛顿法的局部精细搜索性,从而克服了粒子群算法的不足,把超越方程转化为函数优化的问题,利用该算法求解,数值实验结果表明,算法有较高的收敛速度和求解精度。     

Algorithms for solving nonlinear dynamic decision models

In this paper we discuss two Newton-type algorithms for solving economic models. The models are preprocessed by reordering the equations in order to minimize the dimension of the simultaneous block. The solution algorithms are then applied to this block. The algorithms evaluate numerically, as required, selected columns of the Jacobian of the simultaneous part. Provisions also exist for similar systems to be solved, if possible, without actually reinitialising the Jacobian. One of the algorithms also uses the Broyden update to improve the Jacobian. Global convergence is maintained by an Armijo-type stepsize strategy.The global and local convergence of the quasi-Newton algorithm is discussed. A novel result is established for convergence under relaxed descent directions and relating the achievement of unit stepsizes to the accuracy of the Jacobian approximation. Furthermore, a simple derivation of the Dennis-Moré characterisation of the Q-superlinear convergence rate is given.The model equation reordering algorithm is also described. The model is reordered to define heart and loop variables. This is also applied recursively to the subgraph formed by the loop variables to reduce the total number of above diagonal elements in the Jacobian of the complete system. The extension of the solution algorithms to consistent expectations are discussed. The algorithms are compared with Gauss-Seidel SOR algorithms using the USA and Spanish models of the OECD Interlink system.     

A Structured Secant Method Based on a New Quasi-Newton Equation for Nonlinear Least Squares Problems

In this paper, a new quasi-Newton equation is applied to the structured secant methods for nonlinear least squares problems. We show that the new equation is better than the original quasi-Newton equation as it provides a more accurate approximation to the second order information. Furthermore, combining the new quasi-Newton equation with a product structure, a new algorithm is established. It is shown that the resulting algorithm is quadratically convergent for the zero-residual case and superlinearly convergent for the nonzero-residual case. In order to compare the new algorithm with some related methods, our preliminary numerical experiments are also reported.     

Convergence of quasi-Newton method with new inexact line search

Quasi-Newton method is a well-known effective method for solving optimization problems. Since it is a line search method, which needs a line search procedure after determining a search direction at each iteration, we must decide a line search rule to choose a step size along a search direction. In this paper, we propose a new inexact line search rule for quasi-Newton method and establish some global convergent results of this method. These results are useful in designing new quasi-Newton methods. Moreover, we analyze the convergence rate of quasi-Newton method with the new line search rule.     

非单调广义对角拟牛顿算法

本文研究了无约束最优化的求解问题.利用新的对角拟牛顿校正和非单调技术,获得了一种非单调广义对角拟牛顿算法.新算法具有低存储、低计算量的特点,非常适合大规模问题的求解,推广了文献[8]的结果.     

A QP-FREE AND SUPERLINEARLY CONVERGENT ALGORITHM FOR INEQUALITY CONSTRAINED OPTIMIZATIONS

1 IntroductionConsider tl1e optimizatioll problemndn{f(x): gj(x) 5 0, j e I, x E R"}, j1)where f(x), gj(x): R" - R, j E I = {l,2,...,m}.We know tl1e quasi-Newton meth.d[1]'[9]1[5]1[1O1 is one of the most effective methods to solveproblenl (1) due to its property of superlinear convergence and is still all hot topic at presenttime, which attracts a Iot of authors to make iInprovemellt both in theory a1ld app1ication.Fechinei and Lucidi[3] in 1995 proposed a locally superlinearly convergell…     

A Switching Algorithm Based on Modified Quasi-Newton Equation

In this paper, a switching method for unconstrained minimization is proposed. The method is based on the modified BFGS method and the modified SR1 method. The eigenvalues and condition numbers of both the modified updates are evaluated and used in the switching rule. When the condition number of the modified SR1 update is superior to the modified BFGS update, the step in the proposed quasi-Newton method is the modified SR1 step. Otherwise the step is the modified BFGS step. The efficiency of the proposed method is tested by numerical experiments on small, medium and large scale optimization. The numerical results are reported and analyzed to show the superiority of the proposed method.     

Pointwise quasi-Newton method for unconstrained optimal control problems,II

In this paper, the necessary optimality conditions for an unconstrained optimal control problem are used to derive a quasi-Newton method where the update involves only second-order derivative terms. A pointwise update which was presented in a previous paper by the authors is changed to allow for more general second-order sufficiency conditions in the control problem. In particular, pointwise versions of the Broyden, PSB, and SR1 update are considered. A convergence rate theorem is given for the Broyden and PSB versions.This research was supported by NSF Grant No. DMS-89-00410, by NSF Grant No. INT-88-00560, by AFOSR Grant No. AFOSR-89-0044, and by the Deutsche Forschungsgemeinschaft.     

The least prior deviation quasi-Newton update

We propose a new choice for the parameter in the Broyden class and derive and discuss properties of the resulting self-complementary quasi-Newton update. Our derivation uses a variational principle that minimizes the extent to which the quasi-Newton relation is violated on a prior step. We discuss the merits of the variational principle used here vis-a-vis the other principle in common use, which minimizes deviation from the current Hessian or Hessian inverse approximation in an appropriate Frobenius matrix norm. One notable advantage of our principle is an inherent symmetry that results in the same update being obtained regardless of whether the Hessian matrix or the inverse Hessian matrix is updated.We describe the relationship of our update to the BFGS, SR1 and DFP updates under particular assumptions on line search accuracy, type of function being minimized (quadratic or nonquadratic) and norm used in the variational principle.Some considerations concerning implementation are discussed and we also give a numerical illustration based on an experimental implementation using MATLAB.Corresponding author.     

New quasi-Newton methods via higher order tensor models

Many researches attempt to improve the efficiency of the usual quasi-Newton (QN) methods by accelerating the performance of the algorithm without causing more storage demand. They aim to employ more available information from the function values and gradient to approximate the curvature of the objective function. In this paper we derive a new QN method of this type using a fourth order tensor model and show that it is superior with respect to the prior modification of Wei et al. (2006) [4]. Convergence analysis gives the local convergence property of this method and numerical results show the advantage of the modified QN method.     

Some remarks on the symmetric rank-one update

We consider the symmetric rank-one, quasi-Newton formula. The hereditary properties of this formula do not require quasi-Newton directions of search. Therefore, this formula is easy to use in constrained optimization algorithms; no explicit projections of either the Hessian approximations or the parameter changes are required. Moreover, the entire Hessian approximation is available at each iteration for determining the direction of search, which need not be a quasi-Newton direction. Theoretical difficulties, however, exist. Even for a positive-definite, quadratic function with no constraints, it is possible that the symmetric rank-one update may not be defined at some iteration. In this paper, we first demonstrate that such failures of definition correspond to either losses of independence in the directions of search being generated or to near-singularity of the Hessian approximation being generated. We then describe a procedure that guarantees that these updates are well-defined for any nonsingular quadratic function. This procedure has been incorporated into an algorithm for minimizing a function subject to box constraints. Box constraints arise naturally in the minimization of a function with many minima or a function that is defined only in some subregion of the space.     

A Memoryless Augmented Gauss-Newton Method for Nonlinear Least-Squares Problems

In this paper, we develop, analyze, and test a new algorithm for nonlinear least-squares problems. The algorithm uses a BFGS update of the Gauss-Newton Hessian when some heuristics indicate that the Gauss-Newton method may not make a good step. Some important elements are that the secant or quasi-Newton equations considered are not the obvious ones, and the method does not build up a Hessian approximation over several steps. The algorithm can be implemented easily as a modification of any Gauss-Newton code, and it seems to be useful for large residual problems.     

Symmetric minimum-norm updates for use in gibbs free energy calculations

This paper examines a type of symmetric quasi-Newton update for use in nonlinear optimization algorithms. The updates presented here impose additional properties on the Hessian approximations that do not result if the usual quasi-Newton updating schemes are applied to certain Gibbs free energy minimization problems. The updates derived in this paper are symmetric matrices that satisfy a given matrix equation and are least squares solutions to the secant equation. A general representation for this class of updates is given. The update in this class that has the minimum weighted Frobenius norm is also presented. This work was done at Sandia National Laboratories and supported by the US Dept. of Energy under contract no. DE-AC04-76DP00789.     

A combined conjugate-gradient quasi-Newton minimization algorithm

Although quasi-Newton algorithms generally converge in fewer iterations than conjugate gradient algorithms, they have the disadvantage of requiring substantially more storage. An algorithm will be described which uses an intermediate (and variable) amount of storage and which demonstrates convergence which is also intermediate, that is, generally better than that observed for conjugate gradient algorithms but not so good as in a quasi-Newton approach. The new algorithm uses a strategy of generating a form of conjugate gradient search direction for most iterations, but it periodically uses a quasi-Newton step to improve the convergence. Some theoretical background for a new algorithm has been presented in an earlier paper; here we examine properties of the new algorithm and its implementation. We also present the results of some computational experience.This research was supported by the National Research Council of Canada grant number A-8962.     

Conjugate direction methods with variable storage

In this paper we study conjugate gradient algorithms for large optimization problems. These methods accelerate (or precondition) the conjugate gradient method by means of quasi-Newton matrices, and are designed to utilize a variable amount of storage, depending on how much information is retained in the quasi-Newton matrices. We are concerned with the behaviour of such methods on the underlying quadratic model, and in particular, with finite termination properties.     

一类改进BFGS算法及其收敛性分析

本文针对无约束最优化问题,基于目标函数的局部二次模型近似,提出一类改进的BFGS算法,称为 MBFGS算法。其修正 B_k的公式中含有一个参数θ∈[0,l],当 θ= 1时即得经典的BFGS公式;当θ∈[0、l）时,所得公式已不属于拟Newton类。在目标函数一致凸假设下,证明了所给算法的全局收敛性及局部超线性收敛性。     

Limited memory quasi-newton method for large-scale linearly equality-constrained minimization

1. IntroductionConsider the following linearly constrained nonlinear programming problemwhere x e R", A E Rmxn and f E C2. We are interested in the case when n and m arelarge and when the Hessian matrix of f is difficult to compute or is dense. It is ajssumed thatA is a matrix of full row rank and that the level set S(xo) = {x: f(x) 5 f(xo), Ax ~ b} isnonempty and compact.In the past few years j there were two kinds of methods for solving the large-scaleproblem (1.1). FOr the one kind, pr…