Power-flow equations and tropical intersections

Tianran Chen

Department of Mathematics
Auburn University at Montgomery

Oct. 4, 2020
AMS Fall Eastern Virtual Sectional Meeting

Joint work with Robert Davis (Colgate University)

Power networks carry alternating current (AC) electric power and make modern life possible.

Power-flow equations describes the intricate balancing conditions on "buses" of a AC power network derived from Kirchhoff's circuit laws.

Their solutions, i.e. "power-flow solutions", corresponds power network's state of operation
(including physically impossible states).

Different buses

We can model an AC power network as graph $G$ whose vertices represent "buses" and edges represent junctions.

Three basic types of buses

  • PV-buses are generator buses.
  • PQ-buses are load buses.
  • Reference buses provide references relative to which all other buses are measured.

PV and PQ buses result in very different formulations.

Lossless PQ-type formulation

Here we only focus on a much simplified formulation in which all non-reference buses are modeled as PQ buses, and no electric energy is lost in the network.

  • These assumptions are not realistic.
  • Such formulations are studied in engineering context.
  • More realistic formulations involve a mixture of PV and PQ (and reference) buses as well as power loss.
  • Realistic formulation can be obtained from this formulation by removing equations and adding constraints.

Power-flow equations

Derived from Kirchhoff's circuit laws, the PQ-type power-flow equations for power network $G$ consisting of $N$ buses is a system of $N-1$ equations

\[ S_i = \sum_{j \in N_G(i)} \overline{Y}_{ij} v_i \overline{v}_j \quad\text{for } i = 2,\dots,N \]

in the $N-1$ complex variables $v_2, \dots, v_N$ with $v_1 = 1$ , where $\overline{v}_j$ denotes the complex conjugate of $v_j$

Power-flow equations

\[ S_i = \sum_{j \in N_G(i)} \overline{Y}_{ij} v_i \overline{v}_j \quad\text{for } i = 2,\dots,N \]

One of the central object in "power-flow study" in the analysis of power networks.

Similar systems also appear in the study of wind turbine farm operations and other applications.

Closely related to Kuramoto equations, reactive power balancing equations for solar farms, and bilinear TL-type consensus network equations.

\[ S_i = \sum_{j \in N_G(i)} \overline{Y}_{ij} v_i \overline{v}_j \quad\text{for } i = 2,\dots,N \]

  • Is there a solution?
  • How to find one solution?
  • How many solutions are there?
  • How to find all/many solutions?

Despite the simplicity, these questions are not trivial.

  • Not linear
  • Not polynomial
  • Not holomorphic / complex differentiable

Algebraic geometry approaches to PQ-type power-flow:


  • J. Baillieul and C. Byrnes Geometric Critical Point Analysis of Lossless Power System Models. (1982) IEEE Transactions on Circuits and Systems
  • T.-Y. Li, T. Sauer, and J. Yorke Numerical Solution of a Class of Deficient Polynomial Systems SIAM Journal of Numerical Analysis (1987)
  • (Recent survey) D. Mehta, D. Molzahn and K. Turitsyn "Recent advances in computational methods for the power flow equations", 2016 American Control Conference.
  • (Many related works on the PV-type power-flow)

Solution count

\[ S_i = \sum_{j \in N_G(i)} \overline{Y}_{ij} v_i \overline{v}_j \quad\text{for } i = 2,\dots,N \]

How many nonzero complex solutions can there be?

J. Baillieul and C. Byrnes (1982) Geometric Critical Point Analysis of Lossless Power System Models
T.-Y. Li, T. Sauer, and J. Yorke (1987) Numerical Solution of a Class of Deficient Polynomial Systems

  • There can be more than one solutions.
  • There can be at most $\binom{2(N-1)}{N-1}$ solutions.
  • This upper bound is attainable.

PQ-type power-flow equations: Upper bound on the number of complex solutions is $\binom{2(N-1)}{N-1}$

  • This bound is only attained for dense power networks.
  • What about sparse networks? The bound should be lower.
    • S. Guo and F. Salam, The number of (equilibrium) steady-state solutions of models of power systems. (1994) IEEE Transactions on Circuits and Systems I.
    • D. Molzahn, D. Mehta, M. Niemerg, Toward topologically based upper bounds on the number of power flow solutions. (2016) American Control Conference.
    • T. Chen, D. Mehta On the Network Topology Dependent Solution Count of the Algebraic Load Flow Equations. (2018) IEEE Transactions on Power Systems.
    • T. Chen (2019) Unmixing the mixed volume computation. Discrete & Computational Geometry

Solution count for sparse networks

For sparse networks the upper bound for the number of power-flow solutions depends on network topology.

  • Guo and Salam:
     Cut-vertex decomposition
  • Molzahn, Mehta, and Niemerg:
     Algebraic geometry approach to very sparse networks.
  • Chen and Mehta:
    the bound is mixed volume of $N-1$ polytopes
  • Chen: the bound is the volume of "adjacency polytope"
  • (Many related results for PV-type formulation)

Our recent/current works

We focused on an algebraic/convex/tropical geometry approach to certain aspects of this problem.


  • The solution count problem should be a purely combinatorial problem.
  • Can we turn the power-flow equations into linear system?
  • How to sample power-flow solutions quickly?

Theorem. (R. Davis and Chen, 2020) arXiv:2007.11051
Given a network $G$, the maximum number of power-flow solutions on this network is bounded above by the number of $D(G)$-draconian sequences derived from $G$.

Definition. For a network/graph $G$ with vertices $1,\dots,N$. We call $(a_1,\dots,a_N) \in \mathbb{Z}_{\geq 0}^N$ a $D(G)$-draconian sequence if $\sum a_i = N-1$ and, for any $1 \leq i_1 < \cdots < i_k \leq N$, \[ a_{i_1} + \cdots + a_{i_k} < \left|\{i_1,\dots,i_k\} \cup \left(\bigcup_{j=1}^k \mathcal{N}_G(i_j)\right)\right| \]

What's the point?

  • We transformed this question about a nonlinear system into a well-studied question in combinatorics.
  • Many answers are already known (e.g. cycles, outer-planar, certain wheel, complete bipartite graphs)
  • Large networks can be decomposed into smaller graphs.

Power-flow: a tropical view

Another direction of our project is to study power-flow equations from a new "tropical" point of view.

  • Turn one complicated nonlinear problem into a family of simple linear problems.
  • Each linear component is easy to solve and understand.
  • The linear components encodes network topology.

What is a tropical intersection?

Tropical geometry studies polynomials by turning them into piece-wise linear functions.

\[ \operatorname{Trop}( a x^3 + b x^4 y^5 ) = \min \{ A + 3x \,,\, B+4x+5y \, \} \] where $A$ and $B$ are the "valuation" of $a$ and $b$.

  • Turns $+$ into $\min$
  • Turns $\cdot$ into $+$
  • Turns power into $\cdot$
  • Turns polynomial into piecewise-linear functions

Tropical hypersurfaces, generalized

Definition. The tropical hypersurface defined by a tropical polynomial $\operatorname{Trop}(f)(x_1,\dots,x_n)$ is the set of all points in $\mathbb{R}^n$ such that the minimum in $\operatorname{Trop}(f)(x_1,\dots,x_n)$ is attained at least twice.

This is the widely used definition, but it is not sufficient in our study. Motivated by the PQ-type power-flow equations, we define the concept of generalized tropical hypersurface .

Definition. The tropical hypersurface of type $t$ defined by a tropical polynomial $\operatorname{Trop}(f)(x_1,\dots,x_n)$ is the set of all points in $\mathbb{R}^n$ such that the minimum in $\operatorname{Trop}(f)(x_1,\dots,x_n)$ is attained at least $t+1$ times.

The original definition of a tropical hypersurface is a special case of this definition with type $t=1$.

Generalized intersection of $n$ tropical hypersurfaces $(H_1,\dots,H_N)$ of type $(t_1,\dots,t_N)$ is their set-theoretic intersection in $\mathbb{R}^N$.

Theorem. (T. Chen & R. Davis) Counting multiplicity, the power-flow solutions are in one-to-one correspondence with a subset of the generalized intersections of tropical hypersurfaces defined by $L_i$ of all possible types $(t_1,\dots,t_N) \in \mathbb{Z}_0^N$ with $\sum_{i=1}^N t_i = N$, where \[ L_{i}(z_1,\dots,z_N) = z_i + \sum_{j \in \mathcal{N}_(i)} c_{ij} \, z_j. \]

  • Power-flow solutions can be studied through generalized tropical hypersurfaces defined by linear polynomials $L_i$'s.
  • $L_i$'s encodes the sparsity in the power network.

Summary

We focused on the PQ-type power-flow equations \[ S_i = \sum_{j \in N_G(i)} \overline{Y}_{ij} v_i \overline{v}_j \quad\text{for } i = 2,\dots,N \]

  • Turned the problem of bounding the number of power-flow solutions into a well-studied combinatorics problem.
    • Many existing results can be utilized.
    • Potentially faster to compute (complexity unknown)
  • Mapped power-flow solutions to "generalized intersections of tropical hypersurfaces" of linear polynomials.

Future directions / open problems

  • The complexity of all the problems involved in computing the upper bound of the power-flow solutions (mostly unknown, other than no worse than #P).
  • Scalable parallel implementations (GPU-accelerated).
  • Can these techniques be applied to other nonlinear systems derived from other types networks?

Acknowledgement

My collaborators on this and related projects: Rob Davis, Evgeniia Korchevskaia, Wuwei Li, Jakub Marecek, Dhagash Mehta, Dan Molzahn, Matthew Niemerg.

My advisor Tien-Yien Li (1945-2020).

This research is supported, in part, by NSF and AUM grant-in-aid program

Thank You!

ti@nranchen.org
http://www.tianranchen.org/