Exact worst-case convergence rates for Douglas-Rachford and Davis-Yin splitting

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. 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. Our tight analysis thus enables us to identify the importance of the update order on the convergence rate of DYS.