A Symplectic Discretization Based Proximal Point Algorithm for Convex Minimization
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915061067415552 |
|---|---|
| author | Yuan, Ya-xiang Zhang, Yi |
| author_facet | Yuan, Ya-xiang Zhang, Yi |
| contents | The proximal point algorithm plays a central role in non-smooth convex programming. The Augmented Lagrangian Method, one of the most famous optimization algorithms, has been found to be closely related to the proximal point algorithm. Due to its importance, accelerated variants of the proximal point algorithm have received considerable attention. In this paper, we first study an Ordinary Differential Equation (ODE) system, which provides valuable insights into proving the convergence rate of the desired algorithm. Using the Lyapunov function technique, we establish the convergence rate of the ODE system. Next, we apply the Symplectic Euler Method to discretize the ODE system to derive a new proximal point algorithm, called the Symplectic Proximal Point Algorithm (SPPA). By utilizing the proof techniques developed for the ODE system, we demonstrate the convergence rate of the SPPA. Additionally, it is shown that existing accelerated proximal point algorithm can be considered a special case of the SPPA in a specific manner. Furthermore, under several additional assumptions, we prove that the SPPA exhibits a finer convergence rate. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_09077 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Symplectic Discretization Based Proximal Point Algorithm for Convex Minimization Yuan, Ya-xiang Zhang, Yi Optimization and Control 49J52, 65B99, 65K10, 65K15, 68Q25, 90C25, 90C26 The proximal point algorithm plays a central role in non-smooth convex programming. The Augmented Lagrangian Method, one of the most famous optimization algorithms, has been found to be closely related to the proximal point algorithm. Due to its importance, accelerated variants of the proximal point algorithm have received considerable attention. In this paper, we first study an Ordinary Differential Equation (ODE) system, which provides valuable insights into proving the convergence rate of the desired algorithm. Using the Lyapunov function technique, we establish the convergence rate of the ODE system. Next, we apply the Symplectic Euler Method to discretize the ODE system to derive a new proximal point algorithm, called the Symplectic Proximal Point Algorithm (SPPA). By utilizing the proof techniques developed for the ODE system, we demonstrate the convergence rate of the SPPA. Additionally, it is shown that existing accelerated proximal point algorithm can be considered a special case of the SPPA in a specific manner. Furthermore, under several additional assumptions, we prove that the SPPA exhibits a finer convergence rate. |
| title | A Symplectic Discretization Based Proximal Point Algorithm for Convex Minimization |
| topic | Optimization and Control 49J52, 65B99, 65K10, 65K15, 68Q25, 90C25, 90C26 |
| url | https://arxiv.org/abs/2412.09077 |