Introduction

Imagine a thousand computers, each sitting on a slice of your data, trying together to train the best possible model. Sending all that data to one machine is slow, costly, and often illegal. Can they find the global answer without ever pooling their data?

ADMM — the Alternating Direction Method of Multipliers — says yes. Developed in the 1970s by Glowinski & Marroco and Gabay & Mercier, and rediscovered as the backbone of modern distributed learning by Boyd et al. in 2011, ADMM works by splitting an optimization problem into small local pieces each agent can solve by itself, then coordinating those solutions through a shared dual variable that acts like a price signal nudging everyone toward agreement.

The magic is that each agent only talks to a coordinator, solves a tiny local problem, and still provably converges to the global optimum — as long as the overall problem is convex. Splitting without losing optimality is the key insight.

Watch Two Agents Converge

Two agents each have a private target value (their local cost minimum). They must agree on a single shared value — the consensus point — while each tries to stay as close as possible to their own target.

Press Run ADMM to watch them negotiate via the dual variable (the price of deviation). Each iteration you see both agents update their local estimate, the coordinator averages them, and the dual variable tightens the agreement.

<div class="controls">
  <label>Agent 1 target (a): <span id="t1val">2</span>
    <input type="range" id="t1" min="-4" max="4" step="0.5" value="2">
  </label>
  <label>Agent 2 target (b): <span id="t2val">8</span>
    <input type="range" id="t2" min="-4" max="12" step="0.5" value="8">
  </label>
  <label>Penalty &rho;: <span id="rhoval">0.5</span>
    <input type="range" id="rho" min="0.1" max="3" step="0.1" value="0.5">
  </label>
</div>
<div class="btns">
  <button id="run" type="button">Run ADMM</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div id="status" class="status"></div>
<canvas id="chart" width="520" height="210"></canvas>
<div id="log" class="log"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.controls { display: flex; flex-direction: column; gap: .4rem; margin-bottom: .7rem; }
label { font-size: .88rem; display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; }
input[type=range] { flex: 1; min-width: 80px; accent-color: #1d3557; }
.btns { display: flex; gap: .5rem; margin-bottom: .6rem; }
button { font: 600 14px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.4em; margin-bottom: .4rem; color: #0a7d33; }
canvas { border: 1px solid #dde4ea; border-radius: 8px; background: #f8fafc;
         display: block; max-width: 100%; }
.log { font: .76rem/1.5 ui-monospace, monospace; color: #555; margin-top: .5rem;
       max-height: 76px; overflow-y: auto; border: 1px solid #e3e8ed; border-radius: 6px;
       padding: .3rem .5rem; background: #fafbfc; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// ADMM consensus demo — two agents must agree on a shared value z
// while each minimizes its own local cost fi(xi) = (xi - ti)^2 / 2
//
// Proper scaled-form ADMM with separate dual variables (Boyd et al. 2011):
//   xi_k+1 = argmin [ fi(xi) + (rho/2)||xi - z_k + u_i_k||^2 ]
//          = (t_i + rho*(z_k - u_i_k)) / (1 + rho)
//   z_k+1  = mean_i( xi_k+1 + u_i_k )   // [coordinator minimizes coupling]
//   u_i_k+1 = u_i_k + xi_k+1 - z_k+1    // [dual update per agent]
//
// Optimal solution: z* = (a + b) / 2  (equal weights)
// Convergence: primal residual ||x - z*1|| -> 0 at rate O(1/k)

const MAX_ITER = 35;
const EPS = 1e-5;

function runADMM(a, b, rho) {
  // Start from zero (not the average) to show convergence dynamics
  let x1 = 0, x2 = 0, z = 0, u1 = 0, u2 = 0;
  const steps = [];
  steps.push({ iter: 0, x1, x2, z, u: 0, pRes: null });

  for (let k = 1; k <= MAX_ITER; k++) {
    // Local x-updates (each agent independently)
    const x1n = (a + rho * (z - u1)) / (1 + rho);
    const x2n = (b + rho * (z - u2)) / (1 + rho);
    // Coordinator z-update: average of (xi + ui)
    const zn  = ((x1n + u1) + (x2n + u2)) / 2;
    // Dual updates
    const u1n = u1 + x1n - zn;
    const u2n = u2 + x2n - zn;
    // Primal residual: how far agents are from consensus
    const pRes = Math.sqrt((x1n - zn) ** 2 + (x2n - zn) ** 2);
    const dz   = Math.abs(zn - z);
    x1 = x1n; x2 = x2n; z = zn; u1 = u1n; u2 = u2n;
    steps.push({ iter: k, x1, x2, z, u: (Math.abs(u1) + Math.abs(u2)) / 2, pRes });
    if (dz < EPS) break;
  }
  return { steps, optimal: (a + b) / 2 };
}

function drawChart(steps, optimal, a, b) {
  const canvas = document.getElementById('chart');
  const ctx = canvas.getContext('2d');
  const W = canvas.width, H = canvas.height;
  const pad = { top: 18, right: 20, bottom: 38, left: 46 };
  const cW = W - pad.left - pad.right;
  const cH = H - pad.top - pad.bottom;

  ctx.clearRect(0, 0, W, H);

  const allVals = steps.flatMap(s => [s.x1, s.x2, s.z]).concat([a, b, optimal]);
  const minV = Math.min(...allVals) - 0.8;
  const maxV = Math.max(...allVals) + 0.8;
  const n = steps.length;

  const sx = i => pad.left + (i / Math.max(n - 1, 1)) * cW;
  const sy = v => pad.top + cH - ((v - minV) / (maxV - minV)) * cH;

  // Grid
  ctx.strokeStyle = '#e0e6ec'; ctx.lineWidth = 1;
  for (let g = 0; g <= 4; g++) {
    const y = pad.top + (g / 4) * cH;
    ctx.beginPath(); ctx.moveTo(pad.left, y); ctx.lineTo(pad.left + cW, y); ctx.stroke();
    const val = maxV - (g / 4) * (maxV - minV);
    ctx.fillStyle = '#777'; ctx.font = '10px system-ui'; ctx.textAlign = 'right';
    ctx.fillText(val.toFixed(1), pad.left - 4, y + 3);
  }

  // Optimal dashed line
  ctx.strokeStyle = '#aaa'; ctx.lineWidth = 1.2; ctx.setLineDash([4, 3]);
  ctx.beginPath(); ctx.moveTo(pad.left, sy(optimal)); ctx.lineTo(pad.left + cW, sy(optimal)); ctx.stroke();
  ctx.setLineDash([]);
  ctx.fillStyle = '#888'; ctx.textAlign = 'left'; ctx.font = '10px system-ui';
  ctx.fillText('z*=' + optimal.toFixed(1), pad.left + cW + 2, sy(optimal) + 3);

  // Series: x1 (blue), x2 (red), z (green)
  const series = [
    { key: 'x1', color: '#1d78c8', label: 'Agent 1 (x₁)' },
    { key: 'x2', color: '#e63946', label: 'Agent 2 (x₂)' },
    { key: 'z',  color: '#2a9d54', label: 'Consensus z' }
  ];
  series.forEach(({ key, color }) => {
    ctx.strokeStyle = color; ctx.lineWidth = 2;
    ctx.beginPath();
    steps.forEach((s, i) => { i === 0 ? ctx.moveTo(sx(i), sy(s[key])) : ctx.lineTo(sx(i), sy(s[key])); });
    ctx.stroke();
    steps.forEach((s, i) => {
      if (i % Math.max(1, Math.floor(n / 12)) === 0 || i === n - 1) {
        ctx.fillStyle = color;
        ctx.beginPath(); ctx.arc(sx(i), sy(s[key]), 3, 0, 2 * Math.PI); ctx.fill();
      }
    });
  });

  // X-axis
  ctx.fillStyle = '#555'; ctx.font = '10px system-ui'; ctx.textAlign = 'center';
  const lStep = Math.max(1, Math.floor(n / 8));
  steps.forEach((s, i) => {
    if (i % lStep === 0 || i === n - 1) ctx.fillText(s.iter, sx(i), H - pad.bottom + 14);
  });
  ctx.fillText('Iteration k', pad.left + cW / 2, H - 2);

  // Y-axis label
  ctx.save(); ctx.translate(11, pad.top + cH / 2); ctx.rotate(-Math.PI / 2);
  ctx.fillStyle = '#555'; ctx.textAlign = 'center'; ctx.fillText('Value', 0, 0); ctx.restore();

  // Legend
  const leg = [{ c: '#1d78c8', l: 'Agent 1' }, { c: '#e63946', l: 'Agent 2' },
               { c: '#2a9d54', l: 'Consensus z' }, { c: '#aaa', l: 'Optimal z*' }];
  let lx = pad.left;
  ctx.font = '10px system-ui'; ctx.textAlign = 'left';
  leg.forEach(({ c, l }) => {
    ctx.fillStyle = c; ctx.fillRect(lx, 3, 12, 7);
    ctx.fillStyle = '#333'; ctx.fillText(l, lx + 14, 11);
    lx += 14 + ctx.measureText(l).width + 10;
  });
}

function runDemo() {
  const a = parseFloat(document.getElementById('t1').value);
  const b = parseFloat(document.getElementById('t2').value);
  const rho = parseFloat(document.getElementById('rho').value);
  const { steps, optimal } = runADMM(a, b, rho);

  drawChart(steps, optimal, a, b);

  const last = steps[steps.length - 1];
  const iters = last.iter;
  document.getElementById('status').textContent =
    fmt('Converged in %iters% iteration(s) → z = %z%  (optimal = %optimal%)', { iters: iters, z: last.z.toFixed(4), optimal: optimal.toFixed(4) });

  document.getElementById('log').innerHTML =
    steps.slice(0, 10).map(s =>
      `k=${String(s.iter).padStart(2)}: x1=${s.x1.toFixed(3)}  x2=${s.x2.toFixed(3)}  z=${s.z.toFixed(4)}  pRes=${s.pRes !== null ? s.pRes.toExponential(2) : '—'}`
    ).join('<br>') + (steps.length > 10 ? fmt('<br>… (%v% more iterations)', { v: steps.length - 10 }) : '');
}

function resetDemo() {
  const ctx = document.getElementById('chart').getContext('2d');
  ctx.clearRect(0, 0, 520, 210);
  document.getElementById('status').textContent = '';
  document.getElementById('log').innerHTML = '';
}

['t1', 't2', 'rho'].forEach(id => {
  const el = document.getElementById(id);
  const disp = document.getElementById(id + 'val');
  el.addEventListener('input', () => { disp.textContent = el.value; resetDemo(); });
});
document.getElementById('run').addEventListener('click', runDemo);
document.getElementById('reset').addEventListener('click', resetDemo);

// Inline verification
(function verify() {
  function admmResult(a, b, rho) {
    let x1=0, x2=0, z=0, u1=0, u2=0;
    for (let k=1; k<=200; k++) {
      const x1n=(a+rho*(z-u1))/(1+rho), x2n=(b+rho*(z-u2))/(1+rho);
      const zn=((x1n+u1)+(x2n+u2))/2;
      const dz=Math.abs(zn-z);
      u1+=x1n-zn; u2+=x2n-zn;
      x1=x1n; x2=x2n; z=zn;
      if(dz<1e-6) break;
    }
    return z;
  }
  const tests = [[2,8,0.5,5],[0,10,1.0,5],[-3,3,0.5,0],[4,4,1.0,4],[1,5,2.0,3]];
  tests.forEach(([a,b,rho,opt]) => {
    const z = admmResult(a,b,rho);
    if (Math.abs(z-opt)>1e-4) console.error('ADMM FAIL', a, b, rho, 'got', z, 'expected', opt);
    else console.log(fmt('ADMM OK: a=%a% b=%b% rho=%rho% -> z=%z% (expected %opt%)', { a: a, b: b, rho: rho, z: z.toFixed(6), opt: opt }));
  });
})();
Result
Console

Notice the dual variable grows whenever the agents still disagree and flattens when they converge. The final consensus value is the average of the targets — provably optimal for this equal-weight problem. Drag the sliders to change each agent's private target and watch the convergence path change.

The Real Complexity

ADMM sits at the intersection of two classical ideas:

  • Dual decomposition splits the primal problem across agents but converges slowly.
  • Augmented Lagrangian adds a penalty term that speeds convergence but couples the subproblems, forcing a joint solve.

ADMM gets the best of both: add the quadratic penalty term and split the subproblems. Each agent's local problem gains a small coupling term (the ρ penalty times a squared deviation from consensus), but it remains separable and solvable locally.

Convergence guarantees — For convex problems, ADMM converges to the global optimum at an O(1/k)O(1/k) rate, where k is the number of iterations. Under stronger conditions (strong convexity, smooth objectives), it converges linearly. The penalty parameter ρ controls the trade-off: too small and primal convergence is slow; too large and dual convergence suffers. Choosing ρ well — or adapting it automatically — is an active research area.

Limits — ADMM requires convexity. For non-convex problems (like training deep neural networks) it can still work in practice but loses its guarantees. It also requires each local subproblem to have a closed-form or cheaply solvable answer — if the local solve is itself expensive, the communication savings evaporate.

ADMM does not solve the hardness of non-convex optimization: it sidesteps it by assuming convexity in the first place. Within that assumption it is one of the most practical distributed algorithms known.

Where It Matters

ADMM's ability to split problems without losing the global answer makes it the algorithm of choice wherever data is large, distributed, or private:

  • Federated learning: each device (phone, hospital) solves a local model update; ADMM coordinates them into a global model without raw data ever leaving the device. Privacy and accuracy at once.
  • LASSO and sparse regression: the split cleanly separates the squared-loss term (solved in closed form) from the L1 regularizer (solved by soft-thresholding), producing one of the most elegant ADMM decompositions known.
  • Image and signal reconstruction: MRI scanners reconstruct images by solving a large compressed-sensing problem; ADMM distributes the reconstruction across processors, each handling a block of measurements.
  • Power grid optimization: the optimal power flow problem that balances supply and demand across a grid decomposes naturally by region — ADMM lets each region solve locally while a coordinator enforces the inter-region flow constraints.
  • Model predictive control: robotics and autonomous vehicles solve a trajectory optimization at every time step; ADMM's warm-starting (reuse the previous iterate) makes it fast enough for real-time use.

The common thread is linear programming and convex structure: wherever a large convex problem can be split into manageable local pieces with a shared coupling constraint, ADMM turns a single hard solve into many easy ones.

Conclusion

ADMM's core insight is surprisingly simple: if a problem is convex and can be split, you do not need everyone in the same room. Each agent solves its own local piece, a coordinator averages the answers and sends a correction signal, and the process repeats until everyone agrees. The global optimum emerges from purely local work.

That elegance has made ADMM the quiet engine behind federated learning, compressed sensing, and power grid control. Next time your phone trains a personal model without sending your data to a server, or an MRI reconstructs your scan in seconds, there is a good chance ADMM — and the dual variable nudging agents toward consensus — is doing the heavy lifting.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/admm/Content licensed under CC BY-NC 4.0.