Operator Splitting: ADMM and Douglas-Rachford

Intuition Beginner

Some problems are really two problems chained together by a shared agreement. One part of you wants to fit the data well; another part wants the answer to stay simple or legal. Each part is happy to solve its own piece if only it knew what the other part was doing. The trouble is the two pieces must agree on a common answer in the end. Operator splitting is a way to let each piece work on its own copy of the variable, then gently force the copies to match.

Here is the everyday picture. Two contractors share one wall between their rooms. One picks where to put a door; the other picks where to put a window. Neither wants to redesign the whole building, but the wall has to line up. So a manager runs rounds: let each contractor finish their own room given the latest plan, then the manager notes how far apart the wall edges are and nudges both with a "penalty" for disagreement. Round by round, the gap shrinks and the wall lines up.

The alternating direction method of multipliers, or ADMM, is that manager. It keeps two work variables and one "price of disagreement." Each round it does three small jobs: let the first piece minimize its own cost plus a penalty for drifting from the agreement; let the second piece do the same; then update the price so that whatever disagreement remains gets pushed harder next round. The penalty is the augmented Lagrangian, and the price is the dual variable.

The beauty is that each small job is exactly the kind of friendly step you already know. When the penalty is a squared distance, minimizing one piece plus that squared distance is a proximal step. So ADMM is just: prox the first piece, prox the second piece, update the price, repeat. Because every step is cheap and each piece is handled by the move that suits it, ADMM tackles huge problems by splitting them into manageable parts that talk to each other.

Visual Beginner

Picture one ADMM round as three moves. The first variable updates by minimizing its own cost while staying near the current agreement; the second variable does the same; then the price of disagreement moves by how much they still differ.

   round k                      what each step does

   x-update  ----------->   minimize f plus a spring pulling
   (first piece)            toward the agreement (a prox step)
        |
        v
   z-update  ----------->   minimize g plus a spring pulling
   (second piece)           toward the new x (a prox step)
        |
        v
   price update  ------>    push the price by the leftover
   (dual y)                 disagreement Ax + Bz - c
        |
        v
   repeat until Ax + Bz - c  is small  (the agreement holds)

the piece	its update does
first cost $f$	prox-type step: minimize $f$ plus a squared penalty for drifting from the deal
second cost $g$	prox-type step: minimize $g$ plus a squared penalty for drifting from the new $x$
price of disagreement	add the leftover mismatch $Ax+Bz-c$ to the running price

Worked example Beginner

We run two rounds of ADMM on a tiny problem where both pieces pull on one number. Minimize $f(x)+g(z)$ subject to $x-z=0$, with $f(x)=\frac{1}{2}(x-4{)}^2$ and $g(z)=\frac{1}{2}{z}^2$. The agreement is $x=z$. We use penalty strength $\rho =1$ and start at $z=0$, price $y=0$.

Step 1. The x-update. Minimize $\frac{1}{2}(x-4{)}^2+y(x-z)+\frac{1}{2}(x-z{)}^2$ over $x$. The slope in $x$ is $(x-4)+y+(x-z)$. Set it to zero: $2x=4-y+z$. With $y=0$, $z=0$ this gives $x=2$.

Step 2. The z-update. Now minimize $\frac{1}{2}{z}^2+y(x-z)+\frac{1}{2}(x-z{)}^2$ over $z$. The slope in $z$ is $z-y-(x-z)$. Set it to zero: $2z=y+x$. With $y=0$, $x=2$ this gives $z=1$.

Step 3. The price update. Add the leftover mismatch: $y\leftarrow y+(x-z)=0+(2-1)=1$.

Step 4. Second round. Repeat the x-update with $y=1$, $z=1$: $2x=4-1+1=4$, so $x=2$. The z-update: $2z=y+x=1+2=3$, so $z=1.5$. The price: $y\leftarrow 1+(2-1.5)=1.5$.

What this tells us. The gap $x-z$ started at $2-1=1$ and shrank to $2-1.5=0.5$. The true answer minimizes $\frac{1}{2}(x-4{)}^2+\frac{1}{2}{x}^2$ at $x=2$, and indeed $x$ sat at $2$ while $z$ climbed toward it. ADMM is closing the gap between the two copies round by round.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, $f:{\mathbb{R}}^n\to (-\infty ,+\infty ]$ and $g:{\mathbb{R}}^m\to (-\infty ,+\infty ]$ are proper closed convex, $A\in {\mathbb{R}}^{p\times n}$, $B\in {\mathbb{R}}^{p\times m}$, $c\in {\mathbb{R}}^p$, with $⟨\cdot ,\cdot ⟩$ the Euclidean inner product and $\Vert \cdot \Vert$ its norm. The proximal operator ${\mathrm{prox}}_{tg}$ and its identity as the resolvent $(I+t\partial g{)}^{-1}$ are from 44.06.02; the Fenchel conjugate $f^{\ast }$ and Fenchel duality are from 44.02.03.

Definition (the splitting model). Consider

$$\underset{x,z}{\min }f(x)+g(z)\text{subject to}Ax+Bz=c.$$

This separable objective with linear coupling is the canonical form ADMM solves; many composite problems ${\min }_{x}f(x)+g(Ax)$ rewrite into it by setting $z=Ax$, i.e. $B=-I$, $c=0$.

Definition (augmented Lagrangian). For penalty parameter $\rho >0$, the augmented Lagrangian is

$$L_{\rho }(x,z,y)=f(x)+g(z)+⟨y,Ax+Bz-c⟩+\frac{\rho }{2}\Vert Ax+Bz-c{\Vert }^2,$$

the ordinary Lagrangian augmented by a quadratic penalty on the constraint residual (the augmentation framework is the method of multipliers; the augmented-Lagrangian construction is developed in 44.04.02).

Definition (ADMM iteration). Given $(z^k,y^k)$, ADMM produces $(x^{k+1},z^{k+1},y^{k+1})$ by

$$\begin{array}{rl}{x}^{k+1}& =\arg \underset{x}{\min }{L}_{\rho }(x,z^k,y^k),\\ z^{k+1}& =\arg \underset{z}{\min }{L}_{\rho }(x^{k+1},z,y^k),\\ y^{k+1}& =y^k+\rho (A{x}^{k+1}+B{z}^{k+1}-c).\end{array}$$

The two minimizations are taken in alternating directions (hence the name); minimizing the joint $L_{\rho }$ over $(x,z)$ together would be the method of multipliers.

Definition (scaled form). Substituting the scaled dual variable $u=y/\rho$ and completing the square, $⟨y,r⟩+\frac{\rho }{2}\Vert r{\Vert }^2=\frac{\rho }{2}\Vert r+u{\Vert }^2-\frac{\rho }{2}\Vert u{\Vert }^2$ for the residual $r=Ax+Bz-c$, gives the scaled form

$$\begin{array}{rl}{x}^{k+1}& =\arg \underset{x}{\min }\{f(x)+\frac{\rho }{2}\Vert Ax+B{z}^k-c+u^k{\Vert }^2\},\\ z^{k+1}& =\arg \underset{z}{\min }\{g(z)+\frac{\rho }{2}\Vert A{x}^{k+1}+Bz-c+u^k{\Vert }^2\},\\ u^{k+1}& =u^k+A{x}^{k+1}+B{z}^{k+1}-c,\end{array}$$

which is the form used in practice. When $A=I$ and $B=-I$, $c=0$, the $x$- and $z$-updates are literally proximal steps: $x^{k+1}={\mathrm{prox}}_{f/\rho }(z^k-u^k)$ and $z^{k+1}={\mathrm{prox}}_{g/\rho }(x^{k+1}+u^k)$.

Definition (residuals and stopping). The primal residual $r^{k+1}=A{x}^{k+1}+B{z}^{k+1}-c$ measures constraint violation; the dual residual $s^{k+1}=\rho A^{\top }B(z^{k+1}-z^k)$ measures failure of the dual feasibility condition. A standard stopping rule halts when $\Vert r^k\Vert \le {\epsilon }_{\mathrm{pri}}$ and $\Vert s^k\Vert \le {\epsilon }_{\mathrm{dual}}$, with tolerances built from absolute and relative parts ^{[Boyd, S., Parikh, N., Chu, E., Peleato, B. & Eckstein, J. — Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers (2011)]}.

Definition (Douglas-Rachford splitting). For the monotone inclusion $0\in (\mathcal{A}+\mathcal{B})(w)$ with $\mathcal{A},\mathcal{B}$ maximal monotone and step $t>0$, write the resolvents $J_{t\mathcal{A}}=(I+t\mathcal{A}{)}^{-1}$, $J_{t\mathcal{B}}=(I+t\mathcal{B}{)}^{-1}$ and the reflected resolvents $R_{t\mathcal{A}}=2J_{t\mathcal{A}}-I$, $R_{t\mathcal{B}}=2J_{t\mathcal{B}}-I$. Douglas-Rachford splitting iterates

$$v^{k+1}=T_{\mathrm{DR}}(v^k),T_{\mathrm{DR}}=\frac{1}{2}(I+R_{t\mathcal{B}}{R}_{t\mathcal{A}}),$$

and recovers a solution as $w^k=J_{t\mathcal{A}}(v^k)$. For $\mathcal{A}=\partial f$, $\mathcal{B}=\partial g$ the resolvents are proximal operators, so $T_{\mathrm{DR}}$ is built from two prox evaluations and their reflections.

Counterexamples to common slips Intermediate+

• "ADMM is forward-backward splitting." Forward-backward of 44.06.02 uses an explicit gradient step on a smooth $f$ and a prox on $g$; ADMM uses a prox-type (implicit) step on both $f$ and $g$ and so needs neither smooth, handling two nonsmooth pieces. The two methods coincide only in degenerate cases.

• "The penalty $\rho$ must be small for convergence, like a step size." ADMM converges for every fixed $\rho >0$ when $f,g$ are closed proper convex and a saddle point exists, because the underlying Douglas-Rachford operator is averaged for any $t>0$. The value of $\rho$ affects speed, not whether it converges.

• "The x- and z-updates can be done in parallel." They are sequential: $z^{k+1}$ uses the just-computed $x^{k+1}$. Replacing $x^{k+1}$ by $x^k$ in the $z$-update (Jacobi rather than Gauss-Seidel) breaks the convergence guarantee in general; the alternation is essential.

Key theorem with proof Intermediate+

The convergence of ADMM is not proved by descent on the augmented Lagrangian directly; it is proved by recognizing ADMM as Douglas-Rachford splitting applied to the Fenchel dual, where a single averaged-operator fixed-point argument applies. The fixed-point characterization first certifies that limits are optimal.

Theorem (ADMM equals Douglas-Rachford on the dual; convergence). Let $f,g$ be proper closed convex, $A,B$ have full column rank, and suppose the unaugmented Lagrangian $L_0$ has a saddle point $(x^{\star },z^{\star },y^{\star })$. Then:

(i) (Fixed point.) $(x^{\star },z^{\star },y^{\star })$ is a saddle point iff $A{x}^{\star }+B{z}^{\star }=c$, $-A^{\top }{y}^{\star }\in \partial f(x^{\star })$, and $-B^{\top }{y}^{\star }\in \partial g(z^{\star })$; equivalently $y^{\star }$ solves the Fenchel dual ${\max }_y-f^{\ast }(-A^{\top }y)-g^{\ast }(-B^{\top }y)+⟨y,c⟩$.

(ii) (Equivalence.) The ADMM dual sequence $y^k$ is the Douglas-Rachford sequence for the dual inclusion $0\in \mathcal{A}(y)+\mathcal{B}(y)$ with $\mathcal{A}(y)=A\partial f^{\ast }(-A^{\top }y)$-type and $\mathcal{B}$ the analogous term, run with step $t=\rho$.

(iii) (Convergence.) The residual $A{x}^k+B{z}^k-c\to 0$, the objective $f(x^k)+g(z^k)\to p^{\star }$, and $y^k\to y^{\star }$ a dual optimum.

Proof. (i) A saddle point of $L_0(x,z,y)=f(x)+g(z)+⟨y,Ax+Bz-c⟩$ minimizes in $(x,z)$ and maximizes in $y$. Stationarity in $y$ is primal feasibility $A{x}^{\star }+B{z}^{\star }=c$. Minimizing the convex separable $f(x)+⟨y^{\star },Ax⟩$ gives, by Fermat's rule and the sum rule 44.06.02, $0\in \partial f(x^{\star })+A^{\top }{y}^{\star }$, i.e. $-A^{\top }{y}^{\star }\in \partial f(x^{\star })$; likewise $-B^{\top }{y}^{\star }\in \partial g(z^{\star })$. By the conjugacy inversion $w\in \partial f(x)⟺x\in \partial f^{\ast }(w)$ of 44.02.03, these read $x^{\star }\in \partial f^{\ast }(-A^{\top }{y}^{\star })$ and $z^{\star }\in \partial g^{\ast }(-B^{\top }{y}^{\star })$; substituting into feasibility, $0\in A\partial f^{\ast }(-A^{\top }{y}^{\star })+B\partial g^{\ast }(-B^{\top }{y}^{\star })-c$, which is the stationarity of the Fenchel dual objective $\Phi (y)=-f^{\ast }(-A^{\top }y)-g^{\ast }(-B^{\top }y)+⟨y,c⟩$, a concave function whose maximizers are the dual optima of 44.02.03.

(ii) Define the two maximal monotone operators governing the dual: $\mathcal{A}=\partial (f^{\ast }\circ (-A^{\top }))$ shifted by $-c$ appropriately and $\mathcal{B}=\partial (g^{\ast }\circ (-B^{\top }))$, so that $0\in (\mathcal{A}+\mathcal{B})(y)$ is exactly the dual stationarity of (i). The augmented $x$-minimization $x^{k+1}=\arg {\min }_{x}f(x)+⟨y^k,Ax⟩+\frac{\rho }{2}\Vert Ax+B{z}^k-c{\Vert }^2$ has optimality $0\in \partial f(x^{k+1})+A^{\top }(y^k+\rho (A{x}^{k+1}+B{z}^k-c))$. Writing the intermediate multiplier $\hat{y}=y^k+\rho (A{x}^{k+1}+B{z}^k-c)$, this is $-A^{\top }\hat{y}\in \partial f(x^{k+1})$, i.e. (by conjugacy inversion) $x^{k+1}\in \partial f^{\ast }(-A^{\top }\hat{y})$ — a resolvent of $\mathcal{A}$ evaluated at a reflected point. The $z$-update followed by the dual update $y^{k+1}=y^k+\rho (A{x}^{k+1}+B{z}^{k+1}-c)$ likewise realizes the resolvent of $\mathcal{B}$ on the reflection $2y^{k+1/2}-y^k$. Assembling the two resolvents and the two reflections produces precisely $y^{k+1}=\frac{1}{2}(I+R_{\rho \mathcal{B}}{R}_{\rho \mathcal{A}})(\cdot )$ acting on the running variable $v^k=y^k-\rho (B{z}^k-\text{const})$; this is the Douglas-Rachford operator with $t=\rho$. (The bookkeeping that the ADMM variable equals the DR variable up to the affine change $v^k=y^k+\rho B{z}^k-\rho c$ is the content of the equivalence; full detail in the proof set.)

(iii) The Douglas-Rachford operator $T_{\mathrm{DR}}=\frac{1}{2}(I+R_{\rho \mathcal{B}}{R}_{\rho \mathcal{A}})$ is $\frac{1}{2}$-averaged: each reflected resolvent $R_{t\mathcal{A}}=2J_{t\mathcal{A}}-I$ is nonexpansive because the resolvent $J_{t\mathcal{A}}$ is firmly nonexpansive (44.06.02 for the prox case, monotone-operator theory in general), the composition $R_{\rho \mathcal{B}}{R}_{\rho \mathcal{A}}$ of two nonexpansive maps is nonexpansive, and averaging with the identity makes $T_{\mathrm{DR}}$ averaged. An averaged operator with a nonempty fixed-point set has Krasnoselskii-Mann-convergent iterates: $v^k\to v^{\star }$ a fixed point, and a fixed point of $T_{\mathrm{DR}}$ yields a zero of $\mathcal{A}+\mathcal{B}$, a dual optimum $y^{\star }$. Then $-A^{\top }{y}^k\to -A^{\top }{y}^{\star }\in \partial f(x^{\star })$ forces the primal residual to zero and the objective to $p^{\star }=d^{\star }$ by Fenchel strong duality 44.02.03. $\square$

Bridge. The averaged-operator fixed-point argument is the foundational reason ADMM converges for any $\rho >0$, and it builds toward the distributed consensus and sharing schemes where the same iteration runs blockwise across agents. This is exactly the dual face of the forward-backward splitting of 44.06.02: where that method composed one explicit and one implicit step for $f+g$ on the primal, ADMM composes two reflected resolvents on the dual, so the method generalises proximal splitting from one prox-friendly term to a coordinated pair coupled by $Ax+Bz=c$. The convergence proof is dual to the descent-lemma telescoping of 44.06.02 — there a quadratic comparison, here an averaged-operator contraction in disguise — and the optimality condition $0\in (\mathcal{A}+\mathcal{B})(y^{\star })$ appears again in primal-dual and three-operator splitting. Putting these together, the central insight is that ADMM is Douglas-Rachford on the Fenchel dual, which is itself the proximal point algorithm on a monotone splitting; the bridge is the resolvent $J_{\rho \partial g}={\mathrm{prox}}_{\rho g}$ of 44.06.02, the single primitive that both the primal and dual readings share.

Exercises Intermediate+

Advanced results Master

The ADMM iteration is $x^{k+1}=\arg {\min }_x{L}_{\rho }(x,z^k,y^k)$, $z^{k+1}=\arg {\min }_z{L}_{\rho }(x^{k+1},z,y^k)$, $y^{k+1}=y^k+\rho (A{x}^{k+1}+B{z}^{k+1}-c)$. The results below place it inside maximal-monotone operator theory, fix its rate, and exhibit the distributed forms it was built for.

Theorem 1 (Eckstein-Bertsekas: the three-way identification). For proper closed convex $f,g$, ADMM with parameter $\rho$ on $\min f(x)+g(z)$ s.t. $Ax+Bz=c$ is identical, iterate for iterate, to Douglas-Rachford splitting applied to the Fenchel dual inclusion $0\in (\mathcal{A}+\mathcal{B})(y)$ run with step $t=\rho$, which is in turn the proximal point algorithm applied to the maximal monotone splitting operator $S=(R_{t\mathcal{B}}{R}_{t\mathcal{A}}+I{)}^{-1}$-type associated with $\mathcal{A}+\mathcal{B}$ ^{[Eckstein, J. & Bertsekas, D. P. — On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators (1992)]}. Convergence of the dual sequence to a dual optimum, and of the primal residual to zero, holds for every $\rho >0$ provided a saddle point exists; full column rank of $A,B$ secures convergence of the primal iterates themselves. The proximal-point reading also yields relaxed and over-relaxed ADMM variants (a relaxation factor $\alpha \in (0,2)$) inheriting the same convergence.

Theorem 2 (Douglas-Rachford as an averaged-operator iteration). The operator $T_{\mathrm{DR}}=\frac{1}{2}(I+R_{t\mathcal{B}}{R}_{t\mathcal{A}})$ is firmly nonexpansive: each $R_{t\mathcal{A}},R_{t\mathcal{B}}$ is nonexpansive because the resolvent $J_{t\mathcal{A}}=(I+t\mathcal{A}{)}^{-1}$ is firmly nonexpansive for maximal monotone $\mathcal{A}$ (44.06.02 for $\mathcal{A}=\partial f$), and $\frac{1}{2}(I+N)$ with $N$ nonexpansive is $\frac{1}{2}$-averaged ^{[Bauschke & Combettes Ch. 4, 26]}. By the Krasnoselskii-Mann theorem, an averaged operator with nonempty fixed-point set has weakly convergent (in ${\mathbb{R}}^n$, convergent) iterates, and $\mathrm{Fix}{T}_{\mathrm{DR}}\ne \varnothing$ iff $\mathrm{zer}(\mathcal{A}+\mathcal{B})\ne \varnothing$, with $w^{\star }=J_{t\mathcal{A}}(v^{\star })$ recovering a zero. This is the engine behind ADMM convergence and the reason no smoothness and no small-step restriction are needed — the contrast with the forward-backward method of 44.06.02, whose step is capped at $1/L$ because its forward step is explicit.

Theorem 3 (ergodic $O(1/k)$ rate). For closed proper convex $f,g$ with a saddle point, the ADMM running averages ${\bar{x}}^K=\frac{1}{K}{\sum }_{k=1}^K{x}^k$, ${\bar{z}}^K$ satisfy $f({\bar{x}}^K)+g({\bar{z}}^K)-p^{\star }=O(1/K)$ and $\Vert A{\bar{x}}^K+B{\bar{z}}^K-c\Vert =O(1/K)$ ^{[Beck, A. — First-Order Methods in Optimization (SIAM, 2017)]}. Under additional regularity — strong convexity of one block and Lipschitz gradient of the other — ADMM converges linearly, the rate set by a condition-number-like quantity and the choice of $\rho$, which is then tunable to optimize the contraction factor. The ergodic average, not the last iterate, carries the worst-case rate, paralleling the averaging used in primal first-order methods.

Theorem 4 (consensus and sharing forms). Two structured splittings drive distributed optimization ^{[Boyd, S., Parikh, N., Chu, E., Peleato, B. & Eckstein, J. — Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers (2011)]}. Global variable consensus: $\min {\sum }_{i=1}^N{f}_i(x_i)$ s.t. $x_i=z$ has each $x_i$-update a local prox $x_i^{k+1}={\mathrm{prox}}_{f_i/\rho }(z^k-u_i^k)$ computed in parallel, a $z$-update equal to the average $z^{k+1}={\bar{x}}^{k+1}+{\bar{u}}^k$, and dual updates $u_i^{k+1}=u_i^k+x_i^{k+1}-z^{k+1}$; the only communication is the average, so consensus ADMM scales across machines. Sharing: $\min {\sum }_i{f}_i(x_i)+g({\sum }_i{x}_i)$ dualizes the coupling through the shared sum, the $g$-block handling the aggregate. These are the templates for distributed LASSO, distributed logistic regression, and exchange problems, where each agent holds a private $f_i$ and only summary statistics cross the network.

Theorem 5 (variable metric and the role of $A,B$). When $A^{\top }A$ and $B^{\top }B$ are not multiples of the identity, the ADMM subproblems acquire the quadratic metric $\frac{\rho }{2}\Vert A\cdot {\Vert }^2$, making the $x$-update a generalized proximal step in the $A^{\top }A$-metric rather than the Euclidean prox; a proximal ADMM linearizes the quadratic coupling by adding $\frac{1}{2}\Vert x-x^k{\Vert }_G^2$ with a suitable $G⪰0$ to restore a plain prox of $f$, trading exactness for a cheap closed-form update ^{[Beck, A. — First-Order Methods in Optimization (SIAM, 2017)]}. The linearized variant is what makes total-variation denoising, graph-guided regularization, and other $A\ne I$ problems tractable, and it interpolates ADMM with the forward-backward and primal-dual splitting families, all of which are averaged-operator iterations on different reformulations of $0\in \mathcal{A}+\mathcal{B}$.

Synthesis. ADMM is exactly Douglas-Rachford splitting on the Fenchel dual, and this single identification is the foundational reason the method coheres: the augmented Lagrangian's alternating minimizations are reflected resolvents in disguise, the dual variable update is the Douglas-Rachford fixed-point recursion, and the convergence for every $\rho >0$ is the averagedness of $T_{\mathrm{DR}}=\frac{1}{2}(I+R_{t\mathcal{B}}{R}_{t\mathcal{A}})$ — a property dual to the firm nonexpansiveness of the prox proved in 44.06.02. The central insight is that splitting a coupled sum $f(x)+g(z)$ across the constraint $Ax+Bz=c$ and handling each block by its own proximal-type step escapes the need for any smoothness, which is exactly why ADMM dominates forward-backward of 44.06.02 when both pieces are nonsmooth; this generalises the single-prox forward-backward iteration to a coordinated pair, and the Eckstein-Bertsekas reading further generalises both to the proximal point algorithm on a monotone splitting. Putting these together, the optimality condition $0\in (\mathcal{A}+\mathcal{B})(y^{\star })$ is the Fenchel-dual stationarity of 44.02.03 read as a monotone inclusion, the resolvent $J_{\rho \partial g}={\mathrm{prox}}_{\rho g}$ is the shared primitive of 44.06.02, and the bridge from this unit to distributed optimization is the consensus split, where the $z$-update collapses to an average and the method becomes a network algorithm. This is exactly the structural payoff: one averaged-operator theorem buys convergence, an $O(1/k)$ ergodic rate, and a distributed implementation at once.

Full proof set Master

Proposition 1 (saddle-point optimality conditions). Let $f,g$ be proper closed convex. Then $(x^{\star },z^{\star },y^{\star })$ is a saddle point of $L_0(x,z,y)=f(x)+g(z)+⟨y,Ax+Bz-c⟩$ iff $A{x}^{\star }+B{z}^{\star }=c$, $-A^{\top }{y}^{\star }\in \partial f(x^{\star })$, and $-B^{\top }{y}^{\star }\in \partial g(z^{\star })$.

Proof. Saddle means $L_0(x^{\star },z^{\star },y)\le L_0(x^{\star },z^{\star },y^{\star })\le L_0(x,z,y^{\star })$ for all $x,z,y$. The left inequality, for all $y$, is $⟨y-y^{\star },A{x}^{\star }+B{z}^{\star }-c⟩\le 0$ for all $y$, which forces $A{x}^{\star }+B{z}^{\star }-c=0$. The right inequality says $(x^{\star },z^{\star })$ minimizes the convex separable $x\mapsto f(x)+⟨y^{\star },Ax⟩$ and $z\mapsto g(z)+⟨y^{\star },Bz⟩$. By Fermat's rule and the sum rule for the subdifferential (the linear term is differentiable, so the sum rule applies without qualification) 44.06.02, $0\in \partial f(x^{\star })+A^{\top }{y}^{\star }$ and $0\in \partial g(z^{\star })+B^{\top }{y}^{\star }$, i.e. the stated inclusions. Each step reverses, so the conditions are equivalent to the saddle property. $\square$

Proposition 2 (dual problem and conjugacy). The conditions of Proposition 1 hold for some $(x^{\star },z^{\star })$ iff $y^{\star }$ maximizes the Fenchel dual $\Phi (y)=-f^{\ast }(-A^{\top }y)-g^{\ast }(-B^{\top }y)+⟨y,c⟩$, and then $\Phi (y^{\star })=p^{\star }$.

Proof. By the conjugacy inversion $w\in \partial f(x)⟺x\in \partial f^{\ast }(w)$ of 44.02.03, $-A^{\top }{y}^{\star }\in \partial f(x^{\star })⟺x^{\star }\in \partial f^{\ast }(-A^{\top }{y}^{\star })$ and likewise for $g$. The dual function $\Phi$ is concave (a sum of negated closed convex conjugates composed with linear maps, plus a linear term). Its supergradient is $\partial (-\Phi )(y)=A\partial f^{\ast }(-A^{\top }y)+B\partial g^{\ast }(-B^{\top }y)-c$, so $0\in \partial (-\Phi )(y^{\star })$ iff there exist $x^{\star }\in \partial f^{\ast }(-A^{\top }{y}^{\star })$, $z^{\star }\in \partial g^{\ast }(-B^{\top }{y}^{\star })$ with $A{x}^{\star }+B{z}^{\star }=c$ — exactly the conditions of Proposition 1. Strong duality $\Phi (y^{\star })=p^{\star }$ is Fenchel duality 44.02.03 under the saddle-point (constraint-qualification) hypothesis. $\square$

Proposition 3 (the ADMM x-update is a reflected resolvent step). The x-minimization $x^{k+1}=\arg {\min }_x{L}_{\rho }(x,z^k,y^k)$ satisfies $-A^{\top }{\hat{y}}^k\in \partial f(x^{k+1})$ with ${\hat{y}}^k=y^k+\rho (A{x}^{k+1}+B{z}^k-c)$, equivalently $x^{k+1}\in \partial f^{\ast }(-A^{\top }{\hat{y}}^k)$.

Proof. The augmented objective is $f(x)+⟨y^k,Ax+B{z}^k-c⟩+\frac{\rho }{2}\Vert Ax+B{z}^k-c{\Vert }^2$. Fermat plus the sum rule give $0\in \partial f(x^{k+1})+A^{\top }{y}^k+\rho A^{\top }(A{x}^{k+1}+B{z}^k-c)=\partial f(x^{k+1})+A^{\top }{\hat{y}}^k$ with ${\hat{y}}^k$ as stated. Hence $-A^{\top }{\hat{y}}^k\in \partial f(x^{k+1})$, and conjugacy inversion 44.02.03 gives the resolvent form $x^{k+1}\in \partial f^{\ast }(-A^{\top }{\hat{y}}^k)$. The intermediate multiplier ${\hat{y}}^k$ is the reflection point feeding the next resolvent. $\square$

Proposition 4 (reflected resolvents are nonexpansive; $T_{\mathrm{DR}}$ is averaged). For maximal monotone $\mathcal{A}$ and $t>0$, $R_{t\mathcal{A}}=2J_{t\mathcal{A}}-I$ is nonexpansive, and $T_{\mathrm{DR}}=\frac{1}{2}(I+R_{t\mathcal{B}}{R}_{t\mathcal{A}})$ is firmly nonexpansive.

Proof. $J=J_{t\mathcal{A}}$ is firmly nonexpansive: if $p=Jx$, $q=Jy$ then $\frac{x-p}{t}\in \mathcal{A}(p)$, $\frac{y-q}{t}\in \mathcal{A}(q)$, and monotonicity of $\mathcal{A}$ gives $⟨(x-p)-(y-q),p-q⟩\ge 0$, i.e. $⟨x-y,p-q⟩\ge \Vert p-q{\Vert }^2$ (44.06.02 proves this for $\mathcal{A}=\partial f$). Then $\Vert Rx-Ry{\Vert }^2=4\Vert p-q{\Vert }^2-4⟨p-q,x-y⟩+\Vert x-y{\Vert }^2\le \Vert x-y{\Vert }^2$, so $R$ is nonexpansive. The composition $N=R_{t\mathcal{B}}{R}_{t\mathcal{A}}$ is nonexpansive. For $T=\frac{1}{2}(I+N)$, $⟨Tx-Ty,x-y⟩-\Vert Tx-Ty{\Vert }^2=\frac{1}{4}(\Vert x-y{\Vert }^2-\Vert Nx-Ny{\Vert }^2)\ge 0$, the firm-nonexpansiveness inequality. $\square$

Proposition 5 (fixed points of $T_{\mathrm{DR}}$ are zeros of $\mathcal{A}+\mathcal{B}$). $v^{\star }=T_{\mathrm{DR}}(v^{\star })$ iff $w^{\star }:=J_{t\mathcal{A}}(v^{\star })$ satisfies $0\in (\mathcal{A}+\mathcal{B})(w^{\star })$.

Proof. $v^{\star }=T_{\mathrm{DR}}(v^{\star })$ iff $v^{\star }=\frac{1}{2}(v^{\star }+R_{t\mathcal{B}}{R}_{t\mathcal{A}}{v}^{\star })$ iff $v^{\star }=R_{t\mathcal{B}}{R}_{t\mathcal{A}}{v}^{\star }$. Put $w^{\star }=J_{t\mathcal{A}}{v}^{\star }$, so $R_{t\mathcal{A}}{v}^{\star }=2w^{\star }-v^{\star }$ and $\frac{v^{\star }-w^{\star }}{t}\in \mathcal{A}(w^{\star })$. The fixed-point equation $v^{\star }=R_{t\mathcal{B}}(2w^{\star }-v^{\star })$ means $J_{t\mathcal{B}}(2w^{\star }-v^{\star })=\frac{1}{2}((2w^{\star }-v^{\star })+v^{\star })=w^{\star }$, so $\frac{(2w^{\star }-v^{\star })-w^{\star }}{t}=\frac{w^{\star }-v^{\star }}{t}\in \mathcal{B}(w^{\star })$. Adding the two inclusions, $\frac{v^{\star }-w^{\star }}{t}+\frac{w^{\star }-v^{\star }}{t}=0\in (\mathcal{A}+\mathcal{B})(w^{\star })$. Each step is reversible. $\square$

Proposition 6 (convergence of ADMM). Let $f,g$ be proper closed convex with a saddle point of $L_0$. Then the ADMM primal residual $A{x}^k+B{z}^k-c\to 0$, the objective $f(x^k)+g(z^k)\to p^{\star }$, and $y^k\to y^{\star }$ a dual optimum, for every $\rho >0$.

Proof. By Propositions 2-3 and the bookkeeping of the Key theorem (ii), the ADMM dual sequence is the Douglas-Rachford sequence $v^{k+1}=T_{\mathrm{DR}}(v^k)$ for the dual operators with $t=\rho$. By Proposition 4, $T_{\mathrm{DR}}$ is firmly nonexpansive hence averaged; the saddle point gives, via Proposition 2, a dual optimum, so $\mathrm{zer}(\mathcal{A}+\mathcal{B})\ne \varnothing$ and by Proposition 5 $\mathrm{Fix}{T}_{\mathrm{DR}}\ne \varnothing$. The Krasnoselskii-Mann theorem for averaged operators with nonempty fixed-point set gives $v^k\to v^{\star }\in \mathrm{Fix}{T}_{\mathrm{DR}}$, whence $y^k\to y^{\star }$ and $w^{\star }=J_{\rho \mathcal{A}}(v^{\star })$ a dual zero. Continuity of the resolvents transfers convergence to the primal blocks: $-A^{\top }{y}^k\to -A^{\top }{y}^{\star }\in \partial f(x^{\star })$ pins $x^k\to x^{\star }$ (full column rank of $A$), similarly $z^k\to z^{\star }$, so the residual $A{x}^k+B{z}^k-c\to A{x}^{\star }+B{z}^{\star }-c=0$ and, by lower semicontinuity and Fenchel strong duality 44.02.03, $f(x^k)+g(z^k)\to f(x^{\star })+g(z^{\star })=p^{\star }$. $\square$

Proposition 7 (ergodic $O(1/k)$ bound). With the running averages ${\bar{x}}^K=\frac{1}{K}{\sum }_{k=1}^K{x}^k$, ${\bar{z}}^K=\frac{1}{K}{\sum }_{k=1}^K{z}^k$, the objective gap and constraint residual are $O(1/K)$.

Proof sketch. The variational inequality satisfied by each ADMM iterate — from the three optimality conditions of Propositions 1 and 3 — yields, for any $(x,z,y)$, $L({\bar{x}}^K,{\bar{z}}^K,y)-L(x,z,{\bar{y}}^K)\le \frac{C}{K}$ where $L$ is the unaugmented Lagrangian and $C$ depends on $\Vert v^0-v^{\star }{\Vert }^2$, by averaging the per-step monotonicity estimate $\Vert v^{k+1}-v^{\star }{\Vert }^2\le \Vert v^k-v^{\star }{\Vert }^2-\Vert v^{k+1}-v^k{\Vert }^2$ (firm nonexpansiveness of $T_{\mathrm{DR}}$, Proposition 4) and telescoping. Specializing $(x,z)=(x^{\star },z^{\star })$ and $y=y^{\star }\pm$ a unit direction bounds both $f({\bar{x}}^K)+g({\bar{z}}^K)-p^{\star }$ and $\Vert A{\bar{x}}^K+B{\bar{z}}^K-c\Vert$ by $O(1/K)$; the detailed constant is in the cited source ^{[Beck, A. — First-Order Methods in Optimization (SIAM, 2017)]}. $\square$

Connections Master

• ADMM is the dual-side companion of the forward-backward proximal-gradient method of 44.06.02: both are averaged-operator iterations on the inclusion $0\in \mathcal{A}+\mathcal{B}$, but forward-backward composes an explicit gradient step (capped at $1/L$) with one prox, while ADMM composes two reflected resolvents and so converges for any $\rho >0$ with no smoothness. The resolvent $J_{\rho \partial g}={\mathrm{prox}}_{\rho g}$ and the firm nonexpansiveness proved there are the exact primitives this unit's reflected resolvents and Douglas-Rachford operator are assembled from.

• The dual problem ADMM solves is the Fenchel dual of 44.02.03: the saddle conditions $-A^{\top }{y}^{\star }\in \partial f(x^{\star })$, $-B^{\top }{y}^{\star }\in \partial g(z^{\star })$ become, by the conjugacy inversion $\partial f^{\ast }=(\partial f{)}^{-1}$ established there, the dual stationarity $0\in A\partial f^{\ast }(-A^{\top }y)+B\partial g^{\ast }(-B^{\top }y)-c$, and the convergence of the objective to $p^{\star }$ is Fenchel strong duality. The conjugate calculus of that unit is what makes the dual inclusion concrete enough to split.

• The augmented Lagrangian that ADMM minimizes blockwise is the method-of-multipliers construction of 44.04.02: ADMM is precisely the method of multipliers with the single joint $(x,z)$-minimization replaced by one Gauss-Seidel sweep of alternating minimizations, so that unit supplies the augmentation and dual-ascent framework while this unit supplies the splitting that makes each step a separate prox-type subproblem.

Historical & philosophical context Master

The Douglas-Rachford method began as a 1956 scheme of Jim Douglas and H. H. Rachford for solving the heat equation by alternating implicit steps in each spatial direction, a finite-difference splitting with no convex-optimization content ^{[Douglas & Rachford 1956]}. Pierre-Louis Lions and Bertrand Mercier in 1979 recast it as a method for the sum of two maximal monotone operators, $0\in \mathcal{A}+\mathcal{B}$, introducing the reflected-resolvent operator whose fixed points solve the inclusion ^{[Lions & Mercier 1979]}. The alternating direction method of multipliers arose independently in the mid-1970s in the work of Roland Glowinski and A. Marroco (1975) and of Daniel Gabay and Bertrand Mercier (1976) on variational problems and the numerical solution of nonlinear PDEs by augmented-Lagrangian splitting. The decisive unification is due to Jonathan Eckstein and Dimitri Bertsekas, whose 1992 paper proved that ADMM is Douglas-Rachford splitting applied to the dual and that Douglas-Rachford is itself the proximal point algorithm of Rockafellar applied to a particular splitting operator, yielding convergence for any fixed penalty parameter ^{[Eckstein & Bertsekas 1992]}. The method's modern prominence in statistics and machine learning was established by the 2011 monograph of Boyd, Parikh, Chu, Peleato, and Eckstein, which assembled the consensus and sharing forms and the residual-based stopping rules now standard in distributed optimization ^{[Boyd, Parikh, Chu, Peleato & Eckstein 2011]}.

Bibliography Master

@article{boyd2011admm,
  author  = {Boyd, Stephen and Parikh, Neal and Chu, Eric and Peleato, Borja and Eckstein, Jonathan},
  title   = {Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers},
  journal = {Foundations and Trends in Machine Learning},
  volume  = {3},
  number  = {1},
  pages   = {1--122},
  year    = {2011}
}

@book{beck2017fom,
  author    = {Beck, Amir},
  title     = {First-Order Methods in Optimization},
  series    = {MOS-SIAM Series on Optimization},
  number    = {25},
  publisher = {SIAM},
  year      = {2017}
}

@article{ecksteinbertsekas1992,
  author  = {Eckstein, Jonathan and Bertsekas, Dimitri P.},
  title   = {On the {Douglas-Rachford} splitting method and the proximal point algorithm for maximal monotone operators},
  journal = {Mathematical Programming},
  volume  = {55},
  pages   = {293--318},
  year    = {1992}
}

@article{lionsmercier1979,
  author  = {Lions, Pierre-Louis and Mercier, Bertrand},
  title   = {Splitting algorithms for the sum of two nonlinear operators},
  journal = {SIAM Journal on Numerical Analysis},
  volume  = {16},
  number  = {6},
  pages   = {964--979},
  year    = {1979}
}

@article{douglasrachford1956,
  author  = {Douglas, Jim and Rachford, H. H.},
  title   = {On the numerical solution of heat conduction problems in two and three space variables},
  journal = {Transactions of the American Mathematical Society},
  volume  = {82},
  number  = {2},
  pages   = {421--439},
  year    = {1956}
}

@article{gabaymercier1976,
  author  = {Gabay, Daniel and Mercier, Bertrand},
  title   = {A dual algorithm for the solution of nonlinear variational problems via finite element approximation},
  journal = {Computers \& Mathematics with Applications},
  volume  = {2},
  number  = {1},
  pages   = {17--40},
  year    = {1976}
}

@book{bauschkecombettes2017,
  author    = {Bauschke, Heinz H. and Combettes, Patrick L.},
  title     = {Convex Analysis and Monotone Operator Theory in Hilbert Spaces},
  edition   = {2},
  series    = {CMS Books in Mathematics},
  publisher = {Springer},
  year      = {2017}
}