Distributed Actuator Selection: Achieving Optimality Via a Primal-Dual Algorithm

Abstract

This paper addresses the actuator selection problem, i.e., given an interconnection of asymptotically stable linear dynamical systems on a network and m possible actuators choose nu among them to achieve a certain objective. In general, this is a combinatorial optimisation problem which is hard to solve; convex relaxations do not usually yield an optimal solution for the original problem. In this paper we focus on a particular instance of the actuator selection problem, namely the formulation with the trace of the controllability gramian matrix as the optimisation metric, and show that such a choice gives rise to an integer linear program. Using properties of integral polyhedra, we show through a sequence of reformulations that the optimal solution of this problem can be determined by means of a linear program without introducing any relaxation gap. This allows us to obtain the optimal solution using a primal-dual distributed algorithm, thus providing a scalable approach to the problem of actuator placement which has been up to now performed in a centralised manner enumerating all possible placement alternatives. We illustrate the main features of our approach by means of a case study involving a simplified model of the European power grid.