Automatic differentiation of hessian matrices

Author(s)

Robert Mansel Gower

• Document type: Master's Dissertation
• Press: Campinas, SP.
• Institution: Universidade Estadual de Campinas (UNICAMP). Instituto de Matemática, Estatística e Computação Científica
• Defense date: 2011-04-15

Examining board members

Margarida Pinheiro Mello; Aurelio Ribeiro Leite de Oliveira; Ernesto Julián Goldberg Birgin

• Advisor: Margarida Pinheiro Mello

Abstract

In the context of nonlinear programming, many algorithms boil down to the application of Newton's method to the system constituted by the first order Lagrangian conditions. The calculation of Hessian matrices is necessary in this class of solvers. Our focus is on the exact calculation, within machine precision, of Hessian matrices through automatic differentiation. To this end, we detail the calculations of the Hessian matrix under two points of view. The first is an intuitive graph model that focuses on what symmetries occur throughout the Hessian calculation. This provides insight on how one should calculate the Hessian matrix, and we use this enlightened perspective to deduce a new reverse Hessian algorithm called edge pushing. The second viewpoint is a purely algebraic representation of the Hessian calculation via a closed formula. This formula can be used to demonstrate existing algorithms and design new ones. In order to illustrate, we deduce two new algorithms, edge pushing and a new forward algorithm, and a series of other known Hessian methods [1], [20, p.157] and [9]. We present theoretical and empirical studies of the edge pushing algorithm, establishing memory and temporal bounds, and comparing the performance of its computer implementation against that of two algorithms available as drivers of the software ADOL-C [14, 19, 30] on sixteen functions from the CUTE collection [5]. Test results indicate that the new algorithm is very promising. As a by-product of the edge pushing algorithm, we obtain an efficient algorithm, edge pushing sp, for automatically obtaining the sparsity pattern of Hessian matrices, a necessary step in a class of methods used for computing Hessian matrices via graph coloring, [14, 19, 30]. Complexity bounds are developed and numerical tests are carried out comparing the new sparsity detection algorithm against a recently developed method [30] and the results favor the new edge pushing sp algorithm. In the final chapter, motivated by the increasing commercial availability of multiprocessors, we investigate the implementation of parallel versions of the edge pushing algorithm. We address the concurrent calculation of Hessian matrices of partially separable functions. This includes a general approach to be used in conjunction with any Hessian software, and a strategy specific to reverse Hessian methods. Tests are carried out on a shared memory computer using the OpenMP paradigm (AU)

• FAPESP's process: 09/04785-7 - Automatic differentiation of Hessian matrices
• Grantee: Robert Mansel Gower
• Support Opportunities: Scholarships in Brazil - Master