  We introduce a novel approach for analyzing the performance of first-order
black-box optimization methods. We focus on smooth unconstrained convex
minimization over the Euclidean space $R^d$. Our approach relies on the
observation that by definition, the worst case behavior of a black-box
optimization method is by itself an optimization problem, which we call the
Performance Estimation Problem (PEP). We formulate and analyze the PEP for two
classes of first-order algorithms. We first apply this approach on the
classical gradient method and derive a new and tight analytical bound on its
performance. We then consider a broader class of first-order black-box methods,
which among others, include the so-called heavy-ball method and the fast
gradient schemes. We show that for this broader class, it is possible to derive
new numerical bounds on the performance of these methods by solving an
adequately relaxed convex semidefinite PEP. Finally, we show an efficient
procedure for finding optimal step sizes which results in a first-order
black-box method that achieves best performance.
