Estimation of sparse hessian matrices and graph coloring problems

Large scale optimization problems often require an approximation to the Hessian matrix. If the Hessian matrix is sparse then estimation by differences of gradients is attractive because the number of required differences is usually small compared to the dimension of the problem. The problem of estimating Hessian matrices by differences can be phrased as follows: Given the sparsity structure of a symmetric matrixA, obtain vectorsd ₁,d ₂, …d _p such thatAd ₁,Ad ₂, …Ad _p determineA uniquely withp as small as possible. We approach this problem from a graph theoretic point of view and show that both direct and indirect approaches to this problem have a natural graph coloring interpretation. The complexity of the problem is analyzed and efficient practical heuristic procedures are developed. Numerical results illustrate the differences between the various approaches. Work supported in part by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38.     

An assessment of two approaches to variable metric methods

Two recent suggestions in the field of variable metric methods for function minimization are reviewed: the self-scaling method, first introduced by Oren and Luenberger, and the method of Biggs. The two proposals are considered both from a theoretical and computational aspect. They are compared with methods which use correction formulae from the Broyden one-parameter family, in particular the BFGS formula and the Fletcher switching strategy.     

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.     

Graph coloring in the estimation of sparse derivative matrices: Instances and applications

We describe a graph coloring problem associated with the determination of mathematical derivatives. The coloring instances are obtained as intersection graphs of row partitioned sparse derivative matrices. The size of the graph is dependent on the partition and can be varied between the number of columns and the number of nonzero entries. If solved exactly our proposal will yield a significant reduction in computational cost of the derivative matrices. The effectiveness of our approach is demonstrated via a practical problem from computational molecular biology. We also remark on the hardness of the generated coloring instances.     

On the global convergence of trust region algorithms for unconstrained minimization

Many trust region algorithms for unconstrained minimization have excellent global convergence properties if their second derivative approximations are not too large [2]. We consider how large these approximations have to be, if they prevent convergence when the objective function is bounded below and continuously differentiable. Thus we obtain a useful convergence result in the case when there is a bound on the second derivative approximations that depends linearly on the iteration number.     

Determinantal formulae for matrices with sparse inverses

The determinant of a matrix is expressed in terms of certain of its principal minors by a formula which can be “read off” from the graph of the inverse of the matrix. The only information used is the zero pattern of the inverse, and each zero pattern yields one or more corresponding formulae for the determinant.     

A new arc algorithm for unconstrained optimization

The gradient path of a real valued differentiable function is given by the solution of a system of differential equations. For a quadratic function the above equations are linear, resulting in a closed form solution. A quasi-Newton type algorithm for minimizing ann-dimensional differentiable function is presented. Each stage of the algorithm consists of a search along an arc corresponding to some local quadratic approximation of the function being minimized. The algorithm uses a matrix approximating the Hessian in order to represent the arc. This matrix is updated each stage and is stored in its Cholesky product form. This simplifies the representation of the arc and the updating process. Quadratic termination properties of the algorithm are discussed as well as its global convergence for a general continuously differentiable function. Numerical experiments indicating the efficiency of the algorithm are presented.     

An alternative variational principle for variable metric updating

We describe a variational principle based upon minimizing the extent to which the inverse hessian approximation, sayH, violates the quasi-Newton relation, on the step immediately prior to the step used to constructH. Its application to the case when line searches are exact suggests use of the BFGS update. This paper is based upon results first presented at the 1979 Mathematical Programming Symposium. Montreal, Canada.     

A quasi-Newton method can be obtained from a method of conjugate directions

In a recent paper McCormick and Ritter consider two classes of algorithms, namely methods of conjugate directions and quasi-Newton methods, for the problem of minimizing a function ofn variablesF(x). They show that the former methods possess ann-step superlinear rate of convergence while the latter are every step superlinear and therefore inherently superior. In this paper a simple and computationally inexpensive modification of a method of conjugate directions is presented. It is shown that the modified method is a quasi-Newton method and is thus every step superlinearly convergent. It is also shown that under certain assumptions on the second derivatives ofF the rate of convergence of the modified method isn-step quadratic.This work was supported by the National Research Council of Canada under Research Grant A8189.     

Multi-step quasi-Newton methods for optimization

Quasi-Newton methods update, at each iteration, the existing Hessian approximation (or its inverse) by means of data deriving from the step just completed. We show how “multi-step” methods (employing, in addition, data from previous iterations) may be constructed by means of interpolating polynomials, leading to a generalization of the “secant” (or “quasi-Newton”) equation. The issue of positive-definiteness in the Hessian approximation is addressed and shown to depend on a generalized version of the condition which is required to hold in the original “single-step” methods. The results of extensive numerical experimentation indicate strongly that computational advantages can accrue from such an approach (by comparison with “single-step” methods), particularly as the dimension of the problem increases.     

On a conjecture of Dixon and other topics in variable metric methods

A conjecture of Dixon relating to the behaviour of variable metric methods on functions with special symmetry is validated under suitable onditions. The relation between Huang's class and Oren's class is explored. Then the equivalence of Davidon's and Oren and Spedicato's approaches to optimal conditioning is demonstrated.     

Curvilinear path steplength algorithms for minimization which use directions of negative curvature

The Armijo and Goldstein step-size rules are modified to allow steps along a curvilinear path of the formx() + x + s + ² d, wherex is the current estimate of the minimum,s is a descent direction andd is a nonascent direction of negative curvature. By using directions of negative curvature when they exist, we are able to prove, under fairly mild assumptions, that the sequences of iterates produced by these algorithms converge to stationary points at which the Hessian matrix of the objective function is positive semidefinite.This grant was supported in part by the Army Research Office, Grant No. DAAG 29-77-G-0114.     

Computational experiments with scaled initial hessian approximation for the broyden family methods ∗

In this paper we consider two alternative choices for the factor used to scale the initial Hessian approximation, before updating by a member of the Broyden family of updates for quasi-Newton optimization methods. By extensive computational experiments carried out on a set of standard test problems from the CUTE collection, using efficient implemen-tations of the quasi-Newton method, we show that the proposed new scaling factors are better, in terms of efficiency achieved (number of iterations, number of function and gradient evaluations), than the standard choice proposed in the literature     

Determinantal formulae for matrices with sparse inverses,II: asymmetric zero patterns

In an earlier paper, formulae for det A as a ratio of products of principal minors of A were exhibited, for any given symmetric zero-pattern of A⁻¹. These formulae may be presented in terms of a spanning tree of the intersection graph of certain index sets associated with the zero pattern of A⁻¹. However, just as the determinant of a diagonal and of a triangular matrix are both the product of the diagonal entries, the symmetry of the zero pattern is not essential for these formulae. We describe here how analogous formulae for det A may be obtained in the asymmetric-zero-pattern case by introducing a directed spanning tree. We also examine the converse question of determining all possible zero patterns of A⁻¹ which guarantee that a certain determinantal formula holds.     

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.     

Optimization of unconstrained functions with sparse hessian matrices-newton-type methods

Newton-type methods for unconstrained optimization problems have been very successful when coupled with a modified Cholesky factorization to take into account the possible lack of positive-definiteness in the Hessian matrix. In this paper we discuss the application of these method to large problems that have a sparse Hessian matrix whose sparsity is known a priori. Quite often it is difficult, if not impossible, to obtain an analytic representation of the Hessian matrix. Determining the Hessian matrix by the standard method of finite-differences is costly in terms of gradient evaluations for large problems. Automatic procedures that reduce the number of gradient evaluations by exploiting sparsity are examined and a new procedure is suggested. Once a sparse approximation to the Hessian matrix has been obtained, there still remains the problem of solving a sparse linear system of equations at each iteration. A modified Cholesky factorization can be used. However, many additional nonzeros (fill-in) may be created in the factors, and storage problems may arise. One way of approaching this problem is to ignore fill-in in a systematic manner. Such technique are calledpartial factorization schemes. Various existing partial factorization are analyzed and three new ones are developed. The above algorithms were tested on a set of problems. The overall conclusions were that these methods perfom well in practice.     

A quasi-Newton trust-region method

The classical trust-region method for unconstrained minimization can be augmented with a line search that finds a point that satisfies the Wolfe conditions. One can use this new method to define an algorithm that simultaneously satisfies the quasi-Newton condition at each iteration and maintains a positive-definite approximation to the Hessian of the objective function. This new algorithm has strong global convergence properties and is robust and efficient in practice.     

Quasi-Newton acceleration for equality-constrained minimization

Optimality (or KKT) systems arise as primal-dual stationarity conditions for constrained optimization problems. Under suitable constraint qualifications, local minimizers satisfy KKT equations but, unfortunately, many other stationary points (including, perhaps, maximizers) may solve these nonlinear systems too. For this reason, nonlinear-programming solvers make strong use of the minimization structure and the naive use of nonlinear-system solvers in optimization may lead to spurious solutions. Nevertheless, in the basin of attraction of a minimizer, nonlinear-system solvers may be quite efficient. In this paper quasi-Newton methods for solving nonlinear systems are used as accelerators of nonlinear-programming (augmented Lagrangian) algorithms, with equality constraints. A periodically-restarted memoryless symmetric rank-one (SR1) correction method is introduced for that purpose. Convergence results are given and numerical experiments that confirm that the acceleration is effective are presented. This work was supported by FAPESP, CNPq, PRONEX-Optimization (CNPq / FAPERJ), FAEPEX, UNICAMP.