On the Use of Restricted Pseudo-inverses for the Unified Derivation of Quasi-Newton Updates

A new approach for deriving minimum norm quasi-Newton updatesis given. We use restricted pseudo-inverses of a single linearoperator to derive all known useful minimum norm updates, includingthose preserving sparsity and symmetry. This approach is direct,and unifies the theory of minimum norm quasi-Newton updates.We also prove a generalization of a theorem of Dennis &Schnabel using this approach.     

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 GENERALIZED QUASI-NEWTON EQUATION AND COMPUTATIONAL EXPERIENCE

The quasi-Newton equation has played a central role in the quasi-Newton methods forsolving systems of nonlinear equations and/or unconstrained optimization problems.In-stead,Pan suggested a new equation,and showed that it is of the second order while thetraditional of the first order,in certain approximation sense[12].In this paper,we makea generalization of the two equations to include them as special cases.The generalizedequation is analyzed,and new updates are derived from it.A DFP-like new update out-performed the traditional DFP update in computational experiments on a set of standardtest problems.     

Adjoint-based quasi-Newton methods for partially separable problems

In this paper the concepts of partitioned quasi-Newton methods are applied to adjoint Broyden updates. Consequently a corresponding partitioned adjoint Broyden update is presented and local convergence results are given. Numerical results compare the partitioned adjoint Broyden update methods to the corresponding unpartitioned quasi-Newton method and to Newton's method for nonlinear equations. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

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.     

Metric-Based Symmetric Rank-One Updates

Metric-based SR1 updates which are stabilized by a variationalrelaxation of the quasi-Newton relation are examined. Thisinvestigation reveals an interesting and surprising connection to theorigin of quasi-Newton methods as first formulated by Davidon [1]. Anextended version of Davidon's original direct prediction SR1 updateis shown to be self-complementary and to possess a finite terminationproperty on quadratics, and limited-memory versions of the update areshown to be globally convergent. Variants of this update are testednumerically and compared to several other metric-based SR1 variantsand the BFGS update. Finally, metric-based stabilizations of the SR1update are critiqued in general, and a promising new model-basedstrategy recently developed is briefly described.     

A note on quasi-newton formulae for sparse second derivative matrices

In order to apply quasi-Newton methods to solve unconstrained minimization calculations when the number of variables is very large, it is usually necessary to make use of any sparsity in the second derivative matrix of the objective function. Therefore, it is important to extend to the sparse case the updating formulae that occur in variable metric algorithms to revise the estimate of the second derivative matrix. Suitable extensions suggest themselves when the updating formulae are derived by variational methods [1, 3]. The purpose of the present paper is to give a new proof of a theorem of Dennis and Schnabel [1], that shows the effect of sparsity on updating formulae for second derivative estimates.     

A Modified BFGS Formula Maintaining Positive Definiteness with Armijo-Goldstein Steplengths

1.IntroductionAlinesearchmethodforminimizingarealfunctionfgeneratesasequencex1,x2,.-.ofpointsbyapplyingtheiterationxk+i=xk+akpk,k=1,2,....(1)Inaquasi-NewtonmethodthesearchdirectionpkischosensothatBkpk=-gk,whereBkis(usually)apositivedefiIiltematrirandgkdenotesVf(xk)-FortheBFGSupdate,(see[21,forexample),thematricesBkaredefinedbytheformulawheresk=xk+1-xkandyk=gk+1-gk'ItiswellknownthatifB1ispositivedefiniteands[Y*>O(3)thenallmatricesBk+1,k=1,2,...generatedby(2)arepositivedefiinte.Thuspkisadi…     

对称矩阵分解因子的直接换元修正法

§1.引言 考虑非线性方程组 F(x)=0, (1)其中F:Ω?R~n→R~n使F′(x)对称.本文给出求解(1)的一种分解修正法,这种方法始于Jacobian F′(x)的初始对称三角分解,然后利用换元技巧直接修正上三角分解因子,进而前代与回代求迭代点.本文分析了分解修正法的运算量,证明了这个算法不用重新启动仍具有局部超线性收敛性和大范围收敛性.此外,这个算法自然保持分解因子的稀疏传递性和修正矩阵的对称传递性,特别当Jacobian正定时,还具有正定传递性.由此本文完成了[1]和[2]无法完成的工作.本算法特别适于大规模带状方程组和最优化问题,数值例子也表明了这一点.     

A Survey of Quasi-Newton Equations and Quasi-Newton Methods for Optimization

Quasi-Newton equations play a central role in quasi-Newton methods for optimization and various quasi-Newton equations are available. This paper gives a survey on these quasi-Newton equations and studies properties of quasi-Newton methods with updates satisfying different quasi-Newton equations. These include single-step quasi-Newton equations that use only gradient information and that use both gradient and function value information in one step, and multi-step quasi-Newton equations that use the gradient information in last m steps. Main properties of quasi-Newton methods with updates satisfying different quasi-Newton equations are studied. These properties include the finite termination property, invariance, heredity of positive definite updates, consistency of search directions, global convergence and local superlinear convergence properties.     

Family of optimally conditioned quasi-Newton updates for unconstrained optimization

In this note, a general optimal conditioning problem for updates which satisfy the quasi-Newton equation is solved. The new solution is a family of updates which contains other known optimally conditioned updates but also includes new formulas of increased rank. A new factorization formula for the Broyden family and some preliminary numerical results are also given.     

Non-Quasi-Newton Updates for Unconstrained Optimization

1.IntroductionUnconstrainedoptimizationistominimizeanonlinearfunctionf(x)inafinit('dimensionalspace3thatisNewton'smethodforproblem(l.1)isiterativeandatthek-thiterationacllrreIltaDDroximationsolutionxLisavailable.TheNewtonsteDatthek-thiterationis'OneadvantageofNewton'smethodisthatitconvergencequadratically-Assumex*isastationarypOintof(1.1)atwhichV'f(X*)isnon-singular.ThenforxksuffiCientlyclosetox*wehavethatHoweverNewton'smethodalsohassomediSadvantages.FirstlytheHessianV'f(xk)maybesingul…     

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.     

Optimization of unconstrained functions with sparse Hessian matrices—Quasi-Newton methods

Newton-type methods and quasi-Newton methods have proven to be very successful in solving dense unconstrained optimization problems. Recently there has been considerable interest in extending these methods to solving large problems when the Hessian matrix has a known a priori sparsity pattern. This paper treats sparse quasi-Newton methods in a uniform fashion and shows the effect of loss of positive-definiteness in generating updates. These sparse quasi-Newton methods coupled with a modified Cholesky factorization to take into account the loss of positive-definiteness when solving the linear systems associated with these methods were tested on a large set of problems. The overall conclusions are that these methods perform poorly in general—the Hessian matrix becomes indefinite even close to the solution and superlinear convergence is not observed in practice. Research for this paper was performed at the Department of Operations Research, Stanford, CA 94305. The research was partially supported by the Department of Energy Contract AM03-76SF00326. PA# DE-AT03-76ER72018: Office of Naval Research Contract N00014-75-C-0267; National Science Foundation Grants MCS-7681259, MCS-7926009 and ECS-8012974.     

Improved Hessian approximation with modified secant equations for symmetric rank-one method

Symmetric rank-one (SR1) is one of the competitive formulas among the quasi-Newton (QN) methods. In this paper, we propose some modified SR1 updates based on the modified secant equations, which use both gradient and function information. Furthermore, to avoid the loss of positive definiteness and zero denominators of the new SR1 updates, we apply a restart procedure to this update. Three new algorithms are given to improve the Hessian approximation with modified secant equations for the SR1 method. Numerical results show that the proposed algorithms are very encouraging and the advantage of the proposed algorithms over the standard SR1 and BFGS updates is clearly observed.     

A factorization with update procedures for a KKT matrix arising in direct optimal control

Quadratic programs obtained for optimal control problems of dynamic or discrete-time processes usually involve highly block structured Hessian and constraints matrices, to be exploited by efficient numerical methods. In interior point methods, this is elegantly achieved by the widespread availability of advanced sparse symmetric indefinite factorization codes. For active set methods, however, conventional dense matrix techniques suffer from the need to update base matrices in every active set iteration, thereby loosing the sparsity structure after a few updates. This contribution presents a new factorization of a KKT matrix arising in active set methods for optimal control. It fully respects the block structure without any fill-in. For this factorization, matrix updates are derived for all cases of active set changes. This allows for the design of a highly efficient block structured active set method for optimal control and model predictive control problems with long horizons or many control parameters.     

An SR1/BFGS SQP algorithm for nonconvex nonlinear programs with block-diagonal Hessian matrix

We present a quasi-Newton sequential quadratic programming (SQP) algorithm for nonlinear programs in which the Hessian of the Lagrangian function is block-diagonal. Problems with this characteristic frequently arise in the context of optimal control; for example, when a direct multiple shooting parametrization is used. In this article, we describe an implementation of a filter line-search SQP method that computes search directions using an active-set quadratic programming (QP) solver. To take advantage of the block-diagonal structure of the Hessian matrix, each block is approximated separately by quasi-Newton updates. For nonconvex instances, that arise, for example, in optimum experimental design control problems, these blocks are often found to be indefinite. In that case, the block-BFGS quasi-Newton update can lead to poor convergence. The novel aspect in this work is the use of SR1 updates in place of BFGS approximations whenever possible. The resulting indefinite QPs necessitate an inertia control mechanism within the sparse Schur-complement factorization that is carried out by the active-set QP solver. This permits an adaptive selection of the Hessian approximation that guarantees sufficient progress towards a stationary point of the problem. Numerical results demonstrate that the proposed approach reduces the number of SQP iterations and CPU time required for the solution of a set of optimal control problems.     

Some numerical experiments with variable-storage quasi-Newton algorithms

This paper describes some numerical experiments with variable-storage quasi-Newton methods for the optimization of some large-scale models (coming from fluid mechanics and molecular biology). In addition to assessing these kinds of methods in real-life situations, we compare an algorithm of A. Buckley with a proposal by J. Nocedal. The latter seems generally superior, provided that careful attention is given to some nontrivial implementation aspects, which concern the general question of properly initializing a quasi-Newton matrix. In this context, we find it appropriate to use a diagonal matrix, generated by an update of the identity matrix, so as to fit the Rayleigh ellipsoid of the local Hessian in the direction of the change in the gradient.Also, a variational derivation of some rank one and rank two updates in Hilbert spaces is given.Work supported in part by FNRS (Fonds National de la Recherche Scientifique), Belgium.     

Inertia-preserving secant updates

A class of rank-two, inertia-preserving updates for symmetric matricesH _c is studied. To ensure that inertia is preserved, the updates are chosen to be of the formH ₊=FH _c F ^t, whereF=I+qr ^t, withq andr selected so that the secant equation is satisfied. A characterization is given for all such updates. Using a parameterization of this family of updates, the connection between them and the Broyden class of updates is established. Also, parameter selection criteria that can be used to choose the optimally conditioned update or the update closest to the SR1 update are discussed.The work of the first author was partially supported by AFOSR Grant 84-0326. The work of the second author was partially supported by NSF Grant EAR-82-18743.     

A Kantorovich Theorem for the Structured PSB Update in Hilbert Space

The convergence behavior of quasi-Newton methods has been well investigated for many update rules. One exception that has to be examined is the PSB update in Hilbert space. Analogous to the SR1 update, the PSB update takes advantage of the symmetry property of the operator, but it does not require the positive definiteness of the operator to work with. These properties are of great practical importance, for example, to solve minimization problems where the starting operator is not positive definite, which is necessary for other updates to ensure local convergence. In this paper, a Kantorovich theorem is presented for a structured PSB update in Hilbert space, where the structure is exploited in the sense of Dennis and Walker. Finally, numerical implications are illustrated by various results on an optimal shape design problem.