Lyapunov analysis of quadratically symmetric neighborhood consensus algorithms

We consider a class of neighborhood consensus algorithms for multi-agent systems. Within this class, the agents move along the gradients of a particular function, which can be represented as the sum of the minimums of several quadratically symmetric nonnegative functions. For these systems, we provide generic Lyapunov functions that are nonincreasing along the trajectories. Under some mild technical assumptions, the Lyapunov functions prove convergence of the algorithms when the number of agents is finite. We show that a well-known model of multi-agent systems, namely the opinion dynamics model, is a special case of this class. The opinion dynamics model was first introduced by Krause and consists of a distribution of agents on the real line, where the agents simultaneously update their positions by moving to the average of the positions of their neighbors including themselves. We show that a specific Lyapunov function that was previously proposed for the opinion dynamics model by Blondel et. al. can be recovered from our generic Lyapunov function. In addition to providing intuition about the dynamics of neighborhood consensus algorithms, our Lyapunov analysis is particularly useful for analysis of the infinite-dimensional case, where extensions of the combinatorial approaches may not be convenient or possible.