title: Optimized first-order methods for smooth convex minimization.
abstract: We introduce new optimized first-order methods for smooth unconstrained convex minimization. Drori and Teboulle [5] recently described a numerical method for computing theN-iteration optimal step coefficients in a class of first-order algorithms that includes gradient methods, heavy-ball methods [15], and Nesterov's fast gradient methods [10,12]. However, the numerical method in [5] is computationally expensive for largeN, and the corresponding numerically optimized first-order algorithm in [5] requires impractical memory and computation for large-scale optimization problems. In this paper, we propose optimized first-order algorithms that achieve a convergence bound that is two times smaller than for Nesterov's fast gradient methods; our bound is found analytically and refines the numerical bound in [5]. Furthermore, the proposed optimized first-order methods have efficient forms that are remarkably similar to Nesterov's fast gradient methods.
authors.affiliation: Dept. of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, MI 48109 USA.
authors.forename: Donghwan
authors.initials: D
authors.lastname: Kim
authors.affiliation: Dept. of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, MI 48109 USA.
authors.forename: Jeffrey A
authors.initials: JA
authors.lastname: Fessler
keywords: Convergence bound; Fast gradient methods; First-order algorithms; Smooth convex minimization