A branch and bound methodology for matrix polytope stability problems arising in power systems

Christopher L. DeMarco, V. Balakrishnan, Stephen Boyd1990 · DOI

Abstract

The authors propose a formulation representing a family of linearizations in a power system dynamic model as a polytope of matrices. Using this polytope structure, a simple sufficient condition for robust stability of the matrix polytope is developed. An optimization scheme is proposed to provide a sufficient condition for instability of the polytope. These two tests are combined in a branch-and-bound algorithm that divides the polytope into smaller and smaller sub-polytopes, repeatedly testing for instability or robust stability. The algorithm terminates when any sub-polytope proves unstable or when all sub-polytopes prove robustly stable.

Introduction: The Stability Challenge in Power Grids

Power grids are complex dynamic systems that must maintain stability across a wide range of fluctuating consumer demands. Traditionally, engineers assess stability by linearizing the system's equations around a specific operating point and checking if the eigenvalues of the resulting Jacobian matrix reside in the left half-plane.

However, real-world operation involves infinitely many possible states. Conventional "Monte-Carlo" sampling—checking thousands of random scenarios—is computationally intensive and risks missing small, critical regions of instability. This paper introduces a deterministic branch-and-bound algorithm designed to provide a rigorous guarantee of stability over an entire range of uncertain conditions.

Methodology: From Physical Dynamics to Matrix Polytopes

1. Polytope Parameterization

The core innovation lies in how system uncertainties are modeled. Rather than focusing on bus power injections, the authors utilize voltage phase angle differences ($\sigma$) across transmission lines. This choice is strategic: it allows the Jacobian matrix $J$, which represents the system dynamics, to be expressed as a sum of diagonal matrices weighted by trigonometric functions of these angles.

The Jacobian matrix $J$ expressed in terms of line angles $\sigma$, showing the trigonometric dependence.

By treating the bounds of these trigonometric terms as independent linear parameters ($z_i$), the family of possible system matrices is transformed into a matrix polytope. This high-dimensional "box" represents every possible system state as a weighted sum of fixed vertex matrices, making the stability problem mathematically tractable.

The linearized Jacobian $J(z)$ represented as a matrix polytope, where $z$ parameters define the uncertainty bounds.

2. Stability and Instability Testing

The algorithm employs two primary tests to evaluate the polytope:

  • Stability Test: Utilizing a matrix norm bound based on the Bauer-Fike theorem, the algorithm checks if the entire polytope is sufficiently distant from the boundary of instability. While fast, this test is conservative and may return an inconclusive result for safe but "close" systems.
  • Instability Test: To counter conservatism, the authors formulate an optimization problem to search for a specific point within the polytope that has an eigenvalue on the imaginary axis—the definitive "tipping point" of failure.

3. The Branch and Bound Recursive Strategy

If neither test provides a definitive answer, the algorithm "branches" by bisecting the uncertainty box. This recursive splitting continues on smaller sub-polytopes. Because the accuracy of the stability and instability tests improves as the boxes shrink, the algorithm is guaranteed to eventually reach a definitive verdict of "Stable" or "Unstable."

Key Insights and Results

  • Linearity through Parameterization: The shift to line angles as parameters is the "secret sauce" that enables the linear polytope structure, moving the problem from intractable non-linear sampling to structured optimization.
  • Efficiency: Early computational tests indicate that the optimization-based instability test is highly effective at identifying marginal stability points, often reducing the need for extensive branching.
  • Mathematical Rigor: Unlike heuristics, this framework provides a mathematically sound "yes/no" answer for the entire range of uncertainty, ensuring that if a system is labeled stable, it truly is robust against the defined fluctuations.

Limitations and Future Outlook

Despite its rigor, the methodology faces the "curse of dimensionality." In very large power grids with thousands of states, the number of sub-polytopes to check could grow exponentially. Additionally, the current model treats line angles as independent variables, which can lead to "over-bounding"—flagging instability for states that are mathematically possible within the polytope but physically impossible under Kirchhoff’s laws. Future research aims to scale these methods for nation-sized grids and refine the parameter constraints to reduce conservatism.

Summary updated

Abstract

The authors propose a formulation representing a family of linearizations in a power system dynamic model as a polytope of matrices. Using this polytope structure, a simple sufficient condition for robust stability of the matrix polytope is developed. An optimization scheme is proposed to provide a sufficient condition for instability of the polytope. These two tests are combined in a branch-and-bound algorithm that divides the polytope into smaller and smaller sub-polytopes, repeatedly testing for instability or robust stability. The algorithm terminates when any sub-polytope proves unstable or when all sub-polytopes prove robustly stable.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>
BibTeX
@misc{demarco1990branch,
  author = {Christopher L. DeMarco and V. Balakrishnan and Stephen Boyd},
  title = {{A branch and bound methodology for matrix polytope stability problems arising in power systems}},
  year = {1990},
  doi = {10.1109/cdc.1990.203338},
}
Figure