Must ADMM run on several machines?

No. It can be useful on one machine whenever the split simplifies the computation.

Does ADMM require differentiable objectives?

No. Nonsmooth terms can be handled when their subproblems or proximal operations are tractable.

Is every nonconvex ADMM application guaranteed to converge?

No. Such guarantees require additional assumptions and a relevant result for the particular formulation.

AI Glossary / Mathematics and optimization / Advanced

Alternating direction method of multipliers

Definition

The alternating direction method of multipliers, or ADMM, is an iterative optimization method that splits a structured problem into subproblems and coordinates their solutions through a constraint and a dual-variable update. It is especially useful when different parts of an objective are easier to handle separately, including some distributed and regularized learning problems.

What it means

A standard problem has the form minimize f(x)+g(z), subject to Ax+Bz=c. The variables x and z represent separate blocks, while the linear equality links them.

ADMM alternates between improving one block and improving the other, then adjusts a multiplier that responds to constraint disagreement. This is more than ordinary alternating minimization: the augmented Lagrangian and multiplier update are essential. Splitting can expose useful computational structure, but it does not automatically make every problem faster or guarantee convergence for arbitrary nonconvex formulations.

How it works

Form an augmented Lagrangian by adding both a linear multiplier term and a quadratic penalty for the equality residual Ax+Bz-c. Choose a positive penalty parameter rho.

At each iteration, minimize this expression over x while holding z and the multiplier fixed. Then minimize over z using the newly updated x. Finally update the multiplier using the new constraint residual.

In scaled form, the multiplier is represented by u, and its update adds the residual directly. Monitor both primal disagreement and a dual residual related to successive variable changes. Under standard two-block convex assumptions and the existence of a suitable saddle point, ADMM has convergence guarantees. Additional blocks, approximate solves, or nonconvex objectives require their own analysis.

Three practical examples

1. Sparse estimation: split a smooth fitting term from an absolute-value penalty so that each update has a convenient form.

2. Distributed learning: use a consensus formulation that coordinates local model variables with shared variables under a specified communication scheme.

3. Constrained reconstruction: separate a data-fitting objective from another term or constraint whose projection or proximal operation is easier to compute independently.

Think of it this way

Think of two planning teams working on different parts of one project. Each revises its own plan, and a coordinator tracks where their shared commitments disagree.

The analogy is limited: ADMM uses exact mathematical updates, not ordinary negotiation. The multiplier is an optimization variable, not a human judgment, and convergence depends on the problem and update rules rather than goodwill between the teams.

Worked example

Consider minimizing 0.5(x-4)^2+|z| subject to x=z. Use scaled ADMM with rho=1 and initialize z=0, u=0.

The x update minimizes 0.5(x-4)^2+0.5(x-z+u)^2, giving x=(4+z-u)/2. The z update applies soft thresholding at 1 to x+u: subtract 1 from a positive input above 1, add 1 to a negative input below -1, and otherwise return zero. Then set u to u+x-z.

Iteration one gives x=2, z=1, u=1. The primal residual x-z is 1, so the pair is infeasible. Iteration two gives x=2, z=2, u=1. Although its primal residual is now zero, z changed by 1, so the dual residual has not vanished. Iteration three gives x=z=2.5 and u=1.

The constrained scalar optimum is x=z=3, with objective 0.5+3=3.5. The first, infeasible pair has split objective 2+1=3, which is lower; this is not a better feasible solution. The hand calculation illustrates why objective value and primal feasibility alone are insufficient stopping checks.

Illustrative case study

Fictional case: an analytics team fits a sparse linear model with a large data-fitting term and a separate sparsity penalty. It experiments with ADMM because the split permits reusable linear algebra and a simple thresholding update.

The first dashboard displays only objective values. After finding that early iterates violate the linking constraint, the team adds primal and dual residuals with explicit tolerances. It also compares elapsed time against a suitable alternative solver.

The evaluation records the formulation, penalty parameter, stopping rule, and achieved accuracy. It does not claim that splitting alone guarantees faster training or that every intermediate coefficient vector solves the original constrained problem.

Common misconceptions and mistakes

ADMM is not simply gradient descent with two variable names. Each block update solves or approximately solves a specified subproblem.

The penalty parameter controls algorithm behavior; it is distinct from a model's regularization strength unless a formulation explicitly relates them.

Distributed computation does not automatically provide privacy. Exchanged variables can reveal information unless separate protections and threat assumptions are established.

Do not infer convergence merely because the blocks agree once. A small primal residual can coexist with a large dual residual, as the worked example shows. Similarly, classic two-block convex results cannot be transferred unchanged to every multi-block variant.

Business use

ADMM can make structured optimization practical when splitting yields cheap, reusable, or parallelizable updates. Its value depends on the cost of those updates, communication overhead, and the required solution accuracy.

Before choosing it, compare the complete workflow with alternatives under matched tolerances. Document how subproblems are solved, how rho is selected or adapted, and how residuals are scaled. Preserve a clear distinction between a solver stopping successfully and an operational model performing well on unseen data.

Check your understanding

In iteration two of the example, x equals z. Why should the algorithm not stop solely on that fact?

Answer: The agreement satisfies the linking constraint, but z is still changing and the dual residual is nonzero. The common value 2 is not the optimal value 3.

Related terms

Augmented Lagrangian
Proximal operator
Convex optimization
dual variable
soft thresholding
consensus optimization
primal residual
dual residual
operator splitting

Learn next

Work through several more iterations of the scalar example and track both residuals. Then derive a split formulation for a small least-squares problem with an absolute-value penalty. Read the two-block convergence assumptions before extending the method to distributed, approximate, or nonconvex settings.

Least squares

Sources

Primary author monograph Sections 3.1–3.3 read: Boyd and colleagues, Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers: https://web.stanford.edu/~boyd/papers/pdf/admm_distr_stats.pdf . Supplied glossary definition also checked: https://aaltodictionaryofml.github.io/ADictML_Main.pdf . The scalar updates are original hand calculations, not an executed solver benchmark.

Previous: Alternating decision tree Next: Alternative hypothesis