Fast Nonconvex SDP Solvers for Large-Scale Power System State Estimation

Yu Lan, Hao Zhu, Xiaohong Guan

TL;DR

This paper introduces a high-speed approach for power system state estimation (SE) by reformulating the problem as a nonconvex semidefinite program (SDP). By leveraging Burer-Monteiro factorization and accelerated gradient descent, the authors achieve the near-global optimality of convex SDP solvers but at a fraction of the computational cost, making it viable for real-time monitoring of large-scale grids.

What Problem Does This Paper Address?

State Estimation (SE) is the "brain" of power grid operations; it takes noisy raw measurements (voltage magnitudes, power flows) and calculates the actual state of the grid (complex voltage phasors). Traditionally, this is solved using the Gauss-Newton (GN) method. However, GN is prone to divergence, especially during heavy grid loading or when "bad data" (outliers) are present.

To fix this, researchers previously proposed Semidefinite Programming (SDP) reformulations, which are convex and can find the global optimum. The catch? Standard SDP solvers use interior-point methods that scale poorly—roughly $O(N^{4.5})$—making them too slow for large, real-world power systems. This paper aims to bridge that gap: providing the reliability of SDP with the speed required for real-time operations.

Methods

The authors employ several key strategies to speed up the solver:

  1. Burer-Monteiro Factorization: Instead of solving for a large $N \times N$ matrix $V$, they represent it as $V = uu^H$, where $u$ is a vector. This eliminates the expensive positive semi-definite (PSD) constraint and turns the problem into an unconstrained (though nonconvex) optimization over $u$.
  2. Factored Gradient Descent (FGD-SE): They apply simple first-order gradient descent to this factored objective. Crucially, they prove that for power systems, the objective function is "well-behaved" (strongly convex and smooth) within a restricted set of realistic voltage ranges, guaranteeing a linear convergence rate.
  3. Nesterov Acceleration (AGD-SE): To handle the ill-conditioned nature of power flow equations, they incorporate a momentum-based acceleration scheme. This significantly reduces the number of iterations needed to reach a solution.
  4. Robustness via Truncated Gradients: To handle outliers (bad sensors or cyber-attacks), they use a "hard thresholding" operator. In each iteration, they discard measurements with the highest mismatch errors, preventing outliers from pulling the estimate away from the truth.
  5. PMU Integration: The solver is extended to naturally incorporate high-accuracy synchrophasor data (PMUs) as a linear regularization term.

Datasets

The algorithms were evaluated using standard power system benchmarks:

  • IEEE 118-bus system: A medium-sized standard test case.
  • IEEE 300-bus system: A larger, more complex network.
  • ACTIVSg2000-bus system: A synthetic 2000-bus system representing a large-scale footprint (similar to the Texas grid), used to test scalability.

Key Insights and Ideas

  • Nonconvexity isn't always scary: While the factored problem is technically nonconvex, the physics of power systems (specifically the narrow range of allowable voltage magnitudes, e.g., $\pm 5\%$) restricts the search space to a region where the problem behaves like a convex one.
  • Complexity Reduction: By moving from matrix-space to vector-space, the computational burden per iteration becomes extremely light, consisting mostly of simple vector-matrix multiplications.
  • Acceleration is Essential: The authors found that standard gradient descent can be slow due to the high condition number of the SE objective. Nesterov's acceleration acts as a "heuristic" that works remarkably well in this nonconvex landscape, even though its theoretical guarantees are usually reserved for convex problems.

Key Results

  • Speedup: On the 300-bus system, the proposed AGD-SE solver took 0.277 seconds, compared to 98.5 seconds for a standard SDP solver (CVX/SeDuMi)—a nearly 350x improvement.
  • Scalability: For the 2000-bus system, standard SDP solvers failed to find a solution in a reasonable time. The AGD-SE solver finished in 35.7 seconds.
  • Convergence Reliability: In the 2000-bus case, the traditional Gauss-Newton method only converged 30% of the time. The proposed FGD and AGD methods achieved 100% convergence to the near-optimal solution.
  • Outlier Rejection: The robust version (RAGD) achieved a 72% success rate in identifying outliers in the 2000-bus system, significantly outperforming classical robust estimators like Least Absolute Value (LAV).

Limitations and Future Work

  • Initialization: The method requires a reasonably good starting point (like a "flat start" or a DC-SE solution). While this is standard in the industry, the theoretical convergence still relies on this initial proximity.
  • Theoretical Gap: While AGD-SE performs excellently, a rigorous proof of its convergence rate for this specific nonconvex power system objective remains an open question.
  • Constrained SE: Future work could involve incorporating hard constraints, such as strict voltage limits or line flow limits, directly into the gradient descent framework.

Summary updated

Abstract

Fast power system state estimation (SE) solution is of paramount importance for achieving real-time decision making in power grid operations. Semidefinite programming (SDP) reformulation has been shown effective to obtain the global optimum for the nonlinear SE problem, while suffering from high computational complexity. Thus, we leverage the recent advances in nonconvex SDP approach that allows for the simple first-order gradient-descent (GD) updates. Using the power system model, we can verify that the SE objective function enjoys nice properties (strongly convex, smoothness) which in turn guarantee a linear convergence rate of the proposed GD-based SE method. To further accelerate the convergence speed, we consider the accelerated gradient descent (AGD) extension, as well as their robust versions under outlier data and a hybrid GD-based SE approach with additional synchrophasor measurements. Numerical tests on the IEEE 118-bus, 300-bus and the synthetic ACTIVSg2000-bus systems have demonstrated that FGD-SE and AGD-SE, can approach the near-optimal performance of the SDP-SE solution at significantly improved computational efficiency, especially so for AGD-SE.
BibTeX
@article{lan2019fast,
  author = {Yu Lan and Hao Zhu and Xiaohong Guan},
  title = {{Fast Nonconvex SDP Solvers for Large-Scale Power System State Estimation}},
  journal = {IEEE Transactions on Power Systems},
  year = {2019},
  doi = {10.1109/tpwrs.2019.2950392},
}

Loading related content...

Figure