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

Florian Jarre; Philippe L. Toint

doi:10.1007/s10107-015-0913-2

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

Florian Jarre, Philippe L. Toint

Namur Institute for Complex Systems

Résultats de recherche: Contribution à un journal/une revue › Article › Revue par des pairs

Résumé

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.

langue originale	Anglais
Pages (de - à)	23-34
journal	Mathematical Programming
Volume	158
Numéro de publication	1
Les DOIs	https://doi.org/10.1007/s10107-015-0913-2
Etat de la publication	Publié - juin 2016

Accès au document

10.1007/s10107-015-0913-2

Autres fichiers et liens

Link to publication in Scopus

8 Citations
1 Chapitre
1 Article
1 Papier de travail

Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models
Cartis, C., Gould, N. I. M. & Toint, P., juin 2019, Springer Optimization and Its Applications: Algorithms, Complexity and Applications. Demetriou, I. & Pardalos, P. (eds.). Springer Heidelberg, p. 5-26 22 p. (Springer Optimization and Its Applications; Vol 145).
Résultats de recherche: Contribution dans un livre/un catalogue/un rapport/dans les actes d'une conférence › Chapitre
Evaluation complexity for nonlinear constrained optimization using unscaled KKT conditions and high-order models
Birgin, E., Gardenghi, J., Martinez, J.-M., Santos, S. & Toint, P., 2016, Dans: SIAM Journal on Optimization. 26, 2, 20 p.
Résultats de recherche: Contribution à un journal/une revue › Article › Revue par des pairs

File
Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models
Birgin, E., Gardenghi, J., Martinez, J.-M., Santos, S. A. & Toint, P., juin 2015, 2015: Namur center for complex systems, 8 p. (naXys Technical Reports; Vol 05-2015).
Résultats de recherche: Papier de travail

File

Contient cette citation

@article{d19d58d6f7d844ab90188652664d92e8,

title = "Simple examples for the failure of Newton{\textquoteright}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{\textquoteright}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{\textquoteright}s method, Wolfe conditions",

author = "Florian Jarre and Toint, {Philippe L.}",

year = "2016",

month = jun,

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",

}

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

AN - SCOPUS:84929629741

SN - 0025-5610

VL - 158

SP - 23

EP - 34

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1

ER -

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

Résumé

Accès au document

Autres fichiers et liens

Empreinte digitale

Résultat de recherche

Evaluation complexity bounds for smooth constrained nonlinear optimization using scaled KKT conditions and high-order models

Evaluation complexity for nonlinear constrained optimization using unscaled KKT conditions and high-order models

Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models

Contient cette citation