Worst-case functions for the gradient method with fixed variable step sizes

This master thesis brings new elements in the analysis of the worst-case performances of first-order methods. We have focused this work on the gradient method with fixed variable step sizes for unconstrained smooth (possibly strongly) convex minimization. The aim was to derive the functions that achieve the worst-case behaviors of the gradient method according to objective function accuracy. These behaviors are numerically computed with the PESTO toolbox. PESTO relies on the performance estimation framework and allows the computing of tight worst-case performance of first-order methods by solving a semidefinite program. A conjecture on the exact worst-case bound of two steps of the gradient method for unconstrained smooth (possibly strongly) convex minimization has recently been developed. A conjecture for three steps has also been derived. In this master thesis, we have identified the functions that reach the worst-case bounds conjectured for two and three steps of the gradient method. These functions are called worst-case functions. The approach to identify these functions is based on convex interpolation. We also provide some conclusions for N steps of the gradient method.