The open archive for STFC research publications

Full Record Details

Persistent URL http://purl.org/net/epubs/work/54458
Record Status Checked
Record Id 54458
Title Complexity bounds for second-order optimality in unconstrained optimization
Abstract This paper examines worst-case evaluation bounds for finding weak minimizers in unconstrained optimization. For the cubic regularization algorithm, Nesterov and Polyak (2006) and Cartis, Gould and Toint (2010a) show that at most O(epsilon−3) iterations may have to be performed for finding an iterate which is within epsilon of satisfying second-order optimality conditions. We first show that this bound can be derived for a version of the algorithm which only uses one-dimensional global optimization of the cubic model and that it is sharp. We next consider the standard trust-region method and show that a bound of the same type may also be derived for this method, and that it is also sharp in some cases. We conclude by showing that a comparison of the worst-case behaviour of the ARC and trust-region algorithms favours the first of these methods.
Organisation CSE , CSE-NAG , STFC
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-002. 2011. RAL-TR-2011-002.pdf 2011
Journal Article Journal of Complexity 28, no. 1 (2012): 93-108. doi:10.1016/j.jco.2011.06.001 2012