Abstract
We study tightness properties of a Lagrangian dual (LD) bound for the nonconvex alternating current optimal power flow (ACOPF) problem. We show an LD bound that can be computed in a parallel, decentralized manner. Specifically, the proposed approach partitions the network into a set of subnetworks, dualizes the coupling constraints (giving the LD function), and maximizes the LD function with respect to the dual variables of the coupling constraints (giving the desired LD bound). The dual variables that maximize the LD are obtained by using a proximal bundle method. We show that the bound is less tight than the popular semidefinite programming relaxation but as tight as the second-order cone programming relaxation. We demonstrate our developments using PGLib-OPF test instances.
Introduction
The Alternating Current Optimal Power Flow (ACOPF) problem is a cornerstone of power systems engineering, determining the most cost-effective generation and transmission strategy while adhering to the physical laws of electricity. However, because these laws involve non-linear and non-convex relationships between voltage and power, finding a global optimum is NP-hard.
In practice, engineers often use local optimization. The challenge is that without a reliable lower bound, it is impossible to determine how close a local solution is to the true global optimum. While Semidefinite Programming (SDP) relaxations provide tight bounds, they scale poorly. Conversely, Second-Order Cone Programming (SOCP) relaxations are faster but often too loose. This research proposes a decentralized Lagrangian Dual (LD) approach that balances tightness and scalability.
Methodology: Lagrangian Decomposition
The authors utilize a "divide and conquer" strategy to handle large-scale grids:
- Network Partitioning: The grid is decomposed into smaller, manageable subnetworks.
- Dualization: Coupling constraints between subnetworks are moved to the objective function, associated with Lagrangian multipliers ($\lambda$) that represent the "shadow prices" of power exchange.
- Lagrangian Dual Function: By solving each subnetwork independently for given prices, a dual function is defined. Maximizing this function yields the lower bound.
- Proximal Bundle Method (PBM): An iterative PBM is used to efficiently find the optimal multipliers. A key advantage of this approach is that it provides a valid lower bound at every iteration, allowing for early termination if needed.
- Local Relaxation: To ensure subproblems remain tractable, a local SDP relaxation is applied within each subnetwork.
Numerical Validation and Tightness
The proposed bound, denoted as $\hat{z}_{SDP}$, was tested against standard benchmarks from the PGLib-OPF library. Theoretically, the authors established a hierarchy: $z_{LD} \geq z_{SDP} \geq \hat{z}_{SDP} \geq z_{SOC}$. Numerical results confirm that the decentralized bound is consistently tighter than the standard SOCP relaxation and often approaches the quality of centralized SDP bounds.
As shown in the table above, for challenging cases like case5_pjm, the SOCP gap of 14.55% is reduced to 5.31% using the proposed $\hat{z}_{SDP}$ bound. Similar improvements are seen across various IEEE test cases.
Computational Performance and Scalability
While the decentralized nature of the subproblems allows for parallel execution, the coordination of these subproblems—the "Master Problem"—presents a scaling challenge. As the number of partitions increases, the complexity of the Master Problem grows due to the increasing number of coupling constraints.
Analysis of the solution times reveals that while subproblem solution time scales relatively well, the Master Problem becomes a significant bottleneck as the grid is partitioned into more pieces. This suggests that future work should focus on more efficient coordination algorithms to enable the analysis of continent-scale power networks.
Conclusion
This research demonstrates that a decentralized Lagrangian Dual approach can provide high-quality lower bounds for the ACOPF problem. By proving a tightness hierarchy and validating it numerically, the authors offer a scalable framework for assessing solution quality in modern power grids. Future efforts will look toward optimizing the Master Problem and extending the framework to handle uncertainty and multi-period operations.
Summary updated