FoCM 2014 conference

Workshop B3 - Continuous Optimization

December 15, 15:00 ~ 15:30 - Room A21

A Trust Region Algorithm with a Worst-Case Global Function Evaluation Complexity of ${\cal O}(\epsilon^{-3/2})$ for Nonconvex Smooth Optimization

Frank E. Curtis

Lehigh University, United States   -

We present a trust region algorithm for solving nonconvex optimization problems that, in the worst-case, is able to drive the norm of the gradient of the objective below a prescribed threshold $\epsilon > 0$ after at most ${\cal O}(\epsilon^{-3/2})$ function evaluations, gradient evaluations, or iterations. Our work has been inspired by the recently proposed Adaptive Regularisation framework using Cubics (i.e., the ARC algorithm), which attains the same worst-case complexity bound. Our algorithm is modeled after a traditional trust region algorithm, but employs modified step acceptance criteria and a novel trust region updating mechanism that allows it to achieve this desirable property. Importantly, our method also maintains standard global and fast local convergence guarantees.

Joint work with Daniel P. Robinson (Johns Hopkins University) and Mohammadreza Samadi (Lehigh University).

View abstract PDF