Equivalent relaxations of optimal power flow

I Introduction

The optimal power flow (OPF) problem seeks an operating point of a power network that minimizes a certain cost, e.g., generation cost, transmission losses, etc. It is a fundamental problem as it underlies many applications such as unit commitment, economic dispatch, state estimation, volt/var control, and demand response. There has been a great deal of research since Carpentier’s first formulation in 1962 and an early solution by Dommel and Tinney ; recent surveys can be found in, e.g., . OPF is generally nonconvex and NP-hard. A large number of optimization algorithms and relaxations have been proposed, the most popular of which is linearization (called DC OPF) ; See also for a more accurate linear approximation. An important observation was made in that OPF can be formulated as a quadratically constrained quadratic program and therefore can be approximated by a semidefinite program (SDP). Instead of solving OPF directly, the authors in propose to solve its convex Lagrangian dual problem. Sufficient conditions have been studied by many authors under which an optimal solution for the non-convex problem can be derived from an optimal solution of its SDP relaxation; e.g., for radial networks and in for resistive networks. These papers all use the standard bus injection model where the Kirchhoff’s laws are expressed in terms of the complex nodal voltages in rectangular coordinates.

Branch flow models on the other hand formulate OPF in terms of branch power and current flows in addition to nodal voltages, e.g., . They have been mainly used for modeling radial distribution networks. A branch flow model has been proposed in to study OPF for both radial and mesh networks and a relaxation based on second-order cone program (SOCP) is developed. Sufficient conditions are obtained in under which the SOCP relaxation is exact for radial networks.

I-B Summary

Since the OPF problem in the bus injection model is a quadratically constrained quadratic program it is equivalent to a rank-constrained SDP . This formulation naturally leads to an SDP relaxation that removes the rank constraint and solves for a full positive semidefinite matrix. If the rank condition is satisfied at an optimal point, the relaxation is said to be exact and an optimal solution of OPF can be recovered through the spectral decomposition of the positive semidefinite matrix. Even though SDP is polynomial time solvable it is nonetheless impractical to compute for large power networks. Practical networks, however, are sparse. In this paper we develop two equivalent formulations of OPF using partial matrices that involve much fewer variables than the full SDP.

The key idea is to characterize classes of partial matrices that are easy to compute and, when the relaxations are exact, are completable to full positive semidefinite matrices of rank 1 from which a solution of OPF can be recovered through spectral decomposition. One of these equivalent problems leads to an SDP relaxation based on chordal extension of the network graph and the other leads to an SOCP relaxation . In this work, we prove equivalence relations among these problems and their relaxations. Our results imply that, for radial networks, all three relaxations are equivalent and we should always solve the SOCP relaxation. For mesh networks there is a tradeoff between computational effort and accuracy (in terms of exactness of relaxation) in deciding between solving SOCP relaxation or the other two relaxations. Between the chordal relaxation and the full SDP, if all the maximal cliques of a chordal extension of the network graph have been pre-computed offline then solving the chordal relaxation is always better because it has the same accuracy as the full SDP but typically involves far fewer variables and is faster to compute. This is explained in Section II. Chordal relaxation has been suggested in for solving OPF, and SOCP relaxation in the bus injection model has also been studied in . Here we provide a framework that unifies and contrasts these approaches.

In Section III we present the branch flow model of for OPF and the corresponding SOCP relaxation developed in . In Section IV we prove the equivalence of the branch flow model and the bus injection model by exhibiting a bijection between these two models and their relaxations. Indeed the relations among the various problems in this paper, both in the bus injection model and the branch flow model, are established through relations among their feasible sets.

It is important that we utilize both the bus injection and the branch flow models. Even though they are equivalent, some relaxations are much easier to formulate and some sufficient conditions for exact relaxation are much easier to prove in one model than the other. For instance the semidefinite relaxation of power flows has a much cleaner formulation in the bus injection model. The branch flow model especially for radial networks has a convenient recursive structure that not only allows a more efficient computation of power flows e.g. , but also plays a crucial role in proving the sufficient conditions for exact relaxation in . Since the variables in the branch flow model correspond directly to physical quantities such as branch power flows and injections it is sometimes more convenient in applications.

In Section V, we illustrate the relations among the various relaxations and OPF through simulations. First, we visualize the feasible sets of a 3-bus example in . Then we compare the running times and accuracies of these relaxations on IEEE benchmark systems . We conclude the paper in Section VI.

I-C Notations

II Bus injection model and conic relaxations

In this section we formulate OPF in the bus injection model and describe three equivalent problems. These problems lead naturally to semidefinite relaxation, chordal relaxation, and second-order cone relaxation of OPF. We prove equivalence relations among these problems and their exact relaxations.

Consider a power network modeled by a connected undirected graph $G(N,E)$ where each node in $N:=\{1,2,\ldots,n\}$ represents a bus and each edge in $E$ represents a line. For each edge $(i,j)\in E$ let $y_{ij}$ be its admittance . A bus $j\in N$ can have a generator, a load, both or neither. Typically the loads are specified and the generations are variables to be determined. Let $s_{j}$ be the net complex power injection (generation minus load) at bus $j\in N$. Also, let $V_{j}$ be the complex voltage at bus $j\in N$ and $|V_{j}|$ denote its magnitude. Bus 1 is the slack bus with a fixed magnitude $|V_{1}|$ (normalized to 1). The bus injection model is defined by the following power flow equations that describe the Kirchhoff’s law The current flowing from bus $j$ to bus $k$ is $(V_{j}-V_{k})y_{jk}$.:

The power injections at all buses satisfy

where $\underline{s}_{j}$ and $\overline{s}_{j}$ are known limits on the net injection at bus $k$. It is often assumed that the slack bus (node 1) has a generator and there is no limit of $s_{1}$; in this case $-\underline{s}_{j}=\overline{s}_{j}=\infty$. We can eliminate the variables $s_{k}$ from the OPF formulation by combining (1)–(2) into

Then OPF in the bus injection model can be formulated in terms of just the $n\times 1$ voltage vector $V$. All voltage magnitudes are constrained:

where $\underline{V}_{j}$ and $\overline{V}_{j}$ are known lower and upper voltage limits. Typically $|V_{1}|=1=\underline{V}_{1}=\overline{V}_{1}$. These constraints define the feasible set of the optimal power flow problem in the bus injection model:

Let the cost function be $c(V)$. Typical costs include the total cost of generating real power at all buses or line loss over the network. All these costs can be expressed as functions of $V$. Thus, we obtain the following optimization problem. Optimal power flow problem $OPF$:

The OPF formulation usually includes additional constraints such as thermal or stability limits on power or current flows on the lines, or security constraints; see surveys in . Our results generalize to OPF with some of these constraints, e.g., line limits . Our model can also include a shunt element at each bus. We omit these refinements for ease of presentation.

II-B SDP relaxation: 𝒫1\mathcal{P}_{1} and ℛ1\mathcal{R}_{1}

Note that (3) is linear in the variables $W_{jj}:=|V_{j}|^{2}$ for $j\in N$ and $W_{jk}:=V_{j}V_{k}^{H}$ for $(j,k)\in E$. This motivates the definition of a $G$-partial matrix. Define the index set $I_{G}$:

A ${G}$-partial matrix $W_{G}$ is a collection of complex numbers indexed by the set $I_{G}$, i.e., $[W_{G}]_{jk}$ is defined iff $j=k\in N$ or $(j,k)\in E$. This is illustrated in Figure 2. For graph $G_{1}$, we have $n=5$ nodes and $I_{G_{1}}=\{(1,1),(2,2),(3,3),(4,4),(5,5),(1,2),(2,1),(2,3),\linebreak(3,2),(3,4),(4,3),(1,4),(4,1),(4,5),(5,4)\}$ as shown in Figure 2(a) as a partially filled matrix. For graph $G_{2}$ in Figure 1(b), $I_{G_{2}}$ is represented in Figure 2(b). If $G$ is a complete graph, i.e., every pair of nodes share an edge, then $W_{G}$ is an $n\times n$ matrix.

The relations in (3)–(4) can be rewritten in terms of $W_{G}$ as:

We assume the cost function $c(V)$ in OPF depends on $V$ only through the $G$-partial matrix $W_{G}$. For instance, if the objective is to minimize the total real power loss in the network then

If the objective is to minimize a weighted sum of real power generation at various nodes then

where $p_{j}^{d}$ is the given real power demand at bus $j\in N$. Henceforth we refer to the cost function as $c(W_{G})$.

$\mathcal{R}_{1}$ is an SDP and can be solved in polynomial time using interior-point algorithms . Let $W^{*}$ be an optimal solution of $\mathcal{R}_{1}$. If $W^{*}$ is rank-1 then $W^{*}$ also solves $\mathcal{P}_{1}$ optimally. We say the relaxation $\mathcal{R}_{1}$ is exact with respect to $\mathcal{P}_{1}$ if there exists an optimal solution of $\mathcal{R}_{1}$ that satisfies the rank constraint in $\mathcal{P}_{1}$ and hence optimal for $\mathcal{P}_{1}$.

In this paper we define a relaxation to be exact as long as one of its optimal solutions satisfies the constraints of the original problem, even though a relaxation may have multiple optimal solutions with possibly different ranks. The exactness of $\mathcal{R}_{1}$ in general does not guarantee that we can compute efficiently a rank-1 optimal $W_{*}$ if non-rank-1 optimal solutions also exist. Many sufficient conditions for exact relaxation in the recent literature, however, do guarantee that every optimal solution of the relaxation is optimal for the original problem, e.g., or they lead to a polynomial time algorithm to construct an optimal solution of $\mathcal{P}_{1}$ from any optimal solution of the relaxation, e.g., .

II-C Chordal relaxation: 𝒫c​h\mathcal{P}_{ch} and ℛc​h\mathcal{R}_{ch}

To define the next relaxation we need to extend the definitions of Hermitian, psd, and rank-1 for matrices to partial matrices:

The complex conjugate transpose of a $G$-partial matrix $W_{G}$ is the $G$-partial matrix $(W_{G})^{H}$ that satisfies

We say $W_{G}$ is Hermitian if $W_{G}=(W_{G})^{H}$.

A matrix $M$ is psd if and only if all its principal submatrices (including $M$ itself) are psd. We extend the definition of psd to $G$-partial matrices using this property. Informally a $G$-partial matrix is said to be psd if, when viewed as a partially filled $n\times n$ matrix, all its fully-specified principal submatrices are psd. This notion can be formalized as follows. A clique is a complete subgraph of a given graph. A clique on $k$ nodes is referred to as a $k$-clique. For the graph $G_{1}$ in Figure 1(a), the cliques are the edges. For the graph $G_{2}$ in Figure 1(b), the cliques consist of the edges and the triangles $\{1,2,3\}$ and $\{1,3,4\}$. A $k$-clique $C$ in graph $G$ on nodes $\{n_{1},n_{2},\ldots,n_{k}\}$ fully specifies the $k\times k$ submatrix $W_{G}(C)$ For any graph $F$, a partial matrix $W_{F}$, and a subgraph $H$ of $F$, the partial matrix $W_{F}(H)$ is a submatrix of $W_{F}$ corresponding to the $I_{H}$ entries of $W_{F}$. If subgraph $H$ is a $k$ clique, then $W_{F}(H)$ is a $k\times k$ matrix.:

We say a $G$-partial matrix $W_{G}$ is positive semidefinite (psd), written as $W_{G}\succeq 0$, if and only if $W_{G}(C)\succeq 0$ for all cliques $C$ in graph $G$.

A matrix $M$ has rank one if $M$ has exactly one linearly independent row (or column). We say a $G$-partial matrix $W_{G}$ has rank one, written as $\rank W_{G}=1$, if and only if $\rank W_{G}(C)=1\text{ for all cliques }C\text{ in }G.$

If $G$ is a complete graph then $W_{G}$ specifies an $n\times n$ matrix and the definitions of psd and rank-1 for the $G$-partial matrix $W_{G}$ coincide with the regular definitions.

A cycle on $k$ nodes in graph $G$ is a $k$-tuple $(n_{1},n_{2},\ldots,n_{k})$ such that $(n_{1},n_{2})$, $(n_{2},n_{3})$, $\ldots$, $(n_{k},n_{1})$ are edges in $G$. A cycle $(n_{1},n_{2},\ldots,n_{k})$ in $G$ is minimal if no strict subset of $\{n_{1},n_{2},\ldots,n_{k}\}$ defines a cycle in $G$. In graph $G_{1}$ in Figure 1(a) the 4-tuple $(1,2,3,4)$ defines a minimal cycle. In graph $G_{2}$ in Figure 1(b) however the same 4-tuple is a cycle but not minimal. The minimal cycles in $G_{2}$ are $(1,2,3)$ and $(1,3,4)$. A graph is said to be chordal if all its minimal cycles have at most 3 nodes. In Figure 2, $G_{2}$ is a chordal graph while $G_{1}$ is not. A chordal extension of a graph $G$ on $n$ nodes is a chordal graph $G_{ch}$ on the same $n$ nodes that contains $G$ as a subgraph. Note that all graphs have a chordal extension; the complete graph on the same set of vertices is a trivial chordal extension of a graph. In Figure 2, $G_{2}$ is a chordal extension of $G_{1}$.

Let $G_{ch}$ be any chordal extension of $G$. Define the following optimization problem over a Hermitian $G_{ch}$-partial matrix $W_{ch}:=W_{G_{ch}}$, where the constraints (7a)-(7b) are imposed only on the index set $I_{G}\subseteq I_{G_{ch}}$, i.e., in terms of the $G$-partial submatrix $W_{ch}(G)$ of the $G_{ch}$-partial matrix $W_{ch}$. Problem $\mathcal{P}_{ch}$:

Let $\mathcal{R}_{ch}$ be the rank-relaxation of $P_{ch}$. Problem $\mathcal{R}_{ch}$:

Let $W_{ch}^{*}$ be an optimal solution of $\mathcal{R}_{ch}$. If $W_{ch}^{*}$ is rank-1 then $W_{ch}^{*}$ also solves $\mathcal{P}_{ch}$ optimally. Again, we say $\mathcal{R}_{ch}$ is exact with respect to $\mathcal{P}_{ch}$ if there exists an optimal solution $W_{ch}^{*}$ of $\mathcal{R}_{ch}$ that has rank 1 and hence optimal for $\mathcal{P}_{ch}$; see Remark 2 for more details.

To illustrate, consider graph $G_{1}$ in Figure 1(a) and its chordal extension $G_{2}$ in Figure 1(b). The cliques in $G_{2}$ are $\{1,2\}$, $\{2,3\}$, $\{3,4\}$, $\{4,1\}$, $\{1,3\}$, $\{1,2,3\}$, $\{1,3,4\}$ and $\{4,5\}$. Thus the constraint $W_{ch}\succeq 0$ in $\mathcal{R}_{ch}$ imposes positive semidefiniteness on $W_{ch}(C)$ for each clique $C$ in the above list. Indeed imposing $W_{ch}(C)\succeq 0$ for maximal cliques $C$ of $G$ is sufficient, where a maximal clique of a graph is a clique that is not a subgraph of another clique in the same graph. This is because $W_{ch}(C)\succeq 0$ for a maximal clique $C$ implies $W_{ch}(C^{\prime})\succeq 0$ for any clique $C^{\prime}$ that is a subgraph of $C$. The maximal cliques in graph $G_{2}$ are $\{1,2,3\}$, $\{1,3,4\}$ and $\{4,5\}$ and thus $W_{ch}\succeq 0$ is equivalent to $W_{ch}(C)\succeq 0$ for all maximal cliques $C$ listed above. Even though listing all maximal cliques of a general graph is NP-complete it can be done efficiently for a chordal graph. This is because a graph is chordal if and only if it has a perfect elimination ordering and computing this ordering takes linear time in the number of nodes and edges . Given a perfect elimination ordering all maximal cliques $C$ can be enumerated and $W_{ch}(C)$ constructed efficiently . Moreover the computation depends only on network topology, not on operational data, and therefore can be done offline. For more details on chordal extension see . A special case of chordal relaxation is studied in where the underlying chordal extension extends every basis cycle of the network graph into a clique.

II-D SOCP relaxation: 𝒫2\mathcal{P}_{2} and ℛ2\mathcal{R}_{2}

We say a $G$-partial matrix $W_{G}$ satisfies the cycle condition if, over every cycle $(n_{1},\ldots,n_{k})$ in $G$, we have

Consider any spanning tree of $G$. A “basis cycle” in $G$ is a cycle that has all but one of its edges common with the spanning tree. If (8) holds over all basis cycles in $G$ with respect to a spanning tree then (8) holds over all cycles of $G$ .

For any edge $e=(i,j)$ in $G$, $W_{G}(e)$ is the $2\times 2$ principal submatrix of $W_{G}$ defined by the 2-clique $e$. Define the following optimization problem over Hermitian $G$-partial matrices $W_{G}$. Problem $\mathcal{P}_{2}$:

Both the cycle condition (8) and the rank-1 condition are nonconvex constraints. Relaxing them, we get the following second-order cone program. Problem $\mathcal{R}_{2}$:

For $e=(i,j)$ and Hermitian $W_{G}$ we have

The right-hand side of (9) is a second-order cone constraint and hence $\mathcal{R}_{2}$ can be solved as an SOCP. If an optimal solution $W_{G}^{*}$ of $\mathcal{R}_{2}$ is rank-1 and also satisfies the cycle condition then $W_{G}^{*}$ solves $\mathcal{P}_{2}$ optimally and we say that relaxation $\mathcal{R}_{2}$ is exact with respect to $\mathcal{P}_{2}$.

II-E Equivalent and exact relaxations

So far, we have defined the problems $\mathcal{P}_{1}$, $\mathcal{P}_{ch}$ and $\mathcal{P}_{2}$ and obtained their convex relaxations $\mathcal{R}_{1}$, $\mathcal{R}_{ch}$ and $\mathcal{R}_{2}$ respectively. We now characterize the relations among these problems.

Let $p^{*}$ be the optimal cost of OPF. Let $p^{*}_{1}$, $p^{*}_{ch}$, $p^{*}_{2}$ be the optimal cost of $\mathcal{P}_{1}$, $\mathcal{P}_{ch}$, $\mathcal{P}_{2}$ respectively and let $r^{*}_{1}$, $r^{*}_{ch}$, $r^{*}_{2}$ be the optimal cost of their relaxations $\mathcal{R}_{1}$, $\mathcal{R}_{ch}$, $\mathcal{R}_{2}$ respectively.

Let $G_{ch}$ denote any chordal extension of $G$. Then

$r^{*}_{1}=r^{*}_{ch}\geq r^{*}_{2}$. If $G$ is acyclic, then $r^{*}_{1}=r^{*}_{ch}=r^{*}_{2}$.

$\mathcal{R}_{1}$ is exact iff $\mathcal{R}_{ch}$ is exact. $\mathcal{R}_{1}$ and $\mathcal{R}_{ch}$ are exact if $\mathcal{R}_{2}$ is exact. If $G$ is acyclic, then $\mathcal{R}_{2}$ is exact iff $\mathcal{R}_{1}$ is exact.

We make three remarks. First, part (a) says that the optimal cost of $\mathcal{P}_{1}$, $\mathcal{P}_{ch}$ and $\mathcal{P}_{2}$ are the same as that of OPF. Our proof claims a stronger result: the underlying $G$-partial matrices in these problems are the same. Informally the feasible sets of these problems, and hence the problems themselves, are equivalent and one can construct a solution of OPF from a solution of any of these problems.

Third, part (c) says that solving $\mathcal{R}_{1}$ is the same as solving $\mathcal{R}_{ch}$ and, in the case where $G$ is acyclic (a tree, since $G$ is assumed to be connected), is the same as solving $\mathcal{R}_{2}$. $\mathcal{R}_{1}$ and $\mathcal{R}_{ch}$ are SDPs while $\mathcal{R}_{2}$ is an SOCP. Though they can all be solved in polynomial time , SOCP in general requires a much smaller computational effort than SDP. Part (b) suggests that, when $G$ is a tree, we should always solve $\mathcal{R}_{2}$. When $G$ has cycles then there is a tradeoff between computational effort and exactness in deciding between solving $\mathcal{R}_{2}$ or $\mathcal{R}_{ch}$/$\mathcal{R}_{1}$. As our simulation results in Section V confirm, if all maximal cliques of a chordal extension are available then solving $\mathcal{R}_{ch}$ is always better than solving $\mathcal{R}_{1}$ as they have the same accuracy (in terms of exactness) but $\mathcal{R}_{ch}$ is usually much faster to solve for large sparse networks $G$. Indeed $G$ is a subgraph of any chordal extension $G_{ch}$ of $G$ which is, in turn, a subgraph of the complete graph on $n$ nodes (denoted as $C_{n}$), and hence $I_{G}\subseteq I_{G_{ch}}\subseteq I_{C_{n}}$. Therefore, typically, the number of variables is the smallest in $\mathcal{R}_{2}$ $(|I_{G}|)$, the largest in $\mathcal{R}_{1}$ $(|I_{C_{n}}|)$, with $\mathcal{R}_{ch}$ in between. However the actual number of variables in $\mathcal{R}_{ch}$ is generally greater than $|I_{G_{ch}}|$, depending on the choice of the chordal extension $G_{ch}$. Choosing a good $G_{ch}$ is nontrivial; see for more details. This choice however does not affect the optimal value $r_{ch}^{*}$.

If $G$ is acyclic then $p_{*}=p_{1}^{*}=p_{ch}^{*}=p_{2}^{*}\geq r_{1}^{*}=r_{ch}^{*}=r_{2}^{*}$.

If $G$ has cycles then $p_{*}=p_{1}^{*}=p_{ch}^{*}=p_{2}^{*}\geq r_{1}^{*}=r_{ch}^{*}\geq r_{2}^{*}$.

Theorem 1 and Corollary 2 do not provide conditions that guarantee any of the relaxations $\mathcal{R}_{1},\mathcal{R}_{ch},\mathcal{R}_{2}$ are exact. See for such sufficient conditions in the bus injection model. Corollary 2 implies that if $\mathcal{R}_{2}$ is exact, so are $\mathcal{R}_{ch}$ and $\mathcal{R}_{1}$. Moreover Lemma 4 below relates the feasible sets of $\mathcal{R}_{1},\mathcal{R}_{ch},\mathcal{R}_{2}$, not just their optimal values. It implies that $\mathcal{R}_{1},\mathcal{R}_{ch},\mathcal{R}_{2}$ are equivalent problems if $G$ has no cycles.

II-F Proof of Theorem 1

To define the set of $G$-partial matrices associated with $\mathcal{P}_{1},\mathcal{P}_{ch},\mathcal{P}_{2}$ suppose $F$ is a graph on $n$ nodes such that $G$ is a subgraph of $F$, i.e., $I_{G}\subseteq I_{F}$. An $F$-partial matrix $W_{F}$ is called an $F$-completion of the $G$-partial matrix $W_{G}$ if

i.e., $W_{F}$ agrees with $W_{G}$ on the index set $I_{G}$. If $F$ is $C_{n}$, the complete graph on $n$ nodes, then $W_{F}$ is an $n\times n$ matrix. $W_{F}$ is a Hermitian $F$-completion if $W_{F}=W_{F}^{H}$. $W_{F}$ is a psd $F$-completion if in addition $W_{F}\succeq 0$. $W_{F}$ is a rank-1 $F$-completion if $\rank W_{F}=1$. It can be checked that if $W_{G}\not\succeq 0$ then $W_{G}$ does not have a psd $F$-completion. If $\rank W_{G}\neq 1$ then it does not have a rank-1 $F$-completion. Define

Similarly define the corresponding sets for $\mathcal{P}_{ch}$ and $\mathcal{R}_{ch}$:

The sketch of the proof is as follows. We prove Theorem 1(a) in Lemma 3 and then Theorem 1(b) in Lemma 4 below. Theorem 1(c) then follows from these two lemmas.

Now, fix a chordal extension $G_{ch}$ of $G$. We now prove:

Let $T_{r}$ be true for all $3\leq r\leq k$ and consider a cycle $(n_{1},n_{2},\ldots,n_{k+1})$ of length $k+1$ in $G_{ch}$. Since $G_{ch}$ is chordal, this cycle must have a chord, i.e., an edge between two nodes, say, $n_{1}$ and $n_{k^{\prime}}$, that are not adjacent on the cycle. Then $(n_{1},n_{2},\ldots,n_{k^{\prime}})$ and $(n_{1},n_{k^{\prime}},n_{k^{\prime}+1},\ldots,n_{k})$ are two cycles in $G_{ch}$. By hypothesis, $T_{k^{\prime}}$ and $T_{k-k^{\prime}+2}$ are true and hence

Note that the above definition is well-defined: if there is another sequence of edges from node 1 to node $j$, the above relation still defines $\theta_{j}$ uniquely because $W_{G}$ satisfies the cycle condition. Let

To prove Theorem 1(c) note that parts (a) and (b) imply

Hence $\mathcal{R}_{1}$ is exact $(p_{1}^{*}=r_{1}^{*})$ iff $\mathcal{R}_{ch}$ is exact $(p_{ch}^{*}=r_{ch}^{*}$). If $\mathcal{R}_{2}$ is exact, i.e., $p_{2}^{*}=r_{2}^{*}$, then both inequalities above become equalities, proving Theorem 1(c). This completes the proof of Theorem 1.

III Branch flow model and SOCP relaxation

$z_{ij}$: The complex impedance on the line. Thus $z_{ij}=1/y_{ij}$.

$I_{ij}$: The complex current from bus $i$ to bus $j$.

$S_{ij}$: The sending-end complex power from buses $i$ to $j$.

Recall that for each node $i\in N$, $V_{i}$ is the complex voltage at bus $i$ and $s_{i}$ is the net complex power injection (generation minus load) at bus $i$.

The branch flow model of is defined by the following set of power flow equations:

where (11a) imposes power balance at each bus and (11b) defines branch power and describes Ohm’s law. The power injections at all buses satisfy

where $\underline{s}_{j}$ and $\overline{s}_{j}$ are known limits on the net generation at bus $j$. It is often assumed that the slack bus (node 1) has a generator and there is no limit of $s_{1}$; in this case $-\underline{s}_{j}=\overline{s}_{j}=\infty$. As in the bus injection model, we can eliminate the variables $s_{j}$ by combining (11a) and (12) into:

All voltage magnitudes are constrained as follows:

Similarly, if the objective is to minimize the weighted sum of real power generation in the network, then

where $p_{j}^{d}$ is the given real power demand at bus $j\in N$.

and the convex superset that is a second-order cone:

The first row of $C$ corresponds to the slack bus. Define the $m\times(n-1)$ reduced incidence matrix $B$ obtained from $C$ by removing the first row and taking the transpose. Consider the set of $x$ such that

A solution $\theta$, if exists, is unique in $[-\pi,\pi)^{n}$. Moreover the necessary and sufficient condition for the existence of a solution to (21) has a familiar interpretation: the implied voltage angle differences $\beta(x)$ sum to zero (mod $2\pi$) around any cycle [37, Theorem 2].

IV Equivalence of bus injection and branch flow models

Second, it is important that we utilize both models because some relaxations are much easier to formulate and some sufficient conditions for exact relaxation are much easier to prove in one model than the other. For instance the semidefinite relaxation of power flows has a much cleaner formulation in the bus injection model. The branch flow model especially for radial networks has a convenient recursive structure that not only allows a more efficient computation of power flows e.g. , but also plays a crucial role in proving the sufficient conditions for exact relaxation in . Since the variables in the branch flow model correspond directly to physical quantities such as branch power flows and injections it is sometimes more convenient in applications.

$g$ is injective, i.e., $g(x)\neq g(x^{\prime})$ if $x\neq x^{\prime}$.

$g$ is surjective and hence its inverse exists; moreover $g^{-1}$ defined in (28)–(29) is indeed $g$’s inverse.

where the last equality follows from (17). Substituting this and (28)–(29) into (7a) we get, for each $j\in N$:

where the last equality follows from (18). Substituting (17) into (33) yeilds $[W_{G}]_{ii}[W_{G}]_{jj}=\left|[W_{G}]_{ij}\right|^{2}$. This together with $[W_{G}]_{ii}\geq 0$ (from (28)) means $W_{G}(i,j)\succeq 0$ and $\rank{W_{G}}(i,j)=1$.

where the last equality follows from (17). Hence $W_{G}$ satisfies (27) and $g(W_{G})=x$. ∎

V Numerics

We now illustrate the theory developed so far through simulations. First we visualize in Section V-A the feasible sets of OPF and their relaxations for a simple 3-bus example from . Next we report in Section V-B the running times and accuracies (in terms of exactness) of different relaxations on IEEE benchmark systems.

Consider the 3-bus example in Figure 4 taken from (but we do not impose line limits) with line parameters in per units in Table I. Note that this network has shunt elements. For this example, $\mathcal{P}_{1}$ is the same problem as $\mathcal{P}_{ch}$ and $\mathcal{R}_{1}$ is the same problem as $\mathcal{R}_{ch}$. Hence we will focus on the feasible sets of $\mathcal{P}_{1}$ (which is the same as that of $\mathcal{P}_{2}$) and the feasible sets of $\mathcal{R}_{1}$, $\mathcal{R}_{2}$. Each problem has a Hermitian $3\times 3$ matrix $W$ as its variable. Recall that $s_{j}=p_{j}+\textbf{i}q_{j}$ is the complex power injection at node $j\in N$ and thus for each Hermitian matrix $W$, we have the following map:

To visualize the various feasible sets, define the following set in 2 dimensions:

For the projections on the $q_{1}-q_{2}$ plane define the set

V-B IEEE benchmark systems

For IEEE benchmark systems , we solve $\mathcal{R}_{1}$, $\mathcal{R}_{2}$ and $\mathcal{R}_{ch}$ in MATLAB using CVX with the solver SeDuMi after some minor modifications to the resistances on some lines A resistance of $10^{-5}$ p.u. is added to lines with zero resistance.. The objective values and running times are presented in Table II. The problems $\mathcal{R}_{1}$ and $\mathcal{R}_{ch}$ have the same optimal objective value, i.e., $r_{1}^{*}=r_{ch}^{*}$, as predicted by Theorem 1. We also report the ratios of the first two eigenvalues of the optimal $W^{*}$ in $\mathcal{R}_{1}$ For the 2383-bus system, we only run $\mathcal{R}_{ch}$. For the optimal $G_{ch}$-partial matrix $W_{ch}^{*}$, we report the maximum and the median of the non-zero ratios of the first and second eigenvalues of $W_{ch}^{*}(C)$ over all cliques $C$ in $G_{ch}$.; for most cases, it is small indicating that the relaxation is exact. The optimal objective value of $\mathcal{R}_{2}$ is lower ($r_{2}^{*}<r_{1}^{*}$), indicating that the optimum of the SOCP relaxation that is computed is not feasible for $\mathcal{P}_{1}$. As Table II shows, $\mathcal{R}_{ch}$ is much faster than $\mathcal{R}_{1}$ for large networks. The chordal extensions of the graphs are computed a priori for each case . $\mathcal{R}_{2}$ is faster than both $\mathcal{R}_{1}$ and $\mathcal{R}_{ch}$, but yields an infeasible solution for most IEEE benchmark systems considered.

VI Conclusion

Acknowledgment

We are thankful to Prof. K. Mani Chandy and Lingwen Gan at Caltech for helpful discussions. We also acknowledge the support of NSF through NetSE grant CNS 0911041, DoE’s ARPA-E through grant DE-AR0000226, the National Science Council of Taiwan (R. O. C.) through grant NSC 103-3113-P-008-001, Southern California Edison, and the Resnick Institute at Caltech.

References