This thesis derives exact worst-case convergence bounds for three canonical first-order optimization methods: gradient descent, proximal gradient descent (or difference-of-convex algorithm), and Douglas-Rachford splitting, applied to smooth, weakly convex functions. While the asymptotic behavior of these algorithms is well established, traditional analyses often rely on big-O notation, which hides the constants that determine their true guaranteed convergence speed. This work goes beyond asymptotic descriptions to establish tight, non-improvable bounds that characterize the exact theoretical performance limits of these methods. Such bounds provide a clearer understanding of the capabilities and limitations of first-order methods in deterministic smooth optimization. The analysis is fully analytical and interpretable, inspired by the Performance Estimation Problem (PEP) framework but developed independently of computer-generated proofs. Our goal is to provide transparent derivations that reveal the underlying structure of the algorithms, typically in weakly convex settings. The main results include a complete worst-case analysis of gradient descent with constant stepsizes. This analysis captures its behavior across weakly convex, convex, and strongly convex regimes, showing how the rates continuously interpolate between different curvature assumptions and providing optimized stepsize schedules, particularly those independent of a priori fixed iteration counts. Extending to constrained minimization, proximal gradient descent is examined through its equivalence with the difference-of-convex algorithm, a simpler parameter-free approach. The analysis provides tight performance bounds on the convergence to critical points. It also extends previous works by introducing the novelty of accommodating weakly convex functions in the second, subtracted term. This yields the broadest admissible range of proximal gradient descent stepsizes and reveals a continuous bridge between smooth nonconvex and convex regimes, with tight rates in all cases. Finally, new exact bounds are established for the Douglas-Rachford splitting method applied to smooth, weakly convex plus prox-bounded functions, covering the entire range of stepsizes and relaxation parameters that ensure convergence. Together, these results offer a unified and rigorous characterization of the worst-case performance of fundamental first-order methods. Although such worst cases rarely occur in practice, understanding them clarifies the theoretical boundaries of algorithmic behavior and strengthens the connection between optimization theory and its practical applications.
Teodor Rotaru (Mon,) studied this question.