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.
Oracle complexity, worst-case analysis, finite-differences, first-order methods, derivative free optimization, nonconvex optimization
Written: 18 October 2010
Published in SIAM Journal on Optimization.
