Topology Design and Identification for Dynamic Networks
Chuangchuang Sun, Ran Dai · 2017
This chapter addresses two types of problem, network topology design (NTD) and network topology identification (NTI), both of which are classified as NP-hard problems. It generalizes the NTI problem as a nonconvex quadratically constrained quadratic programming (QCQP) problem. A general QCQP can be equivalently transformed into a linear matrix programming problem by introducing a to-be-determined rank-one matrix. Through these conversions, the NTI problem is also equivalently formulated as an rank-constrained optimization problem (RCOP), where the constrained rank is equal to 1. The chapter introduces an iterative rank minimization (IRM) method to solve RCOPs, where each iteration is formulated as a semidefinite programming (SDP) problem. To validate the effectiveness and efficiency of the proposed algorithm, the chapter applies IRM to two representative NTD problems and one NTI problem where dynamics of each node is driven by consensus protocol.