ePubs
The open archive for STFC research publications
Home
About ePubs
Content Policies
News
Help
Privacy/Cookies
Contact ePubs
Full Record Details
DOI
10.5286/raltr.2011011
Persistent URL
http://purl.org/net/epubs/work/56238
Record Status
Checked
Record Id
56238
Title
Optimal Newton-type methods for nonconvex smooth optimization problems
Contributors
C Cartis (Edinburgh U.)
,
NIM Gould (STFC Rutherford Appleton Lab.)
,
PL Toint (Facultes Universitaires de la Paix)
Abstract
We consider a general class of second-order iterations for unconstrained optimization that includes regularization and trust-region variants of Newton’s method. For each method in this class, we exhibit a smooth, bounded-below objective function, whose gradient is globally Lipschitz continuous within an open convex set containing any iterates encountered and whose Hessian is _?H¨older continuous (for given _ 2 [0, 1]) on the path of the iterates, for which the method in question takes at least b_?(2+_)/(1+_)c function-evaluations to generate a first iterate whose gradient is smaller than _ in norm. This provides a lower bound on the evaluation complexity of second-order methods in our class when applied to smooth problems satisfying our assumptions. Furthermore, for _ = 1, this lower bound is of the same order in _ as the upper bound on the evaluation complexity of cubic regularization, thus implying cubic regularization has optimal worst-case evaluation complexity within our class of second-order methods.
Organisation
CSE
,
CSE-NAG
,
STFC
Keywords
Funding Information
Related Research Object(s):
Licence Information:
Language
English (EN)
Type
Details
URI(s)
Local file(s)
Year
Report
RAL Technical Reports
RAL-TR-2011-011. 2011.
RAL-TR-2011-011.pdf
2011
Showing record 1 of 1
Recent Additions
Browse Organisations
Browse Journals/Series
Login to add & manage publications and access information for OA publishing
Username:
Password:
Useful Links
Chadwick & RAL Libraries
SHERPA FACT
SHERPA RoMEO
SHERPA JULIET
Journal Checker Tool
Google Scholar