Resolvent splitting for sums of monotone operators with minimal lifting

• 成果类型: Article
• 署名作者: Malitsky, Yura; Tam, Matthew K. K.
• 署名单位: Linkoping University; University of Melbourne
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01906-4
• 发表日期: 2023
• 页码: 231-262
• 关键词: algorithms

摘要

In this work, we study fixed point algorithms for finding a zero in the sum of n >= 2 maximally monotone operators by using their resolvents. More precisely, we consider the class of such algorithms where each resolvent is evaluated only once per iteration. For any algorithm from this class, we show that the underlying fixed point operator is necessarily defined on a d-fold Cartesian product space with d >= n - 1. Further, we show that this bound is unimprovable by providing a family of examples for which d = n - 1 is attained. This family includes the Douglas-Rachford algorithm as the special case when n = 2. Applications of the new family of algorithms in distributed decentralised optimisation and multi-block extensions of the alternation direction method of multipliers (ADMM) are discussed.