Complexity bounds for second-order optimality in unconstrained optimization (Q657654)

The authors examine the worst-case evaluation bounds for finding weak minimizers in unconstrained optimization. They show that this bound can be derived for a version of the algorithms, which only uses one-dimensional global optimization of the cubic model and that it is sharp. They also 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 sharp in some cases. They also compare the bounds on the worst-case behavior of the cubic regularization and trust-region algorithms favor the first of these methods. The paper is an important topic in the theory of optimization. Introduction and concluding sections of the paper, respectively, containing both historical notes and remarks on the topic of research are interesting and useful.