Publication: Sparsity in higher order methods for unconstrained optimization
Introduction
Applications
Tools
Research Groups
Workshops
Publications
   List Publications
   Advanced Search
   Info
   Add Publications
My Account
About

Sparsity in higher order methods for unconstrained optimization

- Article in a journal -
 

Author(s)
Geir Gundersen , Trond Steihaug

Published in
Optimization Methods and Software

Year
2012

Abstract
In this paper, we introduce data structures for storing the third derivative (tensor) of a multivariate scalar function when the second and third derivatives of the function are sparse. We consider solving unconstrained optimization problems using methods of the Halley class. The gradient, Hessian matrix and the tensor of the objective function are required for the methods and they have a third-order rate of convergence. However, these methods require the solution of two linear systems of equations at each iteration. Solving the linear systems using a factorization will cause fill-ins. The impact of these fill-ins will be discussed and we give the number of arithmetic operations of the methods of the Halley class compared to Newton's method. Finally, we will give some preliminary numerical results showing that including the time to compute the derivatives, the ratios of elapsed time of methods in the Halley class and Newton's method are close to the ratios of arithmetic operations.

AD Theory and Techniques
Higher Order, Sparsity

BibTeX
@ARTICLE{
         Gundersen2012Sih,
       author = "Gundersen, Geir and Steihaug, Trond",
       title = "Sparsity in higher order methods for unconstrained optimization",
       journal = "Optimization Methods and Software",
       volume = "27",
       number = "2",
       pages = "275--294",
       year = "2012",
       doi = "10.1080/10556788.2011.597853",
       url = "http://www.tandfonline.com/doi/abs/10.1080/10556788.2011.597853",
       eprint = "http://www.tandfonline.com/doi/pdf/10.1080/10556788.2011.597853",
       abstract = "In this paper, we introduce data structures for storing the third derivative
         (tensor) of a multivariate scalar function when the second and third derivatives of the function are
         sparse. We consider solving unconstrained optimization problems using methods of the Halley class.
         The gradient, Hessian matrix and the tensor of the objective function are required for the methods
         and they have a third-order rate of convergence. However, these methods require the solution of two
         linear systems of equations at each iteration. Solving the linear systems using a factorization will
         cause fill-ins. The impact of these fill-ins will be discussed and we give the number of arithmetic
         operations of the methods of the Halley class compared to Newton's method. Finally, we will
         give some preliminary numerical results showing that including the time to compute the derivatives,
         the ratios of elapsed time of methods in the Halley class and Newton's method are close to the
         ratios of arithmetic operations.",
       ad_theotech = "Higher Order, Sparsity"
}


back
  

Contact:
autodiff.org
Username:
Password:
(lost password)