7 papers · 1 filter
The AutoLyap software suite for computer-assisted Lyapunov analyses of first-order methods
Manu Upadhyaya, Shuvomoy Das Gupta, Adrien B. Taylor +2
We introduce AutoLyap, a software suite that assists with Lyapunov analyses of a wide class of first-order methods for structured optimization and inclusion problems. Lyapunov anal…
A Lyapunov analysis of Korpelevich's extragradient method with fast and flexible extensions
Manu Upadhyaya, Puya Latafat, Pontus Giselsson
We develop a Lyapunov-based analysis of Korpelevich's extragradient method and show that it achieves an last-iterate convergence rate of the constructed Lyapunov function.…
Extending Douglas-Rachford Splitting for Convex Optimization
Max Nilsson, Anton à kerman, Pontus Giselsson
The Douglas-Rachford splitting method is a classical and widely used algorithm for solving monotone inclusions involving the sum of two maximally monotone operators. It was recentl…
The Chambolle--Pock method converges weakly with and
Sebastian Banert, Manu Upadhyaya, Pontus Giselsson
The Chambolle--Pock method is a versatile three-parameter algorithm designed to solve a broad class of composite convex optimization problems, which encompass two proper, lower sem…
Automated tight Lyapunov analysis for first-order methods
Manu Upadhyaya, Sebastian Banert, Adrien B. Taylor +1
We present a methodology for establishing the existence of quadratic Lyapunov inequalities for a wide range of first-order methods used to solve convex optimization problems. In pa…
The Symmetry Coefficient of Positively Homogeneous Functions
Max Nilsson, Pontus Giselsson
The Bregman distance is a central tool in convex optimization, particularly in first-order gradient descent and proximal-based algorithms. Such methods enable optimization of funct…