Achieving violation-free distributed optimization under coupling constraints

Changxin Liu, Xiao Tan, Xuyang Wu, Dimos V. Dimarogonas, Karl Henrik JohanssonAutomatica 2026 · DOI

TL;DR

This paper introduces a novel distributed optimization algorithm that guarantees all coupling constraints are satisfied at every iteration, not just asymptotically. This is crucial for safety-critical applications where constraint violations can have severe consequences. The method reformulates the problem using auxiliary variables and a network-dependent linear mapping, enabling a distributed min-min optimization approach with provable convergence.

What Problem Does This Paper Address?

Many real-world distributed optimization problems, such as coordinating multi-agent systems or managing power grids, involve decision variables that are subject to "coupling constraints." These constraints often represent shared resources or physical limitations that cannot be violated. While existing distributed optimization algorithms can achieve asymptotic feasibility (meaning violations disappear over time), they often fail to guarantee that intermediate or final solutions are always feasible. This is problematic for safety-critical systems where even temporary violations can be catastrophic. Furthermore, projecting these asymptotically feasible solutions onto the true feasible set is often not possible in a distributed setting. This paper aims to bridge this gap by developing algorithms that ensure all-time constraint satisfaction.

Methods

The core of the proposed solution lies in a clever reformulation of the original optimization problem. The authors introduce auxiliary decision variables and a specific network-dependent linear mapping for each coupling constraint. This transformation allows them to view the problem as a min-min optimization problem, where they first optimize these auxiliary variables and then the original primal variables.

Key aspects of their method include:

  • Reformulation with Auxiliary Variables: By introducing slack variables and a linear transformation involving a matrix derived from the communication network's structure (specifically, I - P[l], where P[l] is a doubly stochastic matrix related to the graph), they ensure that the feasible set of the reformulated problem, when projected back to the original primal variables, remains identical to the original problem's feasible set. This is the key to achieving all-time feasibility.
  • Min-Min Optimization: The reformulated problem is treated as a two-level optimization. The inner problem involves optimizing the auxiliary variables, and the outer problem optimizes the primal variables.
  • Locally Computable Gradients: A crucial contribution is showing that the gradients of the objective function in the outer minimization problem can be computed locally by each agent. This is achieved by leveraging the KKT multipliers of the inner optimization problem and a specific linear mapping that aligns with the network structure.
  • Distributed Algorithms: Based on these insights, two violation-free distributed optimization algorithms are developed: one for strongly convex problems (using accelerated dual averaging) and another for general convex problems (using gradient descent with a compact constraint on auxiliary variables).
  • Convergence Analysis: The paper provides theoretical guarantees for the convergence of these algorithms under reasonable assumptions, including explicit rates for the strongly convex case.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and numerical experiments on a simulated system.

Key Insights and Ideas

  • The Power of Reformulation for Safety: The most significant insight is that by carefully reformulating the problem with auxiliary variables and network-aware linear mappings, one can transform a problem with hard-to-guarantee-feasible intermediate steps into one where feasibility is inherently maintained. This is a powerful paradigm shift for safety-critical distributed control.
  • Network Structure as a Tool, Not Just a Constraint: The authors effectively leverage the network topology (represented by matrices like P[l]) not just to define communication but as an integral part of the optimization formulation itself, enabling local gradient computation.
  • Bridging Asymptotic and All-Time Feasibility: The paper directly addresses the limitations of existing methods that only offer asymptotic feasibility, providing a concrete path to achieving guaranteed safety in distributed systems.
  • Min-Min Optimization for Distributed Control: The min-min approach, combined with the ability to compute gradients locally, offers a flexible framework for designing distributed controllers that respect complex coupling constraints.

Key Results

  • Violation-Free Algorithms: The proposed algorithms are proven to produce violation-free solutions at every iteration, meaning that the coupling constraints are always satisfied.
  • Provable Convergence: The algorithms are shown to converge to the optimal solution with explicit rates for strongly convex problems and convergence guarantees for general convex problems.
  • Application to Control Barrier Functions (CBFs): The effectiveness of the algorithm is demonstrated by applying it to implement a distributed control barrier function (CBF) based controller for a multi-agent system with coupling state constraints. The numerical results show that the algorithm successfully achieves consensus while maintaining constraint satisfaction.
  • Efficiency: The use of network-dependent mappings and local gradient computation contributes to efficient communication and computation.

Limitations and Future Work

  • Assumption 2-ii) Rank Condition: The paper relies on an assumption that certain matrices formed by the constraint coefficients are full row rank. The authors acknowledge that this condition can be relaxed, and they suggest exploring this relaxation as a future research direction.
  • Nonlinear Coupling Constraints: The current work focuses on linearly constrained problems. Extending the approach to handle nonlinear coupling constraints is a natural and important avenue for future research.
  • Strongly Convex Assumption: While the paper presents an extension to general convex problems, the primary algorithm (Algorithm 1) is developed under the assumption of strongly convex local objective functions. Further investigation into the performance and convergence for more general objective functions could be beneficial.
  • Compact Constraint for General Convex Case: For general convex problems, a compact constraint is introduced on the auxiliary variables to ensure boundedness of gradients. While this doesn't affect the optimal solution if chosen large enough, it adds a layer of complexity that might be further optimized.

Summary updated

BibTeX
@article{liu2026achieving,
  author = {Changxin Liu and Xiao Tan and Xuyang Wu and Dimos V. Dimarogonas and Karl Henrik Johansson},
  title = {{Achieving violation-free distributed optimization under coupling constraints}},
  journal = {Automatica},
  year = {2026},
  doi = {10.1016/j.automatica.2025.112774},
}
Figure