Establishing the global rate of convergence of standard algorithms or their global evaluation complexity for nonconvex smooth optimization problems is a natural but challenging aspect of algorithm analysis. Until recently, this question has been entirely open for Newton-type methods in the nonconvex setting. We illustrate that, even when convergent, Newton's method can be---surprisingly---as slow as steepest descent. In fact, all commonly encountered linesearch or trust-region variants turn out to be essentially as inefficient as steepest descent in the worst-case. There is, however, good news: cubic regularization (Griewank, Nesterov-Polyak) and its large-scale variants (Cartis, Gould and Toint) are better than both steepest-descent and Newton's in the worst-case; they are in fact, optimal from a worst-case point of view within a wide class of methods and problems. We also present bounds on the evaluation complexity of nonconvexly constrained problems, and argue that, for certain carefully devised methods, these can be of the same order as in the unconstrained case, a surprising but reassuring result. |