Anytime Feasible Distributed Optimization

74 concepts42 papers1 proposal

When designing distributed optimization algorithms for real-world networks—such as balancing power grids, scheduling cloud computing cycles, or coordinating autonomous vehicles—we usually focus on the final destination: convergence to the optimal solution.

However, in safety-critical systems, the journey matters just as much as the destination. Traditional distributed optimization frameworks (such as dual decomposition or penalty-based methods) only guarantee that constraints are satisfied asymptotically—that is, once the algorithm has fully converged. During the intermediate iterations, the system's state is often highly infeasible.

If a power grid or a cloud network executes an intermediate command before full convergence, this "transient constraint violation" can cause immediate hardware damage, system instability, or catastrophic blackouts (Distributed Resource Allocation Using One-Way Communication with Applications to Power Networks; Distributed Safe Resource Allocation using Barrier Functions).

Anytime feasibility (or all-time feasibility) flips this paradigm. It ensures that every single intermediate iteration of an optimization algorithm yields a valid, physically realizable state. If the algorithm is interrupted early due to strict real-time constraints or communication losses, the current solution can still be safely deployed (Inherently robust suboptimal MPC for autonomous racing with anytime feasible SQP; Momentum-based Distributed Resource Scheduling Optimization Subject to Sector-Bound Nonlinearity and Latency).


Why Traditional Methods Fail the Anytime Test

To understand why anytime feasibility is challenging, consider how traditional distributed algorithms handle constraints.

In a dual-domain optimization approach (like ADMM or primal-dual gradient methods), constraints are relaxed into the objective function using Lagrange multipliers (prices). The algorithm updates the primal variables to minimize cost and updates the dual variables to penalize constraint violations.

Crucially, this means the algorithm approaches the feasible region from the outside. Feasibility is only achieved when the dual variables reach their optimal steady-state values. As Alireza Aghasi et al. note in Accelerated Distributed Allocation, if you terminate a dual-domain algorithm early, the resulting resource allocation will almost certainly violate physical or safety constraints.

Dual Methods (Infeasible Journey):
[Initial State] ---> (Violates Constraints) ---> (Violates Constraints) ---> [Feasible Optimum]

Anytime Feasible Methods (Safe Journey):
[Feasible Initial State] ---> (Feasible Step 1) ---> (Feasible Step 2) ---> [Feasible Optimum]

Anytime feasible algorithms avoid this by operating strictly within the primal domain or by explicitly embedding safety mechanisms into every update step.


Mechanism 1: Conserving Resources via Graph Laplacians

For global equality constraints—such as ensuring that the total power generated across a network exactly matches total demand—anytime feasibility requires that the sum of all agent actions remains perfectly constant at every iteration.

How do agents achieve this locally without a central coordinator? They use Laplacian-based primal optimization.

Think of the network as a fluid system of interconnected tanks. If tank $A$ wants to change its level, it cannot simply create or destroy fluid; it must exchange fluid directly with its neighbors. As reviewed by Alireza Aghasi et al. in Survey of Distributed Algorithms for Resource Allocation over Multi-Agent Systems, this is mathematically enforced by structuring the algorithm's updates using a weight-balanced or undirected graph Laplacian.

When agent updates are governed by the graph Laplacian, the network dynamics inherently preserve the total resource sum. If the system is initialized in a feasible state (where total supply equals total demand), every subsequent consensus and optimization step merely redistributes resources along the network edges. Mohammadreza Doostmohammadian et al. demonstrate that this conservation property holds true even under harsh real-world conditions, such as quantized communication links and rapidly switching network topologies (Fast-Convergent Anytime-Feasible Dynamics for Distributed Allocation of Resources Over Switching Sparse Networks with Quantized Communication Links).


Mechanism 2: Repulsion Fields via Control Barrier Functions

While equality constraints can be managed via conservation laws, inequality constraints (such as keeping a generator within its minimum/maximum capacity or ensuring a vehicle stays on a track) require a different approach. For these boundaries, anytime algorithms borrow a concept from control theory: Control Barrier Functions (CBFs).

In standard optimization, a gradient step moves directly toward the minimum of a function, which often pushes the state right up against—or temporarily through—a constraint boundary.

A safe gradient flow modified by a CBF acts like a magnetic repulsion field around the boundaries of the feasible region. As the optimization state approaches a constraint boundary, the CBF modifies the gradient step, forcing the trajectory to bend and run parallel to the boundary rather than crossing it.

Constraint Boundary ───────────────────────────────────────────
                         ^             /
       Standard Step     │            /  Safe CBF Step
     (Crosses Boundary)  │           /  (Bends Parallel)
                         │          /
─────────────────────────*─────────*───────────────────────────
                      State $x_t$

Ahmed Allibhoy et al. prove in Control Barrier Function Based Design of Gradient Flows for Constrained Nonlinear Programming that if a continuous-time optimization system begins inside the feasible region, this CBF-based design guarantees it will never leave. This allows real-time controllers to stop the solver at any millisecond and safely execute the intermediate result.


Mechanism 3: Safety Buffers and Polyak Feasibility Steps

For discrete-time or online optimization settings where continuous-time tracking isn't possible, researchers use geometric projections and safety margins to maintain feasibility.

One approach is to solve a constrained local subproblem during every single update phase. For instance, Carolyn L. Beck demonstrates that by embedding local capacity constraints directly into the primal update step of a distributed network, agents prevent the system from entering unsafe states during the transient convergence process (Distributed primal dual methods for economic dispatch in power networks).

Alternatively, algorithms can incorporate an explicit safety buffer into their pricing or allocation updates. By solving the optimization problem against a slightly tightened, conservative version of the constraints, the algorithm ensures that even if there are minor transient fluctuations, the physical system never violates the true safety limits (A Safe First-Order Method for Pricing-Based Resource Allocation in Safety-Critical Networks).

Finally, in adversarial or online environments where constraints change dynamically, expensive global projections can be replaced with Polyak feasibility steps. As shown by Spencer Hutchinson et al. in Constrained Online Convex Optimization with Polyak Feasibility Steps, these steps computationally simplify the process of pulling a candidate state back into the feasible region at every round, proving that systems do not need to sacrifice long-term performance (regret) to maintain immediate, anytime safety.

Key Foundational Work

DISTRIBUTED MPC STRATEGIES FOR AUTOMATIC GENERATION CONTROL (2006) — contributed 3 concept elements to this direction.
A Distributed Newton Method for Network Utility Maximization-I: Algorithm (2013) — contributed 1 concept elements to this direction.
A Distributed Newton Method for Network Utility Maximization - Part II: Convergence (2013) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_anytime_feasibility_adf1c766,
  title = {anytime feasibility},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/anytime-feasibility/rdr_adf1c766732647858c7dcaa79a87e7bd},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_anytime_feasibility_adf1c766_v1,
  title = {anytime feasibility},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/anytime-feasibility/rdr_adf1c766732647858c7dcaa79a87e7bd/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake