Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions

Damek Davis and Wotao Yin

To appear in Mathematics of Operations Research

Overview

Splitting schemes are a class of powerful algorithms that solve complicated monotone inclusion and convex optimization problems that are built from many simpler pieces. They give rise to algorithms in which the simple pieces of the decomposition are processed individually. This leads to easily implementable and highly parallelizable algorithms, which often obtain nearly state-of-the-art performance.

In this paper, we provide a comprehensive convergence rate analysis of the Douglas-Rachford splitting (DRS), Peaceman-Rachford splitting (PRS), and alternating direction method of multipliers (ADMM) algorithms under various regularity assumptions. Under strong convexity assumptions, we prove convergence rates of a sequence that strongly converges to a minimizer. Under Lipschitz differentiability assumptions, we prove that the best iterate of the relaxed PRS algorithms converges as least as quickly as the last iterate of the forward-backward splitting (FBS) algorithm, without any knowledge of the Lipschitz constant. In addition, if the Lipschitz constant of the derivative is known, we can choose implicit stepsize parameters such that the entire sequence of objective error converges as quickly as the iterates of the FBS algorithm. Under mixed strong convexity and Lipschitz differentiability assumptions, we show that the relaxed PRS algorithm converges linearly.

Finally, we prove that a relaxed PRS iteration applied to the feasibility problem converges linearly whenever the sets satisfy the standard (bounded) linear regularity assumption.

One of the main consequences of our results is that relaxed PRS and ADMM automatically adapt to the regularity of the problem at hand and achieve convergence rates that improve upon the (tight) worst-case rates that hold in the absence of smoothness and strong convexity. All of our results follow from a basic lemma that derives convergence rates for summable sequences, a simple diagram that decomposes each relaxed PRS iteration, and a few fundamental inequalities.

Citation

D. Davis and W. Yin, Convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions, to appear in Mathematics of Operations Research’17, UCLA CAM Report 14-58, 2014.


« Back