of 51
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, JUNE 2014 (WITH PROOFS)
1
Convex Relaxation of Optimal Power Flow
Part II: Exactness
Steven H. Low
Electrical Engineering, Computing+Mathematical Sciences
Engineering and Applied Science, Caltech
slow@caltech.edu
May 1, 2014
Abstract
This tutorial summarizes recent advances in the convex 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.
Citation:
IEEE Transactions on Control of Network Systems, June 2014.
This is an extended version with Appendex VI that proves
the main results in this tutorial. All proofs can be found in their original papers. We provide proofs here because (i) it is convenient to
have all proofs in one place and in a uniform notation, and (ii) some of the formulations and presentations here are slightly different from
those in the original papers.
A preliminary and abridged version has appeared in Proceedings of the IREP Symposium - Bulk Power System Dynamics and Control -
IX, Rethymnon, Greece, August 25-30, 2013.
arXiv:1405.0814v1 [math.OC] 5 May 2014
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, JUNE 2014 (WITH PROOFS)
2
C
ONTENTS
I
Introduction
3
II OPF and its relaxations
5
II-A
Bus injection model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
II-B
Branch flow model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
II-C
Exactness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
III Radial networks
8
III-A
Linear separability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
III-B
Voltage upper bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
III-C
Angle differences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
III-D
Equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
IV Mesh networks
20
IV-A
AC networks with phase shifters . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
IV-B
DC networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
IV-C
General AC networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
V
Conclusion
25
VI Appendix: proofs
26
VI-A
Proof of Theorem 1 and Corollary 2: linear separability . . . . . . . . . . . . . . 26
VI-B
Proof of Theorem 4: no injection lower bounds (BFM) . . . . . . . . . . . . . . . 28
VI-C
Proof of Theorem 5: voltage upper bounds . . . . . . . . . . . . . . . . . . . . . 29
VI-D
Proof of Theorem 6: uniqueness of SOCP solution . . . . . . . . . . . . . . . . . 36
VI-E
Proof of Corollary 7: hollow feasible set . . . . . . . . . . . . . . . . . . . . . . . 37
VI-F
Proof of Theorem 8: angle difference . . . . . . . . . . . . . . . . . . . . . . . . 37
VI-G
Proof of Theorem 10: mesh networks with phase shifters . . . . . . . . . . . . . 46
References
49
Acknowledgment.
We thank the support of NSF through NetSE CNS 0911041, ARPA-E through GENI
DE-AR0000226, Southern California Edison, the National Science Council of Taiwan through NSC 103-
3113-P-008-001, the Los Alamos National Lab (DoE), and Caltech’s Resnick Institute.
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, JUNE 2014 (WITH PROOFS)
3
I. I
NTRODUCTION
The optimal power flow (OPF) problem is fundamental in power systems as it underlies many
applications such as economic dispatch, unit commitment, state estimation, stability and reliability
assessment, volt/var control, demand response, etc. OPF seeks to optimize a certain objective function,
such as power loss, generation cost and/or user utilities, subject to Kirchhoff’s laws as well as capacity,
stability and security constraints on the voltages and power flows. There has been a great deal of research
on OPF since Carpentier’s first formulation in 1962 [1]. Recent surveys can be found in, e.g., [2], [3],
[4], [5], [6], [7], [8], [9], [10], [11], [12], [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], [17] as an SOCP for radial networks in the branch flow model of [18], [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 to simplify the SDP relaxation of
OPF is first proposed in [21], [22] and analyzed in [23], [24].
Solving OPF through convex relaxation offers several advantages, as discussed in Part I of this tutorial
[25, Section I]. In particular it provides the ability to check if a solution is globally optimal. If it is not,
the solution provides a lower bound on the minimum cost and hence a bound on how far any feasible
solution is from optimality. Unlike approximations, if a relaxed problem is infeasible, it is a certificate
that the original OPF is infeasible.
This tutorial presents main results on convex relaxations of OPF developed in the last few years. In
Part I [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 different
convex relaxations based on semidefinite programming (SDP), chordal extension, and second-order cone
programming (SOCP). When a convex relaxation is exact, an optimal solution of the original nonconvex
OPF can be recovered from every optimal solution of the relaxation. In Part II we summarize main
sufficient conditions that guarantee the exactness of these relaxations.
Network topology turns out to play a critical role in determining whether a relaxation is exact. In
Section II we review the definitions of OPF and their convex relaxations developed in [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 implications on allowable power injections, voltage magnitudes, or voltage
angles:
A
Power injections:
These conditions require that not both constraints on real and reactive power
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, JUNE 2014 (WITH PROOFS)
4
injections be binding 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
type
condition
model
reference
remark
A
power injections
BIM, BFM
[26], [27], [28], [29], [30]
[31], [16], [17]
B
voltage magnitudes
BFM
[32], [33], [34], [35]
allows general injection region
C
voltage angles
BIM
[36], [37]
makes use of branch power flows
TABLE I: Sufficient conditions for radial (tree) networks.
network
condition
reference
remark
with phase shifters
type A, B, C
[17, Part II], [38]
equivalent to radial networks
direct current
type A
[17, Part I], [20], [39]
assumes nonnegative voltages
type B
[40], [41]
assumes nonnegative voltages
TABLE II: Sufficient conditions for mesh networks
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 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 evidences suggest some of these conditions are likely
satisfied in practice. This is important as most power distribution systems are radial.
These conditions are insufficient for general mesh networks because they cannot guarantee that an
optimal solution of a relaxation satisfies the cycle condition discussed in [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 if a network with a given set of phase
shifters can be convexified and, if not, where additional phase shifters are needed for convexification.
These conditions are also sufficient for direct current (dc) mesh networks where all variables are in
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, JUNE 2014 (WITH PROOFS)
5
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], [43]. We discuss three recent
approaches for global optimization of OPF when the semidefinite relaxations discussed in this tutorial
fail.
We conclude in Section V. This extended version differs from the journal version only in the addition
of Appendix VI that proves all main results covered in this tutorial. Even though all proofs can be found
in their original papers, we provide proofs here because (i) it is convenient to have all proofs in one
place and in a uniform notation, and (ii) some of the formulations and presentations here are slightly
different from those in the original papers.
II. OPF
AND ITS RELAXATIONS
We use the notations and definitions from Part I of this paper. In this section we summarize the OPF
problems and their relaxations developed there; see [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 be equivalent. This implies that an optimal solution of
the nonconvex OPF problem can be recovered from
every
optimal solution of its relaxation. This is
important because it ensures any algorithm that solves an exact relaxation always produces a globally
optimal solution to the OPF problem. Indeed interior point methods for solving SDPs tend to produce
a solution matrix with a maximum rank [44], 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 formulated 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)
1
We will use “bus” and “node” interchangeably and “line” and “link” interchangeably.
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, JUNE 2014 (WITH PROOFS)
6
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
]
j j
[
W
G
]
jk
)
s
j
,
j
N
+
(3a)
v
j
[
W
G
]
j j
v
j
,
j
N
+
(3b)
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
V V
H
and use the same symbol
C
to denote
the cost in terms of a full or partial matrix. Moreover we assume
C
depends on the matrix only through
the submatrix
W
G
defined on the network graph
G
. See [25, Section IV] for more details including the
definitions of
W
c
(
G
)

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, Section 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
i j
z
i j
|
I
i j
|
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)
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, JUNE 2014 (WITH PROOFS)
7
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 is 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
i j
z
i j
`
i j
)
+
s
j
,
j
N
+
(11a)
v
j
v
k
=
2 Re
(
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
B
θ
=
β
(
x
)
mod 2
π
(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, Section 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, Section V-A] for 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
.
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, JUNE 2014 (WITH PROOFS)
8
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
)
.
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 optimal 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 as most distribution
systems are radial.
For radial networks, if SOCP relaxation is exact then SDP and chordal relaxations are also exact (see
[25, Theorems 5, 9]). We hence focus in this section on the exactness of OPF-socp in both BIM and
BFM. Since the cycle conditions (4) and (12) are vacuous for radial networks, OPF-socp (7) is exact
if all of its optimal solutions are 2
×
2 rank-1 and OPF-socp (13) is exact if all of its optimal solutions
attain equalities in (11c). We will freely use either BIM or BFM in discussing these results. To avoid
triviality we make the following assumption throughout the paper:
The voltage lower bounds satisfy
v
j
>
0,
j
N
+
. The original 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].
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, JUNE 2014 (WITH PROOFS)
9
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
)
6∈
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], [31]. It can be regarded as an extension of [45] on the SOCP
relaxation of QCQP from the real domain to the complex domain. Consider:
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
[
α
i j
,
α
i j
+
π
]
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 procedure to recover an optimal solution
of QCQP (14) from any optimal solution of its SOCP relaxation (15). The construction does not need
the optimal solution of SOCP (15) to be 2
×
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. Recall that OPF (2) in BIM can be written as 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
for some Hermitian matrices
C
0
,
Φ
j
,
Ψ
j
,
J
j
where
j
N
+
. A2 depends only on the off-diagonal entries
2
All angles should be interpreted as “mod 2
π
”, i.e., projected onto
(
π
,
π
]
.
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, JUNE 2014 (WITH PROOFS)
10
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
]
i j
=
1
2
Y
i j
=
1
2
(
g
i j
i
b
i j
)
if
k
=
i
1
2
Y
H
i j
=
1
2
(
g
i j
+
i
b
i j
)
if
k
=
j
0
if
k
6∈{
i
,
j
}
[
Ψ
k
]
i j
=
1
2
i
Y
i j
=
1
2
(
b
i j
+
i
g
i j
)
if
k
=
i
1
2
i
Y
H
i j
=
1
2
(
b
i j
i
g
i j
)
if
k
=
j
0
if
k
6∈{
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 Figure 1
with their magnitudes normalized to a common value and explained in the caption of the figure.
Condition A2 applied to OPF (16) takes the following form (see Figure 1):
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
is a tree and A2’ 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 Figure 1 that condition A2’ cannot be satisfied if there is a line where both the real
and reactive power injections at both ends are both lower and upper bounded (8 combinations as shown
in the figure). A2’ requires that some of them be unconstrained even though in practice they are always
bounded. It should be interpreted as requiring that the optimal solutions obtained by ignoring these
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, JUNE 2014 (WITH PROOFS)
11
Φ
j
"
#
$
%
j
k
R
e
I
m
Φ
j
#
$
%
&
j
k
Φ
k
[
]
j
k
Φ
k
[
]
j
k
Ψ
j
"
#
$
%
j
k
Ψ
k
[
]
j
k
Ψ
k
[
]
j
k
Ψ
j
#
$
%
&
j
k
lower)bounds)
on))
p
j
,
q
j
,
p
k
,
q
k
α
j
k
[
C
0
]
j
k
upper)bounds)
on))
p
j
,
q
j
,
p
k
,
q
k
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)–(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, Theorem 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
.
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 Figure 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], [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 nondecreasing, rather than strictly increasing, in
`
,
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, JUNE 2014 (WITH PROOFS)
12
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 arXiv version of this paper).
B. Voltage upper bounds
While type A conditions (A2’ and A4 in the last subsection) require that some power injection
constraints not be binding, type B conditions require non-binding voltage upper bounds. They are
proved in [32], [33], [34], [35] using BFM.
For radial networks the model originally proposed in [18], [19], which is (11) with the inequalities
in (11c) replaced by equalities, is exact. This is because the cycle condition (12) is always satisfied as
the reduced incidence matrix
B
is
n
×
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
i j
z
i j
`
i j
)
+
s
j
,
j
N
+
(17a)
v
j
v
k
=
2 Re
(
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
i j
=
0,
`
i j
=
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: for
j
N
,
s
j
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)
for some given
s
j
,
j
N
.
4
Then the SOCP relaxation is
OPF-socp:
min
x
C
(
x
)
subject to (17)
,
(18)
(19)
As defined in Section II-C, 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 the constraint sets
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.
3
A node
j
N
is a
leaf node
if there is no
i
such that
i
j
̃
E
.
4
We assume here that
s
0
is unconstrained, and since
V
0
:
=
1
0
pu, the constraints (18) involve only
j
in
N
, not
N
+
.
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, JUNE 2014 (WITH PROOFS)
13
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 [46], or
q
j
∈{
0
,
a
}
for capacitor configurations.
Geometric insight.
To motivate our sufficient condition, we first explain a simple geometric 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 pu. 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
(
r p
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
=
p
0
2
+
q
0
2
p
0
r
=
p
1
q
0
x
=
q
1
c
p
0
q
0
h
i
g
h
v
1
l
o
w
v
1
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
.
without any constraint is instructive and shown in Figure 2. 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 voltage constraint and as long as constraints on
(
`,
p
0
,
q
0
)
does not remove the high-voltage
(normal) power flow solution
c
. Only when the system is stressed to a point where the high-voltage
solution becomes infeasible will relaxation lose exactness. This agrees with conventional wisdom that
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, JUNE 2014 (WITH PROOFS)
14
power systems under normal operations are well behaved.
Consider now the voltage constraint
v
1
v
1
v
1
. Substituting (20) into (21) we obtain
v
1
= (
1
+
r p
1
+
xq
1
)
−|
z
|
2
`
translating the constraint on
v
1
into a box constraint on
`
:
1
|
z
|
2
(
r p
1
+
xq
1
+
1
v
1
)
`
1
|
z
|
2
(
r p
1
+
xq
1
+
1
v
1
)
Figure 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 Figure 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 power flow solution
c
and is not exact otherwise.
p
0
q
0
c
(a) Voltage constraint not binding
op2mal)solu2on)of)SOCP))
(infeasible)for)OPF))
p
0
q
0
c
(b) Voltage constraint binding
Fig. 3: Impact of voltage upper bound
v
1
on exactness. (a) When
v
1
(corresponding 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.
To state the sufficient condition for a general radial network, recall from [25, Section 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)
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, JUNE 2014 (WITH PROOFS)
15
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 2-dimensional real vectors so that
z
jk
(
S
jk
)
T
is a 2
×
2 matrix with rank less or equal to 1. The
matrices
A
jk
(
S
jk
,
v
j
)
describe how changes in the real and reactive power flows propagate towards the
root node 0; see comments below. Evaluate the Jacobian matrix
A
jk
(
S
jk
,
v
j
)
at the boundary values:
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
6
=
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 0 have
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 be used to
recursively construct from it another optimal solution that attains equalities in (17c).
B2 is affine in the injections
s
:
= (
p
,
q
)
. It enforces the upper bounds on voltage magnitudes because
of (23).
B3 is a technical assumption and has a simple interpretation: the branch power flow
S
jk
on all branches
should move in the same direction. Specifically, given a marginal change in the complex power on line
j
k
, the 2
×
2 matrix
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 towards the root. B3 requires that a small change, positive or
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, JUNE 2014 (WITH PROOFS)
16
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], [33], [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
if the
r
/
x
ratios on all lines are equal, or
if the
r
/
x
ratios increase in the downstream direction from the substation (node 0) to the leaves
then there are no reverse real power flows, or
if the
r
/
x
ratios decrease in the downstream direction then there are no reverse reactive power
flows.
The exactness of SOCP relaxation does not require convexity, 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:
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 examples for mesh networks in [47], [48],
[49], [50].
C. Angle differences
The sufficient conditions in [29], [36], [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 convex surface that is the Pareto front of its
relaxation. This implies that the relaxation is exact. This geometric picture is apparent in earlier work
on the geometry of power flow solutions, see e.g. [47], and underlies the intuition that the dynamics
of a power system is usually benign until it is pushed towards the boundary of its stability region. The
geometric insight in Figures 2 and 3 for BFM and later in this subsection for BIM says that, when it
5
There is a bijection between
X
and the feasible set of OPF (10) (when (18b) are placed by (9b)) [17], [25].
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, JUNE 2014 (WITH PROOFS)
17
is far away from the boundary, the local convexity structure also facilitates exact relaxation. Reactive
power is considered in [37, Theorem 1] with fixed
|
V
j
|
where, with an additional constraint on the lower
bounds of reactive power injections that ensure these lower bounds are not tight, it is proved that if
the original OPF problem is feasible then its SDP relaxation is exact. The case of variable
|
V
j
|
without
reactive power is considered in [36, Theorem 7] but the simple geometric structure is lost.
Recall that
y
jk
=
g
jk
i
b
jk
with
g
jk
>
0
,
b
jk
>
0. Let
V
j
=
|
V
j
|
e
i
θ
j
and suppose
|
V
j
|
are given. Consider:
min
p
,
P
,
θ
C
(
p
)
(26a)
subject to
p
j
p
j
p
j
,
j
N
+
(26b)
θ
jk
θ
jk
θ
jk
,
(
j
,
k
)
E
(26c)
p
j
=
k
:
k
j
P
jk
,
j
N
+
(26d)
P
jk
=
|
V
j
|
2
g
jk
−|
V
j
||
V
k
|
g
jk
cos
θ
jk
+
|
V
j
||
V
k
|
b
jk
sin
θ
jk
,
(
j
,
k
)
E
(26e)
where
θ
jk
:
=
θ
j
θ
k
are the voltage angle differences across lines
(
j
,
k
)
.
We comment on the constraints on angles
θ
jk
in (26). When the voltage magnitudes
|
V
i
|
are fixed,
constraints on real power flows, branch currents, line losses, as well as stability constraints can all be
represented in terms of
θ
jk
. Indeed a line flow constraint of the form
|
P
jk
|≤
P
jk
becomes a constraint
on
θ
jk
using the expression for
P
jk
in (26e). A current constraint of the form
|
I
jk
|≤
I
jk
is also a
constraint on
θ
jk
since
|
I
jk
|
2
=
|
y
jk
|
(
|
V
j
|
2
+
|
V
k
|
2
2
|
V
j
V
k
|
cos
θ
jk
)
. The line loss over
(
j
,
k
)
E
is equal
to
P
jk
+
P
k j
which is again a function of
θ
jk
. Stability typically requires
|
θ
jk
|
to stay within a small
threshold. Therefore given constraints on branch power or current flows, losses, and stability, appropriate
bounds
θ
jk
,
θ
jk
can be determined in terms of these constraints, assuming
|
V
j
|
are fixed.
We can eliminate the branch flows
P
jk
and angles
θ
jk
from (26). Since
|
V
j
|
,
j
N
+
, are fixed we
assume without loss of generality that
|
V
j
|
=
1 pu. Define the injection region
P
θ
:
=
{
p
R
n
p
j
=
k
:
k
j
(
g
jk
g
jk
cos
θ
jk
+
b
jk
sin
θ
jk
)
,
j
N
+
,
θ
jk
θ
jk
θ
jk
,
(
j
,
k
)
E
}
(27)
Let
P
p
:
=
{
p
R
n
|
p
j
p
j
p
j
,
j
N
}
. Then (26) is:
OPF:
min
p
C
(
p
)
subject to
p
P
θ
P
p
(28)
This problem is hard because the set
P
θ
is nonconvex. To avoid triviality we assume OPF (28) is
feasible. For a set
A
let conv
A
denote the convex hull of
A
. Consider the following problem that relaxes
the nonconvex feasible set
P
θ
P
p
of (28) to a convex superset: