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 - frank.e.curtis@gmail.com
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).