Optimal average consensus on multi-agent networks

In this paper, we consider a fastest average agreement scheme on multiagent networks adopting the information exchange protocol xk+1 = Wxk, where xk ∈ Rn is the value possessed by the agents at the kth time step. Mathematically, this problem can be cast as finding an optimal W ∈ Rn×n such that W1 = 1, 1TW = 1T and W ∈ S, where 1 ∈ Rn is an all-one vector and S(P) is the set of real matrices in Rn×n with zeros at the same positions specified by a sparsity pattern P. The optimal W is such that the spectral radius ρ(W - 11T /n) is minimized. To this end, we consider two numerical solution schemes: one using the qth order singular value minimization (q-SVM) and the other gradient sampling (GS), inspired by the methods proposed in (Burke et al., 2002b; Xiao and Boyd, 2004). We theoretically show that when the sparsity pattern P is symmetric, i.e. no information flow from the ith to the jth agent implies no information flow from the jth to the ith agent, the solution Ws(1) from the first order SVM method can be chosen to be symmetric and Ws(1) is a local minimum of the function ρ(W - 11T /n). Numerically we show that the q-SVM method performs much better than the GS method when P is not symmetric.