  We obtain a new lower bound on the information-based complexity of
first-order minimization of smooth and convex functions. We show that the bound
matches the worst-case performance of the recently introduced Optimized
Gradient Method, thereby establishing that the bound is tight and can be
realized by an efficient algorithm. The proof is based on a novel construction
technique of smooth and convex functions.
