Estimation of Complex-Valued Laplacian Matrices for Topology Identification in Power Systems

Morad Halihal, Tirza Routtenberg, H. Vincent Poor

TL;DR

This paper introduces a novel method for estimating the complex-valued Laplacian matrix of power systems, crucial for understanding network topology. By leveraging a joint sparsity constraint and an ADMM algorithm, the authors achieve more accurate recovery of the system's admittance matrix compared to existing methods, particularly under realistic non-linear power flow models.

What Problem Does This Paper Address?

Accurately identifying the topology of power systems is vital for their reliable operation, control, and security. This topology is often represented by the system's admittance matrix. While previous work has focused on estimating real-valued matrices or using simplified power flow models, this paper tackles the more challenging problem of estimating a complex-valued Laplacian matrix that represents the system's admittance. This is important because power systems involve complex-valued quantities (voltage and current phasors), and their interactions are best captured by complex-valued models. A key challenge is that the real and imaginary parts of the complex Laplacian matrix exhibit a "joint sparsity" pattern, meaning they tend to be zero in similar locations, which existing methods don't fully exploit.

Methods

The authors propose a Constrained Maximum Likelihood Estimator (CMLE) for the complex-valued Laplacian matrix. This CMLE is formulated as an optimization problem with constraints on symmetry, null-space property, non-positive off-diagonal entries, positive semi-definiteness, and importantly, joint sparsity between the real and imaginary parts. To handle the non-convexity introduced by the joint sparsity constraint, they employ a convex relaxation using a mixed $\ell_{2,1}$ norm. This relaxation promotes "group sparsity," encouraging simultaneous zeros in corresponding entries of the real and imaginary parts.

The core of their solution is a new Alternating Direction Method of Multipliers (ADMM) algorithm designed to efficiently solve this regularized optimization problem. ADMM is a powerful iterative technique for optimization problems with separable objective functions and constraints, which they adapt here by introducing auxiliary variables to decouple terms. The paper details the three stages of the ADMM algorithm: updating the primary variables (G and B), updating the auxiliary variables (ZG and ZB), and updating the dual variables (Lagrange multipliers). They also propose a sample-covariance-based initialization method for the ADMM algorithm to ensure the initial estimates are valid Laplacian matrices.

Datasets

The authors evaluate their proposed method using data from the IEEE 33-bus power system. They also refer to results from IEEE 14-bus, 57-bus, 118-bus, and 145-bus systems for experimental validation of sparsity patterns and run-time comparisons. The data for these simulations are generated using the MATPOWER software package, simulating power flow under different models (AC, DLPF, and DC).

Key Insights and Ideas

  • Joint Sparsity is Key: The paper highlights that the real and imaginary parts of the complex Laplacian matrix are not just individually sparse but exhibit a joint sparsity pattern. Exploiting this is crucial for accurate topology recovery.
  • Complex-Valued Models Matter: Using complex-valued models (like the AC power flow model) provides a more accurate representation of power systems and leads to better estimation results compared to simplified linear models (DLPF, DC).
  • ADMM for Complex Laplacian: The development of a specialized ADMM algorithm is a significant contribution, enabling efficient and tractable optimization for this complex estimation problem.
  • Initialization is Important: A well-designed initialization procedure for the ADMM algorithm is shown to be beneficial, ensuring that the algorithm starts with valid Laplacian matrices.

Key Results

  • The proposed ADMM algorithm, particularly the ADMM-AC variant (using the AC power flow model), outperforms existing methods in terms of Mean Squared Error (MSE) and F-score for estimating the admittance matrix.
  • The F-score results for various IEEE test systems (Table I) demonstrate that the real and imaginary parts of the admittance matrix are indeed nearly jointly sparse, with F-scores often above 0.9.
  • In simulations based on the DLPF model, the proposed ADMM-DLPF method showed monotonic decrease in MSE with increasing SNR, outperforming other methods at lower SNRs where some methods plateaued.
  • When using the more accurate AC model, the ADMM-AC algorithm significantly outperformed DC-based methods and ADMM-DLPF, underscoring the advantage of using a more realistic power flow model.
  • The ADMM-based methods demonstrate good scalability in terms of run-time as the system size increases, making them practical for large-scale power systems.

Limitations and Future Work

  • Blind Scenarios: The paper acknowledges that scenarios with missing voltage and/or power measurements (blind scenarios) are not fully addressed and suggest this as future work.
  • Performance Bounds: Developing theoretical performance bounds for the estimation approach is identified as an area for further research.
  • General GSP Tools: The authors suggest that developing Graph Signal Processing (GSP) tools specifically for complex-valued Laplacians would be beneficial for broader applications.
  • Distribution Networks (DNs): Applying the proposed methods to Distribution Networks, which are much larger and often less observable than Transmission Networks, requires further work to address issues like missing measurements and integrate structural characteristics.
  • Sensor Allocation: Investigating sensor allocation strategies to guarantee system identifiability is another promising direction.

Summary updated

Abstract

In this paper, we investigate the problem of estimating a complex-valued Laplacian matrix with a focus on its application in the estimation of admittance matrices in power systems. The proposed approach is based on a constrained maximum likelihood estimator (CMLE) of the complex-valued Laplacian, which is formulated as an optimization problem with Laplacian and sparsity constraints. The complex-valued Laplacian is a symmetric, non-Hermitian matrix that exhibits a joint sparsity pattern between its real and imaginary parts. Thus, we present a group-sparse-based penalized log-likelihood approach for the Laplacian estimation. Leveraging the mixed \ell 2,1 norm relaxation of the joint sparsity constraint, we develop a new alternating direction method of multipliers (ADMM) estimation algorithm for the implementation of the CMLE of the Laplacian matrix under a linear Gaussian model. Next, we apply the proposed ADMM algorithms for the problem of estimating the admittance matrix under three commonly used measurement models that stem from Kirchhoff and Ohm laws, each with different assumptions and simplifications: 1) the nonlinear alternating current (AC) model; 2) the decoupled linear power flow (DLPF) model; and 3) the direct current (DC) model. The performance of the ADMM algorithm is evaluated using data from the IEEE 33-bus power system data under different settings. The numerical experiments demonstrate that the proposed algorithm outperforms existing methods in terms of mean-squared-error (MSE) and F-score, thus providing a more accurate recovery of the admittance matrix.
BibTeX
@article{halihal2024estimation,
  author = {Morad Halihal and Tirza Routtenberg and H. Vincent Poor},
  title = {{Estimation of Complex-Valued Laplacian Matrices for Topology Identification in Power Systems}},
  journal = {IEEE Trans. Signal Process.},
  year = {2024},
  doi = {10.1109/tsp.2024.3436524},
}
Figure