Scheduled-Asynchronous Distributed Algorithm for Optimal Power Flow

Chin-Yao Chang, Jorge Cortés, Sonia Martı́nez

TL;DR

This paper introduces a "scheduled-asynchronous" distributed algorithm to solve the Optimal Power Flow (OPF) problem in power grids. By using a clever alternating update scheme based on a directed acyclic graph orientation, the authors eliminate the need for global clock synchronization while maintaining the fast convergence properties of traditional synchronous methods like ADMM.

What Problem Does This Paper Address?

The Optimal Power Flow (OPF) problem is the "bread and butter" of power systems engineering—it's how operators determine the most cost-effective way to generate and move electricity while keeping voltages and line loads within safe limits.

Historically, OPF was solved centrally. However, modern grids are becoming increasingly complex due to the rise of distributed renewable energy (like rooftop solar) and "plug-and-play" devices. This shift creates three major challenges:

  1. Scale: Centralized solvers struggle with the massive number of variables in modern distribution networks.
  2. Uncertainty: Real-time fluctuations in renewables require faster, more frequent optimizations.
  3. Robustness: Centralized systems have a single point of failure.

Distributed algorithms are the natural solution, but existing ones often require a global clock to keep all "agents" (buses/nodes) in sync. In a large, geographically spread-out grid, maintaining this synchronization is difficult and prone to communication delays.

Methods

The authors propose a multi-step approach to bring asynchrony to OPF:

  1. Convexification via SDP: The original OPF problem is notoriously non-convex (hard to solve). The authors use a Semidefinite Programming (SDP) relaxation, which turns the problem into a convex one that can be solved efficiently and is known to be "exact" (providing the true global optimum) for many real-world power networks.
  2. Scheduled-Asynchronous Logic: Instead of everyone updating at once, nodes update in a specific order. Every pair of connected nodes updates their variables in an alternating fashion. This is "asynchronous" because it doesn't require a global clock—nodes just need to know when their neighbors have finished.
  3. Acyclic Orientation: To prevent "deadlocks" (where Node A waits for Node B, who is waiting for Node A), the authors require the network graph to have an acyclic orientation. They treat the grid as a directed graph where updates flow from "tails" to "heads."
  4. Distributed Graph Coloring: The speed of the algorithm depends on the "diameter" of this directed graph (the longest path of updates). The authors developed a distributed graph coloring algorithm to find an orientation with a very small diameter (at most five for typical planar power networks), ensuring updates propagate through the network quickly.

Datasets

The algorithm was evaluated using standard industry benchmarks from the Power Systems Test Case Archive:

  • IEEE 6-bus system
  • IEEE 14-bus system
  • IEEE 30-bus system
  • IEEE 57-bus system

These cases represent various scales of power networks used globally for validating new algorithms.

Key Insights and Ideas

  • The "Who Goes First" Rule: The core "aha" moment is that you can replace global synchronization with a local "ordering" rule. By ensuring the update graph is acyclic, you guarantee that every node will eventually get its turn without getting stuck in a loop.
  • Diameter is the Bottleneck: In a distributed setting, the time it takes for information to travel across the network is the limiting factor. By using graph coloring to minimize the "diameter" of the update sequence, the authors significantly boosted convergence speed.
  • Heterogeneous Tuning: The authors found that the algorithm performs much better if you tune the penalty parameters ($\rho$) based on the physical properties of the power lines (specifically, their admittance). Lines that are more "conductive" are more sensitive to perturbations, so they need a higher weight in the optimization.
  • Robustness to Packet Loss: Because the algorithm is asynchronous and relies on local consistency, it is naturally robust. Simulations showed it still converges even with a 10% chance of communication packet drops.

Key Results

  • Proven Convergence: The authors used the LaSalle Invariance Principle to formally prove that the algorithm converges to the global primal-dual optimizer.
  • Speed: For the IEEE 30-bus system, the algorithm reached a high degree of accuracy ($\gamma < 10^{-4}$) in roughly 140 iterations per bus.
  • Efficiency of Orientation: Using their custom coloring algorithm to find a small-diameter orientation resulted in much smoother and faster convergence compared to picking an arbitrary update order, which often caused "abrupt changes" in the optimization path.

Limitations and Future Work

While the paper proves that the algorithm converges, it only conjectures the rate of convergence. Based on its similarities to ADMM, the authors suspect an $O(1/n)$ convergence rate but haven't formally proven it for the asynchronous case yet.

Additionally, while SDP relaxation works for many networks, it isn't universal. Future work could involve extending this asynchronous framework to other types of convex relaxations or even directly to the non-convex "AC-OPF" problem. There is also room to further explore how to optimally select the $\rho$ parameters to squeeze even more performance out of the system.

Summary updated

Abstract

Optimal power flow (OPF) problems are nonconvex and large-scale optimization problems with important applications in power networks. This paper proposes the scheduled-asynchronous algorithm to solve a distributed semidefinite programming formulation of the OPF problem. In this formulation, every agent seeks to solve a local optimization with its own cost function, physical constraints on its nodal power injection, voltage, and power flow of the lines it is connected to, and decision constraints on variables shared with neighbors to ensure consistency of the obtained solution. In the scheduled-asynchronous algorithm, every pair of connected nodes in the electrical network update their local variables in an alternating fashion. This strategy is asynchronous, in the sense that no clock synchronization is required, and relies on an orientation of the electrical network that prescribes the precise ordering of node updates. We establish the asymptotic convergence properties to the primal-dual optimizer when the orientation is acyclic. Given the dependence of the convergence rate on the network orientation, we also develop a distributed graph coloring algorithm that finds an orientation with diameter at most five for electrical networks. Simulations illustrate our results on various IEEE bus test cases.
BibTeX
@article{chang2018scheduled,
  author = {Chin-Yao Chang and Jorge Cortés and Sonia Martı́nez},
  title = {{Scheduled-Asynchronous Distributed Algorithm for Optimal Power Flow}},
  journal = {IEEE Transactions on Control of Network Systems},
  year = {2018},
  doi = {10.1109/tcns.2018.2809963},
}

Loading related content...

Figure