The Douglas-Rachford method is a method to solve a monotone inclusion {0\in (A+B)x} with two maximally monotone operators {A,B} defined on a Hilbert space {X}. The method uses the resolvents {(I + \lambda A)^{-1}} and {(I + \lambda B)^{-1}} and produces two sequences of iterates

\displaystyle \begin{array}{rcl} x^{k+1}& =& (I + \lambda B)^{-1}(v^k)\\ v^{k+1} & = & v^k + (I+\lambda A)^{-1}(2x^{k+1} - v^k) -x^{k+1}. \end{array}

Looks pretty opaque to me and I did not have some good intuition where this methods comes from and why it should work. Here’s a way I can remember (and which is copied from “Preconditioned Douglas-Rachford Splitting Methods for Convex-Concave Saddle-Point Problems” by Hongpeng Sun and Kristian Bredies):

Substituting {w = Ax} gives the optimality system

\displaystyle 0 \in w + Bx,\qquad 0 \in -x + A^{-1} w

or, written differently

\displaystyle 0 \in \begin{bmatrix} B & I\\ -I & A^{-1} \end{bmatrix} \begin{bmatrix} x\\w \end{bmatrix}.

This is again a monotone inclusion, but now on {X\times X}. We introduce the positive definite operator

\displaystyle M = \begin{bmatrix} I & -I\\ -I & I \end{bmatrix}

and perform the iteration

\displaystyle (M + \begin{bmatrix} B & I\\ -I & A^{-1} \end{bmatrix}) \begin{bmatrix} x^{k+1}\\w^{k+1} \end{bmatrix} \ni M \begin{bmatrix} x^k\\w^k \end{bmatrix}.

(This is basically the same as applying the proximal point method to the preconditioned inclusion

\displaystyle 0\in M^{-1} \begin{bmatrix} B & I\\ -I & A^{-1} \end{bmatrix} \begin{bmatrix} x\\w \end{bmatrix}.)

Writing out the iteration gives

\displaystyle \begin{array}{rcl} x^{k+1} & = &(I + B)^{-1}(x^k - w^k)\\ w^{k+1} & = &(I + A^{-1})^{-1}(w^k + 2x^{k+1} - x^k). \end{array}

Now, applying the Moreau identity for monotone operators ({(I + A)^{-1} + (I+A^{-1})^{-1} = I}), gives

\displaystyle \begin{array}{rcl} x^{k+1} & = &(I + B)^{-1}(x^k - w^k)\\ w^{k+1} & = &w^k + 2x^{k+1} - x^k - (I + A)^{-1}(w^k + 2x^{k+1} - x^k) \end{array}

substituting {v^k = x^k - w^k} finally gives Douglas-Rachford:

\displaystyle \begin{array}{rcl} x^{k+1} & = &(I + B)^{-1}(v^k)\\ v^{k+1} & = & -x^{k+1} + v^k + (I + A)^{-1}(2x^{k+1} - v^k) \end{array}

(besides the stepsize {\lambda} which we would get by starting with the equivalent inclusion {0 \in \lambda(A+B)x} in the first place).

Probably the shortest derivation of Douglas-Rachford I have seen. Oh, and also the (weak) convergence proof comes for free: It’s a proximal point iteration and you just use the result by Rockafellar from “Monotone operators and the proximal point algorithm”, SIAM J. Control and Optimization 14(5), 1976.