Anderson Accelerated Douglas-Rachford Splitting

Abstract

We consider the problem of non-smooth convex optimization with linear equality constraints, where the objective function is only accessible through its proximal operator. This problem arises in many different fields such as statistical learning, computational imaging, telecommunications, and optimal control. To solve it, we propose an Anderson accelerated Douglas-Rachford splitting (A2DR) algorithm, which we show either globally converges or provides a certificate of infeasibility/unboundedness under very mild conditions. Applied to a block separable objective, A2DR partially decouples so that its steps may be carried out in parallel, yielding an algorithm that is fast and scalable to multiple processors. We describe an open-source implementation and demonstrate its performance on a wide range of examples.

arXiv comment27 pages, 8 figures

References in corpus (12)

• A note on the group lasso and a sparse group lasso
• CVXPY: A Python-Embedded Modeling Language for Convex Optimization
• Anderson Acceleration for Geometry Optimization and Physics Simulation
• Anderson acceleration for contractive and noncontractive operators
• A Simple Practical Accelerated Method for Finite Sums
• Adaptive Consensus ADMM for Distributed Optimization
• Globally Convergent Type-I Anderson Acceleration for Non-Smooth Fixed-Point Iterations
• SuperMann: a superlinearly convergent algorithm for finding fixed points of nonexpansive operators
• A Distributed Method for Fitting Laplacian Regularized Stratified Models
• Dynamic Energy Management
• Douglas--Rachford Splitting and ADMM for Pathological Convex Optimization
• Convex programming with fast proximal and linear operators

Cited by in corpus (14)

• Fast and Robust Iterative Closest Point
• Geometry of First-Order Methods and Adaptive Acceleration
• Fast and Stable Nonconvex Constrained Distributed Optimization: The ELLADA Algorithm
• Enabling fast convergence of the iterated penalty Picard iteration with $O(1)$ penalty parameter for incompressible Navier-Stokes via Anderson acceleration
• Large-scale Optimization with Linear Equality Constraints using Reduced Compact Representation
• Rapid Convergence of First-Order Numerical Algorithms via Adaptive Conditioning
• An Operator Splitting View of Federated Learning
• Nonmonotone Globalization for Anderson Acceleration via Adaptive Regularization
• Anderson acceleration of coordinate descent
• Anderson Acceleration for Seismic Inversion
• On the Asymptotic Linear Convergence Speed of Anderson Acceleration Applied to ADMM
• Computing Wasserstein Barycenter via operator splitting: the method of averaged marginals
• On Anderson acceleration for partially observable Markov decision processes
• Anderson Acceleration Based on the ${\mathcal{H}}^{-s}$ Sobolev Norm for Contractive and Noncontractive Fixed-Point Operators