Source-linked AI summary
Equivalent relaxations of optimal power flow
Subhonmesh Bose, Steven H. Low, Thanchanok Teeraratkul, Babak Hassibi
TL;DR
The paper studies relations among convex OPF relaxations formulated in bus injection and branch flow models. It proves equivalence results showing that all relaxations coincide on radial networks, while mesh networks require balancing computational effort against exactness.
Problem
The paper addresses how semidefinite, chordal, and second-order cone OPF relaxations relate across bus injection and branch flow models.
Method
The authors prove equivalence relations and bijections among the feasible sets of the models and their relaxations, and illustrate the results through simulations.
Results
For acyclic networks, the SDP, chordal, and SOCP relaxations are equivalent; for mesh networks, the SDP and chordal relaxations are generally tighter than SOCP, while chordal relaxation is generally faster than full SDP.
Takeaways & Limitations
Solve the SOCP relaxation on radial networks; on mesh networks, choose between SOCP and chordal or full SDP according to the tradeoff between computational effort and exactness.
Abstract
from arXiv · showhide
Several convex relaxations of the optimal power flow (OPF) problem have recently been developed using both bus injection models and branch flow models. In this paper, we prove relations among three convex relaxations: a semidefinite relaxation that computes a full matrix, a chordal relaxation based on a chordal extension of the network graph, and a second-order cone relaxation that computes the smallest partial matrix. We prove a bijection between the feasible sets of the OPF in the bus injection model and the branch flow model, establishing the equivalence of these two models and their second-order cone relaxations. Our results imply that, for radial networks, all these relaxations are equivalent and one should always solve the second-order cone relaxation. For mesh networks, the semidefinite relaxation is tighter than the second-order cone relaxation but requires a heavier computational effort, and the chordal relaxation strikes a good balance. Simulations are used to illustrate these results.
I. INTRODUCTION
OPF is a fundamental but generally nonconvex and NP-hard power-network optimization problem. The paper develops and relates convex relaxations in bus injection and branch flow models, using partial matrices to reduce the computational burden of full SDP formulations.
- OPF minimizes network operating costs such as generation cost or transmission losses, subject to power-system constraints.
- The bus injection formulation leads naturally to a rank-constrained SDP and, after relaxing rank, to a full-matrix SDP relaxation.
- The paper develops two equivalent partial-matrix formulations that use fewer variables than the full SDP and lead to chordal SDP and SOCP relaxations.
- The paper proves equivalence relations between bus injection and branch flow models and their relaxations, then illustrates running times and accuracies through simulations.
- OPF is generally nonconvex and NP-hard because its feasible voltage set is defined by quadratic constraints.
B. SDP relaxation: P1 and R1
The bus injection formulation converts OPF into a rank-constrained matrix problem, then relaxes rank and exploits graph sparsity through partial matrices and chordal extensions. The resulting SDP relaxation is exact when an optimal rank-1 solution exists, although exactness alone need not make that solution efficiently computable.
- Partial matrices: A G-partial matrix stores entries indexed by buses and network edges, reducing representation when the graph is sparse.
- P1 formulation: The lifted matrix W = V V^H is positive semidefinite and rank 1, with its G-partial matrix containing only diagonal and edge entries.
- P1 formulation: The original OPF feasible set corresponds one-to-one with the feasible set of the rank-constrained SDP P1.
- R1 relaxation: The SDP relaxation R1 removes the rank constraint while retaining positive semidefiniteness and the OPF constraints on the partial matrix.
- Exactness: R1 is exact when an optimal solution satisfies rank 1, but the existence of non-rank-1 optima can prevent efficient recovery of a rank-1 optimum.
- Chordal relaxation: A chordal extension yields Rch, whose positive-semidefinite constraint can be imposed on maximal cliques rather than the full matrix.
D. SOCP relaxation: P2 and R2
The SOCP relaxation is obtained by relaxing the nonconvex rank-1 and cycle conditions on G-partial matrices. Its exactness requires an optimal solution that satisfies both conditions.
- Cycle condition: The cycle condition requires the summed edge phases around every graph cycle to equal 0 modulo 2π.
- Cycle condition: Checking the cycle condition on basis cycles of a spanning tree is sufficient to establish it for all cycles.
- P2 and R2: P2 imposes rank-1 and cycle conditions on Hermitian G-partial matrices, and both constraints are nonconvex.
- P2 and R2: Relaxing those conditions produces R2, whose edge constraints form a second-order cone program.
- Exactness: R2 is exact when an optimal solution is rank 1 and satisfies the cycle condition.
E. Equivalent and exact relaxations
The paper establishes equivalence and exactness relations among the full-matrix SDP, chordal, and SOCP relaxations. For trees, the relaxations coincide and the SOCP is computationally preferable; for meshes, chordal relaxation balances accuracy and effort.
- R1 is exact if and only if Rch is exact, and exactness of R2 implies exactness of both.
- For acyclic networks, R2 is exact if and only if R1 is exact, while all three relaxations are equivalent.
- The optimal costs of P1, Pch, and P2 equal the OPF optimal cost.
- For trees, R1, Rch, and R2 have the same solution, while R2 is an SOCP and R1 and Rch are SDPs.
- For mesh networks, Rch and R1 have the same accuracy, but Rch is usually faster on large sparse networks.
- The chordal extension affects Rch's variable count and is nontrivial to choose, although it does not affect the optimal value.
F. Proof of Theorem 1
The proof relates feasible partial-matrix sets through completions, cycle conditions, and graph structure. These relations establish equivalence of the relaxations on trees and connect exact relaxed solutions to recoverable OPF solutions.
- The feasible sets of OPF and P1, Pch, and P2 are equivalent on the underlying G-partial matrices.
- A full matrix is an F-completion when it agrees with the G-partial matrix on the shared index set; positive semidefinite and rank-one completions define the relevant constraints.
- The map from voltage vectors to G-partial matrices identifies the feasible set W1 with rank-one positive semidefinite completions.
- For a chordal extension, rank-one positive semidefinite completions imply the cycle condition, yielding the inclusion Wch ⊆ W2.
- Conversely, the cycle condition makes path-defined voltage angles well-defined and produces a rank-one positive semidefinite completion, proving W2 ⊆ W1.
- When G is acyclic, the relaxed feasible sets coincide, and the resulting optimal-value relations yield the theorem's exactness equivalences.
A. OPF formulation
The OPF is formulated through branch-flow variables and then relaxed because its feasible set is generally nonconvex. The SOCP relaxation eliminates voltage and current phase angles, replaces quadratic equalities with inequalities, and requires phase recovery conditions for exactness.
- Branch flow model: The branch flow model represents buses as nodes and transmission lines as directed edges, using sending-end power, current, and voltage variables.The model imposes power balance, Ohm’s-law relations, generation limits, and voltage-magnitude constraints.
- Nonconvex formulation: The branch-flow OPF is generally nonconvex because its quadratic constraints define a nonconvex feasible set.The resulting OPF formulations are nonconvex and, in the stated formulation, NP-hard.
- SOCP relaxation: The SOCP relaxation first eliminates voltage and current phase angles, then relaxes quadratic equalities into inequalities over variables (S, ℓ, v).Here, v_i := |V_i|^2 and ℓ_ij := |I_ij|^2; the relaxed feasible set is a second-order cone.
- Exactness and phase recovery: An SOCP solution is useful only if it satisfies the original quadratic equality and its implied phase differences can be recovered as bus-angle differences.The phase-recovery condition requires implied angle differences to sum to zero modulo 2π around every cycle.
- Radial networks: For radial networks, equality in the SOCP constraint guarantees a unique phase recovery and therefore an optimal solution of the original OPF.The theorem does not itself provide sufficient conditions guaranteeing that the relaxation is exact.
IV. EQUIVALENCE OF BUS INJECTION AND BRANCH FLOW MODELS
The paper establishes bijections between the bus-injection and branch-flow feasible sets and between their corresponding relaxations. These mappings show that the two OPF models are equivalent while preserving the relationships among their relaxation feasible sets.
- Mapping construction: The mappings are constructed by converting partial Hermitian matrix entries into branch-flow variables and reconstructing the matrix from (S, ℓ, v).The inverse construction uses the branch-flow variables and the cycle-angle condition to recover the corresponding partial matrix.
- Feasible-set bijections: The mapping g is a bijection between the bus-injection feasible set W2 and the branch-flow feasible set X2, with g^-1 as its inverse.The proof establishes well-definedness, injectivity, surjectivity, and inverse consistency.
- Relaxation equivalence: The same mapping gives a bijection between the convex relaxation feasible sets W+_2 and X+_2.Thus, the bus-injection and branch-flow SOCP-related relaxations represent corresponding feasible sets.
- Model equivalence: The bijections between W2 and X2, together with their links to the respective OPF feasible sets, establish equivalence of the bus-injection and branch-flow OPF models.The equivalence concerns the feasible sets of the two formulations, not merely their optimal values.
- Overall relations: The feasible-set relations among the bus-injection and branch-flow problems are summarized together with the corresponding relaxations in Figure 3.The branch-flow model includes the equivalent OPF, a phase-eliminated nonconvex relaxation, and its convex relaxation.
V. NUMERICS
The numerical section introduces a 3-bus test network and provides its line admittances for evaluating the relaxation relationships.
- Test network: Figure 4 presents the 3-bus network used in the numerical example.The network is taken from reference [51].
- Network parameters: Table I lists the admittances for the 3-bus network.These parameters specify the line characteristics used in the example.
A. A 3-bus example
The 3-bus example compares projected feasible sets and Pareto fronts for the original problem and its relaxations, showing distinct geometric relationships and exactness behavior.
- The example defines projected sets by fixing diagonal entries of W and the power injection p3(W), then restricting W to relaxation-specific feasible sets.
- The original feasible projection A1 is non-convex, whereas A+1 and A+2 are convex.This reflects the inclusion W1 ⊆ W+1 ⊆ W+2 under a linear projection.
- Relaxation R1 is exact in the example, while R2 is not.
- Figure 5 projects feasible sets onto the p1−p2 plane and magnifies their Pareto fronts for comparison.
B. IEEE benchmark systems
IEEE benchmark simulations compare the SDP, chordal, and SOCP relaxations, showing equivalent objective values for the first two and a speed–feasibility trade-off involving the SOCP relaxation.
- R1 and Rch attain the same optimal objective value, as predicted by Theorem 1.
- The first-to-second eigenvalue ratios of optimal W* in R1 are small in most cases, indicating that the relaxation is usually exact.
- The optimal objective value of R2 is lower than R1, indicating that the SOCP optimum is infeasible for P1.
- Rch is much faster than R1 for large networks, while R2 is faster than both but infeasible for most tested IEEE systems.
VI. CONCLUSION
The paper establishes equivalences among OPF relaxations in bus injection and branch flow models and characterizes their relative tightness and computational effort.
- In the bus injection model, SDP relaxations R1 and Rch are equivalent and generally tighter than SOCP relaxation R2.
- For acyclic networks, all three relaxations are equivalent.
- The branch flow SOCP relaxation R̃2 is equivalent to R2.
- Rch is generally faster to compute than R1, while R2 and R̃2 are faster still but usually have larger feasible sets.