of 12
1
Equivalent relaxations of optimal power flow
Subhonmesh Bose
1
, Steven H. Low
2
,
1
, Thanchanok Teeraratkul
1
, Babak Hassibi
1
1
Electrical Engineering,
2
Computing and Mathematical Sciences
California Institute of Technology
Abstract
—Several convex relaxations of the optimal power flow (OPF)
problem have recently been developed using both bus injection models
and branch flow models. In this paper, we prove relations among three
convex relaxations: a semidefinite relaxation that computes a full matrix, a
chordal relaxation based on a chordal extension of the network graph, and
a second-order cone relaxation that computes the smallest partial matrix.
We prove a bijection between the feasible sets of the OPF in the bus
injection model and the branch flow model, establishing the equivalence
of these two models and their second-order cone relaxations. Our results
imply that, for radial networks, all these relaxations are equivalent and one
should always solve the second-order cone relaxation. For mesh networks,
the semidefinite relaxation is tighter than the second-order cone relaxation
but requires a heavier computational effort, and the chordal relaxation
strikes a good balance. Simulations are used to illustrate these results.
I. I
NTRODUCTION
A. Background
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 [2]
and an early solution by Dommel and Tinney [3]; recent surveys can
be found in, e.g., [4]–[16]. 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)
[17]–[20]; See also [21] for a more accurate linear approximation. An
important observation was made in [22] 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 [23] 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., [24]–[26] for radial
networks and in [23], [27], [28] 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.,
[29]–[36]. They have been mainly used for modeling radial distribution
networks. A branch flow model has been proposed in [37] 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 [34], [38], [39] under which the SOCP relaxation is
exact for radial networks.
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 [22], [23]. This formulation naturally leads to an SDP relax-
ation that removes the rank constraint and solves for a full positive
A preliminary and abridged version has appeared in [1].
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 [40], [41] and the other leads to an
SOCP relaxation [42], [43]. 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 [36], [44] for
solving OPF, and SOCP relaxation in the bus injection model has also
been studied in [1], [26], [28], [45]. Here we provide a framework that
unifies and contrasts these approaches.
In Section III we present the branch flow model of [37] for OPF and
the corresponding SOCP relaxation developed in [34], [37]. 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. [46]–
[48], but also plays a crucial role in proving the sufficient conditions
for exact relaxation in [49], [50]. 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 [51]. Then we compare the running times and
accuracies of these relaxations on IEEE benchmark systems [52], [53].
We conclude the paper in Section VI.
arXiv:1401.1876v1 [cs.SY] 9 Jan 2014
2
C. Notations
Let
R
and
C
denote the sets of real and complex numbers respec-
tively. For vectors
x,y
R
n
,
x
y
denotes inequality componentwise;
if
x,y
C
n
,
x
y
means Re
x
Re
y
and Im
x
Im
y
. For
a matrix
A
, let
A
H
be its hermitian transpose.
A
is called
positive
semidefinite (psd)
, denoted
A

0
, if it is hermitian and
x
H
Ax
0
for all
x
C
n
. Let
i
:=
1
and for any set
B
, let
|
B
|
denote its
cardinality.
II. B
US 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 re-
laxation of OPF. We prove equivalence relations among these problems
and their exact relaxations.
A. OPF formulation
Consider a power network modeled by a connected undirected graph
G
(
N,E
)
where each node in
N
:=
{
1
,
2
,...,n
}
represents a bus and
each edge in
E
represents a line. For each edge
(
i,j
)
E
let
y
ij
be
its admittance [54]. A bus
j
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
N
. Also, let
V
j
be the complex
voltage at bus
j
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
1
:
s
j
=
k
:(
j,k
)
E
V
j
(
V
H
j
V
H
k
)
y
H
jk
for
j
N.
(1)
The power injections at all buses satisfy
s
j
s
j
s
j
for
j
N,
(2)
where
s
j
and
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
s
j
=
s
j
=
. We can eliminate the
variables
s
k
from the OPF formulation by combining (1)–(2) into
s
j
k
:(
j,k
)
E
V
j
(
V
H
j
V
H
k
)
y
H
jk
s
j
for
j
N.
(3)
Then OPF in the bus injection model can be formulated in terms of just
the
n
×
1
voltage vector
V
. All voltage magnitudes are constrained:
V
j
≤|
V
j
|≤
V
j
for
j
N,
(4)
where
V
j
and
V
j
are known lower and upper voltage limits. Typically
|
V
1
|
= 1 =
V
1
=
V
1
. These constraints define the feasible set of the
optimal power flow problem in the bus injection model:
V
:=
{
V
C
n
|
V
satisfies (3)
(4)
}
.
(5)
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
:
minimize
V
c
(
V
)
subject to
V
V
.
Since (3) is quadratic,
V
is generally a nonconvex set. Thus OPF is
nonconvex and NP-hard to solve.
1
The current flowing from bus
j
to bus
k
is
(
V
j
V
k
)
y
jk
.
Remark 1.
The OPF formulation usually includes additional con-
straints such as thermal or stability limits on power or current flows
on the lines, or security constraints; see surveys in [4]–[8], [11]–[15].
Our results generalize to OPF with some of these constraints, e.g., line
limits [37], [45]. Our model can also include a shunt element at each
bus. We omit these refinements for ease of presentation.
B. SDP relaxation:
P
1
and
R
1
Note that (3) is linear in the variables
W
jj
:=
|
V
j
|
2
for
j
N
and
W
jk
:=
V
j
V
H
k
for
(
j,k
)
E
. This motivates the definition of a
G
-partial matrix. Define the index set
I
G
:
I
G
:=
{
(
j,j
)
|
j
N
}
{
(
j,k
)
|
(
j,k
)
E
}
.
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
N
or
(
j,k
)
E
.
This is illustrated in Figure 1. 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)
,
(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
×
n
matrix.
The relations in (3)–(4) can be rewritten in terms of
W
G
as:
s
j
k
:(
j,k
)
E
([
W
G
]
jj
[
W
G
]
jk
)
y
H
jk
s
j
for
j
N,
(7a)
V
2
j
[
W
G
]
jj
V
2
j
for
j
N.
(7b)
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
c
(
V
) =
j
N
Re
s
j
=
j
N
k
:(
j,k
)
E
Re
([
W
G
]
jj
[
W
G
]
jk
)
y
H
jk
.
If the objective is to minimize a weighted sum of real power generation
at various nodes then
c
(
V
) =
j
N
c
j
(
Re
s
j
p
d
j
)
=
j
N
c
j
k
:(
j,k
)
E
Re
([
W
G
]
jj
[
W
G
]
jk
)
y
H
jk
p
D
j
,
where
p
d
j
is the given real power demand at bus
j
N
. Henceforth
we refer to the cost function as
c
(
W
G
)
.
Consider an
n
×
1
voltage vector
V
. Then
W
=
V V
H
is an
n
×
n
psd
matrix of rank 1. Define the
G
-partial matrix
W
(
G
)
as the collection
of
I
G
entries of
W
. To describe the constraints
V
V
, we use the
equivalent constraints in terms of
W
(
G
)
in (7a)-(7b). Formally, OPF
is equivalent to the following problem with
n
×
n
Hermitian matrix
W
:
Problem
P
1
:
minimize
W
c
(
W
(
G
))
subject to
W
(
G
)
satisfies (7a)
(7b)
,
W

0
,
rank
W
= 1
.
Given an
V
V
,
W
=
V V
H
is feasible for
P
1
; conversely given a
feasible
W
it has a unique spectral decomposition [55]
W
=
V V
H
such that
V
V
. Hence there is a one-one correspondence between
the feasible sets of OPF and
P
1
, i.e., OPF is equivalent to
P
1
. Problem
P
1
is a rank-constrained SDP and NP-hard to solve. The nonconvex
3
(a) Graph
G
1
(b) Graph
G
2
Fig. 1: Simple graphs to illustrate
G
-partial matrices.
(a)
G
1
-partial matrix
(b)
G
2
-partial matrix
Fig. 2: Index sets
I
G
1
and
I
G
2
illustrated as entries in a matrix. Entry
(
j,k
)
is marked with a tick if
(
j,k
)
is in the corresponding index set;
otherwise it is marked with a cross.
rank constraint is relaxed to obtain the following SDP.
Problem
R
1
:
minimize
W
c
(
W
(
G
))
subject to
W
(
G
)
satisfies (7a)
(7b)
, W

0
.
R
1
is an SDP [43], [56] and can be solved in polynomial time using
interior-point algorithms [57], [58]. Let
W
be an optimal solution
of
R
1
. If
W
is rank-1 then
W
also solves
P
1
optimally. We say
the relaxation
R
1
is exact with respect to
P
1
if there exists an optimal
solution of
R
1
that satisfies the rank constraint in
P
1
and hence optimal
for
P
1
.
Remark 2.
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
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., [28], [59]–[61] or they lead to a polynomial time algorithm to
construct an optimal solution of
P
1
from
any
optimal solution of the
relaxation, e.g., [45], [62].
C. Chordal relaxation:
P
ch
and
R
ch
To define the next relaxation we need to extend the definitions of
Hermitian, psd, and rank-1 for matrices to partial matrices:
1) The complex conjugate transpose of a
G
-partial matrix
W
G
is the
G
-partial matrix
(
W
G
)
H
that satisfies
[(
W
G
)
H
]
jk
= [
W
G
]
H
kj
for all
(
j,k
)
I
G
.
We say
W
G
is
Hermitian
if
W
G
= (
W
G
)
H
.
2) 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
×
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
,...,n
k
}
fully specifies the
k
×
k
submatrix
W
G
(
C
)
2
:
W
G
(
C
) =
[
W
G
]
n
1
n
1
[
W
G
]
n
1
n
2
···
[
W
G
]
n
1
n
k
[
W
G
]
n
2
n
1
[
W
G
]
n
2
n
2
···
[
W
G
]
n
2
n
k
.
.
.
.
.
.
.
.
.
.
.
.
[
W
G
]
n
k
n
1
[
W
G
]
n
k
n
2
···
[
W
G
]
n
k
n
k
.
We say a
G
-partial matrix
W
G
is
positive semidefinite (psd)
,
written as
W
G

0
, if and only if
W
G
(
C
)

0
for all cliques
C
in graph
G
.
3) A matrix
M
has rank one if
M
has exactly one linearly inde-
pendent 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
for all cliques
C
in
G.
If
G
is a complete graph then
W
G
specifies an
n
×
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
,...,n
k
)
such that
(
n
1
,n
2
)
,
(
n
2
,n
3
)
,
...
,
(
n
k
,n
1
)
are edges in
G
. A cycle
(
n
1
,n
2
,...,n
k
)
in
G
is minimal if no strict subset of
{
n
1
,n
2
,...,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 1,
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
1,
G
2
is a chordal extension of
G
1
.
2
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
×
k
matrix.
4
Let
G
ch
be any chordal extension of
G
. Define the following opti-
mization 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
I
G
ch
, i.e., in terms of the
G
-partial submatrix
W
ch
(
G
)
of the
G
ch
-partial matrix
W
ch
.
Problem
P
ch
:
minimize
W
ch
c
(
W
ch
(
G
))
subject to
W
ch
(
G
)
satisfies (7a)
(7b)
,
W
ch

0
,
rank
W
ch
= 1
.
Let
R
ch
be the rank-relaxation of
P
ch
.
Problem
R
ch
:
minimize
W
ch
c
(
W
ch
(
G
))
subject to
W
ch
(
G
)
satisfies (7a)
(7b)
, W
ch

0
.
Let
W
ch
be an optimal solution of
R
ch
. If
W
ch
is rank-1 then
W
ch
also solves
P
ch
optimally. Again, we say
R
ch
is exact with respect to
P
ch
if there exists an optimal solution
W
ch
of
R
ch
that has rank 1
and hence optimal for
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 con-
straint
W
ch

0
in
R
ch
imposes positive semidefiniteness on
W
ch
(
C
)
for each clique
C
in the above list. Indeed imposing
W
ch
(
C
)

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
)

0
for a maximal clique
C
implies
W
ch
(
C
)

0
for any clique
C
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

0
is equivalent to
W
ch
(
C
)

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
[63] and computing this ordering takes linear time in the number of
nodes and edges [64]. Given a perfect elimination ordering all maximal
cliques
C
can be enumerated and
W
ch
(
C
)
constructed efficiently [40].
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 [40]. A special case of chordal relaxation is
studied in [62] where the underlying chordal extension extends every
basis cycle of the network graph into a clique.
D. SOCP relaxation:
P
2
and
R
2
We say a
G
-partial matrix
W
G
satisfies the
cycle condition
if, over
every
cycle
(
n
1
,...,n
k
)
in
G
, we have
[
W
G
]
n
1
n
2
+
[
W
G
]
n
2
n
3
+
...
+
[
W
G
]
n
k
n
1
= 0 mod 2
π.
(8)
Remark 3.
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
[65].
For any edge
e
= (
i,j
)
in
G
,
W
G
(
e
)
is the
2
×
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
P
2
:
minimize
W
G
c
(
W
G
)
subject to
W
G
satisfies (7a)
(7b) and (8)
,
W
G
(
e
)

0
,
rank
W
G
(
e
) = 1
for all
e
E.
Both the cycle condition (8) and the rank-1 condition are nonconvex
constraints. Relaxing them, we get the following second-order cone
program.
Problem
R
2
:
minimize
W
G
c
(
W
G
)
subject to
W
G
satisfies (7a)
(7b)
,
W
G
(
e
)

0
for all
e
E.
For
e
= (
i,j
)
and Hermitian
W
G
we have
W
G
(
e
)

0
[
W
G
]
ii
[
W
G
]
jj
≥|
[
W
G
]
ij
|
2
.
(9)
The right-hand side of (9) is a second-order cone constraint [43] and
hence
R
2
can be solved as an SOCP. If an optimal solution
W
G
of
R
2
is rank-1 and also satisfies the cycle condition then
W
G
solves
P
2
optimally and we say that relaxation
R
2
is exact with respect to
P
2
.
E. Equivalent and exact relaxations
So far, we have defined the problems
P
1
,
P
ch
and
P
2
and obtained
their convex relaxations
R
1
,
R
ch
and
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
P
1
,
P
ch
,
P
2
respectively and let
r
1
,
r
ch
,
r
2
be the optimal
cost of their relaxations
R
1
,
R
ch
,
R
2
respectively.
Theorem 1.
Let
G
ch
denote any chordal extension of
G
. Then
(a)
p
1
=
p
ch
=
p
2
=
p
.
(b)
r
1
=
r
ch
r
2
. If
G
is acyclic, then
r
1
=
r
ch
=
r
2
.
(c)
R
1
is exact iff
R
ch
is exact.
R
1
and
R
ch
are exact if
R
2
is exact.
If
G
is acyclic, then
R
2
is exact iff
R
1
is exact.
We make three remarks. First, part (a) says that the optimal cost
of
P
1
,
P
ch
and
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.
Second, since
P
1
,
P
ch
and
P
2
are nonconvex we will solve their
relaxations
R
1
,
R
ch
or
R
2
instead. Even though exactness is defined
to be a relation between each pair (e.g.,
R
2
is exact means
r
2
=
p
2
),
part (a) says that if any pair is exact then the relaxed problem is exact
with respect to OPF
as well. For instance if
R
2
is exact with respect
to
P
2
then any optimal
G
-partial matrix
W
G
of
R
2
satisfies (8) and
has rank
W
G
(
e
) = 1
for all
e
E
. Our proof will construct a psd
rank-1
n
×
n
matrix
W
from
W
G
that is optimal for
P
1
. The spectral
decomposition of
W
then yields an optimal voltage vector
V
in
V
for OPF. Henceforth we will simply say that a relaxation
R
1
/
R
ch
/
R
2
is “exact” instead of “exact with respect to
P
1
/
P
ch
/
P
2
.”
Third, part (c) says that solving
R
1
is the same as solving
R
ch
and, in the case where
G
is acyclic (a
tree
, since
G
is assumed to be
connected), is the same as solving
R
2
.
R
1
and
R
ch
are SDPs while
R
2
is an SOCP. Though they can all be solved in polynomial time
[43], [56], SOCP in general requires a much smaller computational
effort than SDP. Part (b) suggests that, when
G
is a tree, we should
always solve
R
2
. When
G
has cycles then there is a tradeoff between
computational effort and exactness in deciding between solving
R
2
or
R
ch
/
R
1
. As our simulation results in Section V confirm, if all maximal
cliques of a chordal extension are available then solving
R
ch
is
always
better
than solving
R
1
as they have the same accuracy (in terms of
exactness) but
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
I
G
ch
I
C
n
. Therefore,
typically
,
the number of variables is the smallest in
R
2
(
|
I
G
|
)
, the largest in
R
1
5
(
|
I
C
n
|
)
, with
R
ch
in between. However the actual number of variables
in
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
[40] for more details. This choice however does not affect the optimal
value
r
ch
.
Corollary 2.
1) If
G
is acyclic then
p
=
p
1
=
p
ch
=
p
2
r
1
=
r
ch
=
r
2
.
2) If
G
has cycles then
p
=
p
1
=
p
ch
=
p
2
r
1
=
r
ch
r
2
.
Theorem 1 and Corollary 2 do not provide conditions that guarantee
any of the relaxations
R
1
,
R
ch
,
R
2
are exact. See [23], [24], [26],
[27], [59]–[62] for such sufficient conditions in the bus injection model.
Corollary 2 implies that if
R
2
is exact, so are
R
ch
and
R
1
. Moreover
Lemma 4 below relates the feasible sets of
R
1
,
R
ch
,
R
2
, not just their
optimal values. It implies that
R
1
,
R
ch
,
R
2
are equivalent problems if
G
has no cycles.
F. Proof of Theorem 1
We now prove that the feasible sets of OPF and
P
1
,
P
ch
,
P
2
are equivalent when restricted to the underlying
G
-partial matrices.
Similarly, the feasible sets of their relaxations are equivalent when
G
is a tree. When any of the relaxations are exact we can construct an
n
-dimensional complex voltage vector
V
V
that optimally solves
OPF.
To define the set of
G
-partial matrices associated with
P
1
,
P
ch
,
P
2
suppose
F
is a graph on
n
nodes such that
G
is a subgraph of
F
, i.e.,
I
G
I
F
. An
F
-partial matrix
W
F
is called an
F
-completion
of the
G
-partial matrix
W
G
if
[
W
F
]
ij
= [
W
G
]
ij
for all
(
i,j
)
I
G
I
F
,
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
×
n
matrix.
W
F
is a Hermitian
F
-completion if
W
F
=
W
H
F
.
W
F
is a psd
F
-completion if
in addition
W
F

0
.
W
F
is a rank-1
F
-completion if rank
W
F
= 1
. It can be
checked that if
W
G
6
0
then
W
G
does not have a psd
F
-completion.
If rank
W
G
6
= 1
then it does not have a rank-1
F
-completion. Define
W
1
:=
{
W
G
|
W
G
satisfies (7a)
(7b)
,
psd rank-1
C
n
-completion of
W
G
}
.
Recall that for
W
, an
n
×
n
matrix,
W
(
G
)
is the
G
-partial matrix
corresponding to the
I
G
entries of
W
. Given an
n
×
n
psd rank-1
matrix
W
that is feasible for
P
1
,
W
(
G
)
is in
W
1
. Conversely given
a
W
G
W
1
, its psd rank-1
C
n
-completion is a feasible solution for
P
1
. Hence
W
1
is the set of
I
G
entries of all
n
×
n
matrices feasible
for
P
1
and is nonconvex. Define
W
+
1
:=
{
W
G
|
W
G
satisfies (7a)
(7b)
,
psd
C
n
-completion of
W
G
}
.
W
+
1
is the set of
I
G
entries of all
n
×
n
matrices feasible for
R
1
. It
is convex and contains
W
1
.
Similarly define the corresponding sets for
P
ch
and
R
ch
:
W
ch
:=
{
W
G
|
W
G
satisfies (7a)
(7b)
,
psd rank-1
G
ch
-completion of
W
G
}
,
W
+
ch
:=
{
W
G
|
W
G
satisfies (7a)
(7b)
,
psd
G
ch
-completion of
W
G
}
.
W
ch
and
W
+
ch
are the sets of
I
G
entries of
G
ch
-partial matrices feasible
for problems
P
ch
and
R
ch
respectively. Again
W
+
ch
is a convex set
containing the nonconvex set
W
ch
. For problems
P
2
and
R
2
define:
W
2
:=
{
W
G
|
W
G
satisfies (7a)
(7b) and (8)
,
W
G
(
e
)

0
,
rank
W
G
(
e
) = 1
for all
e
E
}
,
W
+
2
:=
{
W
G
|
W
G
satisfies (7a)
(7b)
,
W
G
(
e
)

0
for all
e
E
}
.
Informally the sets
W
1
,
W
+
1
,
W
ch
,
W
+
ch
,
W
2
and
W
+
2
describe the
feasible sets of the various problems restricted to the
I
G
entries of
their respective partial matrix variables.
To relate the sets to the feasible set of OPF, consider the map
f
from
C
n
to the set of
G
-partial matrices defined as:
f
(
V
) :=
W
G
where
[
W
G
]
kk
=
|
V
k
|
2
, k
N,
and
[
W
G
]
jk
=
V
j
V
H
k
,
(
j,k
)
E.
Also, let
f
(
V
) :=
{
f
(
V
)
|
V
V
}
.
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.
Lemma 3.
f
(
V
) =
W
1
=
W
ch
=
W
2
.
Proof:
First, we show that
f
(
V
) =
W
1
. Consider
V
V
. Then
W
=
V V
H
is feasible for
P
1
and hence the
G
-partial matrix
W
(
G
)
is
in
W
1
. Thus,
f
(
V
)
W
1
. To prove
W
1
f
(
V
)
, consider the rank-1
psd
C
n
completion of a
G
-partial matrix in
W
1
. Its unique spectral
decomposition yields a vector
V
that satisfies (3)–(4) and hence is in
V
. Hence,
f
(
V
) =
W
1
.
Now, fix a chordal extension
G
ch
of
G
. We now prove:
W
1
W
ch
W
2
W
1
.
To show
W
1
W
ch
, consider
W
G
W
1
, and let
W
be its rank-1
psd
C
n
-completion. Then it is easy to check that
W
(
G
ch
)
is feasible
for
P
ch
and hence
W
G
is in
W
ch
as well.
To show
W
ch
W
2
consider a
W
G
W
ch
and its psd rank-1
G
ch
-completion
W
ch
. Since every edge
e
of
G
is a 2-clique in
G
ch
,
W
G
(
e
) =
W
ch
(
e
)
is psd rank-1 by the definition of psd and rank-1 for
W
ch
. We are thus left to show that
W
G
satisfies the cycle condition
(8). Consider the following statement
T
k
for
3
k
n
:
S
k
: For all cycles
(
n
1
,n
2
,...,n
k
)
of length
k
in
G
ch
we have:
[
W
ch
]
n
1
n
2
+
[
W
ch
]
n
2
n
3
+
...
+
[
W
ch
]
n
k
n
1
= 0 mod 2
π.
For
k
= 3
, a cycle
(
n
1
,n
2
,n
3
)
defines a 3-clique in
G
ch
and thus
W
ch
(
n
1
,n
2
,n
3
)
is psd rank-1 and
W
ch
(
n
1
,n
2
,n
3
) =
uu
H
for some
u
:= (
u
1
,u
2
,u
3
)
C
3
. Then
[
W
ch
]
n
1
n
2
+
[
W
ch
]
n
2
n
3
+
[
W
ch
]
n
3
n
1
=
[
(
u
1
u
H
2
)(
u
2
u
H
3
)(
u
3
u
H
1
)
]
= 0 mod 2
π.
Let
T
r
be true for all
3
r
k
and consider a cycle
(
n
1
,n
2
,...,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
, that are not adjacent on the cycle. Then
(
n
1
,n
2
,...,n
k
)
and
(
n
1
,n
k
,n
k
+1
,...,n
k
)
are two cycles in
G
ch
. By hypothesis,
T
k
and
T
k
k
+2
are true and hence
[
W
ch
]
n
1
n
2
+
[
W
ch
]
n
2
n
3
+
...
+
[
W
ch
]
n
k
n
1
=
[
W
ch
]
n
1
n
k
+
[
W
ch
]
n
k
n
k
+1
+
...
+
[
W
ch
]
n
k
n
1
= 0 mod 2
π.
We conclude that
T
k
+1
is true by adding the above equations and using
[
W
ch
]
n
1
n
k
=
[
W
ch
]
n
k
n
1
mod 2
π
since
W
ch
is Hermitian.
By induction,
W
ch
satisfies the cycle condition. Also,
W
G
=
W
ch
(
G
)
6
satisfies the cycle condition and hence in
W
2
. This completes the proof
of
W
ch
W
2
.
To show
W
2
W
1
suppose
W
G
W
2
. We now construct a psd
rank-1
C
n
-completion of
W
G
to show
W
G
W
1
. Define
θ
C
n
as
follows. Let
θ
1
:= 0
. For
j
N
\{
1
}
let
(1
,n
2
)
,
(
n
2
,n
3
)
,
...,
(
n
k
,j
)
be any path from node 1 to node
j
. Define
θ
j
:=
(
[
W
G
]
1
n
2
+
[
W
G
]
n
2
n
3
+
...
+
[
W
G
]
n
k
j
) mod 2
π.
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
θ
j
uniquely because
W
G
satisfies the cycle condition. Let
V
:=
[
[
W
G
]
11
e
i
θ
1
,
···
[
W
G
]
nn
e
i
θ
n
]
.
Then it can be verified that
W
:=
V V
H
is a psd rank-1
C
n
-completion
of
W
G
. Hence
W
G
W
1
. This completes the proof of the lemma.
Lemma 4.
W
+
1
=
W
+
ch
W
+
2
. If
G
is acyclic, then
W
+
1
=
W
+
ch
=
W
+
2
.
Proof:
It suffices to prove
W
+
ch
W
+
1
W
+
ch
W
+
2
.
(10)
To show
W
+
ch
W
+
1
, suppose
W
G
W
+
ch
. Let
W
ch
be a psd
G
ch
-
completion of
W
G
for a chordal extension
G
ch
. Since any psd partial
matrix on a chordal graph has a psd
C
n
-completion [66, Theorem 7],
W
ch
has a psd
C
n
-completion. Obviously, any psd
C
n
-completion of
W
ch
is also a psd
C
n
-completion of
W
G
, i.e.,
W
G
W
+
1
. The relation
W
+
1
W
+
ch
W
+
2
follows a similar argument to the proof of
Lemma 3.
If
G
is acyclic, then
G
is itself chordal and hence
W
G
has a psd
C
n
-completion, i.e.,
W
+
2
W
+
1
. This implies
W
+
1
=
W
+
ch
=
W
+
2
.
To prove Theorem 1(c) note that parts (a) and (b) imply
p
=
p
1
=
p
ch
=
p
2
r
1
=
r
ch
r
2
.
Hence
R
1
is exact
(
p
1
=
r
1
)
iff
R
ch
is exact
(
p
ch
=
r
ch
). If
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. B
RANCH FLOW MODEL AND
SOCP
RELAXATION
A. OPF formulation
The branch flow model of [37] adopts a directed connected graph
̃
G
= (
N,
̃
E
)
to represent a power network where each node in
N
:=
{
1
,...,n
}
represents a bus and each edge in
̃
E
represents a line. The
orientations of the edges are taken to be arbitrary. Denote the directed
edge from bus
i
to bus
j
by
i
j
̃
E
and define
m
:=
|
̃
E
|
as the
number of directed edges in
G
. For each edge
i
j
̃
E
, define the
following quantities:
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
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 [37] is defined by the following set of
power flow equations:
s
j
=
k
:
j
k
S
jk
i
:
i
j
(
S
ij
z
ij
|
I
ij
|
2
)
for
j
N,
(11a)
S
ij
=
V
i
I
H
ij
and
I
ij
=
y
ij
(
V
i
V
j
)
for
i
j
̃
E,
(11b)
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
s
j
s
j
s
j
for
j
N,
(12)
where
s
j
and
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
s
j
=
s
j
=
. As in the bus injection
model, we can eliminate the variables
s
j
by combining (11a) and (12)
into:
s
j
k
:
j
k
S
jk
i
:
i
j
(
S
ij
z
ij
|
I
ij
|
2
)
s
j
for
j
N.
(13)
All voltage magnitudes are constrained as follows:
V
j
≤|
V
j
|≤
V
j
for
j
N,
(14)
where
V
j
and
V
j
are known lower and upper voltage limits, with
|
V
1
|
= 1 =
V
1
=
V
1
. Denote the variables in the branch flow model
by
̃
x
:= (
S,I,V
)
C
n
+2
m
. These constraints define the feasible set
of the OPF problem in the branch flow model:
X
:=
{
̃
x
C
n
+2
m
|
̃
x
satisfies (11b)
,
(13)
,
(14)
}
.
(15)
To define OPF, consider a cost function
c
( ̃
x
)
. For example, if the
objective is to minimize the real power loss in the network, then we
have
c
( ̃
x
) =
j
N
Re
s
j
=
j
N
Re
k
:
j
k
S
jk
i
:
i
j
(
S
ij
z
ij
|
I
ij
|
2
)
.
Similarly, if the objective is to minimize the weighted sum of real
power generation in the network, then
c
( ̃
x
) =
j
N
c
j
(
Re
s
j
p
d
j
)
=
j
N
c
j
Re
k
:
j
k
S
jk
i
:
i
j
(
S
ij
z
ij
|
I
ij
|
2
)
p
d
j
,
where
p
d
j
is the given real power demand at bus
j
N
.
Optimal power flow problem
OPF
:
minimize
̃
x
c
( ̃
x
)
subject to
̃
x
X
.
(16)
Since (11) is quadratic,
X
is generally a nonconvex set. As before, OPF
is a nonconvex problem.
B. SOCP relaxation:
̃
P
2
,
̃
R
nc
2
and
̃
R
2
The SOCP relaxation of (16) developed in [37] consists of two steps.
First, we use (11b) to eliminate the phase angles from the complex
voltages
V
and currents
I
to obtain for each
i
j
̃
E
,
v
j
=
v
i
2
Re
(
z
H
ij
S
ij
) +
|
z
ij
|
2
`
ij
,
(17)
`
ij
v
i
=
|
S
ij
|
2
.
(18)
where
v
i
:=
|
V
i
|
2
and
`
ij
:=
|
I
ij
|
2
. This is the model first proposed by
Baran-Wu in [29], [30] for distribution systems. Second the quadratic
equalities in (18) are nonconvex; relax them to inequalities:
`
ij
v
i
≥ |
S
ij
|
2
for
i
j
̃
E.
(19)
Let
x
:= (
S,`,v
)
R
n
+3
m
denote the new variables. Note that we
use
S
to denote both a complex variable in
C
m
and the real variables
(
Re
S,
Im
S
)
in
R
2
m
depending on context. Define the nonconvex set:
X
nc
2
:=
{
x
R
n
+3
m
|
x
satisfies
(13)
,
(14)
,
(17)
,
(18)
}
,
and the convex superset that is a second-order cone:
X
+
2
:=
{
x
R
n
+3
m
|
x
satisfies
(13)
,
(14)
,
(17)
,
(19)
}
.
As we discuss below solving OPF over
X
+
2
is an SOCP and hence
efficiently computable. Whether the solution of the SOCP relaxation
yields an optimal for OPF depends on two factors [37]: (a) whether