Alternating Direction Method of Multipliers (ADMM)

ADMM splits a large problem into smaller pieces coupled by a linear constraint, then coordinates their solutions through a dual variable.

The splitting form

ADMM solves problems of the form minimize f(x) + g(z) subject to Ax + Bz = c. The two functions can be handled by different, specialized solvers; the constraint is what forces their answers to agree. This structure appears constantly: f might be a smooth data-fit term and g a nonsmooth regularizer such as an L1 penalty.

The method works on the augmented Lagrangian, which adds a quadratic penalty on the constraint violation to the ordinary Lagrangian: L_rho(x,z,y) = f(x) + g(z) + y^T(Ax + Bz - c) + (rho/2)||Ax + Bz - c||^2. The penalty parameter rho > 0 controls how hard agreement is enforced.

The three updates

Each ADMM iteration cycles through three steps. First minimize over x holding z and y fixed. Then minimize over z holding the new x and y fixed. Finally take a gradient-ascent step on the dual variable y. The x and z minimizations are done separately, which is exactly the point: neither ever sees the other's objective except through the shared constraint.

python

import numpy as np

def admm_lasso(A, b, lam, rho=1.0, iters=200):
    m, n = A.shape
    x = np.zeros(n); z = np.zeros(n); u = np.zeros(n)
    AtA = A.T @ A + rho*np.eye(n)
    Atb = A.T @ b
    L = np.linalg.cholesky(AtA)
    def soft(v, k):
        return np.sign(v)*np.maximum(np.abs(v)-k, 0)
    for _ in range(iters):
        rhs = Atb + rho*(z - u)
        x = np.linalg.solve(L.T, np.linalg.solve(L, rhs))
        z = soft(x + u, lam/rho)      # proximal step for L1
        u = u + x - z                 # scaled dual update
    return z

Why it is used

ADMM converges under mild convexity assumptions and reaches modest accuracy quickly, which suits machine learning and signal processing where high precision is unnecessary. It also parallelizes: consensus ADMM lets many machines each solve a local subproblem and reconcile through a shared variable. The main practical difficulty is tuning rho, since convergence speed depends strongly on it.

In multiphysics engineering models such as those used for the Hyperion breeder, ADMM-style splitting lets separately maintained solvers (for magnetics and for neutron transport, say) be coupled through interface constraints without merging their codebases.