PaperlayerView exact revision on arXiv

Source-linked AI summary

Convex Relaxation of Optimal Power Flow, Part I: Formulations and Equivalence

Steven H. Low

arXiv:1405.0766v1math.OCeess.SY

TL;DR

OPF is difficult because its quadratic power-flow equations produce a generally nonconvex optimization problem. This tutorial presents equivalent bus injection and branch flow formulations, derives convex relaxations, and proves their structural relationships. It recommends the simpler SOCP relaxation for radial networks while identifying tighter but more computationally demanding alternatives for mesh networks, with exactness conditions deferred to Part II.

  • Problem

    OPF is generally nonconvex and NP-hard, motivating relaxations that can provide global-optimality checks and bounds unavailable from local nonlinear methods.

  • Method

    The tutorial presents BIM and BFM, formulates OPF and convex relaxations in both, and proves equivalence and tightness relationships using feasible-set characterizations.

  • Results

    For radial networks, OPF-socp is the tightest and simplest relaxation; for mesh networks, OPF-ch and OPF-sdp are tighter than OPF-socp, while OPF-ch is usually faster than OPF-sdp.

  • Takeaways & Limitations

    The results support solving OPF-socp on radial networks and choosing between tighter relaxations and computational cost on mesh networks.

  • Takeaways & Limitations

    Part I focuses on the simplest OPF formulation and does not cover stochastic or distributed OPF, newer applications, or remedies when relaxations fail.

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

The tutorial develops structural foundations for convex OPF relaxation by presenting equivalent bus injection and branch flow models, formulating their relaxations, and analyzing when they coincide. It emphasizes nonconvexity, model-specific advantages, and the distinction between relaxation relationships and exactness conditions.

  • Motivation: OPF minimizes objectives such as loss, generation cost, or user disutility subject to Kirchhoff’s laws and operational constraints.It supports applications including economic dispatch, unit commitment, state estimation, and reliability assessment.
  • Motivation: Because power flow equations are quadratic, OPF is generally a nonconvex QCQP and is NP-hard in general.DC OPF provides a linear approximation, but it may produce infeasible solutions for the nonlinear equations.
  • Motivation: Convex relaxation can certify global optimality, provide lower bounds when not exact, and certify original infeasibility when the relaxation is infeasible.These guarantees contrast with local optimality and heuristic adjustment associated with other approaches.
  • Scope and models: Part I presents BIM and BFM, proves a bijection between their power-flow solution sets, formulates OPF in each, and establishes relationships among their relaxations.The two models remain useful for different purposes despite their equivalence.
  • Scope and models: BIM offers a cleaner SDP formulation, whereas BFM provides recursive radial-network computations, a useful linear approximation, and direct branch-flow variables.The paper therefore uses each model where its structure is most convenient.

B. Branch flow model

The branch flow model represents network variables and constraints through branch powers, currents, voltages, and injections, yielding a generally nonconvex OPF formulation. Its relationship to the bus injection formulation follows from the equivalence of the underlying models.

  • Formulation: The branch flow model retains branch variables ˜x := (S,I,V,s) and defines OPF over its corresponding feasible set.The cost function is denoted C(˜x).
  • Formulation: Since the branch flow equations are quadratic, their feasible set is generally nonconvex and OPF is NP-hard in general.This nonconvexity motivates the convex relaxations developed later.
  • Equivalence: Under a bijection between BIM and BFM feasible solutions, equivalent cost functions make the two OPF formulations equivalent.The equivalence applies to OPF (7) in BIM and OPF (9) in BFM.
  • Scope: The simplified OPF formulation omits line, security, stability, and chance constraints, although some additions can be incorporated without changing the paper’s results.Shunt elements and line limits are cited as examples that can be included through model modifications.
  • Network equations: The model uses Ohm’s law I = YV to relate network currents and voltages, with bus-injection quantities expressed through admittance-matrix representations.The relevant matrix components need not be Hermitian, so real and imaginary parts are handled separately.

IV. FEASIBLE SETS AND RELAXATIONS: BIM

The BIM feasible set is characterized through full and partial Hermitian matrices, yielding equivalent formulations based on chordal extensions, local 2×2 conditions, and cycle consistency. These characterizations support SDP, chordal, and SOCP relaxations while preserving recovery relationships to OPF solutions.

  • Relaxations: Partial-matrix characterizations naturally produce SDP, chordal, and SOCP relaxations of OPF in the BIM.These formulations replace nonconvex rank-1 or cycle constraints with convex supersets.
  • Semidefinite formulation: The full-matrix formulation is equivalent to a rank-1 matrix problem whose rank-1 constraint is removed to obtain the standard SDP relaxation.A psd rank-1 solution can be uniquely factored as W = VV^H to recover a voltage solution V.
  • Feasible-set characterizations: A network partial matrix has a psd rank-1 completion exactly when it is 2×2 psd rank-1 on G and satisfies the cycle condition, equivalently through a chordal extension.The cycle condition requires voltage phase differences to sum to zero modulo 2π around every cycle.
  • Feasible-set characterizations: Theorem 2 links full-matrix, chordal-extension, and network partial-matrix conditions, enabling simpler computations with smaller submatrices in sparse networks.The theorem identifies (14), (15), and (16)+(13) as equivalent descriptions.
  • Recovery and equivalence: Each feasible chordal-extension or network partial matrix has a unique psd rank-1 completion from which a feasible OPF voltage vector can be recovered.The completion provides the matrix representation needed for rank-1 factorization and voltage recovery.
  • Feasible-set characterizations: The BIM feasible set admits equivalent characterizations using a full matrix, a chordal-extension partial matrix, or a network partial matrix.Theorem 4 states V ≡ W ≡ Wc(G) ≡ WG.

C. Semidefinite relaxations

The equivalent BIM formulations lead to SDP, chordal, and SOCP relaxations by removing rank-1 and cycle constraints or enlarging feasible sets. These relaxations differ in matrix representation while remaining tied to the same OPF formulation.

  • Relaxation construction: Removing rank-1 constraints and the cycle condition from equivalent feasible sets produces SDP, chordal, and SOCP relaxations.The relaxations correspond respectively to W, Wc(G), and WG.
  • Second-order cone relaxation: The SOCP formulation uses a rotated second-order cone representation for its relevant matrix constraint.The resulting problem is an SOCP in rotated form.
  • Related formulations: Prior work introduced SOCP, SDP, and chordal relaxations for OPF in different models and analyzed their relationships.The cited literature includes formulations for both bus injection and branch flow models.

D. Solution recovery

The paper characterizes BFM feasible solutions through phase-consistency conditions and shows how feasible relaxation solutions can recover OPF solutions. It compares SDP, chordal, and SOCP relaxations, including their topology-dependent tightness and computational trade-offs.

  • Solution recovery: When a relaxation optimum lies in the corresponding original feasible set, an optimal OPF voltage solution can be recovered; the construction depends only on WG.The recovery method applies to any feasible solution in W, Wc(G), or WG, not only to optimal solutions.
  • Tightness of relaxations: All three relaxations provide lower bounds, with Copt ≥ Csdp = Cch ≥ Csocp; on trees, the three relaxation values coincide.For radial networks, SOCP is therefore the simplest and tightest of the three, while mesh networks create a tightness-versus-computation trade-off.
  • Chordal relaxation: Chordal extensions preserve the chordal relaxation’s optimal value but determine computational complexity, and finding the minimum-complexity extension is NP-hard.Clique sizes, overlaps, auxiliary variables, and decoupling constraints create competing complexity costs; dropping some decoupling constraints can weaken the relaxation.
  • BFM relaxation: The BFM SOCP relaxation is derived by relaxing phase angles and replacing selected quadratic equalities with inequalities, exposing differences between radial and mesh networks.This derivation motivates recursive radial formulations and phase shifters for convexifying mesh networks.
  • Feasible-set characterization: The BFM relaxation maps feasible OPF solutions into a larger set, while the equivalent feasible subset is characterized by phase differences satisfying cycle consistency.The bijection between the original BFM feasible set and the cycle-consistent subset establishes equivalence within the relaxation variables.
  • Feasible-set characterization: Any x satisfying the cycle condition determines voltage phase angles, allowing recovery of a corresponding BFM power-flow solution.The recovered phase assignment is unique in (−π,π]n when it exists.

B. SOCP relaxation

The SOCP relaxation enlarges the nonconvex feasible set by replacing quadratic equalities with inequalities, yielding nested feasible sets and ordered optimal costs. For radial networks, an optimal SOCP solution can be recovered to an optimal OPF solution when the relevant equality holds.

  • B. SOCP relaxation: Relaxing the quadratic equalities in Xnc produces the convex superset X+, which is a rotated second-order cone.The feasible sets satisfy X ⊆ Xnc ⊆ X+.
  • B. SOCP relaxation: Theorem 9 establishes ˜X ≡ X ⊆ Xnc ⊆ X+, with X = Xnc when the network graph is a tree.The equivalent branch-flow feasible set and its convex-relaxation sets are therefore ordered by inclusion.
  • B. SOCP relaxation: The optimal costs satisfy Copt = Copf ≥ Cnc ≥ Csocp, and radial networks additionally satisfy Copt = Copf = Cnc ≥ Csocp.The SOCP relaxation provides a lower bound on the original OPF cost.
  • B. SOCP relaxation: For radial networks, equality in the SOCP constraint lets an optimal solution of OPF-socp be mapped back to an optimal solution of the original OPF.For mesh networks, recovery additionally requires the cycle condition.

C. Equivalence

The paper establishes equivalence among branch-flow and bus-injection formulations through bijections between their feasible sets. For radial networks, recursive branch-flow structure makes the cycle condition automatic and supports exact reduced formulations.

  • C. Equivalence: The sets X, W_G, Xnc, Wnc, X+, and W+ correspond through bijections linking branch-flow and bus-injection representations.Theorem 11 states X ≡ W_G, Xnc ≡ Wnc, and X+ ≡ W+.
  • C. Equivalence: For radial networks, the reduced branch-flow model is exact because the incident matrix is invertible and the cycle condition is always satisfied.A solution in Xnc can therefore be mapped to a branch-flow solution in ˜X.
  • C. Equivalence: The branch-flow model applies to arbitrary graph orientations and becomes recursive when the network is a tree rooted at bus 0.Different orientations provide different boundary conditions for initializing the recursion.
  • C. Equivalence: With links directed away from the root, the branch-flow equations reduce to the DistFlow equations, which recursively describe power flows and voltages.For a linear network, the recursion can be collapsed into functions of the root injection and solved using the leaf boundary condition.
  • C. Equivalence: The two branch-flow orientations have formally bijective solution sets, so they represent the same power-flow solutions despite different recursive boundary conditions.The paper explicitly states a bijection between the solution sets of the two formulations.

B. Linear approximation and bounds

Branch-flow linearizations provide recursive approximations and bounds on nonlinear power flows and voltages. These bounds remain valid for SOCP-relaxed constraints and motivate different solution strategies for radial and mesh networks.

  • B. Linear approximation and bounds: Setting line-current squared variables to zero yields a linear branch-flow approximation that preserves resistance, voltage variation, and reactive power.Unlike DC OPF, the radial branch-flow approximations retain these distribution-system features.
  • B. Linear approximation and bounds: The linearized branch power underestimates the nonlinear power required to supply subtree loads because it neglects line losses.The nonlinear flow equals the aggregate subtree load plus losses, while the linear approximation omits those losses.
  • B. Linear approximation and bounds: For the reverse orientation, the linear approximation overestimates branch power because it omits line losses from the nonlinear flow.The nonlinear branch power equals subtree injections minus losses in that orientation.
  • B. Linear approximation and bounds: The linearization-based bounds remain valid after relaxing the quadratic branch-flow equalities to SOCP inequalities, provided line-current variables are nonnegative.These bounds are used to prove sufficient conditions for exact SOCP relaxation on radial networks.
  • VII. CONCLUSION: The paper recommends SOCP for radial networks, while mesh networks use chordal relaxation for small instances and SOCP followed by heuristic feasibility search for large instances.The strategy relies on recovering an optimal original OPF solution when the relaxation is exact.

APPENDIX VIII: MATHEMATICAL PRELIMINARIES

The appendix reviews QCQP, SDP, SOCP, graph, and partial-matrix concepts underlying the paper’s relaxations. It explains how lifting removes quadratic structure, while chordal sparsity enables computation with partial matrices and recoverability under rank conditions.

  • Mathematical preliminaries: A QCQP is convex when all quadratic-form matrices are positive semidefinite; otherwise it is generally nonconvex.OPF is formulated as a QCQP before applying SDP and SOCP relaxations.
  • Mathematical preliminaries: Lifting x to X = xx^H makes the QCQP objective and constraints linear in X, leaving the rank-one constraint as the only nonconvex constraint.Removing rank one produces an SDP relaxation.
  • Mathematical preliminaries: If the SDP optimum has rank one, spectral decomposition recovers an optimal solution of the original QCQP.Higher-rank optima do not generally yield a feasible original solution directly.
  • Mathematical preliminaries: SOCP is a convex-program class that includes linear programs and convex QCQPs, and OPF uses its rotated form.The appendix notes that solving SOCP directly is generally more efficient than representing it as an SDP.
  • B. Graph, partial matrix and completion: A partial matrix specifies entries on a graph, while a completion fills unspecified entries so that the completed matrix agrees on all specified diagonal and edge entries.Positive semidefiniteness of a partial matrix is defined through its fully specified maximal-clique submatrices.
  • B. Graph, partial matrix and completion: When QCQP matrices are defined on a sparse graph, objectives and constraints depend only on the graph’s partial matrix, whereas full positive semidefiniteness depends on unspecified entries too.Chordal relaxation seeks a positive-semidefinite partial matrix on a chordal extension, with rank-one structure enabling recovery.

C. Chordal relaxation

The chordal relaxation replaces a large PSD constraint with PSD constraints on maximal-clique submatrices, coupled through auxiliary variables, while preserving SDP equivalence. Its computational benefit depends on balancing clique sizes against the number of coupling constraints.

  • Construction: A chordal extension F partitions the matrix into maximal-clique submatrices whose PSD constraints define the chordal relaxation.The construction lists maximal cliques, forms their principal submatrices, and introduces a partial matrix on F.
  • Equivalence: The chordal relaxation is equivalent to the standard SDP because every feasible chordal solution has a PSD completion with the same cost, and vice versa.The equivalence follows from the PSD-completion theorem for chordal graphs and the fact that the cost matrices are defined on G.
  • Construction: Overlapping clique submatrices require decoupling variables and equality constraints to enforce consistency on shared entries.For the two-clique example, variables u_jk decouple the overlapping matrices and are constrained to agree on shared entries.
  • Computational trade-offs: 4 additional equality constraints arise with 2 cliques of sizes 3 and 4, whereas 8 arise with 3 cliques of size 3.The examples illustrate the trade-off between smaller PSD blocks and more coupling constraints.
  • Computational trade-offs: For large sparse graphs, the chordal relaxation can typically be solved more efficiently than the original SDP, but selecting a good chordal extension is nontrivial.Fewer cliques can create larger submatrices, while more cliques increase decoupling variables and equality constraints.

B. Proof of Theorem 2: rank-1 characterization

Theorem 2 characterizes when a partial matrix associated with the network admits a PSD rank-1 completion. The proof links global completion, chordal-completion conditions, and cycle consistency, and establishes uniqueness of the recovered completion.

  • Rank-1 characterization: A PSD rank-1 matrix has PSD rank-1 principal submatrices, establishing the implication from a global completion to its chordal partial submatrix.Positive diagonal entries exclude rank-zero principal submatrices.
  • Cycle condition: A PSD rank-1 chordal partial matrix induces PSD rank-1 edge submatrices and satisfies the cycle condition through induction on cycle length.The induction uses chordality: every sufficiently long cycle has a chord and can be decomposed into shorter cycles.
  • Completion: Given a partial matrix satisfying the cycle condition, node phases can be constructed along paths to form a PSD rank-1 completion.The resulting vector V is defined relative to a reference phase, and W = VV^H completes the partial matrix.
  • Uniqueness: The PSD rank-1 completion of WG is unique because connectedness makes the phase system have a unique solution.Any two rank-1 completions must have the same magnitudes and phases, yielding identical factor vectors.

E. Proof of Theorem 7: BFM feasible sets

The proof of Theorem 7 establishes a bijection between the BFM feasible set and its alternative representation by reconstructing voltage and current phases from cycle-consistent angle data. A normalized phase interval makes the inverse mapping uniquely defined.

  • Phase reconstruction: Connectedness ensures that, for a fixed integer vector k, the phase solution θ is unique, while integer phase shifts generate equivalent solutions.Restricting θ to (−π,π] removes this representation ambiguity.
  • Phase reconstruction: An inverse mapping exists when (θ,k(θ)) solves the cycle equation, and at most one equivalence class of such solutions exists in the normalized phase interval.Lemma 14 gives both the feasibility condition and uniqueness statement.
  • Mapping between feasible sets: The normalized inverse mapping makes h and its inverse mutually consistent, proving equivalence of the two BFM feasible sets.Although θ itself is not unique without normalization, all equivalent choices map to the same reconstructed feasible point.
  • Cycle condition: Cycle conditions can be checked using a spanning-tree basis because satisfying them on all basis cycles implies satisfaction on every undirected cycle.The proof relates tree-path angle sums to non-tree edges and then derives the general cycle condition.

G. Proof of Theorem 9: radial networks

For radial networks, the BFM cycle condition is automatic because the incidence matrix is square and invertible. The proof therefore identifies the relevant feasible sets and establishes the corresponding bijections through the matrix-to-variable mapping.

  • Radial-network simplification: When the network is a tree, the reduced incidence matrix B is square and invertible, so every point in X^nc satisfies the cycle condition.Consequently, X = X^nc for radial networks.
  • Set bijection: The linear mapping g and its inverse establish a bijection between W_G^+ and X^+.The proof verifies that each map lands in the target set and that their compositions are identities.
  • Set bijection: The same mappings restricted to W_G and X^nc establish the corresponding bijection between the nonconvex feasible sets.The proof explicitly states that the restrictions define the bijection between these sets.
  • Verification: The construction derives voltage- and current-related constraints from the matrix entries and verifies the required edgewise PSD conditions.These checks use the matrix inequalities and the definitions connecting W_G to the BFM variables.

2 Sjk

The section proves equivalence between the cycle conditions in the two formulations under mappings g and g−1. It also establishes a one-to-one correspondence between solutions of the two oriented models, preserving voltage magnitudes and the voltage-magnitude inequality.

  • Mapping equivalence: The mappings g and g−1 are inverses, establishing the correspondence between the relevant feasible sets.The proof verifies both compositions and notes that the restricted mappings on Wnc and Xnc are also inverses.
  • Cycle conditions: The cycle conditions (13) and (26) are equivalent under g and g−1.Theorem 8 supplies the equivalence needed to complete the proof of Theorem 11.
  • Voltage comparison: The voltage magnitudes satisfy v ≤ vlin by transferring the comparison ˆv ≤ ˆvlin between the two graph orientations.The argument proves v = ˆv and vlin = ˆvlin after applying the invertible solution mapping, then invokes Lemma 13.
  • Power transformation: The received-power transformation subtracts line losses from sending-end power when relating the oppositely oriented models.For a branch j → k, −Skj represents power received at bus k net of the line loss zjkℓjk.
  • Oriented models: Reversing the graph orientation yields an invertible mapping between solutions of (33) and (36), with identical voltage magnitudes.The mapping is represented using the diagonal matrix Z, which gives a one-to-one correspondence and preserves v = ˆv.
Loading 1405.0766v1…