Two-Rate ADMM: Solving Long-Horizon Networked Storage Problems in Parallel Across Space and Time

Many energy systems have to make decisions at two very different speeds. A fleet of batteries spread across a grid must be dispatched every few minutes, but how hard each battery is cycled today also sets how fast it wears out over years. Two families of methods each handle one half of this problem. ADMM (the alternating direction method of multipliers) splits a large optimization across many agents. Each agent solves a small local problem, and agents agree on shared quantities through repeated exchanges of prices called multipliers. Time-scale decomposition handles the other half by cutting a long horizon into blocks and attaching a price to the energy carried from one block to the next. These two families have never been combined in the way the problem calls for. Distributed ADMM methods make every agent solve the full time horizon, so their cost grows with horizon length. Time-scale methods coordinate blocks through a single central solver.

We propose to treat the energy carried across block boundaries as one more consensus constraint inside ADMM, but to update its prices on a slow clock. The spatial prices that couple agents within a block are updated every iteration. The temporal prices that couple blocks are updated only after the fast exchanges have roughly settled. With the temporal prices held fixed, every (agent, block) pair becomes an independent small problem. A 20-year, 30-minute horizon can then be solved in parallel across time as well as across space, and each agent's work scales with block length rather than total horizon length. The two-rate structure has a second payoff. Any pair of prices gives a valid lower bound on the true optimum, and fixing the boundary energy targets gives a feasible plan. The method can therefore report a certified optimality gap without any agent revealing its local data to a central solver.

Core Claim

Index agents by $i$ and slow time blocks by $b$. Let $x_{i,b}$ be agent $i$'s fast decisions inside block $b$, and let $s_{i,b}$ be its stored energy at the block's start. The planning problem is

$$ \min \sum_{i,b} f_{i,b}(x_{i,b}, s_{i,b}, s_{i,b+1}) \quad \text{s.t.} \quad \sum_i A_i x_{i,b} \le c_b \ \ \forall b, \qquad s_{i,b+1} \ge \phi_{i,b}(x_{i,b}, s_{i,b}). $$

Here $f_{i,b}$ is the local operating and degradation cost, $A_i x_{i,b} \le c_b$ is a shared network limit such as a feeder import cap, and $\phi_{i,b}$ is the energy left at the end of the block. The second constraint is an inequality rather than an equality. That relaxation is justified by the monotonicity result of Decomposition methods for monotone two-time-scale stochastic optimization problems, which proves it leaves the optimum unchanged when extra stored energy never hurts. Its practical effect is that the temporal multipliers $\lambda_{i,b}$ become nonnegative prices on stored energy.

We dualize both coupling families, with spatial multipliers $\mu_b$ and temporal multipliers $\lambda_{i,b}$. The ordinary Lagrangian then separates into independent per-agent, per-block minimizations:

$$ \underline{V}(\lambda,\mu) = \sum_{i,b} \min_{x_{i,b}, s_{i,b}} \Big[ f_{i,b} + \mu_b^\top A_i x_{i,b} + \lambda_{i,b}\big(\phi_{i,b} - s_{i,b+1}\big) \Big] - \sum_b \mu_b^\top c_b \;\le\; \mathrm{OPT}. $$

The inequality is weak duality, so it holds for any nonnegative multipliers, including mixed-integer local models. Each agent reports one scalar per block. The algorithm itself runs augmented-Lagrangian (ADMM) updates for speed. It periodically evaluates $\underline{V}$ for the lower bound, and it evaluates a primal plan for the upper bound by fixing the boundary targets $s_{i,b}$ to their consensus values. The fixed-target plan is the distributed analogue of the "resource decomposition" bound in the same paper.

The claim is threefold. Updating temporal prices slower than spatial ones converges where a single-rate update oscillates. Per-agent work drops from the $\mathcal{O}(d^2 T)$ of Distributed and Localized Closed Loop Model Predictive Control via System Level Synthesis to roughly $\mathcal{O}(d^2 k)$ per block, where $d$ is the neighborhood size, $T$ the horizon length and $k$ the block length, with the blocks run in parallel. And the method produces gaps competitive with centralized time-block decomposition while keeping data local.

Relation to Prior Work

Our method borrows from two sources.

Three nearby papers motivate the gap rather than close it.

Two further papers constrain the design.

Research Program

We will build the two-rate algorithm on top of standard consensus ADMM. Fast iterations update agent decisions and spatial prices $\mu$. The temporal prices $\lambda$ and boundary targets $s$ are updated every $m$ fast iterations, and $m$ is the main design parameter.

The analysis has two parts.

  • Convex case. We will prove convergence when local costs are convex, treating the slow update as an outer proximal step on a function whose inner minimization is solved inexactly by the fast loop. We will bound how inexact the fast loop may be as a function of $m$.
  • Mixed-integer case. Local models with on/off or degradation-threshold decisions lose convergence guarantees, but weak duality still holds. We will report gaps rather than claim convergence there.

Engineering work covers four pieces: per-block warm starts, adaptive penalties, the periodic bound evaluation, and an online mode in which converged $\lambda$ values serve as storage prices for microsecond-scale local dispatch.

Two limitations are acknowledged in advance. The bounds in the source paper degrade under autocorrelated slow-scale noise, so we evaluate on sampled scenarios rather than claiming stochastic optimality. The approach also needs a monotone storage structure; problems without one are out of scope.

Baselines

The naive reference has two parts. First, each site optimizes alone with no coordination. Second, a sequential hierarchy solves an aggregated single-node time-block problem centrally, fixes per-block energy targets, and lets agents run spatial ADMM within each block with no price feedback. The sequential baseline is what A Tutorial on Multi-time Scale Optimization Models and Algorithms calls decoupled decision-making. That tutorial reports a value of the multi-scale model of \$50,111.77 on its capacity-expansion example, and we report the same metric. Beating this baseline means a measurably lower total cost at equal wall-clock time.

The strongest temporal competitor is centralized price and resource decomposition from Decomposition methods for monotone two-time-scale stochastic optimization problems, applied to the full multi-site problem as one monolithic node. On Site 70 alone that paper reports about a 4.8% gap between lower and upper bounds. It also reports an average price-policy cost of 2.83 M\$ versus 2.86 M\$ for the resource policy, and per-step decision times of 14.9 to 17.7 microseconds. We will rerun it on the same single-site data to reproduce those figures before scaling. Beating it means matching its gap within one percentage point at multi-site scale where it cannot run, or where it runs only by pooling all site data.

The strongest spatial competitor is uniform-horizon distributed ADMM in the style of Distributed and Localized Closed Loop Model Predictive Control via System Level Synthesis. Every agent solves the full horizon, with the same penalty tuning, warm starts and hardware as our method. No numbers on our benchmarks were found on Lacuna for this method; its stated per-subsystem complexity is $\mathcal{O}(d^2 T)$.

The Lyapunov competitor is drift-plus-penalty with single-period ADMM, from Research on Distributed Optimization Scheduling and Its Boundaries in Virtual Power Plants. It reports an 86.11% computation-time reduction and a 2.4% daily cost loss on its virtual power plant benchmark. Beating it means a cost loss under 1% at comparable time.

The key ablation is single-rate temporal ADMM. It is identical to our method except that $m=1$, so temporal prices move every iteration. This isolates whether the time-scale separation itself matters.

All methods get the same tuning budget of a fixed grid over penalty parameters. Where the problem is small enough, a full-space Gurobi solve serves as the exact reference.

Why not just…?

Why not just solve the whole thing centrally? On small instances this is the right answer, and we will use it as ground truth. At realistic scale it breaks: PAMSO: Parametric Autotuning Multi-time Scale Optimization algorithm reports full-space Gurobi returning a loss of -\$8569.38 with an 850% MIP gap on a roughly 26-million-variable multi-timescale model. Centralization also requires pooling private site data. Our 70-site, 20-year instance is of comparable size.

Why not just fix block targets centrally and distribute only within blocks? This is the most serious threat. If an aggregated central plan already sets good per-site energy targets, price feedback adds little. The sequential baseline tests this directly. If its cost falls within a fraction of a percent of ours on all benchmarks, we will report that the temporal-price coordination is unnecessary in this regime and narrow the claim to the certified bound. We expect a gap when the shared feeder limit binds unevenly across sites, because a single aggregated target cannot express which sites should hold energy.

Why not just run ordinary distributed ADMM over the full horizon? For day-scale horizons it may be competitive, and we will say so if it is. Per-agent cost and memory grow linearly in $T$, however, and $T$ here is 350,400 stages. The horizon-scaling sweep below shows where the crossover lies.

Why not just use Lyapunov decoupling? It is fast, but its reported 2.4% loss comes from discarding lookahead. Its heuristic subproblem solver also produces no prices to feed back. We compare cost directly on its own benchmark.

Proposed Experiments

Experiment 1: multi-site battery benchmark. We extend the Schneider Electric 20-year battery benchmark from Site 70 to a multi-site version, using the solar and demand profiles of the 70 sites. The sites share a synthetic feeder import cap, which provides the spatial coupling. Battery price forecasts follow the source paper's construction. We measure three things:

  • the certified gap between lower and upper bounds against block count and against $m$;
  • the policy cost over the source's 1,000 scenarios;
  • wall-clock time with blocks and agents run in parallel.

Experiment 2: distribution feeder. We add batteries at buses of the Southern California Edison 56-bus feeder. We plan a week at five-minute resolution with daily blocks and compare iteration counts against the roughly 5,000 reported for the centralized two-timescale method on that feeder.

Experiment 3: virtual power plant. We rerun the virtual power plant benchmark to compare cost loss and time against the Lyapunov method.

The decisive checks are three.

  • Separation check: single-rate ADMM ($m=1$) oscillates or stalls where moderate $m$ converges. If it does not, the time-scale argument is wrong.
  • Scaling check: per-agent time stays flat as the horizon grows from one week to 20 years while uniform-horizon ADMM grows linearly.
  • Bound check: on the Site 70 single-site case, our distributed lower bound and the centralized price bound agree, confirming the distributed bound is not loose by construction.