ADMM: The Alternating Direction Method of Multipliers

Precise statement: the algorithm and what it guarantees

Consider the problem: minimize f(x) + g(z) subject to Ax + Bz = c, with x ∈ ℝⁿ, z ∈ ℝᵐ, A ∈ ℝᵖˣⁿ, B ∈ ℝᵖˣᵐ, c ∈ ℝᵖ. Assume f and g are closed, proper, convex functions (i.e. lower semicontinuous, not identically +∞, never −∞). Form the augmented Lagrangian with penalty ρ > 0:

L_ρ(x,z,y) = f(x) + g(z) + ⟨y, Ax + Bz − c⟩ + (ρ/2)‖Ax + Bz − c‖².

ADMM iterates, for k = 0, 1, 2, …:

• xᵏ⁺¹ = argmin_x L_ρ(x, zᵏ, yᵏ)
• zᵏ⁺¹ = argmin_z L_ρ(xᵏ⁺¹, z, yᵏ)
• yᵏ⁺¹ = yᵏ + ρ(Axᵏ⁺¹ + Bzᵏ⁺¹ − c).

Theorem. If the unaugmented Lagrangian L₀ has a saddle point (x⋆, z⋆, y⋆), then as k → ∞: the residual rᵏ = Axᵏ + Bzᵏ − c → 0, the objective f(xᵏ) + g(zᵏ) → p⋆ (the optimal value), and yᵏ → a dual optimum y⋆. No differentiability of f or g is required.

The picture: divide the work, let a price coordinate it

The magic is splitting. The method of multipliers minimizes L_ρ over (x, z) jointly, which re-entangles the two blocks the augmentation was meant to keep cheap. ADMM instead sweeps x, then z, holding the other fixed — a single Gauss–Seidel pass rather than a full joint solve. That one relaxation is what turns a monolithic problem into two independent subproblems.

Read economically, y is a vector of shadow prices on the constraint Ax + Bz = c. Each x- and z-update is a decoupled agent minimizing its own cost plus a linear price term plus a quadratic penalty that discourages violating the shared constraint. The dual update raises the price on any constraint currently in surplus (rᵏ > 0) and lowers it on any in deficit. The penalty ρ acts as the dual step size: the augmented term makes the dual objective differentiable, so plain gradient ascent on y — with step exactly ρ — converges. The two agents never exchange full variables; they exchange only the running price and their aggregate contribution to the residual.

Key idea of the proof: ADMM is Douglas–Rachford on the dual

The clean convergence proof, due to Gabay (1983) and sharpened by Eckstein–Bertsekas (1992), identifies ADMM as an operator-splitting method. Define the dual functions via conjugates. Douglas–Rachford (DR) splitting finds a zero of a sum of two maximal monotone operators T₁ + T₂ by iterating the firmly nonexpansive DR operator; because a firmly nonexpansive map with a fixed point has iterates that converge (Krasnosel'skiĭ–Mann), DR converges. Eckstein–Bertsekas prove that applying DR to the dual operators ∂f* (subdifferential of f's conjugate, composed with A) and ∂g* (with B) produces exactly the ADMM iterates.

The elementary Boyd et al. proof instead exhibits a Lyapunov function Vᵏ = (1/ρ)‖yᵏ − y⋆‖² + ρ‖B(zᵏ − z⋆)‖² and shows Vᵏ⁺¹ ≤ Vᵏ − ρ‖rᵏ⁺¹‖² − ρ‖B(zᵏ⁺¹ − zᵏ)‖². Summing this telescoping inequality forces rᵏ → 0 and Bzᵏ to stabilize, and combined with optimality of each subproblem update gives objective and dual convergence.

Canonical example: distributed LASSO / soft-thresholding

Take LASSO: minimize (1/2)‖Dx − b‖² + λ‖x‖₁. Split by introducing z = x, so f(x) = (1/2)‖Dx − b‖², g(z) = λ‖z‖₁, constraint x − z = 0. With scaled dual u = y/ρ, the scaled ADMM reads:

• xᵏ⁺¹ = (DᵀD + ρI)⁻¹(Dᵀb + ρ(zᵏ − uᵏ)) — a ridge solve,
• zᵏ⁺¹ = S_{λ/ρ}(xᵏ⁺¹ + uᵏ) — elementwise soft-threshold,
• uᵏ⁺¹ = uᵏ + xᵏ⁺¹ − zᵏ⁺¹.

Here S_κ(v) = sign(v)·max(|v| − κ, 0) is the proximal operator of κ‖·‖₁. The nonsmooth ℓ₁ term collapses to a closed-form soft-threshold; the smooth quadratic becomes one linear solve whose matrix DᵀD + ρI is factored once and reused every iteration. For consensus ADMM the x-update splits across N machines each holding a data shard; the z-update is a simple average of the local estimates plus dual terms — the mechanism behind large-scale distributed regression.

Why the hypotheses matter — and what breaks without them

Convexity of f and g underpins both proofs: the DR operator is firmly nonexpansive only for monotone (hence convex-subdifferential) operators, and the Lyapunov inequality uses ⟨∂f(x) − ∂f(x'), x − x'⟩ ≥ 0. Drop convexity and ADMM can cycle or converge to a non-stationary point; on nonconvex problems it is only a heuristic with local guarantees under extra smoothness (Wang–Yin–Zeng 2019).

Existence of a saddle point of L₀ is essential — it is the certificate that strong duality holds and a primal-dual optimum exists. Without it (e.g. an infeasible or unbounded problem) the residual need not vanish and yᵏ can diverge.

Closedness/properness guarantees the argmin subproblems are well-posed (the prox operators exist and are single-valued). A subtle trap: with more than two blocks, the direct Gauss–Seidel extension of ADMM can diverge even for feasible convex problems (Chen–He–Ye–Yuan 2016) — three-block splitting requires modification. ADMM's guarantee is genuinely a two-operator result, connecting it to Douglas–Rachford and to Moreau's proximal calculus.

Applications and significance: why ADMM took over

ADMM's appeal is that it decouples a problem exactly along the lines where structure lives: a smooth data-fit term, a nonsmooth regularizer, and possibly a distributed data layout each get their own update. This unlocks total-variation image denoising and deblurring (the TV seminorm becomes a shrinkage), compressed sensing and basis pursuit, sparse and low-rank recovery (nuclear-norm prox via SVD soft-thresholding), SVM and logistic regression at scale, and consensus optimization across sensor networks and data centers where the dual variable is literally passed between nodes.

Its practical value is robustness over raw speed: ADMM reaches modest accuracy in tens of iterations, tolerates inexact subproblem solves, and parallelizes trivially. It also seeded a research program — inexact, accelerated, stochastic, linearized, and nonconvex ADMM variants, plus the ADMM-as-DR viewpoint that ties it to the whole monotone-operator splitting literature (Ryu–Boyd, Combettes–Pesquet). It remains the default recipe when a problem is 'convex but structured, and possibly big.'

ADMM versus neighboring first-order methods for minimizing f(x)+g(z) s.t. Ax+Bz=c

Method	Handles nonsmooth f, g	Exact constraint enforcement	Convergence hypotheses
Dual ascent	Yes (via conjugates)	Asymptotic	f strictly convex / dom coercive; often slow, needs differentiable dual
Method of multipliers (augmented Lagrangian)	Yes	Yes	f,g closed proper convex; but couples x,z — no splitting
ADMM	Yes	Yes (in the limit)	f,g closed proper convex; L₀ has a saddle point
Douglas–Rachford splitting	Yes (proximable operators)	N/A (unconstrained sum)	Maximal monotone operators; equals ADMM on the dual
Proximal gradient (ISTA)	Only one term nonsmooth	N/A	g nonsmooth proximable, f smooth with L-Lipschitz ∇f