Computer-Assisted Search for Differential Equations Corresponding to Optimization Methods and Their Convergence Rates
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914192681861120 |
|---|---|
| author | Tabei, Atsushi Tanaka, Ken'ichiro |
| author_facet | Tabei, Atsushi Tanaka, Ken'ichiro |
| contents | Let $f:\mathbb{R}^n \to \mathbb{R}$ be a continuously differentiable convex function with its minimizer denoted by $x_*$ and optimal value $f_* = f(x_*)$. Optimization algorithms such as the gradient descent method can often be interpreted in the continuous-time limit as differential equations known as continuous dynamical systems. Analyzing the convergence rate of $f(x) - f_*$ in such systems often relies on constructing appropriate Lyapunov functions. However, these Lyapunov functions have been designed through heuristic reasoning rather than a systematic framework. Several studies have addressed this issue. In particular, Suh, Roh, and Ryu (2022) proposed a constructive approach that involves introducing dilated coordinates and applying integration by parts. Although this method significantly improves the process of designing Lyapunov functions, it still involves arbitrary choices among many possible options, and thus retains a heuristic nature in identifying Lyapunov functions that yield the best convergence rates. In this study, we propose a systematic framework for exploring these choices computationally. More precisely, we propose a brute-force approach using symbolic computation by computer algebra systems to explore every possibility. By formulating the design of Lyapunov functions for continuous dynamical systems as an optimization problem, we aim to optimize the Lyapunov function itself. As a result, our framework successfully reproduces many previously reported results and, in several cases, discovers new convergence rates that have not been shown in the existing studies. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_09712 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Computer-Assisted Search for Differential Equations Corresponding to Optimization Methods and Their Convergence Rates Tabei, Atsushi Tanaka, Ken'ichiro Optimization and Control Numerical Analysis Classical Analysis and ODEs Dynamical Systems 34-04, 34D05, 65K99, 90C25, 93D30 Let $f:\mathbb{R}^n \to \mathbb{R}$ be a continuously differentiable convex function with its minimizer denoted by $x_*$ and optimal value $f_* = f(x_*)$. Optimization algorithms such as the gradient descent method can often be interpreted in the continuous-time limit as differential equations known as continuous dynamical systems. Analyzing the convergence rate of $f(x) - f_*$ in such systems often relies on constructing appropriate Lyapunov functions. However, these Lyapunov functions have been designed through heuristic reasoning rather than a systematic framework. Several studies have addressed this issue. In particular, Suh, Roh, and Ryu (2022) proposed a constructive approach that involves introducing dilated coordinates and applying integration by parts. Although this method significantly improves the process of designing Lyapunov functions, it still involves arbitrary choices among many possible options, and thus retains a heuristic nature in identifying Lyapunov functions that yield the best convergence rates. In this study, we propose a systematic framework for exploring these choices computationally. More precisely, we propose a brute-force approach using symbolic computation by computer algebra systems to explore every possibility. By formulating the design of Lyapunov functions for continuous dynamical systems as an optimization problem, we aim to optimize the Lyapunov function itself. As a result, our framework successfully reproduces many previously reported results and, in several cases, discovers new convergence rates that have not been shown in the existing studies. |
| title | Computer-Assisted Search for Differential Equations Corresponding to Optimization Methods and Their Convergence Rates |
| topic | Optimization and Control Numerical Analysis Classical Analysis and ODEs Dynamical Systems 34-04, 34D05, 65K99, 90C25, 93D30 |
| url | https://arxiv.org/abs/2512.09712 |