Linear Convergence of Resolvent Splitting with Minimal Lifting and its Application to a Primal-Dual Algorithm
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_ | 1866916528513875968 |
|---|---|
| author | Simi, Farhana A. Tam, Matthew K. |
| author_facet | Simi, Farhana A. Tam, Matthew K. |
| contents | We consider resolvent splitting algorithms for finding a zero of the sum of finitely many maximally monotone operators. The standard approach to solving this type of problem involves reformulating as a two-operator problem in the product-space and applying the Douglas-Rachford algorithm. However, existing results for linear convergence cannot be applied in the product-space formulation due to a lack of appropriate Lipschitz continuity and strong monotonicity. In this work, we investigate a different approach that does not rely on the Douglas-Rachford algorithm or the product-space directly. We establish linear convergence of the "resolvent splitting with minimal lifting" algorithm due to Malitsky and Tam for monotone inclusions with finitely many operators. Our results are then used to derive linear convergence of a primal-dual algorithm for convex minimization problems involving infimal convolutions. The theoretical results are demonstrated on numerical experiments in image denoising. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_12607 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Linear Convergence of Resolvent Splitting with Minimal Lifting and its Application to a Primal-Dual Algorithm Simi, Farhana A. Tam, Matthew K. Optimization and Control 47H05, 49M27, 65K10, 90C30 We consider resolvent splitting algorithms for finding a zero of the sum of finitely many maximally monotone operators. The standard approach to solving this type of problem involves reformulating as a two-operator problem in the product-space and applying the Douglas-Rachford algorithm. However, existing results for linear convergence cannot be applied in the product-space formulation due to a lack of appropriate Lipschitz continuity and strong monotonicity. In this work, we investigate a different approach that does not rely on the Douglas-Rachford algorithm or the product-space directly. We establish linear convergence of the "resolvent splitting with minimal lifting" algorithm due to Malitsky and Tam for monotone inclusions with finitely many operators. Our results are then used to derive linear convergence of a primal-dual algorithm for convex minimization problems involving infimal convolutions. The theoretical results are demonstrated on numerical experiments in image denoising. |
| title | Linear Convergence of Resolvent Splitting with Minimal Lifting and its Application to a Primal-Dual Algorithm |
| topic | Optimization and Control 47H05, 49M27, 65K10, 90C30 |
| url | https://arxiv.org/abs/2412.12607 |