A general framework for ADMM acceleration

Buccini A.;Dell'Acqua P.;Donatelli M.

2020-01-01

---

Abstract

The Alternating Direction Multipliers Method (ADMM) is a very popular algorithm for computing the solution of convex constrained minimization problems. Such problems are important from the application point of view, since they occur in many fields of science and engineering. ADMM is a powerful numerical tool, but unfortunately its main drawback is that it can exhibit slow convergence. Several approaches for its acceleration have been proposed in the literature and in this paper we present a new general framework devoted to this aim. In particular, we describe an algorithmic framework that makes possible the application of any acceleration step while still having the guarantee of convergence. This result is achieved thanks to a guard condition that ensures the monotonic decrease of the combined residual. The proposed strategy is applied to image deblurring problems. Several acceleration techniques are compared; to the best of our knowledge, some of them are investigated for the first time in connection with ADMM. Numerical results show that the proposed framework leads to a faster convergence with respect to other acceleration strategies recently introduced for ADMM.