Douglas--Rachford Algorithm with Relaxed Resolvents

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.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-16
DOI
https://doi.org/10.48550/arxiv.2611.21377
Primary Topic
Optimization and Variational Analysis
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Douglas--Rachford Algorithm with Relaxed Resolvents

Fernando Roldán, Luis M. Briceño-Arias, Adrien Taylor
arXiv (Cornell University)
Optimization and Variational Analysis
preprint

Douglas--Rachford Algorithm with Relaxed Resolvents

Fernando Roldán, Luis M. Briceño-Arias, Adrien Taylor
preprint en

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.

arXiv (Cornell University)
Optimization and Variational Analysis
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon