Douglas--Rachford Splitting and ADMM for Pathological Convex Optimization
arXiv:1801.06618 · doi:10.1007/s10589-019-00130-9
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.
arXiv commentPublished in Computational Optimization and Applications
References in corpus (7)
- A Note on the Convergence of ADMM for Linearly Constrained Convex Optimization Problems
- Self Equivalence of the Alternating Direction Method of Multipliers
- Douglas-Rachford Feasibility Methods for Matrix Completion Problems
- Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
- Global Behavior of the Douglas-Rachford Method for a Nonconvex Feasibility Problem
- Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs
- Computation with Polynomial Equations and Inequalities arising in Combinatorial Optimization
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