Abstract
This paper addresses the challenge of decentralized online convex optimization (OCO) for heterogeneous linear multi-agent systems. In dynamic environments where cost functions and coupling constraints vary over time, agents must coordinate to minimize a global objective while adhering to their individual physical dynamics. We present a distributed saddle-point control law that achieves a constant regret bound $O(1)$ and sublinear constraint violation $O(\sqrt{T})$. Furthermore, to optimize communication efficiency, an event-triggered mechanism is introduced that maintains these performance guarantees while significantly reducing the frequency of inter-agent data exchange.
Introduction
In modern large-scale systems such as smart power grids, robotic swarms, and autonomous traffic networks, a collective of agents must solve optimization problems in real-time. These scenarios are characterized by two primary difficulties: the "online" nature of the task, where costs and constraints are revealed only as decisions are made, and the physical constraints of the agents themselves.
While traditional Online Convex Optimization (OCO) provides a robust framework for decision-making under uncertainty, it typically assumes agents are "point masses" capable of instantaneous state transitions. This paper bridges the gap between OCO and control theory by considering agents with heterogeneous linear dynamics. The goal is to design a decentralized controller that allows agents to track a moving optimal trajectory while satisfying global coupling constraints using only local information.
Problem Formulation
We consider a system of $N$ agents, where each agent $i$ follows a linear time-invariant (LTI) model: $$\dot{x}_i(t) = A_i x_i(t) + B_i u_i(t)$$ $$y_i(t) = C_i x_i(t)$$
The objective is to minimize a time-varying global cost function $\sum_{i=1}^N f_{i,t}(y_i(t))$ subject to a time-varying coupling inequality constraint $\sum_{i=1}^N g_{i,t}(y_i(t)) \leq 0$. The agents communicate over an undirected, connected graph, sharing information only with their immediate neighbors.
Methodology
Distributed Saddle-Point Controller
The proposed solution utilizes a modified Arrow-Hurwicz saddle-point algorithm adapted for continuous-time dynamics. The controller maintains two primary variables:
- Primal Variable ($u_i$): The control input that drives the agent's state toward the optimal output.
- Dual Variable ($\lambda_i$): A local estimate of the Lagrange multiplier associated with the coupling constraints.
By constructing a global time-varying Lagrangian that includes a "disagreement" penalty, the agents can reach a consensus on the dual variables. This ensures that the global coupling constraint is respected even though no single agent has a global view of the system.
Event-Triggered Communication
To prevent the high bandwidth requirements of continuous communication, the authors implement an event-triggered scheme. Instead of broadcasting states constantly, an agent only sends an update to its neighbors when the difference between its current state and its last broadcast state exceeds a specific, time-decaying threshold. This approach is rigorously proven to avoid "Zeno behavior"—a common pitfall in control systems where an infinite number of triggers occur in a finite time interval.
Key Theoretical Results
Constant Regret ($O(1)$)
The most significant contribution of this work is the achievement of a constant regret bound. In OCO, regret measures the difference between the cumulative cost incurred by the algorithm and the cost of the best fixed decision in hindsight. While most existing literature targets sublinear regret (e.g., $O(\sqrt{T})$), this framework demonstrates that the total cumulative error is capped by a fixed constant, regardless of the time horizon $T$. Specifically, in the continuous-time case, the bound is defined by the initial distance from the optimal state: $\frac{\|y(0)-y^*\|^2}{2\epsilon}$.
Constraint Violation (Fit)
The algorithm ensures that the "fit"—the measure of how much the coupling constraints are violated over time—is bounded by $O(\sqrt{T})$. This guarantees that the average constraint violation vanishes as $T$ approaches infinity, ensuring long-term feasibility of the system's operation.
Simulation and Validation
The researchers validated the controller using a numerical simulation of five agents with heterogeneous dynamics (ranging from 2D to 3D state-space models). Under time-varying quadratic costs and sinusoidal coupling constraints, the system successfully demonstrated the theoretical $O(1)$ regret. The results confirmed that the feedback matrices ($K_\alpha, K_\beta$) allow the agents to effectively "track" the moving optimal point with high precision, even under the constraints of the event-triggered communication schedule.
Conclusion and Future Work
This paper provides a powerful framework for online optimization in physical multi-agent systems, proving that physical dynamics and communication constraints do not necessarily preclude high-performance optimization. The achievement of constant regret represents a significant advancement over previous sublinear results.
Future research directions include:
- Nonlinear Dynamics: Extending the framework to handle complex, non-linear agent models (e.g., quadrotors).
- Directed Networks: Adapting the consensus mechanisms for directed or time-varying communication topologies.
- Model Uncertainty: Developing adaptive or model-free versions of the controller for cases where the $A, B, C$ matrices are not perfectly known.
- Non-Convexity: Addressing the challenges of non-convex cost functions and constraints in a distributed setting.
Summary updated