Modeling Hessian-Vector Products in Nonlinear Optimization: New Hessian-Free Methods

Abstract

In this dissertation, two approaches are proposed to calculate interpolation models for unconstrained smooth nonlinear optimization when Hessian-vector products are available. The main idea is to interpolate the objective function by a quadratic, using function evaluations on a set of points around the current one, and concurrently using the curvature information from products of the Hessian times appropriate vectors, possibly defined by the interpolating points. The resulting enriched interpolating conditions form an affine space of the model Hessians or model Newton directions, from which a particular one can be computed once an equilibrium or least secant principle is defined. A first approach consists in recovering the model Hessian satisfying the enriched interpolating conditions, from which a Newton direction model can then be computed. In a second approach, the recovery problem is directly posed in terms of the Newton direction. These techniques can lead to a significant reduction in the overall number of Hessian-vector products when compared to the inexact or truncated Newton method, although simple implementations may pay an additional cost in the number of function evaluations, and the dense linear algebra involved may pose a scalability challenge. Further ideas on how to improve or generalize the main methodology are discussed, such as concurrent determination of both Newton direction and Hessian inverse, recovery of a modified Newton direction, and use of an iterative solver to compute the Newton direction model.

Nesta dissertação são propostas duas abordagens para calcular modelos de interpolação para optimização não linear suave sem restrições, num contexto em que se supõe ser possível fazer produtos Hessiana-vector. A ideia principal é interpolar a função objectivo por um modelo quadrático, usando os seus valores objectivos num conjunto de pontos em redor do corrente e, simultaneamente, usando a informação de curvatura proveniente dos produtos Hessiana-vector possivelmente definidos pelos pontos de interpolação. As condições de interpolação assim enriquecidas formam um espaço afim de modelos de Hessiana ou de modelos de direcções de Newton, no qual um determinado modelo pode ser calculado uma vez definido um princípio de equilíbrio ou de modificação de secante mínima. Uma primeira abordagem consiste em recuperar a matriz Hessiana-modelo que satisfaz as condições de interpolação enriquecidas, a partir da qual um modelo de direcção de Newton pode então ser calculado. Numa segunda abordagem, o problema da recuperação é colocado directamente em termos da direcção de Newton. Estas técnicas podem levar a uma redução significativa no número total de produtos Hessiana-vector, quando comparadas ao método de Newton inexacto ou truncado, embora implementações simples possam incorrer num custo acrescido de número de avaliações da função, e a álgebra linear densa envolvida constitua um desafio de escalabilidade. São discutidas ideias sobre como melhorar ou generalizar a metodologia principal, como a determinação simultânea da direcção de Newton e do inverso da Hessiana, a recuperação de uma direcção de Newton modificada e o uso de um método iterativo para calcular o modelo de direcção de Newton.