Used in

ADMM theory

Alternating Direction Method of Multipliers for distributed optimization

Foundation

Definition

The Alternating Direction Method of Multipliers (ADMM) is a first-order optimization algorithm that solves constrained convex problems by decomposing them into smaller subproblems coordinated through dual variables. It combines the decomposability of dual ascent methods with the convergence guarantees of the method of multipliers, making it the dominant algorithm for distributed optimization in power systems, machine learning, and signal processing. In Lirion, ADMM is the engine behind distributed OPF: it splits a large network into zones that solve local subproblems in parallel, exchanging only tie-line prices to converge toward a globally consistent dispatch.

The problem ADMM solves

ADMM targets convex optimization problems with a specific separable structure. The variables x and z are coupled only through a linear constraint, which is exactly what arises when a large optimization problem is partitioned: each subsystem optimizes its local variables, and they must agree on shared boundary values.

$$\begin{aligned} \min_{x,\, z} \quad & f(x) + g(z) \\ \text{s.t.} \quad & A x + B z = c \end{aligned}$$

The objective splits into two parts f(x) and g(z), each depending on its own variable block. Many problems in OPF, machine learning, and statistics admit this form naturally or after reformulation. The “consensus” form where multiple agents must agree on a shared variable is a special case, as is “sharing” where multiple resources sum to a common budget.

The augmented Lagrangian

ADMM works with the augmented Lagrangian, which extends the standard Lagrangian by adding a quadratic penalty on constraint violation. The penalty parameter ρ > 0 controls how strongly constraint violation is punished.

$$\mathcal{L}_\rho(x, z, \lambda) = f(x) + g(z) + \lambda^T(Ax + Bz - c) + \frac{\rho}{2}\|Ax + Bz - c\|_2^2.$$

The augmented form has two crucial advantages over the plain Lagrangian:

Strong convexity: even when f or g is only weakly convex, the quadratic penalty makes the Lagrangian strongly convex in (x, z), guaranteeing unique subproblem minimizers.
Convergence under mild conditions: the method of multipliers converges for any ρ > 0 when f and g are closed convex functions, without requiring strict convexity or differentiability.

The downside is that the quadratic penalty term ‖Ax + Bz − c‖² couples x and z — exactly the coupling we wanted to break for decomposition. ADMM’s central insight is to update x and z alternately rather than jointly, restoring decomposability.

The ADMM updates

Starting from any (z&sup0;, λ&sup0;), ADMM iterates three steps per round:

$$\begin{aligned} x^{k+1} &= \arg\min_x \;\mathcal{L}_\rho(x, z^k, \lambda^k) \\ z^{k+1} &= \arg\min_z \;\mathcal{L}_\rho(x^{k+1}, z, \lambda^k) \\ \lambda^{k+1} &= \lambda^k + \rho \,(A x^{k+1} + B z^{k+1} - c) \end{aligned}$$

Each iteration involves three steps:

x-update: minimize the augmented Lagrangian over x with z fixed. Because the penalty term involves x only through Ax, the subproblem is solvable in terms of f(x) and a quadratic in x.
z-update: symmetric — minimize over z with x fixed. The subproblem involves g(z) and a quadratic in z.
Dual update: gradient ascent on the dual function, with step size ρ. The new multiplier reflects how much the latest primal iterate violates the equality constraint.

The x and z subproblems decouple from each other (each treats the other variable as a constant), enabling parallel solution. The dual update is a simple algebraic operation that consolidates the iteration.

Convergence behavior

For convex f, g and any ρ > 0, ADMM converges in three senses (Boyd et al. 2011):

Residual convergence: the primal residual r^k = Ax^k + Bz^k − c → 0 and the dual residual s^k = ρA^TB(z^k − z^k−1) → 0.
Objective convergence: f(x^k) + g(z^k) → optimal value.
Dual convergence: λ^k → some optimal dual variable λ*.

The convergence rate is O(1/k) in objective value and residuals — sublinear, slower than second-order methods like Newton but with two compensating advantages: each iteration is cheap (only subproblems, no Hessian assembly), and the iterations are embarrassingly parallel across subsystems.

In practice, ADMM reaches moderate-accuracy solutions (residuals ∼ 10⁻³) very quickly — often within 50–200 iterations. Reaching high accuracy (residuals ∼ 10⁻⁶) is slower and may require thousands of iterations. For OPF, moderate accuracy is usually sufficient because measurement noise and model approximations already introduce uncertainties at the 10⁻³ level.

Choosing the penalty parameter ρ

ADMM convergence is guaranteed for any ρ > 0, but the rate depends critically on the choice. Too small ρ leads to slow primal convergence; too large ρ leads to slow dual convergence (multipliers update too aggressively, causing oscillation). A common adaptive scheme updates ρ based on the relative magnitudes of primal and dual residuals:

$$\rho^{k+1} = \begin{cases} \tau^{\text{incr}} \cdot \rho^k & \text{if } \|r^k\|_2 > \mu^{\text{incr}} \|s^k\|_2 \\ \rho^k / \tau^{\text{decr}} & \text{if } \|s^k\|_2 > \mu^{\text{decr}} \|r^k\|_2 \\ \rho^k & \text{otherwise} \end{cases}$$

Typical parameter choices: μ_incr = μ_decr = 10, τ_incr = τ_decr = 2. The rule increases ρ when constraint violations dominate (push harder on the constraint) and decreases ρ when dual oscillations dominate (let the multipliers settle). Lirion’s distributed OPF exposes these as keyword arguments, allowing per-network tuning.

Variants and extensions

ADMM has spawned a large family of related algorithms. The most relevant for OPF and large-scale problems:

Consensus ADMM: extension to N agents agreeing on a shared variable z, with each agent updating its local x_i in parallel. The natural fit for OPF with N geographic zones sharing tie-line phases.
Sharing ADMM: extension where multiple resources sum to a common budget. Used in network flow problems with capacity constraints split across owners.
Asynchronous ADMM: relaxes the synchronization barrier between iterations, allowing agents to update at their own pace. Useful for wide-area distributed systems where communication delays are uneven.
Linearized ADMM: replaces the exact x-minimization with a single proximal gradient step, useful when f is differentiable but minimization is expensive.
Generalized ADMM: replaces the quadratic penalty with a Bregman divergence, enabling efficient updates for specific subproblem structures.

For non-convex problems like AC OPF, ADMM lacks a convergence guarantee — but empirically converges to local optima on most instances. This is why ALADIN (Augmented Lagrangian Alternating Direction Inexact Newton) was developed: it augments ADMM with a centralized quadratic program that uses local Hessians and gradients, providing stronger convergence on non-convex problems.

ADMM for distributed OPF

Distributed OPF maps onto ADMM in a natural way:

Partition the network into geographic zones Z₁, …, Z_N, each with its own buses, generators, and demand.
Identify coupling variables on tie-lines connecting different zones — phase angles in DC, voltages and angles in AC, W-variables in SOCWR.
Each zone solves its local OPF subproblem (the x-update for that zone), treating coupling variable values from neighbors as fixed and adding penalty terms for disagreement.
A coordinator updates the consensus variables (the z-update) and broadcasts updated dual prices λ to all zones.
Repeat until coupling variables agree across zones (primal residual small) and dual prices stabilize (dual residual small).

The economic interpretation is clean: λ represents the locational marginal price on tie-lines, and the iteration corresponds to a fictitious trading process where zones exchange power at evolving prices until supply and demand balance globally. This makes ADMM particularly attractive for power markets where physical decomposition mirrors organizational decomposition (ISOs, balancing authorities, control areas).