PaperlayerView exact revision on arXiv

Source-linked AI summary

Convex Relaxation of Optimal Power Flow, Part II: Exactness

Steven H. Low

arXiv:1405.0814v1math.OCeess.SY

TL;DR

The tutorial addresses when convex relaxations of nonconvex OPF are exact. It presents equivalent BIM and BFM formulations and structural sufficient conditions, finding broad support for radial networks but unresolved general conditions for AC mesh networks.

  • Problem

    OPF is nonconvex, and the tutorial examines when convex relaxations can preserve optimal solutions and certify global properties.

  • Method

    The tutorial formulates OPF and its SDP, chordal, and SOCP relaxations in equivalent BIM and BFM representations, then analyzes structural exactness conditions.

  • Results

    Sufficient conditions support exact relaxations for radial networks and selected mesh networks with tunable phase shifters or dc structure, while general AC mesh-network conditions remain elusive.

  • Takeaways & Limitations

    Exact convex relaxations can recover globally optimal OPF solutions, and phase-shifter placement can help determine or achieve convexification in mesh networks.

Abstract

from arXiv · show

This tutorial summarizes recent advances in the convex relaxation of the optimal power flow (OPF) problem, focusing on structural properties rather than algorithms. Part I presents two power flow models, formulates OPF and their relaxations in each model, and proves equivalence relations among them. Part II presents sufficient conditions under which the convex relaxations are exact.

I. INTRODUCTION

This tutorial develops and analyzes SDP, chordal, and SOCP relaxations of OPF, emphasizing when they are exact. It relates BIM and BFM formulations and summarizes sufficient conditions for radial and selected mesh networks.

  • OPF is generally nonconvex and NP-hard because power flows impose nonconvex quadratic constraints on the feasible set.The tutorial motivates convex relaxations as a way to address this structural difficulty.
  • Convex relaxation can certify global optimality, provide a lower bound when not exact, and certify OPF infeasibility when the relaxation is infeasible.
  • The tutorial formulates OPF in bus injection and branch flow models, proves their equivalence, and defines SDP, chordal, and SOCP relaxations.Exactness means that an optimal solution of the original OPF can be recovered from every optimal relaxation solution.
  • Sufficient conditions: For radial networks, sufficient conditions concern power-injection bounds, voltage-magnitude upper bounds, or sufficiently small voltage-angle differences.The conditions are generally not necessary and may be expressed as implications for allowable injections, magnitudes, or angles.
  • Radial networks: BIM and BFM support the same sufficient conditions; with a convex cost on radial networks, exact SOCP relaxation implies a unique optimal solution computable by SOCP.For radial networks, the SDP and chordal relaxations are equivalent to the SOCP relaxation.
  • Mesh networks: The conditions do not generally ensure exactness for mesh networks, but they are sufficient for networks with strategically placed tunable phase shifters and for specified dc mesh networks.Phase shifters effectively make a mesh network behave like a radial network for convex relaxation.

C. Exactness

The paper defines a strong notion of exactness and gives sufficient conditions for SOCP exactness on tree networks, with extensions to mesh networks using strategically placed phase shifters.

  • Definition of exactness: Exactness requires equivalent optimal solution sets for OPF and its relaxation, allowing recovery of an OPF optimum from every relaxation optimum.This stronger definition can exclude relaxations whose optimal solutions include non-rank-1 points, even when an OPF optimum remains recoverable.
  • Radial networks: For tree networks, SOCP exactness implies exactness of the SDP and chordal relaxations because cycle conditions are vacuous.The BIM and BFM formulations are equivalent, so sufficient conditions proved in either model apply to both.
  • Type A conditions: Under A1–A2, the SOCP relaxation of a tree-structured QCQP is exact; A2 requires relevant matrix entries on each link to lie within a common half-plane.A1 requires a positive definite cost matrix, while A2 imposes the angular separation condition.
  • Type A conditions: For OPF, A2’ yields equal optimal values and recovery from every SOCP optimum on a tree, while A1 additionally guarantees exactness.A2’ translates the half-plane condition into restrictions on bounded real and reactive power injections at both line ends.
  • Type A conditions: A2’ cannot hold when both real and reactive injections at both ends of a line have finite lower and upper bounds.The condition is interpreted as requiring that solutions obtained while ignoring some bounds nevertheless satisfy those bounds.

B. Voltage upper bounds

Voltage upper bounds can determine SOCP exactness: relaxing them preserves exactness under stated radial-network conditions, while a binding upper bound can exclude the high-voltage power-flow solution.

  • Two-bus geometry: In a two-bus network, the SOCP relaxation is exact when the high-voltage power-flow solution c remains feasible after constraints are imposed.The relaxation enlarges the nonconvex feasible set to a line segment, and an increasing cost selects c when it remains feasible.
  • Two-bus geometry: A voltage lower bound does not affect exactness in the illustrated two-bus setting, whereas a voltage upper bound can exclude c and destroy exactness.The lower bound corresponds to an upper bound on ℓ, while the upper bound corresponds to a lower bound on ℓ.
  • Radial-network conditions: Theorem 5 establishes exactness on radial networks under B1–B3, including the affine injection constraint condition B2 and the directional-flow condition B3.B3 requires products describing propagation along each leaf-to-root path to be positive.
  • Consequences and scope: If the cost is only nondecreasing rather than strictly increasing in the relevant loss variable, the relaxation may have an optimal solution infeasible for OPF despite recoverability of an OPF optimum.The proof can still construct an optimal OPF solution from such a relaxation optimum, but the relaxation is not exact under the paper’s definition.
  • Radial-network conditions: B3 has the practical interpretation that branch power flows move in the same direction, with sufficient cases involving no reverse flows or particular downstream r/x-ratio patterns.The listed cases include equal r/x ratios, increasing downstream r/x ratios preventing reverse real flows, and decreasing ratios preventing reverse reactive flows.
  • Consequences and scope: Exactness does not require convex costs or convex injection regions, although convexity enables polynomial-time computation and implies uniqueness of the optimal solution when exactness holds.The uniqueness result assumes convex cost functions and convex injection regions on a tree.

C. Angle differences

Bounding voltage angle differences can make the nonconvex OPF feasible set align with the Pareto front of its convex relaxation, yielding exactness under stated conditions. The geometric argument is clearest for fixed voltage magnitudes and simplified power-flow settings.

  • C. Angle differences: Small voltage angle differences produce a locally convex power-flow surface that can coincide with the relaxation’s Pareto front.This supports exactness when the angle bounds are suitably restricted.
  • C. Angle differences: For fixed voltage magnitudes, real power flows, currents, losses, and stability constraints can be expressed using line angle differences.The real-power expression depends on cosθ_jk and sinθ_jk, while current limits depend on cosθ_jk.
  • C. Angle differences: The relaxation replaces the nonconvex feasible set Pθ ∩ Pp with a convex superset, and exactness means every relaxed optimum lies in the original feasible set.Pareto-front reasoning connects this definition to increasing objectives.
  • C. Angle differences: For a tree with strictly increasing cost and suitably bounded angles, Pθ ∩ Pp equals the Pareto front of conv(Pθ) ∩ Pp, so the SOCP relaxation is exact.The theorem also establishes that the stated relaxation is an SOCP.
  • C. Angle differences: Strict increase of the cost is needed for every relaxed optimum to be optimal for OPF; mere nondecrease may allow non-exact relaxed optima.An optimal OPF solution can still be recovered in that weaker case.
  • C. Angle differences: Lower bounds on power injections can threaten exactness when the upper half of the ellipse remains feasible, whereas upper bounds do not affect it in the illustrated setting.The angle condition removes the problematic upper half.

D. Equivalence

For radial networks, the sufficient conditions ensure exact SOCP relaxation, and equivalence between BIM and BFM transfers the result across formulations. Under convex costs, the corresponding optimal solution is unique, and the result also covers SDP and chordal relaxations.

  • D. Equivalence: BIM and BFM are linked by a linear bijection, so exactness conditions established in one model apply to the other.The mapping directly transfers the radial-network results.
  • D. Equivalence: Under conditions A1–A2’, A3–A4, or B1–B3 on tree networks, the BIM and BFM SOCP relaxations are exact.The theorem states exactness for both formulations.
  • D. Equivalence: If the relevant cost is convex, the optimal solution is unique in both BIM and BFM formulations.The BIM condition concerns C(WG), while the BFM condition concerns C(x)=∑j Cj(pj).
  • D. Equivalence: Because SDP and chordal relaxations are equivalent to SOCP on radial networks, the same exactness results apply to them.This extends the theorem beyond the SOCP formulation.

IV. MESH NETWORKS

In mesh networks, radial-network conditions do not ensure the global cycle condition, but strategically placed tunable phase shifters restore implementability of SOCP solutions. The resulting equivalence identifies how phase-shifter placement can convexify mesh OPF.

  • IV. MESH NETWORKS: Radial sufficient conditions enforce local SOCP equalities but not the global cycle condition in mesh networks.The cycle condition is vacuous on trees but may fail when the network contains cycles.
  • IV. MESH NETWORKS: The phase-shifter model is idealized: it shifts sending-end voltage and current angles without impedance or shifted-angle limits.Power transfer remains lossless under the stated modeling assumptions.
  • IV. MESH NETWORKS: Tunable phase shifters on lines outside a spanning tree can make any SOCP solution satisfying local equalities implementable.The phase-shifter angles solve the cycle equations, and only non-tree lines require them.
  • IV. MESH NETWORKS: The feasible-set inclusions imply Copt ≥ CT = Cps = Cnc ≥ Csocp for the original, phase-shifter, and relaxed problems.The phase-shifter variants share an optimal value, while the SOCP value lower-bounds them.
  • IV. MESH NETWORKS: Theorem 10 gives XT = X ≡ Xnc for any fixed spanning tree, equating the phase-shifter-feasible set with the local-equality set.This is the structural basis for extending radial exactness results to selected mesh networks.
  • IV. MESH NETWORKS: If SOCP is exact, phase shifters cannot further reduce operating cost; otherwise, they can make a locally tight SOCP solution physically implementable.This provides a criterion for when phase shifters offer operational benefit.

B. DC networks

For DC networks, the tutorial gives sufficient conditions for exact SOCP and SDP relaxations, while emphasizing that general mesh-network guarantees remain limited.

  • Exactness conditions: Corollaries 13 and 14 provide sufficient conditions for exact SOCP and SDP relaxations under stated structural assumptions.Corollary 13 uses A3–A4 and D0; Corollary 14 uses A1 and A4.
  • Exactness conditions: Theorem 15 proves OPF-socp exactness under either B1, B2”, D0 or B1’, B2’, D0, with uniqueness when the problem is convex.The relaxation includes additional constraints Wjk ≥ 0.
  • Limitations: No general sufficient conditions for exact semidefinite relaxation of AC mesh networks are known.Existing type A results cover only special cases such as lossless cycles, a lossless cycle with one chord, or weakly cyclic networks of size three.
  • Conclusion: For radial networks, the summarized conditions suggest SOCP, and consequently SDP and chordal relaxations, will likely be exact in practice.For mesh networks, applicability is limited to special cases including tunable phase-shifter networks and certain DC networks.

VI. APPENDIX: PROOFS

The appendix proves exactness by constructing feasible rank-1 or original-model solutions from relaxed optima without increasing cost.

  • Theorem 1: Every feasible SOCP matrix is used to construct an x feasible for the QCQP with equal or lower cost.This establishes the recovery direction needed to relate relaxed and nonconvex optima.
  • Theorem 1: When all edge submatrices are 2×2 positive semidefinite and rank-1, tree traversal assigns voltage angles that produce a feasible QCQP solution.The root angle is fixed, and neighboring angles are assigned recursively along the tree.
  • Theorem 1: If some edge submatrix is not rank-1, the proof constructs a modified matrix that is 2×2 positive semidefinite and rank-1 while preserving feasibility and cost dominance.The construction chooses positive edge parameters to enforce the rank-1 condition.
  • Corollary 2: Under A1, strict convexity makes the SOCP optimum unique, so a non-rank-1 optimal solution would contradict uniqueness after modification.Therefore the optimal SOCP matrix must be 2×2 positive semidefinite rank-1 on every edge.

B. Proof of Theorem 4: no injection lower bounds (BFM)

Theorem 4 proves exactness for radial BFM relaxations without injection lower bounds by reducing any strict conic inequality and contradicting optimality.

  • Contradiction construction: The proof starts from an optimal relaxed solution violating equality in (11c) and modifies one line’s current, flows, and endpoint injections.All other currents, flows, voltages, and injections remain unchanged.
  • Contradiction construction: Under A3, reducing the selected line current strictly lowers the objective, while A4 preserves the relevant injection constraints.The proof then checks feasibility at the two affected buses and on the modified line.
  • Feasibility: The modified point satisfies the branch-flow equalities and conic constraints for a sufficiently small positive perturbation.The argument verifies the constraints at both endpoints and on the altered line.
  • Scope boundary: If the cost is merely nondecreasing rather than strictly increasing, A3–A4 still map OPF optima to relaxation optima, but the relaxation may retain strict inequalities.A further construction can recover an optimal original OPF solution from such a relaxed optimum.

C. Proof of Theorem 5: voltage upper bounds

Theorem 5 proves exactness under voltage upper-bound conditions by reducing the first violated line current and propagating the resulting changes through the feeder.

  • Proof setup: The proof is first presented for a linear primary feeder without laterals and then extended to general trees by focusing on a root-to-violating-link path.The closest line to the root with strict inequality is selected as the perturbation site.
  • Figure 7: Figure 7 identifies m as the closest-to-root line where (38) is strict, separating equality before m from weaker inequalities after it.This location determines where the perturbation begins.
  • Perturbation: The construction reduces the current on the first violated line by εm while recursively redefining upstream flows, currents, injections, and voltages.The choice εm ∈ (0, ℓm − |Sm|2/vm] preserves the selected line’s relaxed constraint.
  • Feasibility: The modified point preserves the model’s other constraints, and Lemma 16 establishes the voltage bounds and relaxed conic inequalities.The construction propagates flow changes toward the root and voltage changes in the opposite direction.
  • Exactness: Under B1, B2, and B3’, the modified point is feasible and has strictly lower cost, contradicting optimality of a solution with a strict inequality.Thus every optimal relaxed solution attains equality in the relevant branch-flow constraint.
  • Propagation argument: The key recursion shows that reducing loss on the selected line increases upstream branch powers under B3’.This positivity is established by comparing linear time-varying systems and yields ΔSj > 0 upstream.

D. Proof of Theorem 6: uniqueness of SOCP solution

The proof shows that two distinct optimal SOCP solutions would force equality conditions that make them identical, establishing uniqueness.

  • Convexity makes the midpoint of two distinct optimal relaxation solutions feasible and optimal.
  • Equality in the relaxation constraint forces the optimal solutions’ branch-flow angles and scaled magnitudes to coincide.
  • The relations η_j˜S_jk = ˆS_jk and η_j˜ℓ_jk = ˆℓ_jk propagate through the connected network.
  • Consequently, ˆS = ˜S, ˆℓ = ˜ℓ, ˆv = ˜v, ˆs = ˜s, and therefore ˆx = ˜x.

E. Proof of Corollary 7: hollow feasible set

The corollary establishes that the branch-flow feasible set is hollow: distinct feasible solutions cannot have a feasible convex combination.

  • If two distinct branch-flow solutions belong to X, no convex combination of them can remain in X.
  • Therefore, the feasible set X is nonconvex.

F. Proof of Theorem 8: angle difference

The proof establishes SOCP exactness for radial networks under angle and cost conditions by showing that the relaxation preserves the relevant Pareto front.

  • Case 1: two-bus network: For a two-bus network, branch-flow points form an ellipse as the angle difference varies over its permitted interval.
  • Case 1: two-bus network: The computable relaxation set conv(Pθ)∩Pp is a second-order cone intersected with an affine set and has the same Pareto front under C1.
  • Case 1: two-bus network: Under C1, restricting the feasible set by injection bounds preserves the property that its Pareto front coincides with the original feasible subset.
  • Case 1: two-bus network: Because every minimizer of an increasing objective lies on that Pareto front, every SOCP minimizer is feasible and optimal for the original two-bus OPF.
  • Case 2: tree network: For a tree network, branch-flow regions form a direct product across lines because angle differences can be realized by unique bus angles.
  • Case 2: tree network: The full-rank linear transformation between branch flows and injections preserves the formulation, making conv(Pθ)∩Pp an SOCP feasible set.
  • Case 2: tree network: Under C1, the relaxation is exact because every minimizer lies in the original feasible set’s Pareto front.

G. Proof of Theorem 10: mesh networks with phase shifters

The proof constructs a bijection between phase-shifter branch-flow solutions and the corresponding nonconvex solutions, then uses it to establish equivalence for mesh networks.

  • The proof defines a mapping h and seeks an inverse that converts nonconvex solutions into branch-flow solutions with phase shifters.
  • For each nonconvex solution, a unique angle-and-phase-shifter vector satisfying the required relation is constructed.
  • The constructed inverse maps every nonconvex solution to a phase-shifter branch-flow solution satisfying the branch-flow equations.
  • The maps are inverses, establishing a bijection between X_T and X_nc and proving their equivalence.
  • The same argument shows X_T = X, completing the proof of Theorem 10.
Loading 1405.0814v1…