On the Tightness of the Lagrangian Dual Bound for Alternating Current Optimal Power Flow

Weiqi Zhang, Kibaek Kim, Ví­ctor M. Zavala

This paper, titled "On the Tightness of the Lagrangian Dual Bound for Alternating Current Optimal Power Flow," provides a rigorous look at how we can find better lower bounds for one of the most difficult problems in power systems engineering.

TL;DR

The authors propose a decentralized method to calculate lower bounds for the non-convex Alternating Current Optimal Power Flow (ACOPF) problem using Lagrangian duality and network decomposition. They theoretically prove and numerically demonstrate that their bound is tighter than the standard Second-Order Cone Programming (SOCP) relaxation, offering a scalable way to assess the quality of local solutions in large-scale power grids.

What Problem Does This Paper Address?

The ACOPF problem is the "holy grail" of power systems—it determines the most cost-effective way to generate and move electricity while respecting the physical laws of physics (Kirchhoff’s laws). Because these laws involve non-linear, non-convex relationships between voltage and power, finding the absolute "best" (globally optimal) solution is NP-hard.

Engineers usually rely on local optimization algorithms to find "good enough" solutions. However, without a lower bound, there is no way to know if a local solution is 1% or 50% away from the true global optimum. Existing methods to find these bounds, like Semidefinite Programming (SDP), are very tight but don't scale well to massive, continent-sized grids. Conversely, faster methods like SOCP are often too "loose" to be useful. This paper seeks a middle ground: a bound that is both tight and computationally scalable through decentralization.

Methods

The authors employ a "divide and conquer" strategy known as Lagrangian Decomposition:

  1. Network Partitioning: The power grid is split into several smaller subnetworks.
  2. Dualization: The constraints that link these subnetworks (the "coupling constraints") are moved into the objective function. They are replaced by Lagrangian multipliers ($\lambda$), which act as "shadow prices" for power flowing between regions.
  3. Lagrangian Dual (LD) Function: By solving each subnetwork independently for a given set of prices, the authors define a dual function. Maximizing this function provides the lower bound.
  4. Proximal Bundle Method (PBM): To find the optimal prices ($\lambda$), the authors use a PBM. This iterative algorithm builds a "bundle" of information about the dual function to navigate toward the maximum lower bound efficiently.
  5. Local Relaxation: To ensure the subproblems are solvable, they apply a local SDP relaxation to each subnetwork.

Datasets

The researchers evaluated their approach using the PGLib-OPF (v20.07) library, a standard benchmark in the power systems community. They specifically targeted "hard" instances—cases where the standard SOCP gap is known to be larger than 5%—ranging from small 5-bus systems to larger 179-bus systems (e.g., case179_goc__api).

Key Insights and Ideas

  • The Tightness Hierarchy: The paper’s most significant theoretical contribution is proving where this new bound sits in the mathematical landscape. They establish that: $$z_{LD} \geq z_{SDP} \geq \hat{z}_{SDP} \geq z_{SOC}$$ In plain English: their decentralized bound is guaranteed to be at least as good as the popular SOCP relaxation and, under certain conditions, approaches the tightness of the centralized SDP relaxation.

  • Decentralization as a Feature: Unlike traditional centralized relaxations, this method is designed for parallel computing. Each subnetwork can be solved on a different processor core, making it a candidate for managing future grids with high penetrations of distributed energy resources.

  • Iterative Utility: A unique property of the Lagrangian dual is that it provides a valid lower bound at every iteration. Even if you stop the algorithm early, you still have a mathematically sound (though perhaps slightly looser) bound to work with.

Key Results

  • Numerical Validation: Tests on PGLib instances confirmed the theoretical hierarchy. For example, in case14_ieee__api, the SOCP gap was 5.13%, while the proposed $\hat{z}_{SDP}$ bound narrowed that gap significantly.
  • First-Iteration Strength: The authors observed that the bound is remarkably tight even at the very first iteration when the number of subnetworks is small.
  • Scalability vs. Tightness: As the grid is partitioned into more (and smaller) pieces, the bound becomes slightly less tight, but it remains superior to the SOCP baseline.

Limitations and Future Work

  • The Master Problem Bottleneck: While the subnetworks can be solved in parallel, the "Master Problem" (which coordinates the prices between subnetworks) becomes increasingly difficult to solve as the number of partitions grows. The authors noted that for very large systems, the Master Problem becomes a computational bottleneck because it must handle many dense inequality constraints.
  • Future Directions: The authors aim to develop more scalable methods for solving the Master Problem to enable the analysis of even larger, real-world power networks. They also suggest that this framework could be extended to multi-period (time-varying) or stochastic (uncertain) ACOPF problems.

Summary updated

Abstract

We study tightness properties of a Lagrangian dual (LD) bound for the nonconvex alternating current optimal power flow (ACOPF) problem. We show that the LD bound that can be computed in a parallel, decentralized manner. 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 is as tight as the second-order cone programming relaxation. We demonstrate our developments using PGLib-OPF test instances.
BibTeX
@inproceedings{zhang2022tightness,
  author = {Weiqi Zhang and Kibaek Kim and Ví­ctor M. Zavala},
  title = {{On the Tightness of the Lagrangian Dual Bound for Alternating Current Optimal Power Flow}},
  booktitle = {2022},
  year = {2022},
  doi = {10.1109/pesgm48719.2022.9917169},
}

Loading related content...

Figure