Continuous-Time and Event-Triggered Online Optimization for Linear Multi-Agent Systems

Yang Yu, Xiuxian Li, Lihua Xie

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:

  1. Primal Variable ($u_i$): The control input that drives the agent's state toward the optimal output.
  2. 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

Abstract

This paper studies the decentralized online convex optimization problem for heterogeneous linear multi-agent systems. Agents have access to their time-varying local cost functions related to their own outputs, and there are also time-varying coupling inequality constraints among them. The target of each agent is to minimize the global cost function by selecting appropriate local actions only through communication between neighbors. We design a distributed controller based on the saddle-point method which achieves constant regret bound and sublinear fit bound. Moreover, to diminish the communication overhead, another distributed controller is developed with an event-triggered communication scheme and it is shown that the above bounds are still achieved in the case of discrete communications with no Zeno behavior. A numerical example is given to verify the proposed algorithms.
BibTeX
@inproceedings{yu2022continuous,
  author = {Yang Yu and Xiuxian Li and Li Li and Lihua Xie},
  title = {{Continuous-Time and Event-Triggered Online Optimization for Linear Multi-Agent Systems}},
  booktitle = {CDC},
  year = {2022},
  url = {https://openreview.net/forum?id=0rT1movksm},
}
Figure