Algorithms for leader selection in large dynamical networks: Noise-corrupted leaders

We examine the leader selection problem in multi-agent dynamical networks where leaders, in addition to relative information from their neighbors, also have access to their own states. We are interested in selecting an a priori specified number of agents as leaders in order to minimize the total variance of the stochastically forced network. Combinatorial nature of this optimal control problem makes computation of the global minimum difficult. We propose a convex relaxation to obtain a lower bound on the global optimal value, and use simple but efficient greedy algorithms to obtain an upper bound. Furthermore, we employ the alternating direction method of multipliers to search for a local minimum. Two examples are provided to illustrate the effectiveness of the developed methods.