Relative-error approximate versions of Douglas-Rachford splitting and special cases of the ADMM

• 成果类型: Article
• 署名作者: Eckstein, Jonathan; Yao, Wang
• 署名单位: Rutgers University System; Rutgers University New Brunswick; Rutgers University System; Rutgers University New Brunswick
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1160-5
• 发表日期: 2018
• 页码: 417-444
• 关键词: proximal point algorithm; monotone-operators; CONVERGENCE; shrinkage; selection; SUM

摘要

We derive a new approximate version of the alternating direction method of multipliers (ADMM) which uses a relative error criterion. The new version is somewhat restrictive and allows only one of the two subproblems to be minimized approximately, but nevertheless covers commonly encountered special cases. The derivation exploits the long-established relationship between the ADMM and both the proximal point algorithm (PPA) and Douglas-Rachford (DR) splitting for maximal monotone operators, along with a relative-error of the PPA due to Solodov and Svaiter. In the course of analysis, we also derive a version of DR splitting in which one operator may be evaluated approximately using a relative error criterion. We computationally evaluate our method on several classes of test problems and find that it significantly outperforms several alternatives on one problem class.