IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, 1(1):15–27, MARCH 2014 (WITH PROOFS)
1
Convex Relaxation of Optimal Power Flow
Part I: Formulations and Equivalence
Steven H. Low
Electrical Engineering, Computing+Mathematical Sciences
Engineering and Applied Science, Caltech
slow@caltech.edu
April 15, 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, 15(1): 15–27, March 2014.
This is an extended version with Appendices
VIII and IX that provide some mathematical preliminaries and proofs of the main results. 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.0766v1 [math.OC] 5 May 2014
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, 1(1):15–27, MARCH 2014 (WITH PROOFS)
2
C
ONTENTS
I
Introduction
4
I-A
Outline of paper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
I-B
Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
II
Power flow models
6
II-A
Bus injection model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
II-B
Branch flow model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
II-C
Equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
III
Optimal power flow
8
III-A
Bus injection model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
III-B
Branch flow model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
III-C
OPF as QCQP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
IV
Feasible sets and relaxations: BIM
11
IV-A
Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
IV-B
Feasible sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
IV-C
Semidefinite relaxations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
IV-D
Solution recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
IV-E
Tightness of relaxations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
IV-F
Chordal relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
V
Feasible sets and relaxations: BFM
17
V-A
Feasible sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
V-B
SOCP relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
V-C
Equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
VI
BFM for radial networks
21
VI-A
Recursive equations and graph orientation . . . . . . . . . . . . . . . . . . . . . . . . 21
VI-B
Linear approximation and bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
VII
Conclusion
25
Appendix: VIII: Mathematical preliminaries
26
A
QCQP, SDP, SOCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
B
Graph, partial matrix and completion . . . . . . . . . . . . . . . . . . . . . . . . . . 28
C
Chordal relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, 1(1):15–27, MARCH 2014 (WITH PROOFS)
3
Appendix: IX: Proofs of main results
32
A
Proof of Theorem 1: equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
B
Proof of Theorem 2: rank-1 characterization . . . . . . . . . . . . . . . . . . . . . . . 33
C
Proof of Corollary 3: uniqueness of completion . . . . . . . . . . . . . . . . . . . . . 34
D
Proof of Theorem 5: BIM feasible sets . . . . . . . . . . . . . . . . . . . . . . . . . 34
E
Proof of Theorem 7: BFM feasible sets . . . . . . . . . . . . . . . . . . . . . . . . . 34
F
Proof of Theorem 8: BFM cycle condition . . . . . . . . . . . . . . . . . . . . . . . 36
G
Proof of Theorem 9: radial networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
H
Proof of Theorem 11: equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
I
Proof of Lemma 12: voltage bound . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
References
42
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, 1(1):15–27, MARCH 2014 (WITH PROOFS)
4
I. I
NTRODUCTION
For our purposes an optimal power flow (OPF) problem is a mathematical program that seeks to minimize
a certain function, such as total power loss, generation cost or user disutility, subject to the Kirchhoff’s
laws as well as capacity, stability and security constraints. OPF is fundamental in power system operations
as it underlies many applications such as economic dispatch, unit commitment, state estimation, stability
and reliability assessment, volt/var control, demand response, etc. There has been a great deal of research
on OPF since Carpentier’s first formulation in 1962 [1]. An early solution appears in [2] and extensive
surveys can be found in e.g. [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14].
Power flow equations are quadratic and hence OPF can be formulated as a quadratically constrained
quadratic program (QCQP). It is generally nonconvex and hence NP-hard. A large number of optimization
algorithms and relaxations have been proposed. A popular approximation is a linear program, called DC
OPF, obtained through the linearization of the power flow equations e.g. [15], [16], [17], [18], [19]. See
also [20] for a more accurate linear approximation. To the best of our knowledge solving OPF through
semidefinite relaxation is first proposed in [21] as a second-order cone program (SOCP) for radial (tree)
networks and in [22] as a semidefinite program (SDP) for general networks in a bus injection model. It is
first proposed in [23], [24] as an SOCP for radial networks in the branch flow model of [25], [26]. See
Remark 6 below for more details. While these convex relaxations have been illustrated numerically in [21]
and [22], whether or when they will turn out to be exact is first studied in [27]. Exploiting graph sparsity
to simplify the SDP relaxation of OPF is first proposed in [28], [29] and analyzed in [30], [31].
Convex relaxation of quadratic programs has been applied to many engineering problems; see e.g. [32].
There is a rich theory and extensive empirical experiences. Compared with other approaches, solving OPF
through convex relaxation offers several
advantages
. First, while DC OPF is useful in a wide variety of
applications, it is not applicable in other applications; see Remark 10. Second a solution of DC OPF may not
be feasible (may not satisfy the nonlinear power flow equations). In this case an operator may tighten some
constraints in DC OPF and solve again. This may not only reduce efficiency but also relies on heuristics
that are hard to scale to larger systems or faster control in the future. Third, when they converge, most
nonlinear algorithms compute a local optimal usually without assurance on the quality of the solution. In
contrast a convex relaxation provides for the first time 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 two-part tutorial explains the main theoretical results on semidefinite relaxations of OPF developed
in the last few years. Part I presents two power flow models that are useful in different situations, formulates
OPF and its convex relaxations in each model, and clarifies their relationship. Part II [33] presents sufficient
conditions that guarantee the relaxations are exact, i.e. when one can recover a globally optimal solution
of OPF from an optimal solution of its relaxations. We focus on basic results using the simplest OPF
formulation and does not cover many relevant works in the literature, such as stochastic OPF e.g. [34],
[35], [36], distributed OPF e.g. [37], [38], [39], [40], [41], [42], new applications e.g. [43], [44], or what
to do when relaxation fails e.g. [45], [46], [47], to name just a few.
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, 1(1):15–27, MARCH 2014 (WITH PROOFS)
5
A. Outline of paper
Many mathematical models have been used to model power networks. In Part I of this two-part paper
we present two such models, we call the bus injection model (BIM) and the branch flow model (BFM).
Each model consists of a set of power flow equations. Each models a power network in that the solutions
of each set of equations, called the power flow solutions, describe the steady state of the network. We
prove that these two models are equivalent in the sense that there is a bijection between their solution sets
(Section II). We formulate OPF within each model where the power flow solutions define the feasible set
of OPF (Section III). Even though BIM and BFM are equivalent some results are much easier to formulate
or prove in one model than the other; see Remark 2 in Section II.
The complexity of OPF formulated here lies in the nonconvexity of power flow equations that gives rise
to a nonconvex feasible set of OPF. We develop various characterizations of the feasible set and design
convex supersets based on these characterizations. Different designs lead to different convex relaxations
and we prove their relationship (Sections IV and V). When a relaxation is exact an optimal solution of the
original nonconvex OPF can be recovered from
any
optimal solution of the relaxation. In Part II [33] we
present sufficient conditions that guarantee the exactness of convex relaxations.
Branch flow models are originally proposed for networks with a tree topology, called
radial networks
,
e.g. [25], [26], [48], [49], [50], [51], [23], [52], [53]. They take a recursive structure that simplifies the
computation of power flow solutions, e.g. [54], [55], [48]. The model of [25], [26] also has a linearization
that offers several advantages over DC OPF in BIM; see Remark 10. The linear approximation provides
simple bounds on the branch powers and voltage magnitudes in the nonlinear BFM (Section VI). These
bounds are used in [56] to prove a sufficient condition for exact relaxation.
We make algorithmic recommendations in Section VII based on the results presented here.
This extended version differs from the journal version only in the addition of two Appendices. Appendix
VIII provides some mathematical preliminaries and Appendix IX proofs of all main results. 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.
B. Notations
Let
C
denote the set of complex numbers,
R
the set of real numbers, and
N
the set of integers. For
a
∈
C
, Re
a
and Im
a
denote the real and imaginary parts of
a
respectively. For any set
A
⊆
C
n
, conv
A
denotes the convex hull of
A
. For
a
∈
R
,
[
a
]
+
:
=
max
{
a
,
0
}
. For
a
,
b
∈
C
,
a
≤
b
means Re
a
≤
Re
b
and
Im
a
≤
Im
b
. We abuse notation to use the same symbol
a
to denote either a complex number Re
a
+
i
Im
a
or a 2-dimensional real vector
a
=
(Re
a
, Im
a
) depending on the context.
In general scalar or vector variables are in small letters, e.g.
u
,
w
,
x
,
y
,
z
. Most power system quantities
however are in capital letters, e.g.
S
jk
,
P
jk
,
Q
jk
,
I
j
,
V
j
. A variable without a subscript denotes a vector with
appropriate components, e.g.
s
:
= (
s
j
,
j
=
0
,...,
n
)
,
S
:
= (
S
jk
,
(
j
,
k
)
∈
E
)
. For vectors
x
,
y
,
x
≤
y
denotes
componentwise inequality.
Matrices are usually in capital letters. The transpose of a matrix
A
is denoted by
A
T
and its Hermitian
(complex conjugate) transpose by
A
H
. A matrix
A
is Hermitian if
A
=
A
H
.
A
is positive semidefinite (or
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, 1(1):15–27, MARCH 2014 (WITH PROOFS)
6
psd), denoted by
A
0, if
A
is Hermitian
and x
H
Ax
≥
0 for all
x
∈
C
n
; in particular if
A
0 then by
definition
A
=
A
H
. For matrices
A
,
B
,
A
B
means
A
−
B
is psd. Let
S
n
be the set of all
n
×
n
Hermitian
matrices and
S
n
+
the set of
n
×
n
psd matrices.
A graph
G
= (
N
,
E
)
consists of a set
N
of nodes and a set
E
⊆
N
×
N
of edges. If
G
is undirected then
(
j
,
k
)
∈
E
if and only if
(
k
,
j
)
∈
E
. If
G
is directed then
(
j
,
k
)
∈
E
only if
(
k
,
j
)
6∈
E
; in this case we will
use
(
j
,
k
)
and
j
→
k
interchangeably to denote an edge pointing from
j
to
k
. We sometimes use
̃
G
= (
N
,
̃
E
)
to denote a directed graph. By “
j
∼
k
” we mean an edge
(
j
,
k
)
if
G
is undirected and either
j
→
k
or
k
→
j
if
G
is directed. Sometimes we write
j
∈
G
or
(
j
,
k
)
∈
G
to mean
j
∈
N
or
(
j
,
k
)
∈
E
respectively.
A
cycle c
:
= (
j
1
,...,
j
K
)
is an ordered set of nodes
j
k
∈
N
so that
(
j
k
,
j
k
+
1
)
∈
E
for
k
=
1
,...,
K
with the
understanding that
j
K
+
1
:
=
j
1
. In that case we refer to a link or a node in the cycle by
(
j
k
,
j
k
+
1
)
∈
c
or
j
k
∈
c
respectively.
II. P
OWER FLOW MODELS
In this section we describe two mathematical models of power networks and prove their equivalence. By
a “mathematical model” we mean a set of variables and a set of equations relating these variables. These
equations are motivated by the physical system, but mathematically, they are the starting point from which
all claims are derived.
A. Bus injection model
Consider a power network modeled by a connected undirected graph
G
(
N
+
,
E
)
where
N
+
:
=
{
0
}∪
N
,
N
:
=
{
1
,
2
,...,
n
}
, and
E
⊆
N
+
×
N
+
. Each node in
N
+
represents a bus and each edge in
E
represents
a transmission or distribution line. We use “bus” and “node” interchangeably and “line” and “edge”
interchangeably. For each edge
(
i
,
j
)
∈
E
let
y
i j
∈
C
be its admittance. A bus
j
∈
N
+
can have a generator,
a load, both or neither. Let
V
j
be the complex voltage at bus
j
∈
N
+
and
|
V
j
|
denote its magnitude. Bus 0
is the
slack bus
. Its voltage is fixed and we assume without loss of generality that
V
0
=
1
∠
0
◦
per unit (pu).
Let
s
j
be the net complex power injection (generation minus load) at bus
j
∈
N
+
.
The
bus injection model
(BIM) is defined by the following power flow equations that describe the
Kirchhoff’s laws:
s
j
=
∑
k
:
j
∼
k
y
H
jk
V
j
(
V
H
j
−
V
H
k
)
,
j
∈
N
+
(1)
Let the set of power flow solutions
V
for each
s
be:
V
(
s
)
:
=
{
V
∈
C
n
+
1
|
V
satisfies (1)
}
For convenience we include
V
0
in the vector variable
V
:
= (
V
j
,
j
∈
N
+
)
with the understanding that
V
0
:
=
1
∠
0
◦
is fixed.
Remark 1: Bus types.
Each bus
j
is characterized by two complex variables
V
j
and
s
j
, or equivalently,
four real variables. The buses are usually classified into three types, depending on which two of the four
real variables are specified. For the slack bus 0,
V
0
is given and
s
0
is variable. For a
generator bus
(also
called
PV
-bus), Re
(
s
j
) =
p
j
and
|
V
j
|
are specified and Im
(
s
j
) =
q
j
and
∠
V
j
are variable. For a
load bus
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, 1(1):15–27, MARCH 2014 (WITH PROOFS)
7
(also called
PQ
-bus),
s
j
is specified and
V
j
is variable. The
power flow
or
load flow
problem is: given two
of the four real variables specified for each bus, solve the
n
+
1
complex
equations in (1) for the remaining
2
(
n
+
1
)
real variables. For instance when all
n
buses
j
6
=
0 are all load buses, the power flow problem
solves (1) for the
n
complex voltages
V
j
,
j
6
=
0, and the power injection
s
0
at the slack bus 0. This can
model a distribution system with a substation at bus 0 and
n
constant-power loads at the other buses. For
optimal power flow
problems
p
j
and
|
V
j
|
on generator buses or
s
j
on load buses can be variables as well.
For instance economic dispatch optimizes real power generations
p
j
at generator buses; demand response
optimizes demands
s
j
at load buses; and volt/var control optimizes reactive powers
q
j
at capacitor banks,
tap changers, or inverters. These remarks also apply to the branch flow model presented next.
B. Branch flow model
In the branch flow model we adopt a connected directed graph
̃
G
= (
N
+
,
̃
E
)
where each node in
N
+
:
=
{
0
,
1
,...,
n
}
represents a bus and each edge in
̃
E
⊆
N
+
×
N
+
represents a transmission or distribution line.
Fix an arbitrary orientation for
̃
G
and let
m
:
=
|
̃
E
|
be the number of directed edges in
̃
G
. Denote an edge by
(
j
,
k
)
or
j
→
k
if it points from node
j
to node
k
. For each edge
(
j
,
k
)
∈
̃
E
let
z
jk
:
=
1
/
y
jk
be the complex
impedance on the line; let
I
jk
be the complex current and
S
jk
=
P
jk
+
i
Q
jk
be the
sending-end
complex
power from buses
j
to
k
. For each bus
j
∈
N
+
let
V
j
be the complex voltage at bus
j
. Assume without loss
of generality that
V
0
=
1
∠
0
◦
pu. Let
s
j
be the net complex power injection at bus
j
.
The
branch flow model
(BFM) in [24] is defined by the following set of power flow equations:
∑
k
:
j
→
k
S
jk
=
∑
i
:
i
→
j
(
S
i j
−
z
i j
|
I
i j
|
2
)
+
s
j
,
j
∈
N
+
(2a)
I
jk
=
y
jk
(
V
j
−
V
k
)
,
j
→
k
∈
̃
E
(2b)
S
jk
=
V
j
I
H
jk
,
j
→
k
∈
̃
E
(2c)
where (2b) is the Ohm’s law, (2c) defines branch power, and (2a) imposes power balance at each bus. The
quantity
z
i j
|
I
i j
|
2
represents line loss so that
S
i j
−
z
i j
|
I
i j
|
2
is the receiving-end complex power at bus
j
from
bus
i
.
Let the set of solutions ̃
x
:
= (
S
,
I
,
V
)
of BFM for each
s
be:
̃
X
(
s
)
:
=
{
̃
x
∈
C
2
m
+
n
+
1
|
̃
x
satisfies (2)
}
For convenience we include
V
0
in the vector variable
V
:
= (
V
j
,
j
∈
N
+
)
with the understanding that
V
0
:
=
1
∠
0
◦
is fixed.
C. Equivalence
Even though the bus injection model (1) and the branch flow model (2) are defined by different sets of
equations in terms of their own variables, both are models of the Kirchhoff’s laws and therefore must be
related. We now clarify the precise sense in which these two mathematical models are equivalent. We say
two sets
A
and
B
are
equivalent
, denoted by
A
≡
B
, if there is a bijection between them [57].
Theorem 1:
V
(
s
)
≡
̃
X
(
s
)
for any power injections
s
.
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, 1(1):15–27, MARCH 2014 (WITH PROOFS)
8
Remark 2: Two models.
Given the bijection between the solution sets
V
(
s
)
and
̃
X
(
s
)
any result in one
model is in principle derivable in the other. Some results however are much easier to state or derive in one
model than the other. For instance BIM, which is widely used in transmission network problems, allows
a much cleaner formulation of the semidefinite program (SDP) relaxation. BFM for radial networks has a
convenient recursive structure that allows a more efficient computation of power flows and leads to a useful
linear approximation of BFM; see Section VI. The sufficient condition for exact relaxation in [56] provides
intricate insights on power flows that are hard to formulate or prove in BIM. Finally, since BFM directly
models branch flows
S
jk
and currents
I
jk
, it is easier to use for some applications. We will therefore freely
use either model depending on which is more convenient for the problem at hand.
III. O
PTIMAL POWER FLOW
A. Bus injection model
As mentioned in Remark 1 an optimal power flow problem optimizes both variables
V
and
s
over the
solution set of the BIM (1). In addition all voltage magnitudes must satisfy:
v
j
≤ |
V
j
|
2
≤
v
j
,
j
∈
N
+
(3)
where
v
j
and
v
j
are given lower and upper bounds on voltage magnitudes. Throughout this paper we assume
v
j
>
0 to avoid triviality. The power injections are also constrained:
s
j
≤
s
j
≤
s
j
,
j
∈
N
+
(4)
where
s
j
and
s
j
are given bounds on the injections at buses
j
.
Remark 3: OPF constraints.
If there is no bound on the load or on the generation at bus
j
then
s
j
=
−
∞
−
i
∞
or
s
j
=
∞
+
i
∞
respectively. On the other hand (4) also allows the case where
s
j
is fixed (e.g.
a constant-power load), by setting
s
j
=
s
j
to the specified value. For the slack bus 0, unless otherwise
specified, we always assume
v
0
=
v
0
=
1 and
s
0
=
−
∞
−
i
∞
,
s
0
=
∞
+
i
∞
. Therefore we sometimes replace
j
∈
N
+
in (3) and (4) by
j
∈
N
.
We can eliminate the variables
s
j
from the OPF formulation by combining (1) and (4) into
s
j
≤
∑
k
:
(
j
,
k
)
∈
E
y
H
jk
V
j
(
V
H
j
−
V
H
k
)
≤
s
j
,
j
∈
N
+
(5)
Then OPF in the bus injection model can be defined just in terms of the complex voltage vector
V
. Define
V
:
=
{
V
∈
C
n
+
1
|
V
satisfies (3)
,
(5)
}
(6)
V
is the feasible set of optimal power flow problems in BIM.
Let the cost function be
C
(
V
)
. Typical costs include the cost of generating real power at each generator
bus or line loss over the network. All these costs can be expressed as functions of
V
. Then the problem of
interest is:
OPF:
min
V
C
(
V
)
subject to
V
∈
V
(7)
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, 1(1):15–27, MARCH 2014 (WITH PROOFS)
9
Since (5) is quadratic,
V
is generally a nonconvex set. OPF is thus a nonconvex problem and NP-hard to
solve in general.
B. Branch flow model
Denote the variables in the branch flow model (2) by ̃
x
:
= (
S
,
I
,
V
,
s
)
∈
C
2
(
m
+
n
+
1
)
. We can also eliminate
the variables
s
j
as for the bus injection model by combining (2a) and (4) but it will prove convenient to
retain
s
:
= (
s
j
,
j
∈
N
+
)
as part of the variables. Define the feasible set in the branch flow model:
̃
X
:
=
{
̃
x
∈
C
2
(
m
+
n
+
1
)
|
̃
x
satisfies (2)
,
(3)
,
(4)
}
(8)
Let the cost function in the branch flow model be
C
(
̃
x
)
. Then the optimal power flow problem in the
branch flow model is:
OPF:
min
̃
x
C
(
̃
x
)
subject to
̃
x
∈
̃
X
(9)
Since (2) is quadratic,
X
is generally a nonconvex set. OPF is thus a nonconvex problem and NP-hard to
solve in general.
Remark 4: OPF equivalence.
By Theorem 1 there is a bijection between
V
and
̃
X
. Throughout this
paper we assume that the cost functions in BIM and BFM are equivalent under this bijection and we abuse
notation to denote them by the same symbol
C
(
·
)
. Then OPF (7) in BIM and (9) in BFM are equivalent.
Remark 5: OPF variants.
OPF as defined in (7) and (9) is a simplified version that ignores other important
constraints such as line limits, security constraints, stability constraints, and chance constraints; see extensive
surveys in [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14], [58], [59] and a recent discussion in
[60] on real-life OPF problems. Some of these can be incorporated without any change to the results in this
paper (e.g. see [24], [61] for models that include shunt elements and line limits). Indeed a shunt element
y
j
at bus
j
can be easily included in BIM by modifying (1) into:
s
j
=
∑
k
:
j
∼
k
y
H
jk
V
j
(
V
H
j
−
V
H
k
)+
y
H
j
|
V
j
|
2
or included in BFM by modifying (2a) into:
∑
k
:
j
→
k
S
jk
+
y
H
j
|
V
j
|
2
=
∑
i
:
i
→
j
(
S
i j
−
z
i j
|
I
i j
|
2
)
+
s
j
C. OPF as QCQP
Before we describe convex relaxations of OPF we first show that, when
C
(
V
)
:
=
V
H
CV
is quadratic in
V
for some Hermitian matrix
C
, OPF is indeed a quadratically constrained quadratic program (QCQP) by
converting it into the standard form. We will use the derivation in [61] for OPF (7) in BIM. OPF (9) in
BFM can similarly be converted into a standard form QCQP.
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, 1(1):15–27, MARCH 2014 (WITH PROOFS)
10
Define the
(
n
+
1
)
×
(
n
+
1
)
admittance matrix
Y
by
Y
i j
=
∑
k
:
k
∼
i
y
ik
,
if
i
=
j
−
y
i j
,
if
i
6
=
j
and
i
∼
j
0
otherwise
Y
is symmetric but not necessarily Hermitian. Let
I
j
be the net injection current from bus
j
to the rest of
the network. Then the current vector
I
and the voltage vector
V
are related by the Ohm’s law
I
=
Y V
. BIM
(1) is equivalent to:
s
j
=
V
j
I
H
j
= (
e
H
j
V
)(
I
H
e
j
)
where
e
j
is the
(
n
+
1
)
-dimensional vector with 1 in the
j
th entry and 0 elsewhere. Hence, since
I
=
Y V
,
we have
s
j
=
tr
(
e
H
j
V V
H
Y
H
e
j
)
=
tr
(
Y
H
e
j
e
H
j
)
V V
H
=
V
H
Y
H
j
V
where
Y
j
:
=
e
j
e
H
j
Y
is an
(
n
+
1
)
×
(
n
+
1
)
matrix with its
j
th row equal to the
j
th row of the admittance
matrix
Y
and all other rows equal to the zero vector.
Y
j
is in general not Hermitian so that
V
H
Y
H
j
V
is in
general a complex number. Its real and imaginary parts can be expressed in terms of the Hermitian and
skew Hermitian components of
Y
H
j
defined as:
Φ
j
:
=
1
2
(
Y
H
j
+
Y
j
)
and
Ψ
j
:
=
1
2
i
(
Y
H
j
−
Y
j
)
Then
Re
s
j
=
V
H
Φ
j
V
and Im
s
j
=
V
H
Ψ
j
V
Let their upper and lower bounds be denoted by
p
j
:
=
Re
s
j
and
p
j
:
=
Re
s
j
q
j
:
=
Re
s
j
and
q
j
:
=
Re
s
j
Let
J
j
:
=
e
j
e
H
j
denote the Hermitian matrix with a single 1 in the
(
j
,
j
)
th entry and 0 everywhere else.
Then OPF (7) can be written as a standard form QCQP:
min
V
∈
C
n
+
1
V
H
CV
(10a)
subject to
V
H
Φ
j
V
≤
p
j
,
V
H
(
−
Φ
j
)
V
≤−
p
j
(10b)
V
H
Ψ
j
V
≤
q
j
,
V
H
(
−
Ψ
j
)
V
≤−
q
j
(10c)
V
H
J
j
V
≤
v
j
,
V
H
(
−
J
j
)
V
≤−
v
j
(10d)
where
j
∈
N
+
in (10).
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, 1(1):15–27, MARCH 2014 (WITH PROOFS)
11
IV. F
EASIBLE SETS AND RELAXATIONS
: BIM
In this and the next section we derive semidefinite relaxations of OPF and clarify their relations. The cost
function
C
of OPF is usually assumed to be convex in its variables. The difficulty of OPF formulated here
thus arises from the nonconvex feasible sets
V
for BIM and
̃
X
for BFM. The basic approach to deriving
convex relaxations of OPF is to design convex supersets of (equivalent sets of)
V
or
̃
X
and minimize the
same cost function over these supersets. Different choices of convex supersets lead to different relaxations,
but they all provide a lower bound to OPF. If every optimal solution of a convex relaxation happens to lie
in
V
or
̃
X
then it is also feasible and hence optimal for the original OPF. In this case we say the realxation
is exact.
In this section we present three characterizations of the feasible set
V
in BIM. These characterizations
naturally suggest convex supersets and semidefinite relaxations of OPF, and we prove equivalence relations
among them. In the next section we treat BFM. In Part II of the paper we discuss sufficient conditions that
guaranteed exact relaxations.
A. Preliminaries
Since OPF is a nonconvex QCQP there is a standard semidefinite relaxation through the equivalence
relation: for any Hermitian matrix
M
,
V
H
MV
=
tr
MV V
H
=
tr
MW
for a psd rank-1 matrix
W
. Applying
this transformation to the QCQP formulation (10) leads to an equivalent problem of the form:
min
W
∈
S
n
+
1
tr
CW
subject to
tr
C
l
W
≤
b
l
,
W
0
,
rank
W
=
1
for appropriate Hermitian matrices
C
l
and real numbers
b
l
. This problem is equivalent to (10) because
given a psd rank-1 solution
W
, a unique solution
V
of (10) can be recovered through rank-1 factorization
W
=
V V
H
. Unlike (10) which is quadratic in
V
this problem is convex in
W
except the nonconvex rank-1
constraint. Removing the rank-1 constraint yields the standard SDP relaxation.
We now generalize this intuition to characterize the feasible set
V
in (6) in terms of partial matrices.
These characterizations lead naturally to SDP, chordal, and second-order cone program (SOCP) relaxations
of OPF in BIM, as shown in [57], [31].
We start with some basic definitions on partial matrices and their completions; see e.g. [62], [63], [64]
for more details. Fix any connected undirected graph
F
with
n
vertices and
m
edges connecting distinct
vertices.
1
A
partial matrix W
F
is a set of 2
m
+
n
complex numbers
defined on F
:
W
F
:
=
{
[
W
F
]
j j
,
[
W
F
]
jk
,
[
W
F
]
k j
|
nodes
j
and edges
(
j
,
k
)
of
F
}
W
F
can be interpreted as a matrix with entries partially specified by these complex numbers. If
F
is a
complete graph (in which there is an edge between every pair of vertices) then
W
F
is a fully specified
n
×
n
matrix. A
completion W
of
W
F
is any fully specified
n
×
n
matrix that agrees with
W
F
on graph
F
, i.e.,
[
W
]
j j
= [
W
F
]
j j
,
[
W
]
jk
= [
W
F
]
jk
for
j
,
(
j
,
k
)
∈
F
1
In this subsection we abuse notation and use
n
,
m
to denote general integers unrelated to the number of buses or lines in a power network.
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, 1(1):15–27, MARCH 2014 (WITH PROOFS)
12
Given an
n
×
n
matrix
W
we use
W
F
to denote the
submatrix of W on F ,
i.e., the partial matrix consisting
of the entries of
W
defined on graph
F
. If
q
is a clique (a fully connected subgraph) of
F
then let
W
F
(
q
)
denote the fully-specified principal submatrix of
W
F
defined on
q
. We extend the definitions of Hermitian,
psd, and rank-1 for matrices to partial matrices, as follows. A partial matrix
W
F
is
Hermitian
, denoted by
W
F
=
W
H
F
, if
[
W
F
]
jk
= [
W
F
]
H
k j
for all
(
j
,
k
)
∈
F
; it is
psd
, denoted by
W
F
0, if
W
F
is Hermitian and the
principal submatrices
W
F
(
q
)
are psd for all cliques
q
of
F
; it is
rank-1
, denoted by rank
W
F
=
1, if the
principal submatrices
W
F
(
q
)
are rank-1 for all cliques
q
of
F
. We say
W
F
is 2
×
2
psd (rank-1)
if, for all
edges
(
j
,
k
)
∈
F
, the 2
×
2 principal submatrices
W
F
(
j
,
k
)
:
=
[
[
W
F
]
j j
[
W
F
]
jk
[
W
F
]
k j
[
W
F
]
kk
]
are psd (rank-1), denoted by
W
F
(
j
,
k
)
0 (rank
W
F
(
j
,
k
) =
1
)
.
F
is a
chordal graph
if either
F
has no
cycle or all its minimal cycles (ones without chords) are of length three. A
chordal extension c
(
F
)
of
F
is
a chordal graph that contains
F
, i.e.,
c
(
F
)
has the same vertex set as
F
but an edge set that is a superset
of
F
’s edge set. In that case we call the partial matrix
W
c
(
F
)
a
chordal extension
of the partial matrix
W
F
.
Every graph
F
has a chordal extension, generally nonunique. In particular a complete supergraph of
F
is
a trivial chordal extension of
F
.
For our purposes chordal graphs are important because of the result [62, Theorem 7] that every psd
partial matrix has a psd completion if and only if the underlying graph is chordal. When a positive
definite completion exists, there is a
unique
positive definite completion, in the class of all positive definite
completions, whose determinant is maximal. Theorem 2 below extends this to rank-1 partial matrices.
B. Feasible sets
We can now characterize the feasible set
V
of OPF defined in (6). Recall the undirected connected
graph
G
= (
N
+
,
E
)
that models a power network. Given a voltage vector
V
∈
V
define a partial matrix
W
G
:
=
W
G
(
V
)
: for
j
∈
N
+
and
(
j
,
k
)
∈
E
,
[
W
G
]
j j
:
=
|
V
j
|
2
(11a)
[
W
G
]
jk
:
=
V
j
V
H
k
=
:
[
W
G
]
H
k j
(11b)
Then the constraints (5) and (3) imply that the partial matrix
W
G
satisfies
2
s
j
≤
∑
k
:
(
j
,
k
)
∈
E
y
H
jk
(
[
W
G
]
j j
−
[
W
G
]
jk
)
≤
s
j
,
j
∈
N
+
(12a)
v
j
≤
[
W
G
]
j j
≤
v
j
,
j
∈
N
+
(12b)
2
The constraint (12a) can also be written compactly in terms of the admittance matrix
Y
as in [65]:
s
≤
diag
(
WY
H
)
≤
s
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, 1(1):15–27, MARCH 2014 (WITH PROOFS)
13
Following Section III-C these constraints can also be written in a (partial) matrix form as:
p
j
≤
tr
Φ
j
W
G
≤
p
j
q
j
≤
tr
Ψ
j
W
G
≤
q
j
v
j
≤
tr
J
j
W
G
≤
v
j
The converse is not always true: given a partial matrix
W
G
that satisfies (12) it is not always possible to
recover a voltage vector
V
in
V
. Indeed this is possible if and only if
W
G
has a completion
W
that is psd
rank-1, because in that case
W
satisfies (12) since
y
jk
=
0 if
(
j
,
k
)
6∈
E
and it can be uniquely factored as
W
=
V V
H
with
V
∈
V
. We hence seek conditions additional to (12) on the partial matrix
W
G
that guarantee
that it has a psd rank-1 completion
W
from which
V
∈
V
can be recovered. Our first key result provides
such a characterization.
We say that a partial matrix
W
G
satisfies the
cycle condition
if for every cycle
c
in
G
∑
(
j
,
k
)
∈
c
∠
[
W
G
]
jk
=
0
mod 2
π
(13)
When
∠
[
W
G
]
jk
represent voltage phase differences across each line then the cycle condition imposes that
they sum to zero (mod 2
π
) around any cycle. The next theorem, proved in [57, Theorem 3] and [31],
implies that
W
G
has a psd rank-1 completion
W
if and only if
W
G
is 2
×
2 psd rank-1 on
G
and satisfies
the cycle condition (13), if and only if it has a chordal extension
W
c
(
G
)
that is psd rank-1.
3
Consider the following conditions on
(
n
+
1
)
×
(
n
+
1
)
matrices
W
and partial matrices
W
c
(
G
)
and
W
G
:
W
0
,
rank
W
=
1
(14)
W
c
(
G
)
0
,
rank
W
c
(
G
)
=
1
(15)
W
G
(
j
,
k
)
0
,
rank
W
G
(
j
,
k
) =
1
,
(
j
,
k
)
∈
E
,
(16)
Theorem 2:
Fix a graph
G
on
n
+
1 nodes and any chordal extension
c
(
G
)
of
G
. Assuming
W
j j
>
0,
[
W
c
(
G
)
]
j j
>
0 and
[
W
G
]
j j
>
0,
j
∈
N
+
, we have:
(1) Given an
(
n
+
1
)
×
(
n
+
1
)
matrix
W
that satisfies (14), its submatrix
W
c
(
G
)
satisfies (15).
(2) Given a partial matrix
W
c
(
G
)
that satisfies (15), its submatrix
W
G
satisfies (16) and the cycle condition
(13).
(3) Given a partial matrix
W
G
that satisfies (16) and the cycle condition (13), there is a completion
W
of
W
G
that satisfies (14).
Informally Theorem 2 says that (14) is equivalent to (15) is equivalent to (16)
+
(13). It characterizes a
property of the full matrix
W
(rank
W
=
1) in terms of its submatrices
W
c
(
G
)
and
W
G
. This is important
because the submatrices are typically much smaller than
W
for large sparse networks and much easier to
compute. The theorem thus allows us to solve simpler problems in terms of partial matrices as we now
explain.
3
The theorem also holds with psd replaced by negative semidefinite.
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, 1(1):15–27, MARCH 2014 (WITH PROOFS)
14
Define the set of Hermitian matrices:
W
:
=
{
W
∈
S
n
+
1
|
W
satisfies (12)
,
(14)
}
(17)
Fix any chordal extension
c
(
G
)
of
G
and define the set of Hermitian partial matrices
W
c
(
G
)
:
W
c
(
G
)
:
=
{
W
c
(
G
)
|
W
c
(
G
)
satisfies (12)
,
(15)
}
(18)
Finally define the set of Hermitian partial matrices
W
G
:
W
G
:
=
{
W
G
|
W
G
satisfies (12)
,
(13)
,
(16)
}
(19)
Note that the definition of psd for partial matrices implies that
W
c
(
G
)
and
W
G
are Hermitian. The assumption
v
j
>
0
,
j
∈
N
+
implies that all matrices or partial matrices have strictly positive diagonal entries.
Theorem 2 implies that given a partial matrix
W
c
(
G
)
∈
W
c
(
G
)
or a partial matrix
W
G
∈
W
G
there is a
psd rank-1 completion
W
∈
W
from which a solution
V
∈
V
of OPF can be recovered. In fact we know
more: given any Hermitian partial matrix
W
G
(not necessarily in
W
G
), the set of
all
completions of
W
G
that
satisfies the condition in Theorem 2(3) consists of a single psd rank-1 matrix and infinitely many indefinite
non-rank-1 matrices; see [57, Theorems 5 and 8] and discussions therein. Hence the psd rank-1 completion
W
of a
W
G
∈
W
G
is unique.
Corollary 3:
Given a partial matrix
W
c
(
G
)
∈
W
c
(
G
)
or
W
G
∈
W
G
there is a unique psd rank-1 completion
W
∈
W
.
Recall that two sets
A
and
B
are equivalent (
A
≡
B
) if there is a bijection between them. Even though
W
,
W
c
(
G
)
,
W
G
are different kinds of spaces Theorem 2 and Corollary 3 imply that they are all equivalent
to the feasible set of OPF.
Theorem 4:
V
≡
W
≡
W
c
(
G
)
≡
W
G
.
Theorem 4 suggests three equivalent problems to OPF. We assume the cost function
C
(
V
)
in OPF depends
on
V
only through the partial matrix
W
G
defined in (11). For example if the cost is total real line loss in
the network then
C
(
V
) =
∑
j
Re
s
j
=
∑
j
∑
k
:
(
j
,
k
)
∈
E
Re
(
[
W
G
]
j j
−
[
W
G
]
jk
)
y
H
jk
. If the cost is a weighted sum of
real generation power then
C
(
V
) =
∑
j
(
c
j
Re
s
j
+
p
d
j
)
where
p
d
j
are the given real power demands at buses
j
; again
C
(
V
)
is a function of the partial matrix
W
G
. Then Theorem 4 implies that OPF (7) is equivalent to
min
W
C
(
W
G
)
subject to
W
∈
ˆ
W
(20)
where
ˆ
W
is any one of the sets
W
,
W
c
(
G
)
,
W
G
. Specifically, given an optimal solution
W
opt
in
W
, it can
be uniquely decomposed into
W
opt
=
V
opt
(
V
opt
)
H
. Then
V
opt
is in
V
and an optimal solution of OPF (7).
Alternatively given an optimal solution
W
opt
F
in
W
c
(
G
)
or
W
G
, Corollary 3 guarantees that
W
opt
F
has a unique
psd rank-1 completion
W
opt
in
W
from which an optimal
V
opt
∈
V
can be recovered. In fact given a partial
matrix
W
G
∈
W
G
(or
W
c
(
G
)
∈
W
c
(
G
)
) there is a more direct construction of a feasible solution
V
∈
V
of
OPF than through its completion; see Section IV-D.
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, 1(1):15–27, MARCH 2014 (WITH PROOFS)
15
C. Semidefinite relaxations
Hence solving OPF (7) is equivalent to solving (20) over any of
W
,
W
c
(
G
)
,
W
G
for an appropriate matrix
variable. The difficulty with solving (20) is that the feasible sets
W
,
W
c
(
G
)
, and
W
G
are still nonconvex
due to the rank-1 constraints and the cycle condition (13). Their removal leads to SDP, chordal, and SOCP
relaxations of OPF respectively.
Relax
W
,
W
c
(
G
)
and
W
G
to the following convex supersets:
W
+
:
=
{
W
∈
S
n
+
1
|
W
G
satisfies (12)
,
W
0
}
W
+
c
(
G
)
:
=
{
W
c
(
G
)
|
W
G
satisfies (12)
,
W
c
(
G
)
0
}
W
+
G
:
=
{
W
G
|
W
G
satisfies (12)
,
W
G
(
j
,
k
)
0
,
(
j
,
k
)
∈
E
}
Define the problems:
OPF-sdp:
min
W
C
(
W
G
)
subject to
W
∈
W
+
(21)
OPF-ch:
min
W
c
(
G
)
C
(
W
G
)
subject to
W
c
(
G
)
∈
W
+
c
(
G
)
(22)
OPF-socp:
min
W
G
C
(
W
G
)
subject to
W
G
∈
W
+
G
(23)
The condition
W
G
(
j
,
k
)
0 in the definition of
W
+
G
is equivalent to
[
W
G
]
jk
= [
W
G
]
H
k j
and (recall the
assumption
v
j
>
0
,
j
∈
N
+
)
[
W
G
]
j j
>
0
,
[
W
G
]
kk
>
0
,
[
W
G
]
j j
[
W
G
]
kk
≥
∣
∣
[
W
G
]
jk
∣
∣
2
This is a second-order cone and hence OPF-socp is indeed an SOCP in the rotated form.
Remark 6: Literature.
SOCP relaxation for OPF seems to be first proposed in [21] for the bus injection
model (1), and in [23], [24] for the branch flow model (2) as explained in the next section. By defining a
new set of variables
v
j
:
=
|
V
j
|
2
,
R
jk
:
=
|
V
j
||
V
k
|
cos
(
θ
j
−
θ
k
)
, and
I
jk
:
=
|
V
j
||
V
k
|
sin
(
θ
j
−
θ
k
)
where
θ
j
:
=
∠
V
j
,
[21] rewrites the bus injection model (1) in the complex domain as a set of linear equations in these new
variables in the real domain and the following quadratic equations:
v
j
v
k
=
R
2
jk
+
I
2
jk
Relaxing these equalities to
v
j
v
k
≥
R
2
jk
+
I
2
jk
enlarges the solution set to a second-order cone that is equivalent
to
W
+
G
in this paper. SDP relaxation is first proposed in [22] for the bus injection model and analyzed in
[27]. Chordal relaxation for OPF is first proposed in [28], [29] and analyzed in [30], [31].
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, 1(1):15–27, MARCH 2014 (WITH PROOFS)
16
D. Solution recovery
When the convex relaxations OPF-sdp, OPF-ch, OPF-socp are exact, i.e., if their optimal solutions
W
sdp
,
W
ch
ch
,
W
socp
G
happen to lie in
W
,
W
c
(
G
)
,
W
G
respectively, then an optimal solution
V
opt
of the original OPF
can be recovered from these solutions. Indeed the recovery method works not just for an optimal solution,
but any feasible solution that lies in
W
,
W
c
(
G
)
or
W
G
. Moreover, given a
W
∈
W
or a
W
c
(
G
)
∈
W
c
(
G
)
, the
construction of
V
depends on
W
or
W
c
(
G
)
only through their submatrix
W
G
. We hence describe the method
for recovering the unique
V
from a
W
G
, which may be a partial matrix in
W
G
or the submatrix of a (partial)
matrix in
W
or
W
c
(
G
)
.
Let
T
be an arbitrary spanning tree of
G
rooted at bus 0. Let
P
j
denote the unique path from node 0 to
node
j
in
T
. Recall that
V
0
=
1
∠
0
◦
without loss of generality. For
j
=
1
,...,
n
, let
|
V
j
|
:
=
√
[
W
G
]
j j
∠
V
j
:
=
−
∑
(
i
,
k
)
∈
P
j
∠
[
W
G
]
ik
Then it can be checked that
V
is in (6) and feasible for OPF.
E. Tightness of relaxations
Since
W
⊆
W
+
,
W
c
(
G
)
⊆
W
+
c
(
G
)
,
W
G
⊆
W
+
G
, the relaxations OPF-sdp, OPF-ch, OPF-socp all provide
lower bounds on OPF (7) in light of Theorem 4. OPF-socp is the simplest computationally. OPF-ch usually
requires more computation than OPF-socp but much less than OPF-sdp for large sparse networks (even
though OPF-ch can be as complex as OPF-sdp in the worse case [63], [64]). The relative tightness of the
relaxations depends on the network topology. For a general mesh network OPF-sdp is as tight a relaxation
as OPF-ch and they are strictly tighter than OPF-socp. For a tree (radial) network the hierarchy collapses
and all three are equally tight. We now make this precise.
Consider their feasible sets
W
+
,
W
+
c
(
G
)
and
W
+
G
. We say that a set
A
is an
effective subset
of a set
B
,
denoted by
A
v
B
, if, given a (partial) matrix
a
∈
A
, there is a (partial) matrix
b
∈
B
that has the same cost
C
(
a
) =
C
(
b
)
. We say
A
is
similar to B
, denoted by
A
'
B
, if
A
v
B
and
B
v
A
. Note that
A
≡
B
implies
A
'
B
but the converse may not be true. The feasible set of OPF (7) is an effective subset of the feasible
sets of the relaxations; moreover these relaxations have similar feasible sets when the network is radial.
This is a slightly different formulation of the same results in [57], [31].
Theorem 5:
V
v
W
+
'
W
+
c
(
G
)
v
W
+
G
. If
G
is a tree then
V
v
W
+
'
W
+
c
(
G
)
'
W
+
G
.
Let
C
opt
,
C
sdp
,
C
ch
,
C
socp
be the optimal values of OPF (7), OPF-sdp (21), OPF-ch (22), OPF-socp (23)
respectively. Theorem 4 and Theorem 5 directly imply
Corollary 6: C
opt
≥
C
sdp
=
C
ch
≥
C
socp
. If
G
is a tree then
C
opt
≥
C
sdp
=
C
ch
=
C
socp
.
Remark 7: Tightness.
Theorem 5 and Corollary 6 imply that for radial networks one should always
solve OPF-socp since it is the tightest and the simplest relaxation of the three. For mesh networks there is
a tradeoff between OPF-socp and OPF-ch/OPF-sdp: the latter is tighter but requires heavier computation.
Between OPF-ch and OPF-sdp, OPF-ch is usually preferable as they are equally tight but OPF-ch is usually
much faster to solve for large sparse networks. See [28], [29], [31], [30], [66] for numerical studies that
compare these relaxations.
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, 1(1):15–27, MARCH 2014 (WITH PROOFS)
17
F. Chordal relaxation
Theorem 2 through Corollary 6 apply to
any
chordal extension
c
(
G
)
of
G
. The choice of
c
(
G
)
does not
affect the optimal value of the chordal relaxation but determines its complexity. Unfortunately the optimal
choice that minimizes the complexity of OPF-ch is NP-hard to compute.
This difficulty is due to two conflicting factors in choosing a
c
(
G
)
. Recall that the constraint
W
c
(
G
)
0 in
the definition of
W
+
c
(
G
)
consists of multiple constraints that the principal submatrices
W
c
(
G
)
(
q
)
0, one for
each (maximal) clique
q
of
c
(
G
)
. When two cliques
q
and
q
′
share a node their submatrices
W
c
(
G
)
(
q
)
and
W
c
(
G
)
(
q
′
)
share entries that must be decoupled by introducing auxiliary variables and equality constraints
on these variables. The choice of
c
(
G
)
determines the number and sizes of these submatrices
W
c
(
G
)
(
q
)
as
well as the numbers of auxiliary variables and additional decoupling constraints. On the one hand if
c
(
G
)
contains few cliques
q
then the submatrices
W
c
(
G
)
(
q
)
tend to be large and expensive to compute (e.g. if
c
(
G
)
is the complete graph then there is a single clique, but
W
c
(
G
)
=
W
and OPF-ch is identical to OPF-sdp).
On the other hand if
c
(
G
)
contains many small cliques
q
then there tends to be more overlap and chordal
relaxation tends to require more decoupling constraints. Hence choosing a good chordal extension
c
(
G
)
of
G
is important but nontrivial. See [63], [64] and references therein for methods to compute efficient chordal
relaxations of general QCQP. For OPF [30] proposes effective techniques to reduce the number of cliques
in its chordal relaxation. To further reduce the problem size [66] proposes to carefully drop some of the
decoupling constraints, though the resulting relaxation can be weaker.
V. F
EASIBLE SETS AND RELAXATIONS
: BFM
We now present an SOCP relaxation of OPF in BFM proposed in [23], [24] in two steps. We first relax
the phase angles of
V
and
I
in (2) and then we relax a set of quadratic equalities to inequalities. This
derivation pinpoints the difference between radial and mesh topologies. It motivates a recursive version of
BFM for radial networks (Section VI) and the use of phase shifters for convexification of mesh networks
(Part II [33]).
A. Feasible sets
Consider the following set of equations in the variables
x
:
= (
S
,`,
v
,
s
)
in
R
3
(
m
+
n
+
1
)
:
4
∑
k
:
j
→
k
S
jk
=
∑
i
:
i
→
j
(
S
i j
−
z
i j
`
i j
)
+
s
j
,
j
∈
N
+
(24a)
v
j
−
v
k
=
2 Re
(
z
H
jk
S
jk
)
−|
z
jk
|
2
`
jk
,
j
→
k
∈
̃
E
(24b)
v
j
`
jk
=
|
S
jk
|
2
,
j
→
k
∈
̃
E
(24c)
4
The use of complex variables is only a shorthand and should be interpreted as operations in real variables. For instance (24a) is a
shorthand for
∑
k
:
j
→
k
P
jk
=
∑
i
:
i
→
j
(
P
i j
−
r
i j
`
i j
)
+
p
j
∑
k
:
j
→
k
Q
jk
=
∑
i
:
i
→
j
(
Q
i j
−
x
i j
`
i j
)
+
q
j
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, 1(1):15–27, MARCH 2014 (WITH PROOFS)
18
and define the solution set as:
X
nc
:
=
{
x
∈
R
3
(
m
+
n
+
1
)
|
x
satisfies (3)
,
(4)
,
(24)
}
Note that the vector
v
includes
v
0
and
s
includes
s
0
. The model (24) is first proposed in [25], [26].
5
It can
be derived as a relaxation of BFM (2) as follows. Taking the squared magnitude of (2c) and replacing
|
V
j
|
2
and
|
I
jk
|
2
by
v
j
and
`
jk
respectively yield (24c). To obtain (24b), use (2b)–(2c) to write
V
k
=
V
j
−
z
jk
S
jk
V
−
1
j
and take the squared magnitude on both sides to eliminate the phase angles of
V
and
I
. These operations
define a mapping
h
:
C
2
(
m
+
n
+
1
)
→
R
3
(
m
+
n
+
1
)
by: for any ̃
x
= (
S
,
I
,
V
,
s
)
,
h
(
̃
x
)
:
= (
S
,`,
v
,
s
)
with
`
jk
=
|
I
jk
|
2
and
v
j
=
|
V
j
|
2
.
Throughout this paper we assume the cost function
C
(
̃
x
)
in OPF (9) depends on ̃
x
only through
x
:
=
h
(
̃
x
)
.
For example for total real line loss
C
(
̃
x
) =
∑
(
j
,
k
)
∈
̃
E
Re
z
jk
`
jk
. If the cost is a weighted sum of real generation
power then
C
(
̃
x
) =
∑
j
(
c
j
p
j
+
p
d
j
)
where
p
j
are the real parts of
s
j
and
p
d
j
are the given real power demands
at buses
j
; again
C
(
̃
x
)
depends only on
x
.
Then the model (24) is a relaxation of BFM (2) in the sense that the feasible set
̃
X
of OPF in (9) is an
effective subset of
X
nc
,
̃
X
v
X
nc
, since
h
(
̃
X
)
⊆
X
nc
. We now characterize the subset of
X
nc
that is equivalent
to
̃
X
.
Given an
x
:
= (
S
,`,
v
,
s
)
∈
R
3
(
m
+
n
+
1
)
define
β
(
x
)
∈
R
m
by
β
jk
(
x
)
:
=
∠
(
v
j
−
z
H
jk
S
jk
)
,
j
→
k
∈
̃
E
(25)
Even though
x
does not include phase angles of
V
,
x implies
a phase difference across each line
j
→
k
∈
̃
E
given by
β
jk
(
x
)
. The subset of
X
nc
that is equivalent to
̃
X
are those
x
for which there exists
θ
such that
θ
j
−
θ
k
=
β
jk
(
x
)
. To state this precisely let
B
be the
m
×
n
(transposed) reduced incidence matrix of
̃
G
:
B
l j
=
1
if edge
l
∈
̃
E
leaves node
j
−
1
if edge
l
∈
̃
E
enters node
j
0
otherwise
where
j
∈
N
. Consider the set of
x
∈
X
nc
such that
∃
θ
that solves
B
θ
=
β
(
x
)
mod 2
π
(26)
i.e.,
β
(
x
)
is in the range space of
B
(mod 2
π
). A solution
θ
(
x
)
, if exists, is unique in
(
−
π
,
π
]
n
. Define the
set
X
:
=
{
x
∈
R
3
(
m
+
n
+
1
)
|
x
satisfies (3)
,
(4)
,
(24)
,
(26)
}
The following result characterizes the feasible set
̃
X
of OPF in BFM and follows from [24, Theorems 2,
4].
Theorem 7:
̃
X
≡
X
⊆
X
nc
.
The bijection between
̃
X
and
X
is given by
h
defined above restricted to
̃
X
. Its inverse
h
−
1
(
S
,`,
v
,
s
) =
5
The original model, called the DistFlow equations, in [25], [26] is for radial (distribution) networks, but its extension here to mesh
networks is trivial.
IEEE TRANS. ON CONTROL OF NETWORK SYSTEMS, 1(1):15–27, MARCH 2014 (WITH PROOFS)
19
(
S
,
I
,
V
,
s
)
is defined on
X
in terms of
θ
(
x
)
by:
V
j
:
=
√
v
j
e
i
θ
j
(
x
)
,
j
∈
N
(27a)
I
jk
:
=
√
`
jk
e
i
(
θ
j
(
x
)
−
∠
S
jk
)
,
j
→
k
∈
̃
E
(27b)
The condition (26) is equivalent to the cycle condition (13) in the bus injection model. To see this fix any
spanning tree
T
= (
N
,
E
T
)
of the (directed) graph
̃
G
. We can assume without loss of generality (possibly
after re-labeling the links) that
E
T
consists of links
l
=
1
,...,
n
. Then
B
can be partitioned into
B
=
[
B
T
B
⊥
]
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
. Similarly partition
β
(
x
)
into
β
(
x
) =
[
β
T
(
x
)
β
⊥
(
x
)
]
The next result, proved in [24, Theorems 2 and 4], provides a more explicit characterization of (26)
in terms of
β
(
x
)
. When it holds this characterization has the same interpretation of the cycle condition
in (13): the voltage angle differences implied by
x
sum to zero (mod 2
π
) around any cycle. Formally
let
̃
β
be the extension of
β
from directed to undirected links: for each
j
→
k
∈
̃
E
let
̃
β
jk
(
x
)
:
=
β
jk
(
x
)
and
̃
β
k j
(
x
)
:
=
−
β
jk
(
x
)
. We say
c
:
= (
j
1
,...,
j
K
)
is an
undirected
cycle if, for each
k
=
1
,...,
K
, either
j
k
→
j
k
+
1
∈
̃
E
or
j
k
+
1
→
j
k
∈
̃
E
with the interpretation that
j
K
+
1
:
=
j
1
;
(
j
k
,
j
k
+
1
)
∈
c
denotes one of these
links.
Theorem 8:
An
x
∈
X
nc
satisfies (26) if and only if around each undirected cycle
c
we have
∑
(
j
,
k
)
∈
c
̃
β
jk
(
x
) =
0
mod 2
π
(28)
In that case
θ
(
x
) =
P
(
B
−
1
T
β
T
(
x
)
)
is the unique solution of (26) in
(
−
π
,
π
]
n
, where
P
(
φ
)
projects
φ
to
(
−
π
,
π
]
n
.
Theorem 8 determines when the voltage magnitudes
v
of a given
x
can be assigned phase angles
θ
(
x
)
so
that the resulting ̃
x
:
=
h
−
1
(
x
)
is a power flow solution in
̃
X
.
B. SOCP relaxation
The set
X
nc
that contains the (equivalent) feasible set
X
of OPF is still nonconvex because of the quadratic
equalities in (24c). Relax them to inequalities:
v
j
`
jk
≥ |
S
jk
|
2
,
(
j
,
k
)
∈
̃
E
(29)
and define the set:
X
+
:
=
{
x
∈
R
3
(
m
+
n
+
1
)
|
x
satisfies (3)
,
(4)
,
(24a)
,
(24b)
,
(29)
}