Optimization Online


On large scale unconstrained optimization problems and higher order methods

GEIR GUNDERSEN (geirg***at***ii.uib.no)
TROND STEIHAUG (trond***at***ii.uib.no)

Abstract: Third order methods will in most cases use fewer iterations than a second order method to reach the same accuracy. However, the number of arithmetic operations per iteration is higher for third order methods than a second order method. Newton's method is the most commonly used second order method and Halley's method is the most well-known third order method. Newton's method is more used in practical applications than any third order method. We will show that for a large class of problems the ratio of the number of arithmetic operations of Halley's method and Newton's method is constant per iteration. It is shown that \[\frac{\textrm{One Step Halley}}{\textrm{One Step Newton}} \leq 5.\] We show that the zero elements in the Hessian matrix induce zero elements in the tensor (third derivative). The sparsity structure in the Hessian matrix we consider is the skyline or envelope structure. This is a very convenient structure for solving linear systems of equations with a direct method. The class of matrices that have a skyline structure includes banded and dense matrices. Numerical testing confirm that the ratio of the number of arithmetic operations of a third order method and Newton's method is constant per iteration, and is independent of the number of unknowns.

Keywords: Unconstrained optimization problems, induced sparsity, higher order methods, tensor computations

Category 1: Nonlinear Optimization (Unconstrained Optimization )

Citation: This version will appear in Optimisation Methods and Software

Download: [PDF]

Entry Submitted: 03/12/2007
Entry Accepted: 03/12/2007
Entry Last Modified: 09/26/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society