GRAPHSP – Customized algorithms for topology identification and optimal design of noisy networks
PurposeThis website provides a Matlab implementation of customized algorithms for topology identification and optimal design of undirected consensus networks with additive stochastic disturbances. By introducing regularization into the optimal control formulation aimed at minimizing the steadystate variance amplification, this problem can be cast as a semidefinite program. Standard interiorpoint (IP) method solvers can be used to compute the optimal solution for small and mediumsize networks. We derive a Lagrange dual and exploit structure of the optimality conditions for undirected networks to develop three customized algorithms that are wellsuited for large problems. Our customized algorithms are based on:
The proximal gradient algorithm is a simple firstorder method that updates the controller graph Laplacian via convenient use of the softthresholding operator. In the IP method, the Newton direction is obtained using an inexact iterative procedure based on the preconditioned conjugate gradients and, in the proximal Newton method it is computed using cyclic coordinate descent over the set of active variables. We illustrate that all of our algorithms significantly outperform the generalpurpose solvers and greedy strategies and that the proximal algorithms can solve the problems with more than million edges in the controller graph in a few minutes, on a PC. We also exploit structure of connected resistive networks to demonstrate how additional edges can be systematically added in order to minimize the norm of the closedloop system. Problem formulationWe consider a control problem for undirected consensus networks with nodes where and denote disturbance input and performance output, is the state of the network, and is the control input. Symmetric matrices and are Laplacians of the plant and the controller, and matrices and denote state and control weights in the optimal control problem. Upon closing the loop we obtain Our objective is to identify the optimal topology for and to design the corresponding edge weights in order to achieve the desired tradeoff between controller sparsity and network performance. The performance is quantified by the steadystate variance amplification of the stochasticallyforced network (from the whiteintime input to the performance output which penalizes deviation from consensus and control effort). To achieve consensus in the absence of disturbances, the closedloop network has to be connected. This amounts to positive definiteness of the ‘‘strengthened’’ graph Laplacian of the closedloop network where , is the given incidence matrix of the controller graph, is the vector of controller edge weights, and Structural restrictions on the Laplacian matrices introduce an additional constraint on , Sparsitypromoting optimal control problemThe steadystate amplification of whiteintime disturbances is determined by the norm of stochasticallyforced network, The objective function can be expressed as where The problem of designing a controller graph that provides an optimal tradeoff between the performance of the closedloop network and the controller sparsity can be formulated as where the norm of , is introduced as a proxy for inducing sparsity. In (SP), the positive definite matrix and the vector of the edge weights are optimization variables; the problem data is given by the positive regularization parameter , the plant graph Laplacian , the state and control weights and , and the incidence matrix of the controller graph . Since minimization of the Lagrangian associated with (SP) does not lead to an explicit expression for the dual function, we introduce an auxiliary variable and find the dual of. It is wellknown that the consensus can be achieved even if some edge weights take negative values; e.g., see Xiao and Boyd ’04. By expressing the vector of the edge weights, , as a difference between two nonnegative vectors, and , the optimal control problem can be expressed as The Lagrange dual of the sparsitypromoting optimal control problem (P) is given by where is the dual variable associated with the equality constraint in (P). Growing connected resistive networksThe problem of topology identification and optimal design of stochasticallyforced networks has many interesting variations. An important class of problems is given by resistive networks in which all edge weights are restricted to be nonnegative. Here, we study the problem of growing connected resistive networks. In this, the plant graph is connected and there are no joint edges between the plant and the controller graphs. In the absence of the sparsitypromoting term, the closedloop network is given by a complete graph. Our objective is to add a small number of edges in order to optimally enhance the closedloop performance. The restriction on connected plant graphs implies positive definiteness of the strengthened graph Laplacian of the plant, Thus, is always positive definite for connected resistive networks. As done in problem (P), in order to determine the Lagrange dual of the optimization problem, we introduce an additional optimization variable . The sparsitypromoting optimal control problem simplifies to where the matrix and the vector are optimization variables. Nonnegativity of the edge weights was used to write and to remove positive definite requirements on . The Lagrange dual of the sparsitypromoting optimal control problem is given by where is the dual variable associated with the equality constraint in . AcknowledgementsThis project is supported by the
