417. AutoLyap: A Python package for computer-assisted Lyapunov analyses for first-order methods
Invited abstract in session TC-8: Systematic and computer-aided analyses V: Tools for systematic studies of first-order algorithms, stream Systematic and computer-aided analyses of optimization algorithms.
Tuesday, 14:00-16:00Room: B100/7007
Authors (first author is the speaker)
| 1. | Manu Upadhyaya
|
| Lund University | |
| 2. | Adrien Taylor
|
| Inria/ENS | |
| 3. | Sebastian Banert
|
| Uni Bremen | |
| 4. | Pontus Giselsson
|
| Dept. of Automatic Control, Lund University |
Abstract
We introduce AutoLyap, a Python package designed to automate Lyapunov analysis for a wide class of first-order methods for solving structured optimization and inclusion problems. Lyapunov analyses are structured proof patterns commonly used to establish convergence results for first-order methods. Building on previous work, the core idea behind AutoLyap is to recast the verification of the existence of a Lyapunov analysis as a semidefinite programming (SDP) problem, which can then be solved numerically using standard SDP solvers. Users of the package specify (i) the optimization or inclusion problem, (ii) the first-order method in question, and (iii) the type of Lyapunov analysis they wish to verify. Once these inputs are provided, AutoLyap handles the SDP modeling and proceeds with the numerical solution of the SDP. We numerically verify (and sometimes extend) numerous established convergence results, demonstrating practical relevance.
Keywords
- Complexity and efficiency of algorithms
- Computer-aided algorithm analysis
- Conic and semidefinite optimization
Status: accepted
Back to the list of papers