Performance analysis of primal-dual and second-order optimization methods
(2025)
Files
Thesis_Nizar_BousselmiV2.pdf
Open Access - Adobe PDF
- 3.41 MB
Details
- Authors
- Supervisors
- Abstract
- Optimization theory develops methods to solve optimization problems. One common way to assess the quality of an optimization method is through its worst-case guarantee over a problem class. It certifies that the method will never perform worse than this guarantee on all instances of the problem class. The Performance Estimation Problem (PEP) methodology makes it possible to determine the exact worst-case performance of an optimization method in a computer-assisted way. It formulates the problem of finding the worst-case instance of the problem class for the method in a tractable way and then solves it analytically or numerically. Importantly, the framework relies on the concept of interpolation conditions, that is, an appropriate characterization of the involved class of functions. In the first part of this thesis, we generalize the PEP methodology to first-order methods involving linear operators. This extension requires an explicit formulation of interpolation conditions for those linear operators. We also extend the framework to analyze the performance of first-order methods on quadratic functions. We then investigate primal-dual methods such as the Chambolle-Pock and Condat-Vu methods and improve and extend the existing analysis of their convergence. In the second part, we develop interpolation conditions for classes of univariate Hessian Lipschitz and univariate generalized self-concordant functions. We exploit these conditions together with the PEP framework to analyze the convergence of second-order optimization methods such as Newton’s method and its regularized variants. This allows to obtain new tight analytical and numerical guarantees on these methods for univariate functions.
- Affiliations
UCLouvain SST/ICTM/INMA - Pôle en ingénierie mathématique
Citations
Bousselmi, N. (2025). Performance analysis of primal-dual and second-order optimization methods. https://hdl.handle.net/2078.5/249328