  We present the Branch-and-Bound Performance Estimation Programming (BnB-PEP),
a unified methodology for constructing optimal first-order methods for convex
and nonconvex optimization. BnB-PEP poses the problem of finding the optimal
optimization method as a nonconvex but practically tractable quadratically
constrained quadratic optimization problem and solves it to certifiable global
optimality using a customized branch-and-bound algorithm. By directly
confronting the nonconvexity, BnB-PEP offers significantly more flexibility and
removes the many limitations of the prior methodologies. Our customized
branch-and-bound algorithm, through exploiting specific problem structures,
outperforms the latest off-the-shelf implementations by orders of magnitude,
accelerating the solution time from hours to seconds and weeks to minutes. We
apply BnB-PEP to several setups for which the prior methodologies do not apply
and obtain methods with bounds that improve upon prior state-of-the-art
results. Finally, we use the BnB-PEP methodology to find proofs with potential
function structures, thereby systematically generating analytical convergence
proofs.
