1
Branch Flow Model: Relaxations and
Convexification
(Part I)
Masoud Farivar
Steven H. Low
Engineering and Applied Science
Caltech
Abstract
—We propose a branch flow model for the anal-
ysis and optimization of mesh as well as radial networks.
The model leads to a new approach to solving optimal
power flow (OPF) that consists of two relaxation steps.
The first step eliminates the voltage and current angles
and the second step approximates the resulting problem
by a conic program that can be solved efficiently. For radial
networks, we prove that both relaxation steps are always
exact, provided there are no upper bounds on loads. For
mesh networks, the conic relaxation is always exact but the
angle relaxation may not be exact, and we provide a simple
way to determine if a relaxed solution is globally optimal.
We propose convexification of mesh networks using phase
shifters so that OPF for the convexified network can always
be solved efficiently for an optimal solution. We prove
that convexification requires phase shifters only outside a
spanning tree of the network and their placement depends
only on network topology, not on power flows, generation,
loads, or operating constraints. Part I introduces our
branch flow model, explains the two relaxation steps, and
proves the conditions for exact relaxation. Part II describes
convexification of mesh networks, and presents simulation
results.
I. I
NTRODUCTION
A. Motivation
The bus injection model is the standard model for
power flow analysis and optimization. It focuses on nodal
variables such as voltages, current and power injections
and does not directly deal with power flows on individual
branches. Instead of nodal variables, the branch flow
model focuses on currents and powers on the branches.
It has been used mainly for modeling distribution cir-
cuits which tend to be radial, but has received far less
attention. In this paper, we advocate the use of branch
flow model for
both
radial and mesh networks, and
demonstrate how it can be used for optimizing the design
and operation of power systems.
To appear in
IEEE Trans. Power Systems
, 2013
(submitted
in May 11, 2012, accepted for publication on March 3, 2013). A
preliminary and abridged version has appeared in [1].
One of the motivations for our work is the optimal
power flow (OPF) problem. OPF seeks to optimize a
certain objective function, such as power loss, gener-
ation cost and/or user utilities, subject to Kirchhoff’s
laws, power balance as well as capacity, stability and
contingency constraints on the voltages and power flows.
There has been a great deal of research on OPF since
Carpentier’s first formulation in 1962 [2]; surveys can be
found in, e.g., [3]–[7]. OPF is generally nonconvex and
NP-hard, and a large number of optimization algorithms
and relaxations have been proposed. A popular approx-
imation is the DC power flow problem, which is a lin-
earization and therefore easy to solve, e.g. [8]–[11]. An
important observation was made in [12], [13] that the full
AC OPF can be formulated as a quadratically constrained
quadratic program and therefore can be approximated by
a semidefinite program. While this approach is illustrated
in [12], [13] on several IEEE test systems using an
interior-point method, whether or when the semidefinite
relaxation will turn out to be exact is not studied. Instead
of solving the OPF problem directly, [14] proposes to
solve its convex Lagrangian dual problem and gives
a sufficient condition that must be satisfied by a dual
solution for an optimal OPF solution to be recoverable.
This result is extended in [15] to include other variables
and constraints and in [16] to exploit network sparsity.
In [17], [18], it is proved that the sufficient condition of
[14] always holds for a radial (tree) network, provided
the bounds on the power flows satisfy a simple pattern.
See also [19] for a generalization. These results confirm
that radial networks are computationally much simpler.
This is important as most distribution systems are radial.
The limitation of semidefinite relaxation for OPF is
studied in [20] using mesh networks with 3, 5, and 7
buses: as a line-flow constraint is tightened, the duality
gap becomes nonzero and the solutions produced by the
semidefinite relaxation becomes physically meaningless.
Indeed, examples of nonconvexity have long been dis-
cussed in the literature, e.g., [21]–[23]. See, e.g., [24]
for branch-and-bound algorithms for solving OPF when
convex relaxation fails.
arXiv:1204.4865v4 [cs.SY] 11 Apr 2013
2
The papers above are all based on the bus injection
model. In this paper, we introduce a branch flow model
on which OPF and its relaxations can also be defined.
Our model is motivated by a model first proposed by
Baran and Wu in [25], [26] for the optimal placement and
sizing of switched capacitors in distribution circuits for
Volt/VAR control. One of the insights we highlight here
is that the Baran-Wu model of [25], [26] can be treated
as a particular relaxation of our branch flow model where
the phase angles of the voltages and currents are ignored.
By recasting their model as a set of linear and quadratic
equality constraints, [27], [28] observe that relaxing the
quadratic equality constraints to inequality constraints
yields a second-order cone program (SOCP). It proves
that the SOCP relaxation is exact for radial networks,
when there are no upper bounds on the loads. This
result is extended here to mesh networks with line limits,
and convex, as opposed to linear, objective functions
(Theorem 1). See also [29], [30] for various convex
relaxations of approximations of the Baran-Wu model
for radial networks.
Other branch flow models have also been studied, e.g.,
in [31]–[33], all for radial networks. Indeed [31] studies
a similar model to that in [25], [26], using receiving-
end branch powers as variables instead of sending-end
branch powers as in [25], [26]. Both [32] and [33]
eliminate voltage angles by defining real and imaginary
parts of
V
i
V
∗
j
as new variables and defining bus power
injections in terms of these new variables. This results
in a system of linear quadratic equations in power
injections and the new variables. While [32] develops
a Newton-Raphson algorithm to solve the bus power
injections, [33] solves for the branch flows through an
SOCP relaxation for radial networks, though no proof of
optimality is provided.
This set of papers [25]–[33] all exploit the fact that
power flows can be specified by a simple set of linear and
quadratic equalities if voltage angles can be eliminated.
Phase angles can be relaxed only for radial networks
and generally not for mesh networks, as [34] points out
for their branch flow model, because cycles in a mesh
network impose nonconvex constraints on the optimiza-
tion variables (similar to the angle recovery condition in
our model; see Theorem 2 below). For mesh networks,
[34] proposes a sequence of SOCP where the nononvex
constraints are replaced by their linear approximations
and demonstrates the effectiveness of this approach using
seven network examples. In this paper we extend the
Baran-Wu model from radial to mesh networks and use
it to develop a solution strategy for OPF.
B. Summary
Our purpose is to develop a formal theory of branch
flow model for the analysis and optimization of mesh as
well as radial networks. As an illustration, we formulate
OPF within this alternative model, propose relaxations,
characterize when a relaxed solution is exact, prove that
our relaxations are always exact for radial networks when
there are no upper bounds on loads but may not be exact
for mesh networks, and show how to use phase shifters
to convexify a mesh network so that a relaxed solution
is always optimal for the convexified network.
Specifically we formulate in Section II the OPF prob-
lem using branch flow equations involving complex bus
voltages and complex branch current and power flows.
In Section III we describe our solution approach that
!"#$
!"#%
&'
$
!"#%
('
$
)*&(+$
'),&*&-./$
0/1)'2)$
3'.4)(-./$
5.'$+'))$
/./(./1)*
$
/./(./1)*
$
(./1)*$
&/6,)$
'),&*&-./$
(./0($
'),&*&-./$
Fig. 1: Proposed solution strategy for solving OPF.
consists of two relaxation steps (see Figure 1):
•
Angle relaxation
: relax OPF by eliminating voltage
and current angles from the branch flow equations.
This yields the (extended) Baran-Wu model and a
relaxed problem OPF-ar which is still nonconvex
due to a quadratic equality constraint.
•
Conic relaxation
: relax OPF-ar by changing the
quadratic equality into an inequality constraint. This
yields a convex problem OPF-cr (which is an SOCP
when the objective function is linear).
In Section IV we prove that the conic relaxation OPF-
cr is always exact
even for
mesh networks, provided
there are no upper bounds on real and reactive loads,
i.e.,
any
optimal solution of OPF-cr is also optimal for
OPF-ar. Given an optimal solution of OPF-ar, whether
we can derive an optimal solution of the original OPF
depends on whether we can recover the voltage and
current angles from the given OPF-ar solution. In Section
3
V we characterize the exact condition (the angle recovery
condition) under which this is possible, and present two
angle recovery algorithms. The angle recovery condi-
tion has a simple interpretation: any solution of OPF-
ar implies an angle difference across a line, and the
condition says that the implied angle differences sum to
zero (mod
2
π
) around each cycle. For a radial network,
this condition holds trivially and hence solving the conic
relaxation OPF-cr always produces an optimal solution
for OPF. For a mesh network, the angle recovery con-
dition corresponds to the requirement that the implied
phase angle differences sum to zero around every loop.
The given OPF-ar solution may not satisfy this condition,
but our characterization can be used to check if it yields
an optimal solution for OPF. These results suggest an
algorithm for solving OPF as summarized in Figure 2.
!"#$%&'()*
+,
&
'()&4"#7."8&
9%+"$%,&38:#%4&
,3;03#&
38:#%&,%+"$%,<&
+"8;0."8&2"#;4=&
>&
/%42&
Fig. 2: Proposed algorithm for solving OPF (11)–(12)
without phase shifters. The details are explained in
Sections II–V.
If a relaxed solution for a mesh network does not
satisfy the angle recovery condition, then it is infeasible
for OPF. In Part II of this paper, we propose a simple
way to convexify a mesh network using phase shifters
so that
any
relaxed solution of OPF-ar can be mapped to
an optimal solution of OPF for the convexified network,
with an optimal cost that is lower than or equal to that
of the original network.
C. Extensions: radial networks and equivalence
In [35], [36], we prove a variety of sufficient condi-
tions under which the conic relaxation proposed here is
exact for radial networks. The main difference from The-
orem 1 below is that, [35], [36] allow upper bounds on
the loads but relax upper bounds on voltage magnitudes.
Unlike the proof for Theorem 1 here, those in [35], [36]
exploit the duality theory.
The bus injection model and the branch flow model
are defined by different sets of equations in terms of
their own variables. Each model is self-contained: one
can formulate and analyze power flow problems within
each model, using only nodal variables or only branch
variables. Both models (i.e., the sets of equations in their
respective variables), however, are descriptions of the
Kirchhoff’s laws. In [37] we prove formally the equiv-
alence of these models, in the sense that given a power
flow solution in one model, one can derive a correspond-
ing power flow solution in the other model. Although
the semidefinite relaxation in the bus injection model is
very different from the convex relaxation proposed here,
[37] also establishes the precise relationship between the
various relaxations in these two models. This is useful
because some results are easier to formulate and prove
in one model than in the other. For instance, it is hard to
see how the upper bounds on voltage magnitudes and the
technical conditions on the line impedances in [35], [36]
for exactness in the branch flow model affect the rank
of the semidefinite matrix variable in the bus injection
model, although [37] clarifies conditions that guarantee
their equivalence.
II. B
RANCH FLOW MODEL
Let
R
denote the set of real numbers,
C
complex
numbers, and
N
integers. A variable without a subscript
denotes a vector with appropriate components, e.g.,
s
:=
(
s
i
,i
= 1
,...,n
)
,
S
:= (
S
ij
,
(
i,j
)
∈
E
)
. For a vector
a
= (
a
1
,...,a
k
)
,
a
−
i
denotes
(
a
1
,...,a
i
−
1
,a
i
+1
,a
k
)
.
For a scalar, vector, or matrix
A
,
A
t
denotes its transpose
and
A
∗
its complex conjugate transpose. Given a directed
graph
G
= (
N,E
)
, denote a link in
E
by
(
i,j
)
or
i
→
j
if it points from node
i
to node
j
. We will use
e
,
(
i,j
)
, or
i
→
j
interchangeably to refer to a link in
E
. We write
i
∼
j
if
i
and
j
are connected, i.e., if either
(
i,j
)
∈
E
or
(
j,i
)
∈
E
(but not both). We write
θ
= 0
(mod
2
π
)
if
θ
= 2
πk
, and
θ
=
φ
(mod
2
π
) if
θ
−
φ
= 2
πk
, for
some integer
k
. For an
d
-dimensional vector
α
,
P
(
α
)
denotes its projection onto
(
−
π,π
]
d
by taking modulo
2
π
componentwise.
A. Branch flow model
Let
G
= (
N,E
)
be a connected graph representing a
power network, where each node in
N
represents a bus
and each link in
E
represents a line (condition A1). We
index the nodes by
i
= 0
,
1
,...,n
. The power network
is called
radial
if its graph
G
is a tree. For a distribution
network, which is typically radial, the root of the tree
(node 0) represents the substation bus. For a (generally
meshed) transmission network, node 0 represents the
slack bus.
4
We regard
G
as a directed graph and adopt the follow-
ing orientation for convenience (only). Pick
any
spanning
tree
T
:= (
N,E
T
)
of
G
rooted at node 0, i.e.,
T
is
connected and
E
T
⊆
E
has
n
links. All links in
E
T
point
away from the root. For any link in
E
\
E
T
that is not in
the spanning tree
T
, pick an arbitrary direction. Denote
a link by
(
i,j
)
or
i
→
j
if it points from node
i
to node
j
. Henceforth we will assume without loss of generality
that
G
and
T
are directed graphs as described above.
1
For
each link
(
i,j
)
∈
E
, let
z
ij
=
r
ij
+
i
x
ij
be the complex
impedance on the line, and
y
ij
:= 1
/z
ij
=:
g
ij
−
i
b
ij
be
the corresponding admittance. For each node
i
∈
N
, let
z
i
=
r
i
+
i
x
i
be the shunt impedance from
i
to ground,
and
y
i
:= 1
/z
i
=:
g
i
−
i
b
i
.
2
For each
(
i,j
)
∈
E
, let
I
ij
be the complex current
from buses
i
to
j
and
S
ij
=
P
ij
+
i
Q
ij
be the
sending-end
complex power from buses
i
to
j
. For each node
i
∈
N
,
let
V
i
be the complex voltage on bus
i
. Let
s
i
be the
net complex power injection, which is generation minus
load on bus
i
. We use
s
i
to denote both the complex
number
p
i
+
i
q
i
and the pair
(
p
i
,q
i
)
depending on the
context.
As customary, we assume that the complex voltage
V
0
is given and the complex net generation
s
0
is a
variable. For power flow analysis, we assume other
power injections
s
:= (
s
i
,i
= 1
,...,n
)
are given. For
optimal power flow, VAR control, or demand response,
s
are control variables as well.
Given
z
:= (
z
ij
,
(
i,j
)
∈
E, z
i
,i
∈
N
)
,
V
0
and
bus power injections
s
, the variables
(
S,I,V,s
0
) :=
(
S
ij
,I
ij
,
(
i,j
)
∈
E, V
i
,i
= 1
,...,n, s
0
)
satisfy the
Ohm’s law:
V
i
−
V
j
=
z
ij
I
ij
,
∀
(
i,j
)
∈
E
(1)
the definition of branch power flow:
S
ij
=
V
i
I
∗
ij
,
∀
(
i,j
)
∈
E
(2)
and power balance at each bus: for all
j
∈
N
,
∑
k
:
j
→
k
S
jk
−
∑
i
:
i
→
j
(
S
ij
−
z
ij
|
I
ij
|
2
)
+
y
∗
j
|
V
j
|
2
=
s
j
(3)
We
will
refer
to
(1)–(3)
as
the
branch
flow
model/equations
. Recall that the cardinality
|
N
|
=
n
+1
and let
|
E
|
=:
m
. The branch flow equations (1)–(3)
specify
2
m
+
n
+ 1
nonlinear equations in
2
m
+
n
+ 1
1
The orientation of
G
and
T
are different for different spanning
trees
T
, but we often ignore this subtlety in this paper.
2
The shunt admittance
y
i
represents capacitive devices on bus
i
only and a line is modeled by a series admittance
y
ij
without shunt
elements. If a shunt admittance
i
̃
b
ij
/
2
is included on each end of
line
(
i,j
)
in the
π
-model, then a limit on line flow should be a limit
on
∣
∣
∣
S
ij
−
i
̃
b
ij
|
V
i
|
2
/
2
∣
∣
∣
instead of on
|
S
ij
|
.
complex variables
(
S,I,V,s
0
)
, when other bus power
injections
s
are specified.
We will call a solution of (1)–(3) a
branch flow
solution
with respect to a given
s
, and denote it by
x
(
s
) := (
S,I,V,s
0
)
. Let
X
(
s
)
⊆
C
2
m
+
n
+1
be the set
of all branch flow solutions with respect to a given
s
:
X
(
s
) :=
{
x
:= (
S,I,V,s
0
)
|
x
solves (1)–(3) given
s
}
(4)
and let
X
be the set of all branch flow solutions:
X
:=
⋃
s
∈
C
n
X
(
s
)
(5)
For simplicity of exposition, we will often abuse notation
and use
X
to denote either the set defined in (4) or
that in (5), depending on the context. For instance,
X
is used to denote the set in (4) for a fixed
s
in Section V
for power flow analysis, and to denote the set in (5) in
Section IV for optimal power flow where
s
itself is also
an optimization variable. Similarly for other variables
such as
x
for
x
(
s
)
.
B. Optimal power flow
Consider the optimal power flow problem where,
in addition to
(
S,I,V,s
0
)
,
s
is also an optimization
variable. Let
p
i
:=
p
g
i
−
p
c
i
and
q
i
:=
q
g
i
−
q
c
i
where
p
g
i
and
q
g
i
(
p
c
i
and
q
c
i
) are the real and reactive power gen-
eration (consumption) at node
i
. For instance, [25], [26]
formulate a Volt/VAR control problem for a distribution
circuit where
q
g
i
represent the placement and sizing of
shunt capacitors. In addition to (1)–(3), we impose the
following constraints on power generation: for
i
∈
N
,
p
g
i
≤
p
g
i
≤
p
g
i
, q
g
i
≤
q
g
i
≤
q
g
i
(6)
In particular, any of
p
g
i
,q
g
i
can be a fixed constant by
specifying that
p
g
i
=
p
g
i
and/or
q
g
i
=
q
g
i
. For instance, in
the inverter-based VAR control problem of [27], [28],
p
g
i
are the fixed (solar) power outputs and the reactive power
q
g
i
are the control variables. For power consumption, we
require, for
i
∈
N
,
p
c
i
≤
p
c
i
≤
p
c
i
, q
c
i
≤
q
c
i
≤
q
c
i
(7)
The voltage magnitudes must be maintained in tight
ranges: for
i
= 1
,...,n
,
v
i
≤ |
V
i
|
2
≤
v
i
(8)
Finally, we impose flow limits in terms of branch cur-
rents: for all
(
i,j
)
∈
E
,
|
I
ij
| ≤
I
ij
(9)
5
We allow any objective function that is convex and
does not depend on the angles
∠
V
i
,
∠
I
ij
of voltages and
currents. For instance, suppose we aim to minimize real
power losses
r
ij
|
I
ij
|
2
[38], [39], minimize real power
generation costs
c
i
p
g
i
, and maximize energy savings
through conservation voltage reduction (CVR). Then the
objective function takes the form (see [27], [28])
∑
(
i,j
)
∈
E
r
ij
|
I
ij
|
2
+
∑
i
∈
N
c
i
p
g
i
+
∑
i
∈
N
α
i
|
V
i
|
2
(10)
for some given constants
c
i
,α
i
≥
0
.
To simplify notation, let
`
ij
:=
|
I
ij
|
2
and
v
i
:=
|
V
i
|
2
.
Let
s
g
:= (
s
g
i
, i
= 1
,...,n
) = (
p
g
i
,q
g
i
, i
= 1
,...,n
)
be
the power generations, and
s
c
:= (
s
c
i
, i
= 1
,...,n
) =
(
p
c
i
,q
c
i
, i
= 1
,...,n
)
the power consumptions. Let
s
denote either
s
g
−
s
c
or
(
s
g
,s
c
)
depending on the context.
Given a branch flow solution
x
:=
x
(
s
) := (
S,I,V,s
0
)
with respect to a given
s
, let
ˆ
y
:= ˆ
y
(
s
) := (
S,`,v,s
0
)
de-
note the projection of
x
that have phase angles
∠
V
i
,
∠
I
ij
eliminated. This defines a projection function
ˆ
h
such that
ˆ
y
=
ˆ
h
(
x
)
, to which we will return in Section III. Then
our objective function is
f
(
ˆ
h
(
x
)
,s
)
. We assume
f
(ˆ
y,s
)
is convex (condition A2); in addition, we assume
f
is
strictly increasing in
`
ij
,
(
i,j
)
∈
E
, nonincreasing in
load
s
c
, and independent of
S
(condition A3). Let
S
:=
{
(
S,v,s
0
,s
)
|
(
v,s
0
,s
)
satisfies
(6)
−
(9)
}
All quantities are optimization variables, except
V
0
which is given.
The optimal power flow problem is
OPF
:
min
x,s
f
(
ˆ
h
(
x
)
,s
)
(11)
subject to
x
∈
X
,
(
S,v,s
0
,s
)
∈
S
(12)
where
X
is defined in (5).
The feasible set is specified by the nonlinear branch
flow equations and hence OPF (11)–(12) is in general
nonconvex and hard to solve. The goal of this paper is
to propose an efficient way to solve OPF by exploiting
the structure of the branch flow model.
C. Notations and assumptions
The main variables and assumptions are summarized
in Table I and below for ease of reference:
A1 The network graph
G
is connected.
A2 The cost function
f
(ˆ
y,s
)
for optimal power flow is
convex.
A3 The cost function
f
(ˆ
y,s
)
is strictly increasing in
`
,
nonincreasing in load
s
c
, and independent of
S
.
A4 The optimal power flow problem OPF (11)–(12) is
feasible.
TABLE I: Notations.
G
,
T
(directed) network graph
G
and a span-
ning tree
T
of
G
B
,
B
T
reduced (and transposed) incidence
matrix of
G
and the submatrix corre-
sponding to
T
V
i
,
v
i
complex voltage on bus
i
with
v
i
:=
|
V
i
|
2
s
i
=
p
i
+
i
q
i
net complex load power on bus
i
p
i
=
p
g
i
−
p
c
i
net real power equals generation minus
load;
q
i
=
q
g
i
−
q
c
i
net reactive power equals generation
minus load
I
ij
,
`
ij
complex current from buses
i
to
j
with
`
ij
:=
|
I
ij
|
2
S
ij
=
P
ij
+
i
Q
ij
complex power from buses
i
to
j
(sending-end)
X
set of all branch flow solutions that
satisfy (1)–(3) either for some
s
, or
for a given
s
(sometimes denoted more
accurately by
X
(
s
))
;
ˆ
Y
set of all relaxed branch flow solutions
that satisfy (13)–(16) either for a given
s
or for some
s
;
Y
set of all relaxed branch flow solutions
that satisfy (13)–(15) and (22) either
for a given
s
or for some
s
;
x
= (
S,I,V,s
0
)
∈
X
vector
x
of power flow variables
ˆ
y
= (
S,`,v,s
0
)
∈
ˆ
Y
and its projection
ˆ
y
;
ˆ
y
=
ˆ
h
(
x
);
x
=
h
θ
(ˆ
y
)
projection mapping
ˆ
y
and an inverse
h
θ
z
ij
,
y
i
impedance on line
(
i,j
)
and shunt ad-
mittance from bus
i
to ground
f
=
f
(
ˆ
h
(
x
)
,s
)
objective function of OPF
These assumptions are standard and realistic. For in-
stance, the objective function in (10) satisfies conditions
A2–A3. A3 is a property of the objective function
f
and
not a property of power flow solutions; it holds if the
cost function is strictly increasing in line loss.
III. R
ELAXATIONS AND SOLUTION STRATEGY
A. Relaxed branch flow model
Substituting (2) into (1) yields
V
j
=
V
i
−
z
ij
S
∗
ij
/V
∗
i
.
Taking the magnitude squared, we have
v
j
=
v
i
+
|
z
ij
|
2
`
ij
−
(
z
ij
S
∗
ij
+
z
∗
ij
S
ij
)
. Using (3) and (2) and in
terms of real variables, we therefore have
p
j
=
∑
k
:
j
→
k
P
jk
−
∑
i
:
i
→
j
(
P
ij
−
r
ij
`
ij
) +
g
j
v
j
,
∀
j
(13)
q
j
=
∑
k
:
j
→
k
Q
jk
−
∑
i
:
i
→
j
(
Q
ij
−
x
ij
`
ij
) +
b
j
v
j
,
∀
j
(14)
v
j
=
v
i
−
2(
r
ij
P
ij
+
x
ij
Q
ij
) + (
r
2
ij
+
x
2
ij
)
`
ij
∀
(
i,j
)
∈
E
(15)
`
ij
=
P
2
ij
+
Q
2
ij
v
i
,
∀
(
i,j
)
∈
E
(16)
6
We will refer to (13)–(16) as the
relaxed (branch
flow) model/equations
and a solution a
relaxed (branch
flow) solution
. These equations were first proposed
in [25], [26] to model radial distribution circuits.
They define a system of equations in the variables
(
P,Q,`,v,p
0
,q
0
) := (
P
ij
,Q
ij
,`
ij
,
(
i,j
)
∈
E, v
i
,i
=
1
,...,n, p
0
,q
0
)
. We often use
(
S,`,v,s
0
)
as a short-
hand for
(
P,Q,`,v,p
0
,q
0
)
. The relaxed model has a
solution under A4.
In contrast to the original branch flow equations (1)–
(3), the relaxed equations (13)–(16) specifies
2(
m
+
n
+1)
equations in
3
m
+
n
+2
real variables
(
P,Q,`,v,p
0
,q
0
)
,
given
s
. For a radial network, i.e.,
G
is a tree,
m
=
|
E
|
=
|
N
| −
1 =
n
. Hence the relaxed system (13)–
(16) specifies
4
n
+ 2
equations in
4
n
+ 2
real variables.
It is shown in [40] that there are generally multiple
solutions, but for practical networks where
|
V
0
|'
1
and
r
ij
,x
ij
are small p.u., the solution of (13)–(16) is unique.
Exploiting structural properties of the Jacobian matrix,
efficient algorithms have also been proposed in [41] to
solve the relaxed branch flow equations.
For a connected mesh network,
m
=
|
E
|
>
|
N
|−
1 =
n
, in which case there are more variables than equations
for the relaxed model (13)–(16), and therefore the so-
lution is generally nonunique. Moreover, some of these
solutions may be spurious, i.e., they do not correspond to
a solution of the original branch flow equations (1)–(3).
Indeed, one may consider
(
S,`,v,s
0
)
as a projection
of
(
S,I,V,s
0
)
where each variable
I
ij
or
V
i
is relaxed
from a point in the complex plane to a circle with a
radius equal to the distance of the point from the origin.
It is therefore not surprising that a relaxed solution of
(13)–(16) may not correspond to any solution of (1)–
(3). The key is whether, given a relaxed solution, we
can recover the angles
∠
V
i
,
∠
I
ij
correctly from it. It
is then remarkable that, when
G
is a tree, indeed the
solutions of (13)–(16) coincide with those of (1)–(3).
Moreover
for a general network, (13)–(16) together with
the angle recovery condition in Theorem 2 below are
indeed equivalent to (1)–(3)
, as explained in Remark 5
of Section V.
To understand the relationship between the branch
flow model and the relaxed model and formulate our
relaxations precisely, we need some notations. Fix an
s
. Given a vector
(
S,I,V,s
0
)
∈
C
2
m
+
n
+1
, define its
projection
ˆ
h
:
C
2
m
+
n
+1
→
R
3
m
+
n
+2
by
ˆ
h
(
S,I,V,s
0
) =
(
P,Q,`,v,p
0
,q
0
)
where
P
ij
=
Re
S
ij
, Q
ij
=
Im
S
ij
, `
ij
=
|
I
ij
|
2
(17)
p
i
=
Re
s
i
, q
i
=
Im
s
i
, v
i
=
|
V
i
|
2
(18)
Let
Y
⊆
C
2
m
+
n
+1
denote the set of all
y
:= (
S,I,V,s
0
)
ˆ
h
h
!
C
2
m
+
n
+
1
R
3
m
+
n
+
2
ˆ
Y
Y
X
ˆ
h
X
(
)
Fig. 3:
X
is the set of branch flow solutions and
ˆ
Y
=
ˆ
h
(
Y
)
is the set of relaxed solutions. The inverse
projection
h
θ
is defined in Section V.
whose projections are the relaxed solutions:
3
Y
:=
{
y
:= (
S,I,V,s
0
)
|
ˆ
h
(
y
)
solves (13)–(16)
}
(19)
Define the projection
ˆ
Y
:=
ˆ
h
(
Y
)
of
Y
onto the space
R
2
m
+
n
+1
as
ˆ
Y
:=
{
ˆ
y
:= (
S,`,v,s
0
)
|
ˆ
y
solves (13)–(16)
}
Clearly
X
⊆
Y
and
ˆ
h
(
X
)
⊆
ˆ
h
(
Y
) =:
ˆ
Y
Their relationship is illustrated in Figure 3.
B. Two relaxations
Consider the OPF with angles relaxed:
min
x,s
f
(
ˆ
h
(
x
)
,s
)
subject to
x
∈
Y
,
(
S,v,s
0
,s
)
∈
S
Clearly, this problem provides a lower bound to the
original OPF problem since
Y
⊇
X
. Since neither
ˆ
h
(
x
)
nor the constraints in
Y
involves angles
∠
V
i
,
∠
I
ij
, this
problem is equivalent to the following
OPF-ar
:
min
ˆ
y,s
f
(ˆ
y,s
)
(20)
subject to
ˆ
y
∈
ˆ
Y
,
(
S,v,s
0
,s
)
∈
S
(21)
The feasible set of OPF-ar is still nonconvex due to the
quadratic equalities in (16). Relax them to inequalities:
`
ij
≥
P
2
ij
+
Q
2
ij
v
i
,
(
i,j
)
∈
E
(22)
3
As mentioned earlier, the set defined in (19) is strictly speaking
Y
(
s
)
with respect to a fixed
s
. To simplify exposition, we abuse
notation and use
Y
to denote both
Y
(
s
)
and
⋃
s
∈
C
n
Y
(
s
)
, depending
on the context. The same applies to
ˆ
Y
and
Y
etc.
7
Define the convex second-order cone (see Theorem 1
below)
Y
⊆
R
2
m
+
n
+1
that contains
ˆ
Y
as
Y
:=
{
ˆ
y
:= (
S,`,v,s
0
)
|
ˆ
y
solves (13)–(15) and (22)
}
Consider the following conic relaxation of OPF-ar:
OPF-cr
:
min
ˆ
y,s
f
(ˆ
y,s
)
(23)
subject to
ˆ
y
∈
Y
,
(
S,v,s
0
,s
)
∈
S
(24)
Clearly OPF-cr provides a lower bound to OPF-ar since
Y
⊇
ˆ
Y
.
C. Solution strategy
In the rest of this paper, we will prove the following:
1) OFP-cr is convex. Moreover, if there are no upper
bounds on loads, then the conic relaxation is exact
so that
any
optimal solution
(ˆ
y
cr
,s
cr
)
of OPF-cr
is also optimal for OPF-ar for mesh as well as
radial networks (Section IV, Theorem 1). OPF-cr
is a SOCP when the objective function is linear.
2) Given a solution
(ˆ
y
ar
,s
ar
)
of OPF-ar, if the network
is radial, then we can always recover the phase
angles
∠
V
i
,
∠
I
ij
uniquely to obtain an optimal
solution
(
x
∗
,s
∗
)
of the original OPF through an
inverse projection (Section V, Theorems 2 and 4).
3) For a mesh network, an inverse projection may
not exist to map the given
(ˆ
y
ar
,s
ar
)
to a feasible
solution of OPF. Our characterization can be used
to determined if
(ˆ
y
ar
,s
ar
)
is globally optimal.
These results motivate the algorithm in Figure 2.
In Part II of this paper, we show that a mesh network
can be convexified so that
(ˆ
y
ar
,s
ar
)
can always be
mapped to an optimal solution of OPF for the convex-
ified network. Moreover, convexification requires phase
shifters only on lines outside an arbitrary spanning tree
of the network graph.
IV. E
XACT CONIC RELAXATION
Our first key result says that OPF-cr is exact and a
SOCP when the objective function is linear.
Theorem 1:
Suppose
p
c
i
=
q
c
i
=
∞
,
i
∈
N
. Then
OPF-cr is convex. Moreover, it is exact, i.e.,
any
optimal
solution of OPF-cr is also optimal for OPF-ar.
Proof:
The feasible set is convex since the nonlinear
inequalities in
Y
can be written as the following second
order cone constraint:
∥
∥
∥
∥
∥
∥
2
P
ij
2
Q
ij
`
ij
−
v
i
∥
∥
∥
∥
∥
∥
2
≤
`
ij
+
v
i
Since the objective function is convex, OPF-cr is a conic
optimization.
4
To prove that the relaxation is exact, it
suffices to show that any optimal solution of OPF-cr
attains equality in (22).
Assume for the sake of contradiction that
(ˆ
y
∗
,s
∗
) :=
(
S
∗
,`
∗
,v
∗
,s
g
∗
0
,s
c
∗
0
,s
g
∗
,s
c
∗
)
is optimal for OPF-cr, but a
link
(
i,j
)
∈
E
has strict inequality, i.e.,
[
v
∗
]
i
[
`
∗
]
ij
>
[
P
∗
]
ij
2
+[
Q
∗
]
ij
2
. For some
ε >
0
to be determined below,
consider another point
( ̃
y,
̃
s
) = (
̃
S,
̃
`,
̃
v,
̃
s
g
0
,
̃
s
c
0
,
̃
s
g
,
̃
s
c
)
defined by:
̃
v
=
v
∗
,
̃
s
g
=
s
g
∗
̃
`
ij
= [
`
∗
]
ij
−
ε,
̃
`
−
ij
= [
`
∗
]
−
ij
̃
S
ij
= [
S
∗
]
ij
−
z
ij
ε/
2
,
̃
S
−
ij
= [
S
∗
]
−
ij
̃
s
c
i
= [
s
c
∗
]
i
+
z
ij
ε/
2
,
̃
s
c
j
= [
s
c
∗
]
j
+
z
ij
ε/
2
̃
s
c
−
i
= [
s
c
∗
]
−
i
,
̃
s
c
−
j
= [
s
c
∗
]
−
j
where a negative index means excluding the indexed
element from a vector. Since
̃
`
ij
= [
`
∗
]
ij
−
ε
,
( ̃
y,
̃
s
)
has
a strictly smaller objective value than
(ˆ
y
∗
,s
∗
)
because
of assumption A3. If
( ̃
y,
̃
s
)
is a feasible point, then it
contradicts the optimality of
(ˆ
y
∗
,s
∗
)
.
It suffices then to check that there exists an
ε >
0
such that
( ̃
y,
̃
s
)
satisfies (6)–(9), (13)–(15) and (22), and
hence is indeed a feasible point. Since
(ˆ
y
∗
,s
∗
)
is feasible,
(6)–(9) hold for
( ̃
y,
̃
s
)
too. Similarly,
( ̃
y,
̃
s
)
satisfies (13)–
(14) at all nodes
k
6
=
i,j
and (15), (22) over all links
(
k,l
)
6
= (
i,j
)
. We now show that
( ̃
y,
̃
s
)
satisfies (13)–
(14) also at nodes
i,j
, and (15), (22) over
(
i,j
)
.
Proving (13)–(14) is equivalent to proving (3). At node
i
, we have
̃
s
i
= ̃
s
g
i
−
̃
s
c
i
= [
s
g
∗
]
i
−
[
s
c
∗
]
i
−
z
ij
ε/
2
=
∑
i
→
j
′
[
S
∗
]
ij
′
−
∑
k
→
i
([
S
∗
]
ki
−
z
ki
[
`
∗
]
ki
)
+
y
∗
i
v
i
−
z
ij
ε/
2
=
∑
i
→
j
′
,j
′
6
=
j
̃
S
ij
′
+
(
̃
S
ij
+
z
ij
ε/
2
)
−
∑
k
→
i
(
̃
S
ki
−
z
ki
̃
`
ki
)
+
y
∗
i
̃
v
i
−
z
ij
ε/
2
=
∑
i
→
j
′
̃
S
ij
′
−
∑
k
→
i
(
̃
S
ki
−
z
ki
̃
`
ki
)
+
y
∗
i
̃
v
i
4
The case of linear objective without line limits is proved in [27]
for radial networks. This result is extended here to mesh networks
with line limits and convex objective functions.
8
At node
j
, we have
̃
s
j
= ̃
s
g
j
−
̃
s
c
j
= [
s
g
∗
]
j
−
[
s
c
∗
]
j
−
z
ij
ε/
2
=
∑
j
→
k
[
S
∗
]
jk
−
∑
i
′
→
j
([
S
∗
]
i
′
j
−
z
i
′
j
[
`
∗
]
i
′
j
)
+
y
∗
j
v
j
−
z
ij
ε/
2
=
∑
j
→
k
̃
S
jk
−
∑
i
′
→
j,i
′
6
=
i
(
̃
S
i
′
j
−
z
i
′
j
̃
`
i
′
j
)
+
y
∗
j
̃
v
j
−
(
(
̃
S
ij
+
z
ij
ε/
2)
−
z
ij
(
̃
`
ij
+
ε
)
)
−
z
ij
ε/
2
=
∑
j
→
k
̃
S
jk
−
∑
i
′
→
j
(
̃
S
i
′
j
−
z
i
′
j
̃
`
i
′
j
)
+
y
∗
j
̃
v
j
Hence (13)–(14) hold at nodes
i,j
.
For (15) across link
(
i,j
)
:
̃
v
j
= [
v
∗
]
i
−
2(
r
ij
[
P
∗
]
ij
+
x
ij
[
Q
∗
]
ij
)
+(
r
2
ij
+
x
2
ij
)[
`
∗
]
ij
= ̃
v
i
−
2(
r
ij
̃
P
ij
+
x
ij
̃
Q
ij
) + (
r
2
ij
+
x
2
ij
)
̃
`
ij
For (22) across link
(
i,j
)
, we have
̃
v
i
̃
`
ij
−
̃
P
2
ij
−
̃
Q
2
ij
= [
v
∗
]
i
([
`
∗
]
ij
−
ε
)
−
([
P
∗
]
ij
−
r
ij
ε/
2)
2
−
([
Q
∗
]
ij
−
x
ij
ε/
2)
2
=
(
[
v
∗
]
i
[
`
∗
]
ij
−
[
P
∗
]
2
ij
−
[
Q
∗
]
2
ij
)
−
ε
([
v
∗
]
i
−
r
ij
[
P
∗
]
ij
−
x
ij
[
Q
∗
]
ij
+
ε
(
r
2
ij
+
x
2
ij
)
/
4
)
Since
[
v
∗
]
i
[
`
∗
]
ij
−
[
P
∗
]
2
ij
−
[
Q
∗
]
2
ij
>
0
, we can choose an
ε >
0
sufficiently small such that
̃
`
ij
≥
(
̃
P
2
ij
+
̃
Q
2
ij
)
/
̃
v
i
.
This completes the proof.
Remark 1:
Assumption A3 is used in the proof here
to contradict the optimality of
(ˆ
y
∗
,s
∗
)
. Instead of A3, if
f
(ˆ
y,s
)
is nondecreasing in
`
, the same argument shows
that, given an optimal
(ˆ
y
∗
,s
∗
)
with a strict inequality
[
v
∗
]
i
[
`
∗
]
ij
>
[
P
∗
]
ij
2
+ [
Q
∗
]
ij
2
, one can choose
ε >
0
to
obtain another optimal point
( ̃
y,
̃
s
)
that attains equality
and has a cost
f
( ̃
y,
̃
s
)
≤
f
(ˆ
y
∗
,s
∗
)
. Without A3, there is
always an optimal solution of OPF-cr that is also optimal
for OPF-ar, even though it is possible that the convex
relaxation OPF-cr may also have other optimal points
with strict inequality that are infeasible for OPF-ar.
Remark 2:
The condition in Theorem 1 is equivalent
to the “over-satisfaction of load” condition in [14], [17].
It is needed because we have increased the loads
s
c
∗
on
buses
i
and
j
to obtain the alternative feasible solution
( ̃
y,
̃
s
)
. As we show in the simulations in [42], it is
sufficient but not necessary. See also [35], [36] for exact
conic relaxation of OPF-cr for radial networks where this
condition is replaced by other assumptions.
V. A
NGLE RELAXATION
Theorem 1 justifies solving the convex problem OPF-
cr for an optimal solution of OPF-ar. Given a solution
(ˆ
y,s
)
of OPF-ar, when and how can we recover a
solution
(
x,s
)
of the original OPF (11)–(12)? It depends
on whether we can recover a solution
x
to the branch
flow equations (1)–(3) from
ˆ
y
, given any
s
.
Hence, for the rest of Section V, we fix an
s
. We abuse
notation in this section and write
x,
ˆ
y,θ,
X
,
Y
,
ˆ
Y
instead
of
x
(
s
)
,
ˆ
y
(
s
)
,θ
(
s
)
,
X
(
s
)
,
Y
(
s
)
,
ˆ
Y
(
s
)
respectively.
A. Angle recovery condition
Fix a relaxed solution
ˆ
y
:= (
S,`,v,s
0
)
∈
ˆ
Y
. Define
the
(
n
+ 1)
×
m
incidence matrix
C
of
G
by
C
ie
=
1
if link
e
leaves node
i
−
1
if link
e
enters node
i
0
otherwise
(25)
The first row of
C
corresponds to node
0
where
V
0
=
|
V
0
|
e
i
θ
0
is given. In this paper we will only work with
the
m
×
n
reduced
incidence matrix
B
obtained from
C
by removing the first row (corresponding to
V
0
) and
taking the transpose, i.e., for
e
∈
E,i
= 1
,...,n
,
B
ei
=
1
if link
e
leaves node
i
−
1
if link
e
enters node
i
0
otherwise
,
Since
G
is connected,
m
≥
n
and rank
(
B
) =
n
[43].
Fix any spanning tree
T
= (
N,E
T
)
of
G
. We can
assume without loss of generality (possibly after re-
labeling some of the links) that
E
T
consists of links
e
= 1
,...,n
. Then
B
can be partitioned into
B
=
[
B
T
B
⊥
]
(26)
where the
n
×
n
submatrix
B
T
corresponds to links in
T
and the
(
m
−
n
)
×
n
submatrix
B
⊥
corresponds to links
in
T
⊥
:=
G
\
T
.
Let
β
:=
β
(ˆ
y
)
∈
(
−
π,π
]
m
be defined by:
β
ij
:=
∠
(
v
i
−
z
∗
ij
S
ij
)
,
(
i,j
)
∈
E
(27)
Informally,
β
ij
is the phase angle difference across link
(
i,j
)
that is implied by the relaxed solution
ˆ
y
. Write
β
as
β
=
[
β
T
β
⊥
]
(28)
where
β
T
is
n
×
1
and
β
⊥
is
(
m
−
n
)
×
1
.
Recall the projection mapping
ˆ
h
:
C
2
m
+
n
+1
→
R
3
m
+
n
+2
defined in (17)–(18). For each
θ
:= (
θ
i
,i
=
1
,...,n
)
∈
(
−
π,π
]
n
, define the inverse projection