Stopping Criteria for First-Order Methods

Abstract

This technical note introduces and evaluates stopping criteria for convex optimization. The emphasis is put on criteria that are `cheap' to evaluate if first-order methods, such as gradient projection or the fast gradient method, are applied. We investigate three different criteria which are based either on the complexity results of first-order methods, a property of the gradient mapping or on conjugacy, which to the best of the authors' knowledge results in a novel stopping criterion.