ADMM: The Alternating Direction Method of Multipliers

Proximal gradient methods work beautifully when a problem splits cleanly into "one smooth part plus one simple non-smooth part." Many real problems are messier: two (or more) pieces that are each individually easy to optimize, but are tangled together by a shared variable or a linking constraint, so neither piece can be solved in isolation. ADMM handles exactly this shape of problem — it lets you solve each piece using whatever specialized method fits it best, and separately manages the process of getting the two pieces to agree.

An analogy: two contractors coordinating on one wall

A kitchen renovation needs an electrician and a plumber to both work with the same wall cavity, but their plans conflict slightly — the electrician wants conduit routed where the plumber wants pipe. Rather than making one person solve both trades' problems jointly (hard), you let each work out their own ideal plan independently (easy), then compare the two plans, note where they disagree, and adjust each contractor's instructions slightly to nudge them toward a shared compromise. Repeat: each solves their own easy sub-problem again given the updated instructions, compare again, adjust again. After a few rounds, both plans converge to something they agree on. That back-and-forth, mediated by a running "disagreement penalty," is ADMM.

The method, one symbol at a time

Consider a problem of the form: minimize $f(x) + g(z)$ subject to $x = z$ (two variables tied together by a constraint that they must match). Introduce a "price" $y$ (a Lagrange multiplier) that penalizes disagreement between $x$ and $z$, plus a fixed penalty strength $\rho$. ADMM alternates three simple updates:

$$x_{k+1} = \arg\min_x \left( f(x) + \tfrac{\rho}{2}\|x - z_k + u_k\|^2 \right), \quad z_{k+1} = \arg\min_z \left( g(z) + \tfrac{\rho}{2}\|x_{k+1} - z + u_k\|^2 \right),$$ $$u_{k+1} = u_k + x_{k+1} - z_{k+1} .$$

In plain English: first, solve for $x$ treating $f$'s own difficulty as the only real problem, while lightly penalizing straying from $z$'s current value (adjusted by the running disagreement tracker $u$). Then do the mirror-image update for $z$ using $g$. Finally, update $u$ — the running record of how much $x$ and $z$ still disagree — which is added back into the next round's penalty, so persistent disagreement gets pushed on harder over time. Each of the $x$- and $z$-updates is, crucially, an easy problem on its own (often literally a proximal operator), even though the joint problem was hard.

Worked example 1: a toy 1-D split

Minimize $f(x) = (x-3)^2$ and $g(z) = (z-7)^2$ subject to $x=z$, with $\rho=1$, starting $z_0 = 0, u_0 = 0$. The $x$-update minimizes $(x-3)^2 + \tfrac12(x - 0 + 0)^2$; setting the derivative to zero, $2(x-3) + (x) = 0 \Rightarrow 3x = 6 \Rightarrow x_1 = 2$. The $z$-update minimizes $(z-7)^2 + \tfrac12(2 - z + 0)^2$; derivative zero gives $-2(z-7) - (2-z) = 0 \Rightarrow -2z+14-2+z=0 \Rightarrow z_1 = 12$... rebalancing correctly: $3z = 16 \Rightarrow z_1 \approx 5.33$. Update $u_1 = 0 + 2 - 5.33 = -3.33$. Repeating these three updates several more rounds, $x$ and $z$ both drift toward the true constrained optimum near $x=z=5$ (the midpoint-weighted compromise between pulling toward 3 and pulling toward 7), converging as the disagreement $x-z$ shrinks toward zero.

Worked example 2: lasso via ADMM

A common use is rewriting lasso, $\min_\beta \tfrac12\|y-X\beta\|^2 + \lambda|\beta|$, by introducing a copy $z=\beta$, splitting it into $f(\beta)=\tfrac12\|y-X\beta\|^2$ (smooth, easy: a linear-system solve) and $g(z)=\lambda|z|$ (non-smooth, but its own proximal step is exact soft-thresholding). The $\beta$-update solves a ridge-regression-like linear system each round; the $z$-update is a one-line soft-threshold; and $u$ tracks the running gap between them. After enough rounds, $\beta$ and $z$ converge to the same sparse vector — each round used only operations (linear solve, soft-threshold) that are individually trivial, even though jointly minimizing $f+g$ directly is not.

What this means in practice

ADMM is the go-to tool when a portfolio, risk, or model-fitting problem naturally splits across teams, data sources, or structurally different penalty terms — for example, fitting a factor model with both a smoothness penalty and a sparsity penalty simultaneously, or distributed optimization across separate data shards that can't be pooled. It lets each sub-problem be solved with the specialized, fast method that fits it, rather than forcing one general-purpose solver to handle the whole tangled thing.