Scheduled-Asynchronous Distributed Algorithm for Optimal Power Flow

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

Abstract

Optimal power flow (OPF) problems are non-convex and large-scale optimization problems with important applications in power networks. This paper proposes the scheduled-asynchronous algorithm to solve a distributed semidefinite programming (SDP) 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 with geometric degree distribution. Simulations illustrate our results on various IEEE bus test cases.

Introduction

The Optimal Power Flow (OPF) problem is a cornerstone of power systems engineering, used to determine the most cost-effective generation and transmission strategies while maintaining grid stability. Historically, OPF has been solved centrally. However, modern grids are becoming increasingly complex due to the rise of distributed renewable energy and "plug-and-play" devices. This shift creates challenges in scale, uncertainty, and robustness that centralized solvers struggle to meet.

Distributed algorithms are a natural solution, but existing methods often require a global clock for synchronization. In large, geographically spread-out grids, maintaining this synchronization is difficult and prone to communication delays. This paper introduces a "scheduled-asynchronous" algorithm that eliminates the need for global synchronization while maintaining the fast convergence properties of traditional methods.

Methodology

Distributed SDP Formulation

To address the non-convexity of the original OPF problem, the authors employ a Semidefinite Programming (SDP) relaxation. This transforms the problem into a convex form that is often exact for real-world power networks. In the distributed version, each node (or "bus") solves a local optimization while maintaining consistency with its neighbors through shared decision variables.

Variable splitting and local optimization structure for distributed SDP

As illustrated in the figure above, the physical link between nodes $i$ and $k$ is reformulated into a structure where each node manages its own local variables and constraints, ensuring consistency through iterative updates of shared variables.

The Scheduled-Asynchronous Algorithm

The core contribution is an alternating update scheme. Instead of simultaneous updates, nodes update in a specific order based on an acyclic orientation of the network graph. Every pair of connected nodes updates their variables in an alternating fashion. This is "asynchronous" because it doesn't require a global clock—nodes simply wait for their neighbors to finish their respective updates.

Algorithm 1: Scheduled-Asynchronous Algorithm

Algorithm 1 details this logic. To prevent deadlocks and ensure speed, the authors developed a distributed graph coloring algorithm to find an orientation with a small "diameter" (the longest path of updates). For typical planar power networks, this diameter is at most five, ensuring updates propagate through the network quickly.

Key Insights and Results

The algorithm was evaluated using standard industry benchmarks, including IEEE 6, 14, 30, and 57-bus systems. Key findings include:

  • Proven Convergence: Using the LaSalle Invariance Principle, the authors formally proved that the algorithm converges to the global primal-dual optimizer.
  • Speed and Efficiency: For the IEEE 30-bus system, the algorithm reached high accuracy ($γ < 10^{-4}$) in roughly 140 iterations per bus.
  • Robustness: The system is naturally robust to communication issues, maintaining convergence even with a 10% chance of packet loss.
  • Parameter Tuning: Performance is significantly improved by tuning penalty parameters ($ρ$) based on the physical admittance of the power lines, acknowledging that more conductive lines are more sensitive to perturbations.

Conclusion

The scheduled-asynchronous algorithm provides a robust and scalable framework for distributed OPF. By replacing global synchronization with local ordering rules and minimizing update diameters through graph coloring, it offers a practical solution for modern, complex power grids. Future work will focus on formally proving convergence rates and extending the framework to non-convex AC-OPF problems.

Summary updated

Abstract

Optimal power flow (OPF) problems are non-convex and large-scale optimization problems with important applications in power networks. This paper proposes the scheduled-asynchronous algorithm to solve a distributed semidefinite programming (SDP) 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 with geometric degree distribution. 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},
}
Figure