The (optimal) function/gradient evaluations worst-case complexity analysis available for the Adaptive Regularizations algorithms with Cubics (ARC) for nonconvex smooth unconstrained optimization is extended to finite-difference versions of this algorithm, yielding complexity bounds for first-order and derivative free methods applied on the same problem class. A comparison with the results obtained for derivative-free methods by Vicente (2010) is also discussed, giving some theoretical insight on the relative merits of various methods in this popular class of algorithms.
Citation
@techreport{CartGoulToin10d, author= {C. Cartis and N. I. M. Gould and Ph. L. Toint}, title = {On the oracle complexity of first-order and derivative-free algorithms for smooth nonconvex minimization}, institution = {University of Namur}, address = {61, rue de Bruxelles, 5000 Namur, Belgium}, number = {NAXYS-02-2010}, year = 2010}