Douglas--Rachford Splitting and ADMM for Pathological Convex Optimization

Abstract

Despite the vast literature on DRS and ADMM, there has been very little work analyzing their behavior under pathologies. Most analyses assume a primal solution exists, a dual solution exists, and strong duality holds. When these assumptions are not met, i.e., under pathologies, the theory often breaks down and the empirical performance may degrade significantly. In this paper, we establish that DRS only requires strong duality to work, in the sense that asymptotically iterates are approximately feasible and approximately optimal.

Published in Computational Optimization and Applications

References in corpus (3)

• A Note on the Convergence of ADMM for Linearly Constrained Convex Optimization Problems
• Global Behavior of the Douglas-Rachford Method for a Nonconvex Feasibility Problem
• Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs

Cited by in corpus (4)

• Anderson Accelerated Douglas-Rachford Splitting
• On the Asymptotic Behavior of the Douglas-Rachford and Proximal-Point Algorithms for Convex Optimization
• On the Minimal Displacement Vector of the Douglas-Rachford Operator
• Coordinate-Update Algorithms can Efficiently Detect Infeasible Optimization Problems