Automated tight Lyapunov analysis for first-order methods

Area of Science:

• Optimization Theory
• Convex Analysis
• Control Theory

Background:

• First-order methods are crucial for solving large-scale convex optimization problems.
• Lyapunov inequalities are essential for analyzing the convergence of dynamical systems, including optimization algorithms.
• Existing methods often lack a unified framework for verifying convergence properties.

Purpose of the Study:

• To establish a general methodology for proving the existence of quadratic Lyapunov inequalities for first-order convex optimization methods.
• To provide a necessary and sufficient condition for the existence of such inequalities.
• To extend the applicability of convergence analysis to a broader range of algorithms and parameters.

Main Methods:

• Formulating first-order methods as linear systems in state-space form.
• Analyzing the feedback interconnection with subdifferentials of objective functions.
• Deriving a condition for quadratic Lyapunov inequality existence via semidefinite programming.

Main Results:

• A novel methodology for establishing quadratic Lyapunov inequalities is presented.
• A necessary and sufficient condition for the existence of these inequalities is derived.
• The methodology is demonstrated on various first-order methods, including the Chambolle-Pock algorithm.
• Parameter regions for duality gap convergence in the Chambolle-Pock method are significantly extended.

Conclusions:

• The proposed methodology offers a systematic way to analyze the convergence of first-order optimization algorithms.
• The findings provide deeper insights into the convergence behavior of optimization methods.
• This work facilitates the design and selection of more efficient optimization algorithms for convex problems.