Uniqueness of DRS as the 2 operator resolvent-splitting and impossibility of 3 operator resolvent-splitting

• 成果类型: Article
• 署名作者: Ryu, Ernest K.
• 署名单位: University of California System; University of California Los Angeles
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-019-01403-1
• 发表日期: 2020
• 页码: 233-273
• 关键词: monotone inclusions; algorithm; SUM; optimization

摘要

Given the success of Douglas-Rachford splitting (DRS), it is natural to ask whether DRS can be generalized. Are there other 2 operator resolvent-splittings sharing the favorable properties of DRS? Can DRS be generalized to 3 operators? This work presents the answers: no and no. In a certain sense, DRS is the unique 2 operator resolvent-splitting, and generalizing DRS to 3 operators is impossible without lifting, where lifting roughly corresponds to enlarging the problem size. The impossibility result further raises a question. How much lifting is necessary to generalize DRS to 3 operators? This work presents the answer by providing a novel 3 operator resolvent-splitting with provably minimal lifting that directly generalizes DRS.