Open Collections

Sharp Contraction Factors for the Douglas-Rachford Operator

Banff International Research Station for Mathematical Innovation and Discovery

Recently, several local and global linear convergence rate results for Douglas–Rachford splitting have appeared in the literature. Many of these are derived under strong monotonicity, Lipschitz continuity, and/or cocoercivity assumptions, and most focus on the convex optimization setting in the dual Douglas-Rachford algorithm, i.e., the alternating direction method of multipliers. In the monotone inclusion setting for Douglas-Rachford splitting, Lions and Mercier showed a linear convergence rate bound under the assumption that one of the two operators is strongly monotone and Lipschitz continuous. In this talk, we show that this rate is not sharp, and present a sharp contraction factor for the Douglas-Rachford operator under the stated assumptions. We also present, for many cases sharp, contraction factors for the Douglas-Rachford operator under different combinations of strong monotonicity, Lipschitz continuity, and cocoercivity assumptions. If these stronger properties are split between the operators, our results rely on the introduced notions of negatively averaged operators and negatively linearly regular operators, meaning that the negative operator is averaged and linearly regular respectively.

Mathematics; Operations research, mathematical programming; Operator theory; Control/optimization/operation research

video/mp4

Author affiliation: Lund University (Sweden)

2018-03-26

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/64934

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/