Complexity bounds for second-order optimality in unconstrained optimization

作者：Cartis C^*; Gould N I M; Toint Ph L

来源：Journal of Complexity, 2012, 28(1): 93-108.

DOI：10.1016/j.jco.2011.06.001

• Evaluation complexity
• Worst-case analysis
• Nonconvex optimization
• Second-order optimality conditions

This paper examines worst-case evaluation bounds for finding weak minimizers in unconstrained optimization. For the cubic regularization algorithm, Nesterov and Polyak (2006) [15] and Cartis et al. (2010) [3] show that at most 0(epsilon(-3)) iterations may have to be performed for finding an iterate which is within E 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 bounds on the worst-case behaviour of the cubic regularization and trust-region algorithms favours the first of these methods.

• 出版日期2012-2