An example of slow convergence for Newton's method on a function with globally Lipschitz continuous Hessian

Coralia Cartis, N. I. M. Gould, Ph Toint

Résultats de recherche: Papier de travailArticle de travail

63 Downloads (Pure)

Résumé

An example is presented where Newton's method for unconstrained minimization is applied to find an $\epsilon$-approximate first-order critical point of a smooth function and takes a multiple of $\epsilon^{-2}$ iterations and function evaluations to terminate, which is as many as the steepest-descent method in its worst-case. The novel feature of the proposed example is that the objective function has a globally Lipschitz-continuous Hessian, while a previous example published by the same authors only ensured this critical property along the path of iterates, which is impossible to verify \emph{a priori}.
langue originaleAnglais
ÉditeurNamur center for complex systems
Nombre de pages9
Volume03-2013
étatPublié - 5 mai 2013

Empreinte digitale

Unconstrained Minimization
Steepest Descent Method
Evaluation Function
Terminate
Iterate
Smooth function
Newton Methods
Lipschitz
Critical point
Objective function
Verify
First-order
Iteration
Path

Citer ceci

@techreport{e27e485775a84fc9b51945a547e8afa4,
title = "An example of slow convergence for Newton's method on a function with globally Lipschitz continuous Hessian",
abstract = "An example is presented where Newton's method for unconstrained minimization is applied to find an $\epsilon$-approximate first-order critical point of a smooth function and takes a multiple of $\epsilon^{-2}$ iterations and function evaluations to terminate, which is as many as the steepest-descent method in its worst-case. The novel feature of the proposed example is that the objective function has a globally Lipschitz-continuous Hessian, while a previous example published by the same authors only ensured this critical property along the path of iterates, which is impossible to verify \emph{a priori}.",
keywords = "Complexity theory, nonlinear optimization, Newton method",
author = "Coralia Cartis and Gould, {N. I. M.} and Ph Toint",
year = "2013",
month = "5",
day = "5",
language = "English",
volume = "03-2013",
publisher = "Namur center for complex systems",
type = "WorkingPaper",
institution = "Namur center for complex systems",

}

An example of slow convergence for Newton's method on a function with globally Lipschitz continuous Hessian. / Cartis, Coralia; Gould, N. I. M.; Toint, Ph.

Namur center for complex systems, 2013.

Résultats de recherche: Papier de travailArticle de travail

TY - UNPB

T1 - An example of slow convergence for Newton's method on a function with globally Lipschitz continuous Hessian

AU - Cartis, Coralia

AU - Gould, N. I. M.

AU - Toint, Ph

PY - 2013/5/5

Y1 - 2013/5/5

N2 - An example is presented where Newton's method for unconstrained minimization is applied to find an $\epsilon$-approximate first-order critical point of a smooth function and takes a multiple of $\epsilon^{-2}$ iterations and function evaluations to terminate, which is as many as the steepest-descent method in its worst-case. The novel feature of the proposed example is that the objective function has a globally Lipschitz-continuous Hessian, while a previous example published by the same authors only ensured this critical property along the path of iterates, which is impossible to verify \emph{a priori}.

AB - An example is presented where Newton's method for unconstrained minimization is applied to find an $\epsilon$-approximate first-order critical point of a smooth function and takes a multiple of $\epsilon^{-2}$ iterations and function evaluations to terminate, which is as many as the steepest-descent method in its worst-case. The novel feature of the proposed example is that the objective function has a globally Lipschitz-continuous Hessian, while a previous example published by the same authors only ensured this critical property along the path of iterates, which is impossible to verify \emph{a priori}.

KW - Complexity theory, nonlinear optimization, Newton method

M3 - Working paper

VL - 03-2013

BT - An example of slow convergence for Newton's method on a function with globally Lipschitz continuous Hessian

PB - Namur center for complex systems

ER -