betaFeedback

WorksMathematics

Douglas–Rachford Algorithm with Relaxed Resolvents

Abstract

The Douglas–Rachford algorithm is a classical method for finding a zero of the sum of two maximally monotone operators. In its standard form, both operators are reflected in the same manner and are activated with the same step-size. In this article we break this symmetry by replacing the reflected resolvents by relaxed resolvents, letting the two operators be activated with different step-sizes. We show that this additional freedom is available precisely when the operators are cocoercive, the admissible range of the parameter being determined by their cocoercivity constants and reducing to the classical algorithm when these constants vanish. Within this range we quantify the averagedness of the resulting operator, which yields the weak convergence of the method together with relaxation steps beyond those allowed in the classical case, and, when one of the operators is in addition strongly monotone, a strict contraction. We compute in closed form the parameters minimizing the contraction factor and we exhibit instances attaining it, so that the resulting linear rates are tight. The optimal rates are strictly smaller than the best rates available for the classical Douglas–Rachford algorithm in the monotone inclusion and convex optimization settings, which are studied separately. All theoretical rates are corroborated by the numerical worst cases obtained via performance estimation.

Paper details

vlnc:W_24qz8rtj
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

AI tools

View statement
Looking for related papers…