How much patience do you have? A worst-case perspective on smooth nonconvex optimization

ePubs

The open archive for STFC research publications

DOI	10.5286/raltr.2012008
Persistent URL	http://purl.org/net/epubs/work/62562
Record Status	Checked
Record Id	62562
Title	How much patience do you have? A worst-case perspective on smooth nonconvex optimization
Contributors	C Cartis (Edinburgh U.), NIM Gould (STFC Rutherford Appleton Lab.), PL Toint (Facultes Universaires ND de la Paix, Belgium)
Abstract	We consider the worst-case behaviour of algorithms for smooth non-convex nonlinear optimization. We examine the question of how many function and derivative evaluations might be required to find a point at which a suitable measures of first- and second-order criticality is smaller than a user-given tolerance _. While many popular algorithms can be shown to take O(_?2) evaluations in the worst-case—and there are examples for which this pessimistic bound is achieved—suitable regularized variants of Newton’s method may reduce this to O(_?3/2) evaluations. Progressively improved bounds are possible if the problem is convex or strictly convex. While such bounds were first established in the unconstrained case, the presence of constraints does not significantly alter the picture. We survey the crucial developments in this active area of research.
Organisation	CSE-NAG , STFC , SCI-COMP
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-2012-008. 2012.		RAL-TR-2012-008.pdf	2012