Linear convergence of the Douglas-Rachford algorithm via a generic error bound condition

We provide new insight into the convergence properties of the Douglas-Rachford algorithm for the problem minx f(x)+g(x), where f and g are convex functions. Our approach relies on and highlights the natural primal-dual symmetry between the above problem and its Fenchel dual minu f^*(u) + g_*(u) where g_*(u):=g^*(-u). Our main development is to show the linear convergence of the algorithm when a natural error bound condition on the Douglas-Rachford operator holds. We leverage our error bound condition approach to show and estimate the algorithm's linear rate of convergence for three special classes of problems. The first one is when f org and f^* or g_* are strongly convex relative to the primal and dual optimal sets respectively. The second one is when~f and~g are piecewise linear-quadratic functions. The third one is when~f and~g are the indicator functions of closed convex cones. In all three cases the rate of convergence is determined by a suitable measure of well-posedness of the problem. In the conic case, if the two closed convex cones are a linear subspace L and ℝn_+, we establish the following stronger em finite termination result: the Douglas-Rachford algorithm identifies the em maximum support sets for Lcap ℝn_+ and Lperpcapℝn_+ in finitely many steps. Our developments have straightforward extensions to the more general linearly constrained problem minx,y f(x) + g( y):Ax + By = b thereby highlighting a direct and straightforward relationship between the Douglas-Rachford algorithm and the alternating direction method of multipliers (ADMM).