Simple examples for the failure of Newton’s method with line search for strictly convex minimization

Florian Jarre, Philippe L. Toint

Research output: Contribution to journalArticle

Abstract

In this paper two simple examples of a twice continuously differentiable strictly convex function (Formula presented.) are presented for which Newton’s method with line search converges to a point where the gradient of (Formula presented.) is not zero. The first example uses a line search based on the Wolfe conditions. For the second example, some strictly convex function (Formula presented.) is defined as well as a sequence of descent directions for which exact line searches do not converge to the minimizer of (Formula presented.). Then (Formula presented.) is perturbed such that these search directions coincide with the Newton directions for the perturbed function while leaving the exact line search invariant.

Original languageEnglish
Pages (from-to)23-34
JournalMathematical Programming
Volume158
Issue number1
DOIs
Publication statusPublished - Jun 2016

Fingerprint

Convex Minimization
Line Search
Strictly Convex
Newton-Raphson method
Newton Methods
Convex function
Converge
Continuously differentiable
Descent
Minimizer
Gradient
Invariant
Zero

Keywords

  • Convex minimization
  • Line search
  • Newton’s method
  • Wolfe conditions

Cite this

@article{d19d58d6f7d844ab90188652664d92e8,
title = "Simple examples for the failure of Newton’s method with line search for strictly convex minimization",
abstract = "In this paper two simple examples of a twice continuously differentiable strictly convex function (Formula presented.) are presented for which Newton’s method with line search converges to a point where the gradient of (Formula presented.) is not zero. The first example uses a line search based on the Wolfe conditions. For the second example, some strictly convex function (Formula presented.) is defined as well as a sequence of descent directions for which exact line searches do not converge to the minimizer of (Formula presented.). Then (Formula presented.) is perturbed such that these search directions coincide with the Newton directions for the perturbed function while leaving the exact line search invariant.",
keywords = "Convex minimization, Line search, Newton’s method, Wolfe conditions",
author = "Florian Jarre and Toint, {Philippe L.}",
year = "2016",
month = "6",
doi = "10.1007/s10107-015-0913-2",
language = "English",
volume = "158",
pages = "23--34",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer-Verlag GmbH and Co. KG",
number = "1",

}

Simple examples for the failure of Newton’s method with line search for strictly convex minimization. / Jarre, Florian; Toint, Philippe L.

In: Mathematical Programming, Vol. 158, No. 1, 06.2016, p. 23-34.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Simple examples for the failure of Newton’s method with line search for strictly convex minimization

AU - Jarre, Florian

AU - Toint, Philippe L.

PY - 2016/6

Y1 - 2016/6

N2 - In this paper two simple examples of a twice continuously differentiable strictly convex function (Formula presented.) are presented for which Newton’s method with line search converges to a point where the gradient of (Formula presented.) is not zero. The first example uses a line search based on the Wolfe conditions. For the second example, some strictly convex function (Formula presented.) is defined as well as a sequence of descent directions for which exact line searches do not converge to the minimizer of (Formula presented.). Then (Formula presented.) is perturbed such that these search directions coincide with the Newton directions for the perturbed function while leaving the exact line search invariant.

AB - In this paper two simple examples of a twice continuously differentiable strictly convex function (Formula presented.) are presented for which Newton’s method with line search converges to a point where the gradient of (Formula presented.) is not zero. The first example uses a line search based on the Wolfe conditions. For the second example, some strictly convex function (Formula presented.) is defined as well as a sequence of descent directions for which exact line searches do not converge to the minimizer of (Formula presented.). Then (Formula presented.) is perturbed such that these search directions coincide with the Newton directions for the perturbed function while leaving the exact line search invariant.

KW - Convex minimization

KW - Line search

KW - Newton’s method

KW - Wolfe conditions

UR - http://www.scopus.com/inward/record.url?scp=84929629741&partnerID=8YFLogxK

U2 - 10.1007/s10107-015-0913-2

DO - 10.1007/s10107-015-0913-2

M3 - Article

VL - 158

SP - 23

EP - 34

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1

ER -