Exact worst-case convergence rates for Douglas--Rachford and Davis--Yin splitting methods
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911150954774528 |
|---|---|
| author | Nguyen, Edward Duc Hien Suh, Jaewook J. Jiang, Xin Ma, Shiqian |
| author_facet | Nguyen, Edward Duc Hien Suh, Jaewook J. Jiang, Xin Ma, Shiqian |
| contents | In this work, we aim to establish the exact worst-case convergence rates of Douglas--Rachford splitting (DRS) and Davis--Yin splitting (DYS) when applied to convex optimization problems. Both DRS and DYS have two variants as swapping the roles of the two nonsmooth convex functions in both algorithms yields different sequences of iterates. For both variants of DRS and one variant of DYS, we establish the exact worst-case convergence rates, including the constant factor, using the primal--dual gap function as the performance metric. We provide worst-case examples to verify the tightness of these rates. To the best of our knowledge, this is the first result that establishes the exact worst-case convergence rates for DRS and DYS that include the constant factor. For the other variant of DYS, we establish the best-known convergence rate and provide a concrete example indicating a discrepancy between the convergence rates of the two DYS variants. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_23475 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Exact worst-case convergence rates for Douglas--Rachford and Davis--Yin splitting methods Nguyen, Edward Duc Hien Suh, Jaewook J. Jiang, Xin Ma, Shiqian Optimization and Control In this work, we aim to establish the exact worst-case convergence rates of Douglas--Rachford splitting (DRS) and Davis--Yin splitting (DYS) when applied to convex optimization problems. Both DRS and DYS have two variants as swapping the roles of the two nonsmooth convex functions in both algorithms yields different sequences of iterates. For both variants of DRS and one variant of DYS, we establish the exact worst-case convergence rates, including the constant factor, using the primal--dual gap function as the performance metric. We provide worst-case examples to verify the tightness of these rates. To the best of our knowledge, this is the first result that establishes the exact worst-case convergence rates for DRS and DYS that include the constant factor. For the other variant of DYS, we establish the best-known convergence rate and provide a concrete example indicating a discrepancy between the convergence rates of the two DYS variants. |
| title | Exact worst-case convergence rates for Douglas--Rachford and Davis--Yin splitting methods |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2506.23475 |