of 13
IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS, VOL. 1, NO. 2,
JUNE 2014
177
Convex Relaxation of Optimal Power
Flow—Part II: Exactness
Steven H. Low,
Fellow, IEEE
Abstract
—This tutorial summarizes recent advances in the con-
vex relaxation of the optimal power flow (OPF) problem, focusing
on structural properties rather than algorithms. Part I presents
two power flow models, formulates OPF and their relaxations in
each model, and proves equivalence relations among them. Part II
presents sufficient conditions under which the convex relaxations
are exact.
Index Terms
—Convex relaxation, optimal power flow, power
systems, quadratically constrained quadratic program (QCQP),
second-order cone program (SOCP), semidefinite program (SDP),
semidefinite relaxation.
I. I
NTRODUCTION
T
HE OPTIMAL power flow (OPF) problem is fundamental
in power systems since it underlies many applications,
such as economic dispatch, unit commitment, state estimation,
stability and reliability assessment, volt/var control, demand
response, etc. OPF seeks to optimize a certain objective func-
tion, such as power loss, generation cost, and/or user utilities,
subject to Kirchhoff’s laws as well as capacity, stability, and
security constraints on the voltages and power flows. There
has been a great deal of research on OPF since Carpentier’s
first formulation in 1962 [1]. Recent surveys can be found in,
e.g., [2]–[13].
OPF is generally nonconvex and NP-hard, and a large
number of optimization algorithms and relaxations have been
proposed. To the best of our knowledge solving OPF through
semidefinite relaxation is first proposed in [14] as a second-
order cone program (SOCP) for radial (tree) networks and in
[15] as a semidefinite program (SDP) for general networks in
a bus injection model. It is first proposed in [16] and [17] as
an SOCP for radial networks in the branch flow model of [18]
and [19]. While these convex relaxations have been illustrated
numerically in [14] and [15], whether or when they will turn
out to be exact is first studied in [20]. Exploiting graph sparsity
Manuscript received September 23, 2013; revised April 8, 2014. Date of
publication May 14, 2014; date of current version June 16, 2014. This work
was supported in part by NSF through NetSE CNS 0911041, in part by
ARPA-E through GENI DE-AR0000226, Southern California Edison, in part
by the National Science Council of Taiwan through NSC 103-3113-P-008-
001, in part by the Los Alamos National Lab (DoE), and in part by Caltech’s
Resnick Institute. A preliminary and abridged version has appeared in
Proc.
IREP Symp. Bulk Power Syst. Dynam. Control-IX (IREP)
, Rethymnon, Greece
August 25–30, 2013.
The author is with the Engineering and Applied Science (EAS), California
Institute of Technology (Caltech), Pasadena, CA 91125 USA (e-mail: slow@
caltech.edu).
Color versions of one or more of the figures in this paper are available online
at http://ieeexplore.ieee.org.
Digital Object Identifier 10.1109/TCNS.2014.2323634
to simplify the SDP relaxation of OPF is first proposed in [21]
and [22], and analyzed in [23] and [24].
Solving OPF through convex relaxation offers several ad-
vantages, as discussed in Part I of this tutorial [25, Sec. I]. In
particular, it provides the ability to check whether a solution
is globally optimal. If it is not, the solution provides a lower
bound on the minimum cost and, hence, a bound on how far any
feasible solution is from optimality. Unlike approximations, if a
relaxed problem is infeasible, it is a certificate that the original
OPF is infeasible.
This tutorial presents main results on convex relaxations of
OPF developed in the last few years. In Part I [25], we present
the bus injection model (BIM) and the branch flow model
(BFM), formulate OPF within each model, and prove their
equivalence. The complexity of OPF formulated here lies in the
quadratic nature of power flows, i.e., the nonconvex quadratic
constraints on the feasible set of OPF. We characterize these
feasible sets and design convex supersets that lead to three dif-
ferent convex relaxations based on semidefinite programming,
chordal extension, and second-order cone programming. When
a convex relaxation is exact, an optimal solution of the original
nonconvex OPF can be recovered from every optimal solution
of the relaxation. In Part II, we summarize main sufficient
conditions that guarantee the exactness of these relaxations.
Network topology turns out to play a critical role in deter-
mining whether a relaxation is exact. In Section II, we review
the definitions of OPF and their convex relaxations developed
in [25]. We also define the notion of exactness adopted in
this paper. In Section III, we present three types of sufficient
conditions for these relaxations to be exact for radial networks.
These conditions are generally not necessary and they have im-
plications on allowable power injections, voltage magnitudes,
or voltage angles as follows.
A)
Power injections
: These conditions require that not both
constraints on real and reactive power injections be bind-
ing at both ends of a line.
B)
Voltages magnitudes
: These conditions require that the
upper bounds on voltage magnitudes not be binding.
They can be enforced through affine constraints on power
injections.
C)
Voltage angles
: These conditions require that the voltage
angles across each line be sufficiently close. This is
needed also for stability reasons.
These conditions and their references are summarized in
Tables I and II. Some of these sufficient conditions are proved
using BIM and others using BFM. Since these two models are
equivalent (in the sense that there is a linear bijection between
their solution sets [24], [25]), these sufficient conditions apply
2325-5870 © 2014 IEEE. Translations and content mining are permitted for academic research only. Personal use is also permitted, but republication/
redistribution
requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
178
IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS, VOL. 1, NO. 2,
JUNE 2014
TA B L E I
S
UFFICIENT
C
ONDITIONS FOR
R
ADIAL
(T
REE
)N
ETWORKS
TA B L E I I
S
UFFICIENT
C
ONDITIONS FOR
M
ESH
N
ETWORKS
to both models. The proofs of these conditions typically do
not require that the cost function be convex (they focus on
the feasible sets and usually only need the cost function to
be monotonic). Convexity is required, however, for efficient
computation. Moreover, it is proved in [35] using BFM that
when the cost function is convex, then exactness of the SOCP
relaxation implies uniqueness of the optimal solution for radial
networks. Hence, the equivalence of BIM and BFM implies
that any of the three types of sufficient conditions guarantees
that, for a radial network with a convex cost function, there is a
unique optimal solution and it can be computed by solving an
SOCP. Since the SDP and chordal relaxations are equivalent to
the SOCP relaxation for radial networks [24], [25], these results
apply to all three types of relaxations. Empirical evidence
suggests that some of these conditions are likely satisfied in
practice. This is important as most power distribution systems
are radial.
These conditions are insufficient for general mesh networks
because they cannot guarantee that an optimal solution of
a relaxation satisfies the cycle condition discussed in [25].
In Section IV, we show that these conditions are, however,
sufficient for mesh networks that have tunable phase shifters at
strategic locations. The phase shifters effectively make a mesh
network behave like a radial network as far as convex relaxation
is concerned. The result can help determine whether a network
with a given set of phase shifters can be convexified and, if not,
where additional phase shifters are needed for convexification.
These conditions are also sufficient for direct current (dc) mesh
networks where all variables are in the real rather than complex
domain. Counterexamples are known where SDP relaxation
is not exact, especially for ac mesh networks without tunable
phase shifters [42]–[44]. We discuss three recent approaches
for global optimization of OPF when the relaxations discussed
in this tutorial fail.
We conclude in Section V. All proofs can be found in the
original papers or the arXiv version of this paper.
II. OPF
AND
I
TS
R
ELAXATIONS
We use the notations and definitions from Part I of this paper.
In this section, we summarize the OPF problems and their
relaxations developed there; see [25] for details.
We adopt in this paper a strong sense of “exactness” where
we require the optimal solution set of the OPF problem and
that of its relaxation to be equivalent. This implies that an
optimal solution of the nonconvex OPF problem can be re-
covered from
every
optimal solution of its relaxation. This
is important because it ensures any algorithm that solves an
exact relaxation always produces a globally optimal solution to
the OPF problem. Indeed, interior point methods for solving
SDPs tend to produce a solution matrix with a maximum
rank [45], so can miss a rank-1 solution if the relaxation has
non-rank-1 solutions as well. It can be difficult to recover
an optimal solution of OPF from such a non-rank-1 solution,
and our definition of exactness avoids this complication. See
Section II-C for detailed justifications.
A. Bus Injection Model
The BIM adopts an undirected graph
G
1
and can be formu-
lated in terms of just the complex voltage vector
V
C
n
+1
.
The feasible set is described by the following constraints:
s
j

k
:(
j,k
)
E
y
H
jk
V
j

V
H
j
V
H
k

s
j
,j
N
+
(1a)
v
j
≤|
V
j
|
2
v
j
,j
N
+
(1b)
where
s
j
,
s
j
,v
j
,
v
j
, possibly
±∞ ±
i
, are given bounds on
power injections and voltage magnitudes. Note that the vector
V
includes
V
0
which is assumed given (
v
0
=
v
0
and
V
0
=0
)
unless otherwise specified.
The problem of interest is
OPF
:
min
V
C
n
+1
C
(
V
)
subject to
V
satisfies (1)
.
(2)
For relaxations, consider the partial matrix
W
G
defined on
the network graph
G
that satisfies
s
j

k
:(
j,k
)
E
y
H
jk

[
W
G
]
jj
[
W
G
]
jk

s
j
,j
N
+
(3a)
v
j
[
W
G
]
jj
v
j
,j
N
+
.
(3b)
1
We will use “bus” and “node” interchangeably and “line” and “link”
interchangeably.
LOW: CONVEX RELAXATION OF O
PF—PART II
179
We say that
W
G
satisfies the
cycle condition
if for every
cycle
c
in
G

(
j,k
)
c
[
W
G
]
jk
=0 mod 2
π.
(4)
We assume the cost function
C
depends on
V
only through
VV
H
and use the same symbol
C
to denote the cost in terms of
a full or partial matrix. Moreover, we assume
C
depends on the
matrix only through the submatrix
W
G
defined on the network
graph
G
. See [25] for more details including the definitions of
W
c
(
G
)

0
and
W
G
(
j, k
)

0
. Define the convex relaxations
OPF
-
sdp
:
min
W
S
n
+1
C
(
W
G
)
subject to
W
G
satisfies (3)
,W

0
(5)
OPF
-
ch
:
min
W
c
(
G
)
C
(
W
G
)
subject to
W
G
satisfies (3)
,W
c
(
G
)

0
(6)
OPF
-
socp
:
min
W
G
C
(
W
G
)
subject to
W
G
satisfies (3)
,
W
G
(
j, k
)

0
,
(
j, k
)
E.
(7)
For BIM, we say that OPF-sdp (5) is
exact
if every optimal
solution
W
sdp
of OPF-sdp is psd rank-1; OPF-ch (6) is
exact
if
every optimal solution
W
ch
c
(
G
)
of OPF-ch is psd rank-1 (i.e., the
principal submatrices
W
ch
c
(
G
)
(
q
)
of
W
ch
c
(
G
)
are psd rank-1 for all
maximal cliques
q
of the chordal extension
c
(
G
)
of graph
G
);
OPF-socp (7) is
exact
if every optimal solution
W
socp
G
of OPF-
socp is 2
×
2 psd rank-1 and satisfies the cycle condition (4).
To recover an optimal solution
V
opt
of OPF (2) from
W
sdp
or
W
ch
c
(
G
)
or
W
socp
G
, see [25, Sec. IV-D].
B. Branch Flow Model
The BFM adopts a directed graph
̃
G
and is defined by the
following set of equations:

k
:
j
k
S
jk
=

i
:
i
j

S
ij
z
ij
|
I
ij
|
2

+
s
j
,j
N
+
(8a)
I
jk
=
y
jk
(
V
j
V
k
)
,j
k
̃
E
(8b)
S
jk
=
V
j
I
H
jk
,j
k
̃
E.
(8c)
Denote the variables in BFM (8) by
̃
x
:= (
S, I, V, s
)
C
2(
m
+
n
+1)
. Note that the vectors
V
and
s
include
V
0
(given)
and
s
0
, respectively. Recall from [25] the variables
x
:=
(
S, , v, s
)
R
3(
m
+
n
+1)
that are related to
̃
x
by the mapping
x
=
h
( ̃
x
)
with

jk
:=
|
I
jk
|
2
and
v
j
:=
|
V
j
|
2
. The operational
constraints are
v
j
v
j
v
j
,j
N
+
(9a)
s
j
s
j
s
j
,j
N
+
.
(9b)
We assume the cost function depends on
̃
x
only through
x
=
h
( ̃
x
)
. Then the problem in BFM is
OPF
:
min
̃
x
C
(
x
)
subject to
̃
x
satisfies (8), (9)
.
(10)
For SOCP relaxation, consider

k
:
j
k
S
jk
=

i
:
i
j
(
S
ij
z
ij

ij
)+
s
j
,j
N
+
(11a)
v
j
v
k
=2Re

z
H
jk
S
jk

−|
z
jk
|
2

jk
,j
k
̃
E
(11b)
v
j

jk
≥|
S
jk
|
2
,j
k
̃
E.
(11c)
We say that
x
satisfies the
cycle condition
if
θ
R
n
such that
=
β
(
x
)mod2
π
(12)
where
B
is the
m
×
n
reduced incidence matrix and, given
x
:= (
S, , v, s
)
,
β
jk
(
x
):=
(
v
j
z
H
jk
S
jk
)
can be interpreted
as the voltage angle difference across line
j
k
implied by
x
(See [25, Sec. V]). The SOCP relaxation in BFM is
OPF
-
socp
:
min
x
C
(
x
)
subject to
x
satisfies (11), (9)
.
(13)
For BFM, OPF-socp (13) in BFM is
exact
if every optimal
solution
x
socp
attains equality in (11c) and satisfies the cycle
condition (12). See [25, Sec. V-A] on how to recover an optimal
solution
̃
x
opt
of OPF (10) from any optimal solution
x
socp
of
its SOCP relaxation.
C. Exactness
The definition of exactness adopted in this paper is more
stringent than needed. Consider SOCP relaxation in BIM as an
illustration (the same applies to the other relaxations in BIM
and BFM). For any sets
A
and
B
, we say that
A
is
equivalent
to
B
, denoted by
A
B
, if there is a bijection between these
two sets. Let
M
(
A
)
denote the set of minimizers when a certain
function is minimized over
A
.
Let
V
and
W
+
G
denote the feasible sets of OPF (2) and OPF-
socp (7), respectively:
V
:=

V
C
n
+1
|
V
satisfies (1)

W
+
G
:=
{
W
G
|
W
G
satisfies (3)
,W
G
(
j, k
)

0
,
(
j, k
)
E
}
.
Consider the following subset of
W
+
G
:
W
G
:=
{
W
G
|
W
G
satisfies (3), (4)
,W
G
(
j, k
)

0
,
rank
W
G
(
j, k
)=1
,
(
j, k
)
E
}
.
Our definition of exact SOCP relaxation is that
M
(
W
+
G
)
W
G
.
In particular,
all
optimal solutions of OPF-socp must be 2
×
2
psd rank-1 and satisfy the cycle condition (4). Since
W
G
V
(see [25]), exactness requires that the set of optimal solutions of
OPF-socp (7) be equivalent to that of OPF (2), i.e.,
M
(
W
+
G
)=
M
(
W
G
)
M
(
V
)
.
180
IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS, VOL. 1, NO. 2,
JUNE 2014
If
M
(
W
+
G
)
M
(
W
G
)
M
(
V
)
, then OPF-socp (7) is not
exact according to our definition. Even in this case, however,
every sufficient condition in this paper guarantees that an opti-
mal solution of OPF can be easily recovered from an optimal
solution of the relaxation that is outside
W
G
. The difference
between
M
(
W
+
G
)=
M
(
W
G
)
and
M
(
W
+
G
)
M
(
W
G
)
is often
minor, depending on the objective function; see Remarks 1
and 2 and comments after Theorems 5 and 8 in Section III.
Hence, we adopt the more stringent definition of exactness for
simplicity.
III. R
ADIAL NETWORKS
In this section, we summarize the three types of sufficient
conditions listed in Table I for semidefinite relaxations of
OPF to be exact for radial (tree) networks. These results are
important since most distribution systems are radial.
For radial networks, if SOCP relaxation is exact, then SDP
and chordal relaxations are also exact (see [25, Theor. 5, 9]).
We hence focus in this section on the exactness of OPF-socp in
both BIM and BFM. Since the cycle conditions (4) and (12) are
vacuous for radial networks, OPF-socp (7) is exact if all of its
optimal solutions are 2
×
2 rank-1 and OPF-socp (13) is exact
if all of its optimal solutions attain equalities in (11c). We will
freely use either BIM or BFM in discussing these results. To
avoid triviality, we make the following assumption throughout
this paper:
The voltage lower bounds satisfy
v
j
>
0
,
j
N
+
. The orig-
inal problems OPF (2) and (10) are feasible.
A. Linear Separability
We will first present a general result on the exactness of
the SOCP relaxation of general QCQP and then apply it to
OPF. This result is first formulated and proved using a duality
argument in [27], generalizing the result of [26]. It is proved
using a simpler argument in [31].
Fix an undirected graph
G
=(
N
+
,E
)
, where
N
+
:=
{
0
,
1
,...,n
}
and
E
N
+
×
N
+
. Fix Hermitian matrices
C
l
S
n
+1
,
l
=0
,...,L
, defined on
G
, i.e.,
[
C
l
]
jk
=0
if
(
j, k
)
E
. Consider QCQP
min
x
C
n
+1
x
H
C
0
x
(14a)
subject to
x
H
C
l
x
b
l
,l
=1
,...,L
(14b)
where
C
0
,C
l
C
(
n
+1)
×
(
n
+1)
,
b
l
R
,
l
=1
,...,L
, and its
SOCP relaxation where the optimization variable ranges over
Hermitian partial matrices
W
G
min
W
G
tr
C
0
W
G
(15a)
subject to
tr
C
l
W
G
b
l
,l
=1
,...,L
(15b)
W
G
(
j, k
)

0
,
(
j, k
)
E.
(15c)
The following result is proved in [27] and [31]. It can be
regarded as an extension of [46] on the SOCP relaxation of
Fig. 1. Condition A2

on a line
(
j, k
)
E
. The quantities
([Φ
j
]
jk
,
k
]
jk
,
j
]
jk
,
k
]
jk
)
on the left-half plane correspond to finite upper bounds on
(
p
j
,p
k
,q
j
,q
k
)
in (16a) and (16b);
(
j
]
jk
,
k
]
jk
,
j
]
jk
,
k
]
jk
)
on the right-half plane correspond to finite lower bounds on
(
p
j
,p
k
,q
j
,q
k
)
.
A2

is satisfied if there is a line through the origin, specified by the angle
α
jk
, so that the quantities corresponding to
finite
upper or lower bounds on
(
p
j
,p
k
,q
j
,q
k
)
lie on one side of the line, possibly on the line itself. The
load over-satisfaction condition in [26], [30] corresponds to the Im-axis that
excludes all quantities on the right-half plane. The sufficient condition in [29,
Theor. 2] corresponds to the red line in the figure that allows a finite lower
bound on the real power at one end of the line, i.e.,
p
j
or
p
k
but not both, and
no finite lower bounds on reactive powers
q
j
and
q
k
.
QCQP from the real domain to the complex domain. Consider
(see Fig. 1 for an illustration)
2
:
A1: The cost matrix
C
0
is positive definite.
A2: For each link
(
j, k
)
E
, there exists an
α
jk
such that
[
C
l
]
jk
[
α
ij
ij
+
π
]
for all
l
=0
,...,L
.
Let
C
opt
and
C
socp
denote the optimal values of QCQP (14)
and SOCP (15), respectively.
Theorem 1:
Suppose
G
is a tree and A2 holds. Then
C
opt
=
C
socp
and an optimal solution of QCQP (14) can be recovered
from every optimal solution of SOCP (15).
Remark 1:
The proof of Theorem 1 prescribes a simple pro-
cedure to recover an optimal solution of QCQP (14) from any
optimal solution of its SOCP relaxation (15). The construction
does not need the optimal solution of SOCP (15) to be 2
×
2
rank-1. Hence, the SOCP relaxation may not be exact according
to our definition of exactness, i.e., some optimal solutions of
(15) may be 2
×
2 psd but not 2
×
2 rank-1. If the objective
function is strictly convex, however, then the optimal solution
sets of QCQP (14) and SOCP (15) are indeed equivalent.
Corollary 2:
Suppose
G
is a tree and A1–A2 hold. Then
SOCP (15) is exact.
We now apply Theorem 1 to our OPF problem in a standard
form QCQP [27]
min
x
C
n
V
H
C
0
V
s.t.
V
H
Φ
j
V
p
j
,V
H
(
Φ
j
)
V
≤−
p
j
(16a)
V
H
Ψ
j
V
q
j
,V
H
(
Ψ
j
)
V
≤−
q
j
(16b)
V
H
J
j
V
≤−
v
j
,V
H
(
J
j
)
V
≤−
v
j
2
All angles should be interpreted as “mod
2
π
”, i.e., projected onto
(
π,π
]
.
LOW: CONVEX RELAXATION OF O
PF—PART II
181
for some Hermitian matrices
C
0
,
Φ
j
,
Ψ
j
,J
j
where
j
N
+
.A2
depends only on the off-diagonal entries of
C
0
,
Φ
j
,
Ψ
j
(
J
j
are
diagonal matrices). It implies a simple pattern on the power
injection constraints (16a), (16b). Let
y
jk
=
g
jk
i
b
jk
with
g
jk
>
0
,b
jk
>
0
. Then we have (from [27])
k
]
ij
=
1
2
Y
ij
=
1
2
(
g
ij
i
b
ij
)
if
k
=
i
1
2
Y
H
ij
=
1
2
(
g
ij
+
i
b
ij
)
if
k
=
j
0
if
k
∈{
i, j
}
k
]
ij
=
1
2
i
Y
ij
=
1
2
(
b
ij
+
i
g
ij
)
if
k
=
i
1
2
i
Y
H
ij
=
1
2
(
b
ij
i
g
ij
)
if
k
=
j
0
if
k
∈{
i, j
}
.
Hence, for each line
(
j, k
)
E
, the relevant angles for A2 are
those of
[
C
0
]
jk
and
j
]
jk
=
1
2
(
g
jk
i
b
jk
)
k
]
jk
=
1
2
(
g
jk
+
i
b
jk
)
j
]
jk
=
1
2
(
b
jk
+
i
g
jk
)
k
]
jk
=
1
2
(
b
jk
i
g
jk
)
as well as the angles of
j
]
jk
,
k
]
jk
and
j
]
jk
,
k
]
jk
. These quantities are shown in Fig. 1 with their
magnitudes normalized to a common value and explained in
the caption of the figure.
Condition A2 applied to OPF (16) takes the following form
(see Fig. 1):
A2
: For each link
(
j, k
)
E
, there is a line in the complex
plane through the origin such that
[
C
0
]
jk
as well as those
±
i
]
jk
and
±
i
]
jk
corresponding to
finite
lower or upper
bounds on
(
p
i
,q
i
)
,for
i
=
j, k
, are all on one side of the
line, possibly on the line itself.
Let
C
opt
and
C
socp
denote the optimal values of OPF (2) and
OPF-socp (7), respectively.
Corollary 3:
Suppose
G
isatreeandA2
holds.
1)
C
opt
=
C
socp
. Moreover, an optimal solution
V
opt
of
OPF (2) can be recovered from every optimal solution
W
socp
G
of OPF-socp (7).
2) If, in addition, A1 holds, then OPF-socp (7) is exact.
It is clear from Fig. 1 that condition A2
cannot be satisfied
if there is a line where the real and reactive power injec-
tions at both ends are both lower and upper bounded (eight
combinations as shown in the figure). A2
requires that some
of them be unconstrained even though in practice they are
always bounded. It should be interpreted as requiring that the
optimal solutions obtained by ignoring these bounds turn out
to satisfy these bounds. This is generally different from solving
the optimization
with
these constraints but requiring that they
be inactive (strictly within these bounds) at optimality, unless
the cost function is strictly convex. The result proved in [27]
also includes constraints on real branch power flows and line
losses. Corollary 3 includes several sufficient conditions in the
literature for exact relaxation as special cases; see the caption
of Fig. 1.
Corollary 3 also implies a result first proved in [16], using
a different technique, that SOCP relaxation is exact in BFM
for radial networks when there are no lower bounds on power
injections
s
j
. The argument in [16] is generalized in [17, Part I]
to allow convex objective functions, shunt elements, and line
limits in terms of upper bounds on

jk
. Assume
A3: The cost function
C
(
x
)
is convex, strictly increasing in

, nondecreasing in
s
=(
p, q
)
, and independent of branch
flows
S
=(
P,Q
)
.
A4: For
j
N
+
,
s
j
=
−∞ −
i
.
Popular cost functions in the literature include active power
loss over the network or active power generations, both of
which satisfy A3. The next result is proved in [16] and [17].
Theorem 4:
Suppose
̃
G
is a tree and A3–A4 hold. Then OPF-
socp (13) is exact.
Remark 2:
If the cost function
C
(
x
)
in A3 is only nonde-
creasing, rather than strictly increasing, in

, then A3–A4 still
guarantee that all optimal solutions of OPF (10) are (i.e., can be
mapped to) optimal solutions of OPF-socp (13), but OPF-socp
may have an optimal solution that maintains strict inequalities
in (11c) and, hence, is infeasible for OPF. Even though OPF-
socp is not exact in this case, the proof of Theorem 4 constructs
from it an optimal solution of OPF. (See the proof in the arXiv
version of this paper.)
B. Voltage Upper Bounds
While type A conditions require that some power injection
constraints not be binding, type B conditions require non-
binding voltage upper bounds. They are proved in [32]–[35]
using BFM.
For radial networks, the model originally proposed in [18]
and [19], which is (11) with the inequalities in (11c) replaced by
equalities, is exact. This is because the cycle condition (12) is
always satisfied since the reduced incidence matrix
B
is
n
×
n
and invertible for radial networks. Following [35], we adopt the
graph orientation where every link points
towards
node 0. Then
(11) for a radial network reduces to
S
jk
=

i
:
i
j
(
S
ij
z
ij

ij
)+
s
j
,j
N
+
(17a)
v
j
v
k
=2Re

z
H
jk
S
jk

−|
z
jk
|
2

jk
,j
k
̃
E
(17b)
v
j

jk
≥|
S
jk
|
2
,j
k
̃
E
(17c)
where
v
0
is given and in (17a),
k
denotes the node on the unique
path from node
j
to node 0. The boundary condition is
S
jk
:= 0
when
j
=0
in (17a) and
S
ij
=0
,

ij
=0
when
j
is a leaf
node.
3
As before, the voltage magnitudes must satisfy
v
j
v
j
v
j
,j
N.
(18a)
We allow more general constraints on the power injections: they
can be in an
arbitrary
set
S
j
that is bounded above
s
j
S
j
⊆{
s
j
C
|
s
j
s
j
}
,j
N
(18b)
3
A node
j
N
is a
leaf node
if there is no
i
such that
i
j
̃
E
.
182
IEEE TRANSACTIONS ON CONTROL OF NETWORK SYSTEMS, VOL. 1, NO. 2,
JUNE 2014
Fig. 2.
Feasible set of OPF for a two-bus network without any constraint. It
consists of the (two) points of intersection of the line with the convex surface
(without the interior) and, hence, is nonconvex. SOCP relaxation includes the
interior of the convex surface and enlarges the feasible set to the line segment
joining these two points. If the cost function
C
is increasing in

or
(
p
0
,q
0
)
,
then the optimal point over the SOCP feasible set (line segment) is the lower
feasible point
c
and, hence, the relaxation is exact. No constraint on

or
(
p
0
,q
0
)
will destroy exactness as long as the resulting feasible set contains
c
.
for some given
s
j
,
j
N
.
4
Then the SOCP relaxation is
OPF
-
socp
:
min
x
C
(
x
)
subject to (17), (18)
.
(19)
OPF-socp (19) is exact if every optimal solution
x
socp
attains
equality in (17c). In that case, an optimal solution of BFM (10)
can be uniquely recovered from
x
socp
.
We make two comments on
S
j
in (18b). First,
S
j
need
not be convex nor even connected for convex relaxations to
be exact. They (only) need to be convex to be efficiently
computable. Second, such a general constraint on
s
is useful in
many applications. It includes the case where
s
j
are subject to
simple box constraints, but also allows constraints of the form
|
s
j
|
2
a
,
|
s
j
|≤
φ
j
that is useful for volt/var control [47], or
q
j
∈{
0
,a
}
for capacitor configurations.
Geometric Insight:
To motivate condition B2 below, we
first explain a simple intuition using a two-bus network on
why relaxing voltage upper bounds guarantees exact SOCP
relaxation. Consider bus 0 and bus 1 connected by a line with
impedance
z
:=
r
+
i
x
. Suppose without loss of generality that
v
0
=1
p.u. Eliminating
S
01
=
s
0
from (17), the model reduces
to (dropping the subscript on

01
)
p
0
r
=
p
1
,q
0
x
=
q
1
,p
2
0
+
q
2
0
=

(20)
and
v
1
v
0
=2(
rp
0
+
xq
0
)
−|
z
|
2
.
(21)
Suppose
s
1
is given (e.g., a constant power load). Then the
variables are
(
, v
1
,p
0
,q
0
)
and the feasible set consists of
solutions of (20) and (21) subject to additional constraints on
(
, v
1
,p
0
,q
0
)
. The case without any constraint is instructive
and shown in Fig. 2 (see explanation in the caption). The
point
c
in the figure corresponds to a power flow solution with
a large
v
1
(normal operation) whereas the other intersection
corresponds to a solution with a small
v
1
(fault condition). As
explained in the caption, SOCP relaxation is exact if there is no
4
We assume here that
s
0
is unconstrained, and since
V
0
:= 1
0
p.u., the
constraints (18) involve only
j
in
N
, not
N
+
.
Fig. 3. Impact of voltage upper bound
v
1
on exactness. (a) When
v
1
(corre-
sponding to a lower bound on

) is not binding, the power flow solution
c
is
in the feasible set of SOCP and, hence, the relaxation is exact. (b) When
v
1
excludes
c
from the feasible set of SOCP, the optimal solution is infeasible for
OPF and the relaxation is not exact.
voltage constraint and as long as constraints on
(
, p
0
,q
0
)
do
not remove the high-voltage solution
c
. Only when the system
is stressed so much that
c
becomes infeasible will relaxation
lose exactness. This agrees with the conventional wisdom that
power systems under normal operations are well behaved.
Consider now the voltage constraint
v
1
v
1
v
1
. Substi-
tuting (20) into (21), we obtain
v
1
=(1+
rp
1
+
xq
1
)
−|
z
|
2

translating the constraint on
v
1
into a box constraint on

1
|
z
|
2
(
rp
1
+
xq
1
+1
v
1
)

1
|
z
|
2
(
rp
1
+
xq
1
+1
v
1
)
.
Fig. 2 shows that the lower bound
v
1
(corresponding to an upper
bound on

) does not affect the exactness of SOCP relaxation.
The effect of upper bound
v
1
(corresponding to a lower bound
on

) is illustrated in Fig. 3. As explained in the caption of the
figure, SOCP relaxation is exact if the upper bound
v
1
does not
exclude the high-voltage solution
c
and is not exact otherwise.
For a general radial network, recall from [25, Sec. VI] the
linear approximation of BFM for radial networks obtained by
setting

jk
=0
in (17): for each
s
S
lin
jk
(
s
)=

i
T
j
s
i
(22a)
v
lin
j
(
s
)=
v
0
+2

(
i,k
)
P
j
Re

z
H
ik
S
lin
ik
(
s
)

(22b)
where
T
j
denotes the subtree at node
j
, including
j
, and
P
j
denotes the set of links on the unique path from
j
to 0. The key
property we will use is from [25, Lemma 13 and Remark 9]:
S
jk
S
lin
jk
(
s
)
and
v
j
v
lin
j
(
s
)
.
(23)
Define the 2
×
2 matrix function
A
jk
(
S
jk
,v
j
):=
I
2
v
j
z
jk
(
S
jk
)
T
(24)
where
z
jk
:= [
r
jk
x
jk
]
T
is the line impedance and
S
jk
:=
[
P
jk
Q
jk
]
T
is the branch power flows, both taken as real
vectors so that
z
jk
(
S
jk
)
T
is a 2
×
2matrixwitharankless
or equal to 1. The matrices
A
jk
(
S
jk
,v
j
)
describe how changes
LOW: CONVEX RELAXATION OF O
PF—PART II
183
in branch power flows propagate towards the root node 0; see
comments below. Evaluate the Jacobian matrix
A
jk
(
S
jk
,v
j
)
at
the boundary values
A
jk
:=
A
jk

S
lin
jk
(
s
)
+
,v
j

:=
I
2
v
j
z
jk

S
lin
jk
(
s
)
+

T
.
(25)
Here
([
a
]
+
)
T
is the row vector
[[
a
1
]
+
[
a
2
]
+
]
with
[
a
j
]
+
:=
max
{
0
,a
j
}
.
For a radial network, for
j
=0
, every link
j
k
identifies a
unique node
k
and, therefore, to simplify notation, we refer to
a link interchangeably by
(
j, k
)
or
j
and use
A
j
,
A
j
,
z
j
,etc.in
place of
A
jk
,
A
jk
,
z
jk
, etc., respectively. Assume
B1: The cost function is
C
(
x
):=

n
j
=0
C
j
(Re
s
j
)
with
C
0
strictly increasing. There is no constraint on
s
0
.
B2: The set
S
j
of injections satisfies
v
lin
j
(
s
)
v
j
,
j
N
,
where
v
lin
j
(
s
)
is given by (22).
B3: For each leaf node
j
N
, let the unique path from
j
to
0have
k
links and be denoted by
P
j
:= ((
i
k
,i
k
1
)
,...,
(
i
1
,i
0
))
with
i
k
=
j
and
i
0
=0
. Then
A
i
t
···
A
i
t
z
i
t
+1
>
0
for all
1
t
t
<k
.
The following result is proved in [35].
Theorem 5:
Suppose
̃
G
is a tree and B1–B3 hold. Then OPF-
socp (19) is exact.
We now comment on the conditions B1–B3. B1 requires
that the cost functions
C
j
depend only on the injections
s
j
.
For instance, if
C
j
(Re
s
j
)=
p
j
, then the cost is total active
power loss over the network. It also requires that
C
0
be strictly
increasing but makes no assumption on
C
j
,j >
0
. Common
cost functions, such as line loss or generation cost, usually
satisfy B1. If
C
0
is only nondecreasing, rather than strictly
increasing, in
p
0
, then B1–B3 still guarantee that all optimal
solutions of OPF (10) are (effectively) optimal for OPF-socp
(19), but OPF-socp may not be exact, i.e., it may have an
optimal solution that maintains strict inequalities in (17c). In
this case, the proof of Theorem 5 can construct from it another
optimal solution that attains equalities in (17c).
B2 is affine in the injections
s
:= (
p, q
)
. It enforces the upper
bounds on voltage magnitudes because of (23).
B3 has a simple interpretation: the power flows
S
jk
on all
branches should move in the same direction. Specifically, given
a marginal change in the complex power on line
j
k
,the
2
×
2matrix
A
jk
is (a lower bound on) the Jacobian and
describes the effect of this marginal change on the complex
power on the line immediately upstream from line
j
k
.The
product of
A
i
in B3 propagates this effect upstream toward the
root. B3 requires that a small change, positive or negative, in
the power flow on a line affects
all
upstream branch powers in
the same direction. This seems to hold with a significant margin
in practice; see [35] for examples from real systems.
Theorem 5 unifies and generalizes some earlier results in
[32]–[34]. The sufficient conditions in these papers have the
following simple and practical interpretation: OPF-socp is exact
provided either
• there are no reverse power flows in the network, or
•ifthe
r/x
ratios on all lines are equal, or
•ifthe
r/x
ratios increase in the downstream direction from
the substation (node 0) to the leaves, then there are no
reverse real power flows, or
•ifthe
r/x
ratios decrease in the downstream direction, then
there are no reverse reactive power flows.
The exactness of SOCP relaxation does not require con-
vexity, i.e., the cost
C
(
x
)=

n
j
=0
C
j
(Re
s
j
)
need not be a
convex function and the injection regions
S
j
need not be
convex sets. Convexity allows polynomial-time computation.
Moreover, when it is convex, the exactness of SOCP relaxation
also implies the uniqueness of the optimal solution, as the
following result from [35] shows.
Theorem 6:
Suppose
̃
G
is a tree. Suppose the costs
C
j
,
j
=0
,...,n
, are convex functions and the injection regions
S
j
,
j
=1
,...,n
, are convex sets. If the relaxation OPF-socp (19)
is exact, then its optimal solution is unique.
Consider the model of [18] for radial networks, which is
(17) with the inequalities in (17c) replaced by equalities. Let
X
denote an equivalent feasible set of OPF,
5
i.e., those
x
R
3(
m
+
n
+1)
that satisfy (17), (18), and attain equalities in (17c).
The proof of Theorem 6 reveals that, for radial networks, the
feasible set
X
has a “hollow” interior.
Corollary 7:
Suppose
̃
G
is a tree. If
ˆ
x
and
̃
x
are distinct
solutions in
X
, then no convex combination of
ˆ
x
and
̃
x
can be
in
X
. In particular,
X
is nonconvex.
This property is illustrated vividly in several numerical ex-
amples for mesh networks in [48]–[51].
C. Angle Differences
The sufficient conditions in [29], [36], and [37] require that
the voltage angle difference across each line be small. We
explain the intuition using a result in [36] for an OPF problem
where
|
V
j
|
are fixed for all
j
N
+
and reactive powers are
ignored. Under these assumptions, as long as the voltage angle
difference is small, the power flow solutions form a locally con-
vex surface that is the Pareto front of its relaxation. This implies
that the relaxation is exact. This geometric picture is apparent in
earlier work on the geometry of power flow solutions, see e.g.,
[48], and underlies the intuition that the dynamics of a power
system are usually benign until it is pushed towards the bound-
ary of its stability region. The geometric insight in Figs. 2 and
3 for BFM and later in this subsectionfor BIM says that, when
it is far away from the boundary, the local convexity structure
also facilitates exact relaxation. Reactive power is considered
in [37, Theor. 1] with fixed
|
V
j
|
where, with an additional
constraint on the lower bounds of reactive power injections that
ensure these lower bounds are not tight, it is proved that if
the original OPF problem is feasible, then its SDP relaxation
is exact. The case of variable
|
V
j
|
without reactive power is
considered in [36, Theor. 7] but the simple geometric structure
is lost.
5
There is a bijection between
X
and the feasible set of OPF (10) [when (18b)
is replaced by (9b)] [17], [25].