Distributed Design for Decentralized Control Using Chordal Decomposition and ADMM

Yang Zheng, Maryam Kamgarpour, Aivar Sootla, Antonis Papachristodoulou

TL;DR

This paper introduces a novel distributed method for designing decentralized controllers for complex systems. By leveraging the sparsity of system interactions and a technique called chordal decomposition, the problem is broken down into smaller, manageable subproblems that can be solved collaboratively by subsystems without needing a central model, thus preserving privacy.

What Problem Does This Paper Address?

Designing decentralized controllers for large-scale systems is a significant challenge. In such systems, each controller can only access local information from its subsystem. While decentralized control aims to achieve stability and optimal performance, traditional methods often require a complete model of the entire system, which is impractical for many real-world scenarios (e.g., transportation networks, power grids) due to privacy concerns and the sheer complexity of global models. This paper addresses the need for a distributed design approach that allows subsystems to collaborate on controller design using only their local model information and that of their immediate neighbors, thereby preserving privacy.

Methods

The core of the proposed method lies in combining two key techniques:

  • Chordal Decomposition: This graph-theoretic technique is used to exploit the sparsity pattern of the system's interconnections. By treating the system's structure as a graph, chordal decomposition allows the large, complex optimization problem to be broken down into smaller, interconnected subproblems based on "maximal cliques" (groups of highly connected subsystems). This decomposition is crucial for enabling distributed computation.
  • Alternating Direction Method of Multipliers (ADMM): ADMM is a powerful optimization algorithm well-suited for distributed settings. It allows for solving large-scale optimization problems by breaking them into smaller subproblems that can be solved in parallel. The paper adapts ADMM to solve the decomposed decentralized control problem, where each clique (or subsystem cluster) acts as a computing agent. ADMM iteratively updates variables and uses auxiliary variables to coordinate between these agents, ensuring a globally consistent solution.

The paper also introduces a "convex restriction" technique based on block-diagonal Lyapunov functions. This approach reformulates the original decentralized control problem into a convex optimization problem that inherits the system's sparsity, making it amenable to chordal decomposition and ADMM.

Datasets

Not discussed in the paper. The paper focuses on a theoretical framework and demonstrates its effectiveness through numerical examples based on synthetic system models.

Key Insights and Ideas

  • Sparsity is Key: The paper highlights that the inherent sparsity in the interconnections of complex systems is a valuable resource that can be exploited for distributed design.
  • Chordal Graphs for Structure: The use of chordal graphs provides a principled way to decompose complex systems into manageable, overlapping clusters (maximal cliques), which naturally map to distributed computing agents.
  • Privacy Preservation: By design, the distributed ADMM approach ensures that subsystems only need to share their local model data with their immediate neighbors within a clique, significantly enhancing data privacy compared to centralized methods.
  • Strongly Decentralized Stabilization: The paper introduces and characterizes "strongly decentralized stabilization," a condition that guarantees the existence of a decentralized controller and is crucial for the proposed convex restriction.
  • ADMM as a Natural Fit: ADMM's ability to handle distributed optimization problems with consensus constraints makes it an ideal tool for solving the chordal-decomposed decentralized control problem.

Key Results

  • Distributed Design Framework: The paper successfully develops a distributed algorithm for designing decentralized controllers that preserves model privacy.
  • Numerical Validation: Experiments on synthetic systems (first-order and second-order chains) demonstrate the effectiveness of the proposed ADMM-based approach.
  • Performance Comparison: In a comparison with other methods (sequential approach, localized LQR, truncated LQR), the proposed ADMM algorithm showed superior performance in successfully finding stabilizing decentralized controllers and achieving better H2 performance. For instance, in one example, the ADMM algorithm achieved a 100% success rate in finding stabilizing controllers, outperforming other methods that ranged from 54% to 72%.
  • Convergence: The paper shows that the ADMM algorithm converges within a reasonable number of iterations (e.g., 90% of tests required less than 150 iterations in one example).

Limitations and Future Work

  • Conservatism of Lyapunov Function: The paper acknowledges that the use of a block-diagonal Lyapunov function for the convex restriction might introduce some conservatism, meaning the solution might not be strictly optimal for the original problem.
  • Feasibility of Convex Restriction: While the paper assumes the feasibility of the convex restriction, it notes that this might not always hold even if the original problem is feasible.
  • Future Work: The authors suggest exploring less restrictive convex restrictions than the block-diagonal assumption to potentially improve optimality. They also mention studying convex restrictions that are less restrictive than the block-diagonal assumption, while still allowing distributed computation.

Summary updated

BibTeX
@article{zheng2020distributed,
  author = {Yang Zheng and Maryam Kamgarpour and Aivar Sootla and Antonis Papachristodoulou},
  title = {{Distributed Design for Decentralized Control Using Chordal Decomposition and ADMM}},
  journal = {IEEE Trans. Control. Netw. Syst.},
  year = {2020},
  url = {https://openreview.net/forum?id=kHiXfjVFFe},
}
Figure