Weighted Network Design with Cardinality Constraints via Alternating Direction Method of Multipliers

S. Chuangchuang, R. Dai, and M. Mesbahi

IEEE Transactions on Control of Network Systems

This paper examines simultaneous design of the network topology and the corresponding edge weights in presence of a cardinality constraint on the edge set. Network properties of interest for this design problem lead to optimization formulations with convex objectives, convex constraint sets, and cardinality constraints. This class of problems is referred to as Cardinality-Constrained Optimization Problem (CCOP); the cardinality constraint generally makes CCOPs NP-hard. The traditional relaxation methods, such as the l1-regularization, to approximately represent the cardinality function may fail when applied to the cardinality constraint. In this work, a customized Alternating Direction Method of Multipliers (ADMM) algorithm aiming to improve the scalability of the solution strategy for large-scale CCOPs is proposed. This algorithm utilizes the special structure of the problem formulation to obtain closed-form solutions during each iterative step of the corresponding ADMM updates.

Links: