Please use this identifier to cite or link to this item: http://hdl.handle.net/10316/98611
Title: Modeling Hessian-Vector Products in Nonlinear Optimization: New Hessian-Free Methods
Authors: Song, Lili
Orientador: Vicente, Luís Filipe de Castro Nunes
Gouveia, João
Keywords: nonlinear/nonconvex optimization; Hessian-vector products; Newton direction; Hessian recovery; quadratic interpolation; Optimização Não Linear / Não Convexa; Produtos Hessiana-Vector; Direcção de Newton; Recuperação de Hessiana; Interpolação Quadrática
Issue Date: 4-Jan-2022
Project: FCT/Portugal: PD/BI/128105/2016 and UID/MAT/00324/2019 to L.S. 
FCT/Portugal: UID/MAT/00324/2019 to L.N.V. 
FCT/Portugal: P2020 SAICTPAC/0011/2015 to L.N.V. 
Place of publication or event: Coimbra
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.
Description: Tese no âmbito do Programa Inter-Universitário de Doutoramento em Matemática apresentada à Faculdade de Ciências e Tecnologia da Universidade de Coimbra.
URI: http://hdl.handle.net/10316/98611
Rights: openAccess
Appears in Collections:FCTUC Matemática - Teses de Doutoramento
UC - Teses de Doutoramento

Files in This Item:
File Description SizeFormat
thesis_lili.pdf827.85 kBAdobe PDFView/Open
Show full item record

Page view(s)

51
checked on Sep 16, 2022

Download(s)

30
checked on Sep 16, 2022

Google ScholarTM

Check


This item is licensed under a Creative Commons License Creative Commons