Convex Relaxation of Optimal Power Flow, Part II: Exactness

I Introduction

The optimal power flow (OPF) problem is fundamental in power systems as it underlies many applications such as economic dispatch, unit commitment, state estimation, stability and reliability assessment, volt/var control, demand response, etc. OPF seeks to optimize a certain objective function, such as power loss, generation cost and/or user utilities, subject to Kirchhoff’s laws as well as capacity, stability and security constraints on the voltages and power flows. There has been a great deal of research on OPF since Carpentier’s first formulation in 1962 . Recent surveys can be found in, e.g., .

OPF is generally nonconvex and NP-hard, and a large number of optimization algorithms and relaxations have been proposed. To the best of our knowledge solving OPF through semidefinite relaxation is first proposed in as a second-order cone program (SOCP) for radial (tree) networks and in as a semidefinite program (SDP) for general networks in a bus injection model. It is first proposed in as an SOCP for radial networks in the branch flow model of . While these convex relaxations have been illustrated numerically in and , whether or when they will turn out to be exact is first studied in . Exploiting graph sparsity to simplify the SDP relaxation of OPF is first proposed in and analyzed in .

Solving OPF through convex relaxation offers several advantages, as discussed in Part I of this tutorial [25, Section I]. In particular it provides the ability to check if a solution is globally optimal. If it is not, the solution provides a lower bound on the minimum cost and hence a bound on how far any feasible solution is from optimality. Unlike approximations, if a relaxed problem is infeasible, it is a certificate that the original OPF is infeasible.

This tutorial presents main results on convex relaxations of OPF developed in the last few years. In Part I , we present the bus injection model (BIM) and the branch flow model (BFM), formulate OPF within each model, and prove their equivalence. The complexity of OPF formulated here lies in the quadratic nature of power flows, i.e., the nonconvex quadratic constraints on the feasible set of OPF. We characterize these feasible sets and design convex supersets that lead to three different convex relaxations based on semidefinite programming (SDP), chordal extension, and second-order cone programming (SOCP). When a convex relaxation is exact, an optimal solution of the original nonconvex OPF can be recovered from every optimal solution of the relaxation. In Part II we summarize main sufficient conditions that guarantee the exactness of these relaxations.

Network topology turns out to play a critical role in determining whether a relaxation is exact. In Section II we review the definitions of OPF and their convex relaxations developed in . We also define the notion of exactness adopted in this paper. In Section III we present three types of sufficient conditions for these relaxations to be exact for radial networks. These conditions are generally not necessary and they have implications on allowable power injections, voltage magnitudes, or voltage angles:

Power injections: These conditions require that not both constraints on real and reactive power injections be binding at both ends of a line.

Voltages magnitudes: These conditions require that the upper bounds on voltage magnitudes not be binding. They can be enforced through affine constraints on power injections.

Voltage angles: These conditions require that the voltage angles across each line be sufficiently close. This is needed also for stability reasons.

These conditions and their references are summarized in Tables II and II.

Some of these sufficient conditions are proved using BIM and others using BFM. Since these two models are equivalent (in the sense that there is a linear bijection between their solution sets ), these sufficient conditions apply to both models. The proofs of these conditions typically do not require that the cost function be convex (they focus on the feasible sets and usually only need the cost function to be monotonic). Convexity is required however for efficient computation. Moreover it is proved in using BFM that when the cost function is convex then exactness of the SOCP relaxation implies uniqueness of the optimal solution for radial networks. Hence the equivalence of BIM and BFM implies that any of the three types of sufficient conditions guarantees that, for a radial network with a convex cost function, there is a unique optimal solution and it can be computed by solving an SOCP. Since the SDP and chordal relaxations are equivalent to the SOCP relaxation for radial networks , these results apply to all three types of relaxations. Empirical evidences suggest some of these conditions are likely satisfied in practice. This is important as most power distribution systems are radial.

These conditions are insufficient for general mesh networks because they cannot guarantee that an optimal solution of a relaxation satisfies the cycle condition discussed in . In Section IV we show that these conditions are however sufficient for mesh networks that have tunable phase shifters at strategic locations. The phase shifters effectively make a mesh network behave like a radial network as far as convex relaxation is concerned. The result can help determine if a network with a given set of phase shifters can be convexified and, if not, where additional phase shifters are needed for convexification. These conditions are also sufficient for direct current (dc) mesh networks where all variables are in the real rather than complex domain. Counterexamples are known where SDP relaxation is not exact, especially for AC mesh networks without tunable phase shifters . We discuss three recent approaches for global optimization of OPF when the semidefinite relaxations discussed in this tutorial fail.

We conclude in Section V. This extended version differs from the journal version only in the addition of Appendix VI that proves all main results covered in this tutorial. Even though all proofs can be found in their original papers, we provide proofs here because (i) it is convenient to have all proofs in one place and in a uniform notation, and (ii) some of the formulations and presentations here are slightly different from those in the original papers.

II OPF and its relaxations

We use the notations and definitions from Part I of this paper. In this section we summarize the OPF problems and their relaxations developed there; see for details.

We adopt in this paper a strong sense of “exactness” where we require the optimal solution set of the OPF problem and that of its relaxation be equivalent. This implies that an optimal solution of the nonconvex OPF problem can be recovered from every optimal solution of its relaxation. This is important because it ensures any algorithm that solves an exact relaxation always produces a globally optimal solution to the OPF problem. Indeed interior point methods for solving SDPs tend to produce a solution matrix with a maximum rank , so can miss a rank-1 solution if the relaxation has non-rank-1 solutions as well. It can be difficult to recover an optimal solution of OPF from such a non-rank-1 solution, and our definition of exactness avoids this complication. See Section II-C for detailed justifications.

where $\underline{s}_{j},\overline{s}_{j},\underline{v}_{j},\overline{v}_{j}$, possibly $\pm\infty\pm\textbf{i}\infty$, are given bounds on power injections and voltage magnitudes. Note that the vector $V$ includes $V_{0}$ which is assumed given ($\underline{v}_{0}=\overline{v}_{0}$ and $\angle V_{0}=0^{\circ}$) unless otherwise specified. The problem of interest is: OPF:

For relaxations consider the partial matrix $W_{G}$ defined on the network graph $G$ that satisfies

We say that $W_{G}$ satisfies the cycle condition if for every cycle $c$ in $G$

We assume the cost function $C$ depends on $V$ only through $VV^{H}$ and use the same symbol $C$ to denote the cost in terms of a full or partial matrix. Moreover we assume $C$ depends on the matrix only through the submatrix $W_{G}$ defined on the network graph $G$. See [25, Section IV] for more details including the definitions of $W_{c(G)}\succeq 0$ and $W_{G}(j,k)\succeq 0$. Define the convex relaxations: OPF-sdp:

For BIM, we say that OPF-sdp (5) is exact if every optimal solution $W^{\text{sdp}}$ of OPF-sdp is psd rank-1; OPF-ch (6) is exact if every optimal solution $W_{c(G)}^{\text{ch}}$ of OPF-ch is psd rank-1 (i.e., the principal submatrices $W_{c(G)}^{\text{ch}}(q)$ of $W_{c(G)}^{\text{ch}}$ are psd rank-1 for all maximal cliques $q$ of the chordal extension $c(G)$ of graph $G$); OPF-socp (7) is exact if every optimal solution $W_{G}^{\text{socp}}$ of OPF-socp is $2\times 2$ psd rank-1 and satisfies the cycle condition (4). To recover an optimal solution $V^{\text{opt}}$ of OPF (2) from $W^{\text{sdp}}$ or $W_{c(G)}^{\text{ch}}$ or $W_{G}^{\text{socp}}$, see [25, Section IV-D].

II-B Branch flow model

We say that $x$ satisfies the cycle condition if

II-C Exactness

III Radial networks

In this section we summarize the three types of sufficient conditions listed in Table II for semidefinite relaxations of OPF to be exact for radial (tree) networks. These results are important as most distribution systems are radial.

For radial networks, if SOCP relaxation is exact then SDP and chordal relaxations are also exact (see [25, Theorems 5, 9]). We hence focus in this section on the exactness of OPF-socp in both BIM and BFM. Since the cycle conditions (4) and (12) are vacuous for radial networks, OPF-socp (7) is exact if all of its optimal solutions are $2\times 2$ rank-1 and OPF-socp (13) is exact if all of its optimal solutions attain equalities in (11c). We will freely use either BIM or BFM in discussing these results. To avoid triviality we make the following assumption throughout the paper:

The voltage lower bounds satisfy $\underline{v}_{j}>0$, $j\in N^{+}$. The original problems OPF (2) and (10) are feasible.

We will first present a general result on the exactness of the SOCP relaxation of general QCQP and then apply it to OPF. This result is first formulated and proved using a duality argument in , generalizing the result of . It is proved using a simpler argument in .

The following result is proved in . It can be regarded as an extension of on the SOCP relaxation of QCQP from the real domain to the complex domain. Consider: All angles should be interpreted as “mod $2\pi$”, i.e., projected onto $(-\pi,\pi]$.

The cost matrix $C_{0}$ is positive definite.

For each link $(j,k)\in E$ there exists an $\alpha_{jk}$ such that $\angle\left[C_{l}\right]_{jk}\in[\alpha_{ij},\alpha_{ij}+\pi]$ for all $l=0,\dots,L$.

Let $C^{\text{opt}}$ and $C^{\text{socp}}$ denote the optimal values of QCQP (14) and SOCP (15) respectively.

Suppose $G$ is a tree and A2 holds. Then $C^{\text{opt}}=C^{\text{socp}}$ and an optimal solution of QCQP (14) can be recovered from every optimal solution of SOCP (15).

The proof of Theorem 1 prescribes a simple procedure to recover an optimal solution of QCQP (14) from any optimal solution of its SOCP relaxation (15). The construction does not need the optimal solution of SOCP (15) to be $2\times 2$ rank-1. Hence the SOCP relaxation may not be exact according to our definition of exactness, i.e., some optimal solutions of (15) may be $2\times 2$ psd but not $2\times 2$ rank-1. If the objective function is strictly convex however then the optimal solution sets of QCQP (14) and SOCP (15) are indeed equivalent.

Suppose $G$ is a tree and A1–A2 hold. Then SOCP (15) is exact.

We now apply Theorem 1 to our OPF problem. Recall that OPF (2) in BIM can be written as a standard form QCQP :

for some Hermitian matrices $C_{0},\Phi_{j},\Psi_{j},J_{j}$ where $j\in N^{+}$. A2 depends only on the off-diagonal entries of $C_{0}$, $\Phi_{j}$, $\Psi_{j}$ ($J_{j}$ are diagonal matrices). It implies a simple pattern on the power injection constraints (16)–(16). Let $y_{jk}=g_{jk}-\textbf{i}b_{jk}$ with $g_{jk}>0,b_{jk}>0$. Then we have (from ):

Hence for each line $(j,k)\in E$ the relevant angles for A2 are those of $[C_{0}]_{jk}$ and

as well as the angles of $-[\Phi_{j}]_{jk},-[\Phi_{k}]_{jk}$ and $-[\Psi_{j}]_{jk},-[\Psi_{k}]_{jk}$. These quantities are shown in Figure 1 with their magnitudes normalized to a common value and explained in the caption of the figure.

Condition A2 applied to OPF (16) takes the following form (see Figure 1):

For each link $(j,k)\in E$ there is a line in the complex plane through the origin such that $\left[C_{0}\right]_{jk}$ as well as those $\pm[\Phi_{i}]_{jk}$ and $\pm[\Psi_{i}]_{jk}$ corresponding to finite lower or upper bounds on $(p_{i},q_{i})$, for $i=j,k$, are all on one side of the line, possibly on the line itself.

Let $C^{\text{opt}}$ and $C^{\text{socp}}$ denote the optimal values of OPF (2) and OPF-socp (7) respectively.

$C^{\text{opt}}=C^{\text{socp}}$. Moreover an optimal solution $V^{\text{opt}}$ of OPF (2) can be recovered from every optimal solution $W_{G}^{\text{socp}}$ of OPF-socp (7).

If, in addition, A1 holds then OPF-socp (7) is exact.

It is clear from Figure 1 that condition A2’ cannot be satisfied if there is a line where both the real and reactive power injections at both ends are both lower and upper bounded (8 combinations as shown in the figure). A2’ requires that some of them be unconstrained even though in practice they are always bounded. It should be interpreted as requiring that the optimal solutions obtained by ignoring these bounds turn out to satisfy these bounds. This is generally different from solving the optimization with these constraints but requiring that they be inactive (strictly within these bounds) at optimality, unless the cost function is strictly convex. The result proved in also includes constraints on real branch power flows and line losses. Corollary 3 includes several sufficient conditions in the literature for exact relaxation as special cases; see the caption of Figure 1.

For $j\in N^{+}$, $\underline{s}_{j}=-\infty-\textbf{i}\infty$.

Popular cost functions in the literature include active power loss over the network or active power generations, both of which satisfy A3. The next result is proved in .

III-B Voltage upper bounds

While type A conditions (A2’ and A4 in the last subsection) require that some power injection constraints not be binding, type B conditions require non-binding voltage upper bounds. They are proved in using BFM.

For radial networks the model originally proposed in , which is (11) with the inequalities in (11c) replaced by equalities, is exact. This is because the cycle condition (12) is always satisfied as the reduced incidence matrix $B$ is $n\times n$ and invertible for radial networks. Following we adopt the graph orientation where every link points towards node 0. Then (11) for a radial network reduces to:

As before the voltage magnitudes must satisfy:

for some given $\overline{s}_{j}$, $j\in N$.We assume here that $s_{0}$ is unconstrained, and since $V_{0}:=1\angle 0^{\circ}$ pu, the constraints (18) involve only $j$ in $N$, not $N^{+}$. Then the SOCP relaxation is OPF-socp:

As defined in Section II-C, OPF-socp (19) is exact if every optimal solution $x^{\text{socp}}$ attains equality in (17c). In that case an optimal solution of BFM (10) can be uniquely recovered from $x^{\text{socp}}$.

Consider now the voltage constraint $\underline{v}_{1}\leq v_{1}\leq\overline{v}_{1}$. Substituting (20) into (21) we obtain

where $z_{jk}:=[r_{jk}\ \,x_{jk}]^{T}$ is the line impedance and $S_{jk}:=[P_{jk}\ \,Q_{jk}]^{T}$ is the branch power flows, both taken as 2-dimensional real vectors so that $z_{jk}\left(S_{jk}\right)^{T}$ is a $2\times 2$ matrix with rank less or equal to 1. The matrices $A_{jk}(S_{jk},v_{j})$ describe how changes in the real and reactive power flows propagate towards the root node 0; see comments below. Evaluate the Jacobian matrix $A_{jk}(S_{jk},v_{j})$ at the boundary values:

Here $\left(\left[a\right]^{+}\right)^{T}$ is the row vector $\left[[a_{1}]^{+}\ [a_{2}]^{+}\right]$ with $[a_{j}]^{+}:=\max\{0,a_{j}\}$.

For a radial network, for $j\neq 0$, every link $j\rightarrow k$ identifies a unique node $k$ and therefore, to simplify notation, we refer to a link interchangeably by $(j,k)$ or $j$ and use $A_{j}$, $\underline{A}_{j}$, $z_{j}$ etc. in place of $A_{jk}$, $\underline{A}_{jk}$, $z_{jk}$ etc. respectively.

The cost function is $C(x):=\sum_{j=0}^{n}C_{j}\left(\text{Re}\,s_{j}\right)$ with $C_{0}$ strictly increasing. There is no constraint on $s_{0}$.

We now comment on the conditions B1–B3. B1 requires that the cost functions $C_{j}$ depend only on the injections $s_{j}$. For instance, if $C_{j}\left(\text{Re}\,s_{j}\right)=p_{j}$, then the cost is total active power loss over the network. It also requires that $C_{0}$ be strictly increasing but makes no assumption on $C_{j},j>0$. Common cost functions such as line loss or generation cost usually satisfy B1. If $C_{0}$ is only nondecreasing, rather than strictly increasing, in $p_{0}$ then B1–B3 still guarantee that all optimal solutions of OPF (10) are (effectively) optimal for OPF-socp (19), but OPF-socp may not be exact, i.e., it may have an optimal solution that maintains strict inequalities in (17c). In this case the proof of Theorem 5 can be used to recursively construct from it another optimal solution that attains equalities in (17c).

B2 is affine in the injections $s:=(p,q)$. It enforces the upper bounds on voltage magnitudes because of (23).

B3 is a technical assumption and has a simple interpretation: the branch power flow $S_{jk}$ on all branches should move in the same direction. Specifically, given a marginal change in the complex power on line $j\rightarrow k$, the $2\times 2$ matrix $\underline{A}_{jk}$ is (a lower bound on) the Jacobian and describes the effect of this marginal change on the complex power on the line immediately upstream from line $j\rightarrow k$. The product of $\underline{A}_{i}$ in B3 propagates this effect upstream towards the root. B3 requires that a small change, positive or negative, in the power flow on a line affects all upstream branch powers in the same direction. This seems to hold with a significant margin in practice; see for examples from real systems.

Theorem 5 unifies and generalizes some earlier results in . The sufficient conditions in these papers have the following simple and practical interpretation: OPF-socp is exact provided either

there are no reverse power flows in the network, or

if the $r/x$ ratios on all lines are equal, or

if the $r/x$ ratios increase in the downstream direction from the substation (node 0) to the leaves then there are no reverse real power flows, or

if the $r/x$ ratios decrease in the downstream direction then there are no reverse reactive power flows.

This property is illustrated vividly in several numerical examples for mesh networks in .

III-C Angle differences

The sufficient conditions in require that the voltage angle difference across each line be small. We explain the intuition using a result in for an OPF problem where $|V_{j}|$ are fixed for all $j\in N^{+}$ and reactive powers are ignored. Under these assumptions, as long as the voltage angle difference is small, the power flow solutions form a locally convex surface that is the Pareto front of its relaxation. This implies that the relaxation is exact. This geometric picture is apparent in earlier work on the geometry of power flow solutions, see e.g. , and underlies the intuition that the dynamics of a power system is usually benign until it is pushed towards the boundary of its stability region. The geometric insight in Figures 2 and 3 for BFM and later in this subsection for BIM says that, when it is far away from the boundary, the local convexity structure also facilitates exact relaxation. Reactive power is considered in [37, Theorem 1] with fixed $|V_{j}|$ where, with an additional constraint on the lower bounds of reactive power injections that ensure these lower bounds are not tight, it is proved that if the original OPF problem is feasible then its SDP relaxation is exact. The case of variable $|V_{j}|$ without reactive power is considered in [36, Theorem 7] but the simple geometric structure is lost.

Recall that $y_{jk}=g_{jk}-\textbf{i}b_{jk}$ with $g_{jk}>0,b_{jk}>0$. Let $V_{j}=|V_{j}|\,e^{\textbf{i}\theta_{j}}$ and suppose $|V_{j}|$ are given. Consider:

where $\theta_{jk}:=\theta_{j}-\theta_{k}$ are the voltage angle differences across lines $(j,k)$.

We comment on the constraints on angles $\theta_{jk}$ in (26). When the voltage magnitudes $|V_{i}|$ are fixed, constraints on real power flows, branch currents, line losses, as well as stability constraints can all be represented in terms of $\theta_{jk}$. Indeed a line flow constraint of the form $|P_{jk}|\leq\overline{P}_{jk}$ becomes a constraint on $\theta_{jk}$ using the expression for $P_{jk}$ in (26e). A current constraint of the form $|I_{jk}|\leq\overline{I}_{jk}$ is also a constraint on $\theta_{jk}$ since $|I_{jk}|^{2}=|y_{jk}|(|V_{j}|^{2}+|V_{k}|^{2}-2|V_{j}V_{k}|\cos\theta_{jk})$. The line loss over $(j,k)\in E$ is equal to $P_{jk}+P_{kj}$ which is again a function of $\theta_{jk}$. Stability typically requires $|\theta_{jk}|$ to stay within a small threshold. Therefore given constraints on branch power or current flows, losses, and stability, appropriate bounds $\underline{\theta}_{jk},\overline{\theta}_{jk}$ can be determined in terms of these constraints, assuming $|V_{j}|$ are fixed.

We can eliminate the branch flows $P_{jk}$ and angles $\theta_{jk}$ from (26). Since $|V_{j}|,j\in N^{+}$, are fixed we assume without loss of generality that $|V_{j}|=1$ pu. Define the injection region

$C(p)$ is strictly increasing in each $p_{j}$.

For all $(j,k)\in E$, $-\tan^{-1}\frac{b_{jk}}{g_{jk}}<\underline{\theta}_{jk}\leq\overline{\theta}_{jk}<\tan^{-1}\frac{b_{jk}}{g_{jk}}$.

The following result, proved in , says that (29) is exact provided $\theta_{jk}$ are suitably bounded.

The problem (29) is indeed an SOCP. Moreover it is exact.

Theorem 8 is illustrated in Figures 4 and 5.

When the network is not radial or $|V_{j}|$ are not constants, then the feasible set can be much more complicated than ellipsoids . Even in such settings the Pareto fronts might still coincide, though the simple geometric picture is lost. See for a numerical example on an Australian system or on a three-bus mesh network.

III-D Equivalence

Since BIM and BFM are equivalent, the results on exact SOCP relaxation and uniqueness of optimal solution apply in both models. Recall the linear bijection $g$ from BIM to BFM defined in [25, end of Section V] by ${x}=g(W_{G})$ where

BIM: SOCP relaxation (7) is exact. Moreover if $C(W_{G})$ is convex in $([W_{G}]_{jj},[W_{G}]_{jk})$ then the optimal solution is unique.

BFM: SOCP relaxation (13) is exact. Moreover if $C(x):=\sum_{j}C_{j}(p_{j})$ is convex in $p$ then the optimal solution is unique.

Since both the SDP and the chordal relaxations are equivalent to the SOCP relaxation for radial networks, these results apply to SDP and chordal relaxations as well.

IV Mesh networks

In this section we summarize a result of [17, Part II] on mesh networks with phase shifters and of [17, Part I], on dc networks when all voltages are nonnegative.

To be able to recover an optimal solution of OPF from an optimal solution $W_{G}^{\text{socp}}/x^{\text{socp}}$ of SOCP relaxation, $W_{G}^{\text{socp}}/x^{\text{socp}}$ must satisfy both a local condition and a global cycle condition ((4) for BIM and (12) for BFM); see the definition of exactness in Section II. The conditions of Section III guarantee that every SOCP optimal solution will satisfy the local condition (i.e., $W_{G}^{\text{socp}}$ is $2\times 2$ psd rank-1 and $x^{\text{socp}}$ attains equalities in (11c)), whether the network is radial or mesh, but do not guarantee that it satisfies the cycle condition. For radial networks, the cycle condition is vacuous and therefore the conditions of Section III are sufficient for SOCP relaxation to be exact. The result of [17, Part II] implies that these conditions are sufficient also for a mesh network that has tunable phase shifters at strategic locations.

Similar conditions also extend to dc networks where all variables are real and the voltages are assumed nonnegative.

For BFM the conditions of Section III guarantee that every optimal solution of OPF-socp (13) attains equalities in (11c) but may or may not satisfy the cycle condition (12). If it does then it can be uniquely mapped to an optimal solution of OPF (10), according to [17, Theorem 2]. If it does not then the solution is not physically implementable because it does not satisfy the power flow equations (Kirchhoff’s laws). For a radial network the reduced incidence matrix $B$ in (12) is $n\times n$ and invertible and hence every optimal solution of the SOCP relaxation that attains equalities in (11c) always satisfies the cycle condition [17, Theorem 4]. This is not the case for a mesh network where $B$ is $m\times n$ with $m>n$.

It is proved in [17, Part II] however that if the network has tunable phase shifters then any SOCP solution that attains equalities in (11c) becomes implementable even if the solution does not satisfy the cycle condition. This extends the sufficient conditions A1–A2’, or A3–A4, or B1–B3, or C0–C1 from radial networks to this type of mesh networks.

For BIM the effect of phase shifter is equivalent to introducing a free variable $\phi_{c}$ in (4) for each basis cycle $c$ so that the cycle condition can always be satisfied for any $W_{G}$. The results presented here however start with a simple power flow model (30) for networks with phase shifters. This model makes transparent the effect of the spatial distribution of phase shifters and how they impact the exactness of SOCP relaxation and can be useful in other contexts, such as the design of a network of FACTS (Flexible AC Transmission Systems) devices.

BFM with phase shifters. We consider an idealized phase shifter that only shifts the phase angles of the sending-end voltage and current across a line, and has no impedance nor limits on the shifted angles. Specifically consider an idealized phase shifter parametrized by $\phi_{jk}$ across line $j\rightarrow k$ as shown in Figure 6.

As before let $V_{j}$ denote the sending-end voltage at node $j$. Define $I_{jk}$ to be the sending-end current leaving node $j$ towards node $k$. Let $i$ be the point between the phase shifter $\phi_{jk}$ and line impedance $z_{jk}$. Let $V_{i}$ and $I_{i}$ be the voltage at $i$ and the current from $i$ to $k$ respectively. Then the effect of an idealized phase shifter, parametrized by $\phi_{jk}$, is summarized by the following modeling assumptions:

The power transferred from nodes $j$ to $k$ is still (defined to be) $S_{jk}:=V_{j}I_{jk}^{H}$, which is equal to the power $V_{i}I_{i}^{H}$ from nodes $i$ to $k$ since the phase shifter is assumed to be lossless. Applying Ohm’s law across $z_{jk}$, we define the branch flow model with phase shifters as the following set of equations:

Cycle condition. If every line has a phase shifter then the cycle condition changes from (12) to: given any $x$ that satisfies (11) with equalities in (11c),

It is proved in [17, Part II] that, given any $x$ that attains equalities in (11c), there always exists a $\theta$ in $(-\pi,\pi]^{n}$ and a $\phi$ in $(-\pi,\pi]^{m}$ that solve (31). Moreover phase shifters are needed only on lines not in a spanning tree.

Phase shifters on every line enlarge the feasible set to:

and that where there are phase shifters only outside $T$: OPF-$T$:

Recall the following sets defined in for networks without phase shifters:

Let $C^{\text{nc}}$ and $C^{\text{socp}}$ denote respectively the optimal values of OPF-nc (34) and OPF-socp (13). Theorem 10 then implies

$C^{\text{opt}}\geq C^{T}=C^{\text{ps}}=C^{\text{nc}}\geq C^{\text{socp}}$.

Corollary 11 also implies that, if SOCP is exact, then phase shifters cannot further reduce the cost. This can help determine when phase shifters provide benefit to system operations.

Hence phase shifters in strategic locations make a mesh network behave like a radial network as far as convex relaxation is concerned. The results of Section III then imply

Suppose conditions A1–A2’, or A3–A4, or B1–B3, or C1–C2 hold. Then any optimal solution of OPF-socp (13) solves OPF-ps (32) and OPF-$T$ (33).

IV-B DC networks

In this subsection we consider purely resistive dc networks, i.e., the impedance $z_{jk}=r_{jk}=y_{jk}^{-1}$, the power injections $s_{j}=p_{j}$, and the voltages $V_{j}$ are real. We assume all voltage magnitudes are strictly positive. Formally:

Replace (1b) and (11b) by $0<\underline{V}_{j}\leq V_{j}\leq\overline{V}_{j}$, $j\in N^{+}$, and replace (3b) by $0<\underline{V}_{j}^{2}\leq[W_{G}]_{jj}\leq\overline{V}_{j}^{2}$, $j\in N^{+}$.

Type A conditions. Condition D0 immediately implies that the cycle condition (12) in BFM is satisfied by every feasible $x$ of OPF-socp (13), for

A3–A4 guarantee that any optimal solution of OPF-socp attains equality in (11c) for general mesh networks. Hence [25, Theorem 7] and Theorem 4 imply

Suppose A3–A4 and D0 hold. Then OPF-socp (13) is exact.

For BIM, consider an OPF as a QCQP (16) where all the matrices are real and symmetric. Even though all the QCQP matrices in (16) satisfy condition A2’, Corollary 3 is not directly applicable as its proof constructs a complex (rather than real) $V$ from an optimal solution of OPF-socp. However if there are no lower bounds on the power injections, then only $\Phi_{j}$ are involved in the QCQP so all their off-diagonal entries are negative. It is then observed in that [45, Theorem 3.1] directly implies (without needing D0)

Suppose A1 and A4 hold. Then OPF-sdp (5) and OPF-socp (7) are exact.

Type B conditions. The following result is proved in . Consider:

The cost function is $C(x):=\sum_{j=0}^{n}C_{j}\left(\text{Re}\,s_{j}\right)$ with $C_{j}$ strictly increasing for all $j\in N^{+}$. There is no constraint on $s_{0}$.

Suppose at least one of the following holds:

Then OPF-socp (7) with the additional constraints $W_{jk}\geq 0$, $(j,k)\in E$, is exact. If, in addition, the problem is convex then its optimal solution is unique.

It is possible to enforce B2” by an affine constraint on the power injections, similar to (but different from) condition B2 for radial networks; see for details. See also for a result on the uniqueness of SOCP relaxation.

IV-C General AC networks

Unfortunately no sufficient conditions for exact semidefinite relaxation for general mesh networks are yet known. There are type A conditions on power injections for exact relaxation only for special cases: a lossless cycle or lossless cycle with one chord , or a weakly cyclic network (where every line belongs to at most one cycle) of size 3 .

We close by mentioning three recent approaches for global optimization of OPF when the relaxations in this tutorial fail. First, higher-order semidefinite relaxations on the Lesserre hierarchy for polynomial optimization have been applied to solving OPF when SDP relaxation fails . By going up the hierarchy, the relaxations become tighter and their solutions approach a global optimal of the original polynomial optimization . This however comes at the cost of significantly higher runtime. Techniques are proposed in to reduce the problem sizes, e.g., by exploiting sparsity or adding redundant constraints or applying higher-order relaxations only on (typically small) subnetworks where constraints are violated .

Second, a branch-and bound algorithm is proposed in where a lower bound is computed from the Lagrangian dual of OPF and the feasible set subdivision is based on rectangular or ellipsoidal bisection. The dual problem is solved using a subgradient algorithm. Each iteration of the subgradient algorithm requires minimizing the Lagrangian over the primal variables. This minimization is separable into two subproblems, one being a convex subproblem and the other having a nonconvex quadratic objective. The latter subproblem turns out to be a trust-region problem that has a closed-form solution. It is proved in that the proposed algorithm converges to a global optimal. This method is extended in to include more constraints and alternatively use SDP relaxation for lower bounding the cost.

Finally a new approach is proposed in based on convex quadratic relaxation of OPF in polar coordinates.

V Conclusion

We have summarized the main sufficient conditions for exact semidefintie relaxations of OPF as listed in Tables II and II. For radial networks these conditions suggest that SOCP relaxation (and hence SDP and chordal relaxations) will likely be exact in practice. This is corroborated by significant numerical experience. For mesh networks they are applicable only for special cases: networks that have tunable phase shifters or dc networks where all variables are real and voltages are nonnegative. Even though counterexamples exist where SDP/chordal relaxation is not exact for AC mesh networks numerical experience seems to suggest that SDP/chordal relaxation tends to be exact in many cases. Sufficient conditions that guarantee exact relaxation for AC mesh networks however remain elusive. The main difficulty is in designing relaxations of the cycle condition (4) or (12).

VI Appendix: proofs

The proof is from an updated version of . It is equivalent to the argument of and simpler than the original duality proof in .

Now $W_{G}(j,k)\succeq 0$ for every $(j,k)\in E$ implies that $[W_{G}]_{jj}\geq 0$ for all $j\in N$ and

Hence $x$ is feasible for QCQP (14) and has the same cost as $W_{G}$.

Next suppose $[W_{G}]_{jj}[W_{G}]_{kk}>|[W_{G}]_{jk}|^{2}$ for some $(j,k)$, i.e., $W_{G}$ is $2\times 2$ psd but not $2\times 2$ rank-1. We will

Construct an $\hat{W}_{G}$ that is $2\times 2$ psd rank-1.

i.e., $x$ is feasible for QCQP (14) and has an equal or lower cost than $W_{G}$.

To construct such an $\hat{W}_{G}$ let $[\hat{W}_{G}]_{jj}=[W_{G}]_{jj}$, $j\in N^{+}$. For $(j,k)\in E$ let

for some $r_{jk}>0$ to be determined and $\alpha_{jk}$ in assumption A2. For $\hat{W}_{G}$ to be $2\times 2$ psd rank-1 we need to choose $r_{jk}>0$ such that $[\hat{W}_{G}]_{jj}[\hat{W}_{G}]_{kk}=\left|[\hat{W}_{G}]_{jk}\right|^{2}$ for all $(j,k)\in E$, i.e.,

Therefore setting $r_{jk}:=\sqrt{b^{2}+c}-b>0$ yields an $\hat{W}_{G}$ that is $2\times 2$ psd rank-1.

To show that $\hat{W}_{G}$ is feasible for SOCP (15) and has an equal or lower cost than $W_{G}$, we have for $l=0,1,\dots,L$,

where the last inequality follows because assumption A2 implies

and therefore $\cos\left(\angle[C_{l}]_{jk}+\frac{\pi}{2}-\alpha_{jk}\right)\leq 0$. This completes the proof. ∎

A1 implies that the objective function of SOCP (15) is strictly convex and hence has a unique optimal solution. Suppose $W_{G}$ is an optimal solution of SOCP (15) but $[W_{G}]_{jj}[W_{G}]_{kk}>|[W_{G}]_{jk}|^{2}$ for some $(j,k)$, i.e., $W_{G}$ is $2\times 2$ psd but not $2\times 2$ psd rank-1. Then the above constructs another feasible solution $\hat{W}_{G}$ with equal cost. This contradicts the uniqueness of the optimal solution of SOCP (15), and hence $W_{G}$ must be $2\times 2$ psd rank-1. ∎

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

We will construct an $\hat{x}$ that is feasible for OPF-socp and attains a strictly lower cost, contradicting that $x$ is optimal.

Assumption A4 ensures that $\hat{x}$ satisfies (9). Further $\hat{x}$ satisfies (11a) at buses $i\neq j,k$, and satisfies (11b) and (11c) over lines $(i,l)\neq(j,k)$. We now show that $\hat{x}$ also satisfies (11a) at buses $j$ and $k$ and satisfies (11b) and (11c) over line $(j,k)$.

For (11a) at bus $j$, we have (adopting the graph orientation where every link points away from node 0):

as desired. For (11b) over line $(j,k)$, we have

as desired. For (11c) over line $(j,k)$, we have

VI-C Proof of Theorem 5: voltage upper bounds

The proof here is from with a slightly different presentation. Given an optimal solution $x$ that maintains a strict inequality in (11c), the proof in Section VI-B of Theorem 4 by contradiction constructs another feasible solution $\hat{x}$ that incurs a strictly smaller cost, contradicting the optimality of $x$. The modification is over a single line over which $x$ maintains a strict inequality in (11c). The proof of Theorem 5 is also by contradiction but, unlike that of Theorem 4, the construction of $\hat{x}$ from $x$ involves modifications on multiple lines, propagating from the line that is closest to bus 0 where (11c) holds with strict inequality all the way to bus 0. The proof relies crucially on the recursive structure of the branch flow model (17).

With this notation the branch flow model (17) is the following recursion:

where $v_{0}$ is given. The SOCP relaxation of (37c) is:

OPF on the linear network then becomes ($s_{0}$ is unconstrained by assumption B1): OPF:

and its SOCP relaxation becomes: OPF-socp:

For the linear network assumption B3 reduces:

$\underline{A}_{j}\cdots\underline{A}_{k}\ z_{k+1}>0$ for $1\leq j\leq k<n$.

By construction $\hat{x}$ satisfies (37a), (37b), (37d), and (18b). We only have to prove that $\hat{x}$ satisfies (18a) and (38). Hence the proof of Theorem 5 is complete after Lemma 16 is established, which asserts that $\hat{x}$ is feasible and has a strictly lower cost under assumptions B1, B2, B3’.

Under the conditions of Theorem 5 $\hat{x}$ satisfies

$\underline{v_{j}}\ \leq\ \hat{v}_{j}\ \leq\ \overline{v}_{j}$, $j\in N$.

To simplify the notation redefine $S_{0}:=-s_{0}$ and $\hat{S}_{0}:=-\hat{s}_{0}$. Then for $j\in N^{+}$ define $\Delta S_{j}:=\hat{S}_{j}-S_{j}$ and $\Delta v_{j}:=\hat{v}_{j}-v_{j}$. The key result that leads to Lemma 16 is:

The first inequality is stated more precisely in Lemma 17 and proved after the proof of Lemma 16.

Suppose $m>1$ and B3’ holds. Then $\Delta S_{j}\geq 0$ for $j\in N^{+}$ with $\hat{S}_{j}>S_{j}$ for $j=0,\dots,m-1$. In particular $\hat{s}_{0}<s_{0}$.

We now prove the second inequality together with Lemma 16 assuming Lemma 17 holds.

1) If $m=1$ then, by construction, $\hat{s}_{0}=s_{0}-z_{1}\epsilon_{1}<s_{0}$ since $z_{1}>0$. If $m>1$ then $\hat{s}_{0}<s_{0}$ by Lemma 17. Since $\hat{s}=s$ and $\hat{s}_{0}<s_{0}$ we have

as desired, since $C_{0}$ is strictly increasing.

2) To avoid circular argument we will first prove using Lemma 17

To prove (41), note that both $\hat{v}$ and $v$ satisfy (37b) and hence we have, for $j=1,\dots,n$,

where $\Delta s_{0}:=\hat{s}_{0}-s_{0}<0$ and $s_{j-1}=0$ for $j>1$. Multiplying both sides by $z_{j}^{H}$ and noticing that both sides must be real, we conclude

Substituting into (42) we have for $j=1,\dots,n$

But Lemma 17 implies that $\text{Re }z_{j}^{H}\Delta S_{j}=r_{j}\,\Delta P_{j}+x_{j}\,\Delta Q_{j}\geq 0$. Similarly every term on the right-hand side is nonnegative and hence

implying that $\Delta v_{j}\geq\Delta v_{0}=0$, proving (41).

We now use (41) to prove the second assertion of the lemma. By construction, for $j=m+1,\dots,n$,

as desired, since $\hat{S}_{j}=S_{j}$ and $\hat{v}_{j}\geq v_{j}$. Similarly (38) holds for $\hat{x}$ for $j=m$ because of the choice of $\epsilon_{m}$. For $j=1,\dots,m-1$, $\hat{v}_{j}\geq v_{j}$ again implies

Assumption B2 and [25, Lemma 13] (see also Remark 6 of ) imply that

This proves $\hat{x}$ satisfies (18a) and completes the proof of Lemma 16. ∎

The remainder of this subsection is devoted to proving the key result Lemma 17.

This is proved in three steps, of which we now give an informal overview. First we derive a recursion (44) on $\Delta S_{j}$. This motivates a collection of linear dynamical systems $w$ in (46) that contains the process $(\Delta S_{j}$, $j=0,\dots,m-1)$ as a specific trajectory. Second we construct another collection of linear dynamical systems $\underline{w}$ in (47) such that assumption B3’ implies $\underline{w}>0$. Finally we prove an expression for the process $w-\underline{w}$ that shows $w\geq\underline{w}$ (in Lemmas 18, 19, 20). This then implies $\Delta S=w\geq\underline{w}>0$. We now make these steps precise.

Since both $x$ and $\hat{x}$ satisfy (37a) and $\hat{s}_{j}=s_{j}$ for all $j\in N$ we have (with the redefined $\Delta S_{0}:=-(\hat{s}_{0}-s_{0})$)

The mean value theorem implies for $j=1,\dots,m-1$

Clearly $\Delta S_{j}=\epsilon_{m}\,w(j;m-1)$. Hence, to prove $\Delta S_{j}>0$, it suffices to prove $w(j;m-1)>0$ for all $j$ with $0\leq j\leq m-1$.

To this end we compare the system $w(t;\tau)$ with the following collection of linear time-variant systems: for each $\tau$ with $0<\tau<m$,

where $\underline{A}_{t}$ is defined in (25) and reproduced here:

Note that $\underline{A}_{t}$ are independent of the OPF-socp solution $x$ and our modified solution $\hat{x}$. Then assumption B3’ is equivalent to

We now prove, in Lemmas 18, 19, 20, that $w(t;\tau)\geq\underline{w}(t;\tau)$ and hence B3’ implies $\Delta S_{j}=\epsilon_{m}\,w(j;m-1)\geq\epsilon_{m}\,\underline{w}(j;m-1)>0$, establishing Lemma 17.

for some 2-dimensional vector $\delta_{t}\geq 0$.

Then (50) and $v_{t}\geq\underline{v}_{t}$ impy that $\delta_{t}\geq 0$. ∎

For each $\tau$ with $0<\tau<m$ define the scalars $a(t;\tau)$ in terms of the solution $\underline{w}(t;\tau)$ of (47) and $\delta_{t}$ in Lemma 18:

Fix any $\tau$ with $0<\tau<m$. For each $t=\tau,\tau-1,\dots,0$ we have

Fix a $\tau$ with $0<\tau<m$. We now prove the lemma by induction on $t=\tau,\tau-1,\dots,0$. The assertion holds for $t=\tau$ since $w(\tau;\tau)-\underline{w}(\tau;\tau)=0$. Suppose it holds for $t$. Then for $t-1$ we have from (46) and (47)

where the first term on the right-hand side of the third equality follows from Lemma 18 and the definition of $a(t;\tau)$ in (51), and the second term from the induction hypothesis. The last two equalities follow from (46). ∎

Suppose B3’ holds. Then for each $\tau$ with $0<\tau<m$ and each $t=\tau,\tau-1,\dots,0$,

We prove the lemma by induction on $(t,\tau)$.

Base case: For each $\tau$ with $0<\tau<m$, (52) holds for $t=\tau$, i.e., for $t$ such that $\tau-t=0$.

Induction hypothesis: For each $\tau$ with $0<\tau<m$, suppose (52) holds for $t\leq\tau$ such that $0\leq\tau-t\leq k-1$.

Induction: We will prove that, for each $\tau$ with $0<\tau<m$, (52) holds for $t\leq\tau$ such that $0\leq\tau-t\leq k$. For $t=\tau-k$ we have from Lemma 19

But each $w(t;t^{\prime}-1)$ in the summands satisfies $w(t;t^{\prime}-1)\geq\underline{w}(t;t^{\prime}-1)$ by the induction hypothesis. Hence, since $a(t^{\prime};\tau)>0$,

where the last inequality follows from (49) and (51).

Lemma 20 implies, for $j=0,\dots,m-1$, $\Delta S_{j}=\epsilon_{m}\,w(j;m-1)>0$. This completes the proof of Lemma 17. ∎

This completes the proof of Theorem 5 for the linear network. For a general tree network the proof is almost identical, except with more cumbersome notations, by focusing on a path from the root to a first link over which (17c) holds with strict inequality; see . ∎

VI-D Proof of Theorem 6: uniqueness of SOCP solution

Combining (53)–(55) implies that equalities are attained in both (54) and (55). Hence

VI-E Proof of Corollary 7: hollow feasible set

VI-F Proof of Theorem 8: angle difference

The proof follows that in . We first prove the case of two buses and then extend it to a tree network.

Consider two buses $j$ and $k$ connected by a line with admittance $y_{jk}=g_{jk}-\textbf{i}b_{jk}$ with $g_{jk}>0,b_{jk}>0$. Since $p_{j}=P_{jk}$ and $p_{k}=P_{kj}$ we will work with $P:=(P_{jk},P_{kj})$. Now

where $\theta_{jk}:=\theta_{j}-\theta_{k}$, or in vector form

where $\textbf{1}:=[1\ 1]^{T}$ and $A$ is the positive definite matrix:

Let $\pi_{jk}^{\text{min}}$ denote the minimum $P_{jk}(\theta_{jk})$ and $\pi_{kj}^{\text{min}}$ the minimum $P_{kj}(\theta_{jk})$ on the ellipse as shown in the figure. They are attained when $\theta_{jk}$ takes the values

respectively. This can be easily checked using (57) and

Under condition C1, for the two-bus network,

It is the intersection of a second-order cone with an affine set.

for some $c>0$, as opposed to nonzero $c\geq 0$ $(P_{jk}=\underline{p}_{j}$ corresponds to $c=(c_{1},0),c_{1}>0$). This is why we require in condition C1 that $C(p)$ is strictly increasing in each $p_{j}$. We will henceforth use this characterization of Pareto optimal points unless otherwise specified.

where $(\underline{\pi}_{jk},\underline{\pi}_{kj}):=(P_{jk}(\underline{\theta}_{jk}),P_{kj}(\underline{\theta}_{jk}))$ and $(\overline{\pi}_{jk},\overline{\pi}_{kj}):=(P_{jk}(\overline{\theta}_{jk}),P_{kj}(\overline{\theta}_{jk}))$. This implies that the problem (29) is indeed an SOCP for the two-bus case.

Case 2: tree network

because it implies that, under C1, every minimizer of OPF-socp (29) lies in its Pareto front and hence is feasible and optimal for OPF (28) (see also Remark 3). Hence SOCP relaxation is exact.

We are hence left to prove (62). Half of the equality follows from the following simple properties of Pareto front and convex hull.

For ease of reference we prove Lemma 22 below.

The next lemma says that the feasible set of OPF (28) is a subset of the feasible set of its SOCP relaxation (29).

Lemma 23 means that every optimal solution of OPF (28) is an optimal solution of its SOCP (29). For exactness of OPF-socp (29) we need the converse to hold as well. The remainder of the proof is to show this is indeed true, proving (62).

for some $c>0$. This minimization is equivalent to:

The Slater’s condition holds for OPF (28). By strong duality there exist Lagrange multipliers $\overline{\lambda}\geq 0$ and $\underline{\lambda}\geq 0$ such that $P$ is a minimizer of the Lagrangian:

This reduces the problem to the two-bus case:

Since $c>0$, any node $i$ with $\overline{c}_{i}\leq 0$ has $\underline{\lambda}_{i}>0$ and hence $p_{i}=\underline{p}_{i}$. Consider the biggest subtree $T$ that contains link $(j,k)$ in which every node $i$ has $\overline{c}_{i}\leq 0$ and $p_{i}=\underline{p}_{i}$. Call a node $l$ in the subtree $T$ a boundary node if it is a leaf or connected to another node $l^{\prime}$ outside $T$ where $\overline{c}_{l^{\prime}}>0$. Without loss of generality, take one of the boundary nodes as the root of the network graph and assume this is node 0. For each line $(l,i)$ in the graph, node $i$ is called the parent of node $l$ if $i$ lies in the unique path from $l$ to the root node 0.

VI-G Proof of Theorem 10: mesh networks with phase shifters

Step 1: solution of (31) always exists. Fix an $x$ and the corresponding $\beta:=\beta(x)$. Write $\phi=[\phi_{T}^{t}\ \ \phi_{\perp}^{t}]^{t}$ and set $\phi_{T}=0$. Then (31) becomes

Hence a vector $({\theta}_{*},{\phi}_{*},k_{*})$ with $\theta_{*}\in(-\pi,\pi]^{n}$ and ${\phi}_{*}\in T^{\perp}$ is a solution of (66) if and only if

where $\left[\hat{k}_{*}\right]_{\perp}:=[k_{*}]_{\perp}-B_{\perp}B_{T}^{-1}[k_{*}]_{T}$ is an integer vector. Clearly this can always be satisfied by choosing

where $\mathcal{P}(\cdot)$ projects each component of a vector on to $(-\pi,\pi]$.

Specifically (11a) is equivalent to (30a); (11c) with equalities and (65b) imply (30c). For (30b), we have from (11b),

Since $(\theta(x),\phi(x))$ solves (31), we have

This completes the proof of Theorem 10. ∎

References