ePubs

The open archive for STFC research publications

Full Record Details

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