1
Exact Convex Relaxation of Optimal Power
Flow in Radial Networks
Lingwen Gan, Na Li, Ufuk Topcu, and Steven H. Low
Abstract
The optimal power flow (OPF) problem determines power generation/demand that minimize a certain objective
such as generation cost or power loss. It is nonconvex. We prove that, for radial networks, after shrinking its feasible
set slightly, the global optimum of OPF can be recovered via a second-order cone programming (SOCP) relaxation
under a condition that can be checked a priori. The condition holds for the IEEE 13-, 34-, 37-, 123-bus networks
and two real-world networks, and has a physical interpretation.
I. I
NTRODUCTION
The optimal power flow (OPF) problem determines power generations/demands to minimize a certain objective
such as generation cost or power loss. It has been one of the fundamental problems in power system operation
since it was proposed in 1962 [1]. The OPF problem is increasingly important for distribution networks due
to the advent of distributed generation (e.g., rooftop photovoltaic panels) and controllable loads (e.g., electric
vehicles). Distributed generation is difficult to predict, calling the traditional “generation follows demand” strategy
into question. Meanwhile, controllable loads provide significant potential to compensate for the randomness in
distributed generation. To achieve this, solving the OPF problem in real-time is inevitable. Distribution networks
are usually radial (with a tree topology).
The OPF problem is difficult to solve due to the nonconvex physical laws that goven power flow, and there are
in general three ways to deal with this challenge: (i) linearize the power flow laws; (ii) look for local optima of
the OPF problem; and (iii) convexify power flow laws, which are described in turn.
The power flow laws can be approximated by linear equations known as the DC power flow model [2]–[4], if
1) line resistances are small; 2) voltages are near their nominal values; and 3) voltage angle differences between
adjacent buses are small. With DC power flow model, the OPF problem reduces to a linear program. This method
is widely used in practice for transmission networks and often quite effective, but does not apply to distribution
This work was supported by NSF NetSE grant CNS 0911041, ARPA-E grant de-ar0000226, Southern California Edison, National Science
Council of Taiwan, R.O.C, grant NSC 103-3113-P-008-001, Resnick Institute, and AFOSR award number FA9550-12-1-0302.
Lingwen Gan, Na Li, and Steven H. Low are with the Engineering and Applied Science Department, California Institute of Technology,
Pasadena, CA 91125 USA (e-mail: lgan@caltech.edu).
Ufuk Topcu is with the Electrical and Systems Engineering Division, University of Pennsylvania, Philadelphia, PA 19104 USA.
December 2, 2013
DRAFT
arXiv:1311.7170v1 [math.OC] 27 Nov 2013
2
networks where line resistances are high and voltages deviate significantly from their nominal values. This method
also does not apply to problems where reactive power flow or voltage deviations need to be optimized explicitly,
e.g., power routing with FACTS devices [5] and Volt/VAR control [6].
Various algorithms have been developed to find local optima of the OPF problem, e.g., successive linear/quadratic
programming [7], trust-region based methods [8], [9], Lagrangian Newton method [10], and interior-point methods
[11]–[13]. Some of these algorithms, especially the Newton-Ralphson based ones, are quite successful empirically,
but in general, these algorithms are not guaranteed to convergence, nor converge to (nearly) optimal solutions.
There are two types of convex relaxations of the OPF problem: semidefinite programming (SDP) relaxations and
second-order cone programming (SOCP) relaxations. It is proposed in [14], [15] to transform the nonconvex power
flow constraints into linear constraints on a rank-one positive semidefinite matrix, and then remove the rank-one
constraint to obtain an SDP relaxation. If the solution of the SDP relaxation is feasible for the OPF problem, then
a global optimum of the OPF problem can be recovered. The SDP relaxation is called
exact
in this case. Strikingly,
the SDP relaxation is exact for the IEEE 14-, 30-, 57-, and 118-bus networks [15], and a more recent study on the
computational speed and exactness of the SDP relaxation can be found in [16]. Different SOCP relaxations have
been proposed for different models, first in [17] for a branch flow model in polar coordinate, then in [18], [19]
for a branch flow model due to [20], [21], and in [22] for a bus injection model. In this paper we focus on the
SOCP relaxation proposed in [18], [19] and prove a sufficient condition for the relaxation to be exact. For radial
networks, SOCP relaxation and SDP relaxation are equivalent in the sense that there is a bijection between their
feasible sets [23]. Hence one should always solve SOCP relaxation instead of SDP relaxation for radial networks
since the former has a much lower computational complexity.
SDP/SOCP relaxations are in general not exact and counterexamples can be found in [24]. Significant amount of
work has been devoted to finding sufficient conditions under which these relaxations are exact for radial networks;
see [
?
] for a survey. For
AC radial
networks, these conditions roughly fall into three categories:
1) The power injection constraints satisfy certain patterns [18], [19], [22], [25]–[28], e.g., there are no lower
bounds on the power injections (load over-satisfaction). This sufficient condition, first proved in [26] and
subsequently generalized in [28], includes as special cases the load over-satisfaction condition in [18], [19],
[22], [25] and in [29, Theorem 7], as well as the sufficient condition in [27, Theorem 2].
2) The phase angle difference across each line is bounded in terms of its
r/x
ratio [27], [29], [30]. When the
voltage magnitude is fixed this condition provides a nice geometric insight on why convex relaxations are
exact.
3) The voltage upper bounds are relaxed plus some other conditions [31], [32]. The main result in this paper
generalizes and unifies this set of sufficient conditions; see Section V.
Summary of contributions
The goal of this paper is to show that in radial networks, the SOCP relaxation is exact under a mild condition that
can be checked a priori, after modifying the OPF problem. In particular, contributions of this paper are threefold.
December 2, 2013
DRAFT
3
First, we prove that
if optimal power injections lie in a region where voltage upper bounds do not bind, then
the SOCP relaxation is exact under a mild condition
. The condition can be checked a priori and holds for the
IEEE 13-, 34-, 37-, 123-bus networks and two real-world networks. The condition has a physical interpretation:
it follows from the physical intuition that all upstream reverse power flows should increase if the power loss on
a line is reduced. Second, we
modify the OPF problem by imposing additional constraints on power injections
.
The modification ensures the exactness of the SOCP relaxation under the aforementioned condition, while only
eliminating feasible points that are close to voltage upper bounds. A modification is necessary to ensure an exact
SOCP relaxation since otherwise examples exist where the SOCP relaxation is not exact. Third,
this paper unifies
and generalizes the results in [31], [32]
.
The rest of this paper is organized as follows. The OPF problem and the SOCP relaxation are introduced in
Section II. In Section III, a sufficient condition that guarantees the exactness of the SOCP relaxation is provided.
The condition consists of two parts: C1 and C2. C2 cannot be checked a priori, hence in Section IV, we propose a
modified OPF problem whose corresponding SOCP is exact under C1. We compare C1 with prior works in Section
V and present case studies in Section VI.
II. T
HE OPTIMAL POWER FLOW PROBLEM
This paper studies the optimal power flow (OPF) problem in distribution networks, which includes Volt/VAR
control and demand response as special cases. In the following we present a model that incorporates nonlinear
power flow and a variety of controllable devices including distributed generators, inverters, controllable loads, and
shunt capacitors.
A. Power flow model
A distribution network is composed of buses and lines connecting these buses, and usually has a tree topology.
The root of the tree is a
substation bus
that is connected to the transmission network. It has a fixed voltage and
redistributes the bulk power it receives from the transmission network to other buses. Index the substation bus by 0
and the other buses by
1
,...,n
. Let
N
:=
{
0
,...,n
}
denote the collection of all buses and define
N
+
:=
N\{
0
}
.
Each line connects an ordered pair
(
i,j
)
of buses where bus
j
lies on the unique path from bus
i
to bus 0. Let
E
denote the collection of all lines, and abbreviate
(
i,j
)
∈E
by
i
→
j
whenever convenient.
For each bus
i
∈N
, let
V
i
denote its complex voltage and define
v
i
:=
|
V
i
|
2
. Specifically the substation voltage
v
0
is given and fixed. Let
s
i
=
p
i
+
i
q
i
denote the power injection of bus
i
where
p
i
and
q
i
denote the real and
reactive power injections respectively. Let
P
i
denote the path (a collection of buses in
N
and lines in
E
) from bus
i
to bus 0. For each line
(
i,j
)
∈E
, let
z
ij
=
r
ij
+
i
x
ij
denote its impedance. Let
I
ij
denote the complex current from
bus
i
to bus
j
and define
`
ij
:=
|
I
ij
|
2
. Let
S
ij
=
P
ij
+
i
Q
ij
denote the sending-end power flow from bus
i
to bus
j
where
P
ij
and
Q
ij
denote the real and reactive power flow respectively. Some of the notations are summarized
in Fig. 1. We use a letter without subscripts to denote a vector of the corresponding quantities, e.g.,
v
= (
v
i
)
i
∈N
+
,
December 2, 2013
DRAFT
4
`
= (
`
ij
)
(
i,j
)
∈E
. Note that subscript 0 is not included in nodal quantities such as
v
and
s
. For a complex number
a
∈
C
, let
̄
a
denote the conjugate of
a
.
Bus0
Bus
j
Bus
i
V
i
P
i
s
i
V
j
z
ij
`
ij
=
|
I
ij
|
2
,v
i
=
|
V
i
|
2
S
ij
,I
ij
Fig. 1. Some of the notations.
Given the network graph
(
N
,
E
)
, the impedance
z
, and the substation voltage
v
0
, then the other variables
(
s,S,v,`,s
0
)
are described by the
branch flow model
:
S
ij
=
s
i
+
∑
h
:
h
→
i
(
S
hi
−
z
hi
`
hi
)
,
∀
(
i,j
)
∈E
;
(1a)
0 =
s
0
+
∑
h
:
h
→
0
(
S
h
0
−
z
h
0
`
h
0
);
(1b)
v
i
−
v
j
= 2Re( ̄
z
ij
S
ij
)
−|
z
ij
|
2
`
ij
,
∀
(
i,j
)
∈E
;
(1c)
`
ij
=
|
S
ij
|
2
v
i
,
∀
(
i,j
)
∈E
(1d)
for radial networks [21], [33].
B. The OPF problem
We consider the following controllable devices in a distribution network: distributed generators, inverters, con-
trollable loads such as electric vehicles and smart appliances, and shunt capacitors. Real and reactive power
generation/consumption of these devices can be controlled to achieve certain objectives. For example, in Volt/VAR
control, reactive power injection of inverters and shunt capacitors are controlled to regulate voltages; in demand
response, real power consumption of controllable loads is reduced or shifted in response to power supply conditions.
Mathematically, power injection
s
is the control variable, after specifying which the other variables
(
S,v,`,s
0
)
are
determined by the power flow laws in (1).
The power injection
s
i
of a bus
i
∈N
+
is constrained to be in an pre-specified set
S
i
, i.e.,
s
i
∈S
i
, i
∈N
+
.
(2)
The set
S
i
for some controllable devices are:
•
If
s
i
represents a shunt capacitor with nameplate capacity
q
i
, then
S
i
=
{
s
∈
C
|
Re(
s
) = 0
,
Im(
s
) = 0
or
q
i
}
.
Note that
S
i
is nonconvex and disconnected in this case.
•
If
s
i
represents a solar panel with generation capacity
p
i
, that is connected to the grid through an inverter with
nameplate capacity
s
i
, then
S
i
=
{
s
∈
C
|
0
≤
Re(
s
)
≤
p
i
,
|
s
|≤
s
i
}
.
December 2, 2013
DRAFT
5
•
If
s
i
represents a controllable load with constant power factor
η
, whose real power consumption can vary contin-
uously from
−
p
i
to
−
p
i
(here
p
i
≤
p
i
≤
0
), then
S
i
=
{
s
∈
C
|
p
i
≤
Re(
s
)
≤
p
i
,
Im(
s
) =
√
1
−
η
2
Re(
s
)
/η
}
.
Note that
s
i
can represent the aggregate power injection of multiple such devices with an appropriate
S
i
, and that
the set
S
i
is not necessarily convex or connected.
An important goal of control is to regulate the voltages within a range. This is captured by pre-specified voltage
lower and upper bounds
v
i
and
v
i
(in per unit value), i.e.,
v
i
≤
v
i
≤
v
i
, i
∈N
+
.
(3)
For example, if 5% voltage deviation from nominal values is allowed, then
0
.
95
2
≤
v
i
≤
1
.
05
2
. We consider the
control objective
C
(
s,s
0
) =
∑
i
∈N
f
i
(Re(
s
i
))
(4)
where
f
i
:
R
→
R
denotes the generation cost at bus
i
for
i
∈ N
. If
f
i
(
x
) =
x
for
i
∈ N
, then
C
is the total
power loss in the network.
The OPF problem seeks to minimize the generation cost (4), subject to power flow constraint (1), power injection
constraint (2), and voltage constraint (3):
OPF:
min
∑
i
∈N
f
i
(Re(
s
i
))
over
s,S,v,`,s
0
s
.
t
. S
ij
=
s
i
+
∑
h
:
h
→
i
(
S
hi
−
z
hi
`
hi
)
,
∀
(
i,j
)
∈E
;
(5a)
0 =
s
0
+
∑
h
:
h
→
0
(
S
h
0
−
z
h
0
`
h
0
);
(5b)
v
i
−
v
j
= 2Re( ̄
z
ij
S
ij
)
−|
z
ij
|
2
`
ij
,
∀
(
i,j
)
∈E
;
(5c)
`
ij
=
|
S
ij
|
2
v
i
,
∀
(
i,j
)
∈E
;
(5d)
s
i
∈S
i
, i
∈N
+
;
(5e)
v
i
≤
v
i
≤
v
i
, i
∈N
+
.
(5f)
The following assumptions are made on OPF throughout this work.
A1 The network
(
N
,
E
)
is a tree. Distribution networks are usually radial networks.
A2 The substation voltage
v
0
is fixed and given. In practice,
v
0
can be modified several times a day, and therefore
can be considered as a given constant at the minutes timescale of OPF.
A3 Line resistances and reactances are strictly positive, i.e.,
r
ij
>
0
and
x
ij
>
0
for
(
i,j
)
∈E
. In practice,
r
ij
>
0
since lines are passive (consume power), and
x
ij
>
0
since lines are inductive.
A4 Voltage lower bounds are strictly positive, i.e.,
v
i
>
0
for
i
∈N
+
. In practice,
v
i
is slightly below 1p.u..
December 2, 2013
DRAFT
6
The equality constraint (5d) is nonconvex, and one can relax it to inequality constraints to obtain the following
second-order cone programming (SOCP) relaxation [18], [19]:
SOCP:
min
∑
i
∈N
f
i
(Re(
s
i
))
over
s,S,v,`,s
0
s
.
t
.
(5a)
−
(5c)
,
(5e)
−
(5f)
;
`
ij
≥
|
S
ij
|
2
v
i
,
∀
(
i,j
)
∈E
.
(6)
Note that SOCP is not necessarily convex, since we allow
f
i
to be nonconvex for some
i
∈ N
and
S
i
to be
nonconvex for some
i
∈N
+
. Nonetheless, we call it SOCP for brevity.
If an SOCP solution
w
= (
s,S,v,`,s
0
)
is feasible for OPF, i.e.,
w
satisfies (5d), then
w
is a global optimum of
OPF. This motivates the following definition of
exactness
for SOCP.
Definition 1.
SOCP is exact if every of its solutions satisfies
(5d)
.
III. A
SUFFICIENT CONDITION
We provide a sufficient condition that ensures SOCP to be exact in this section. This condition is composed of
two parts: C1 and C2. C1 is a mild condition that only depends on SOCP parameters. It follows from the physical
intuition that all upstream reverse power flows should increase if the power loss on a line is reduced. C2 depends
on SOCP solutions and cannot be checked a priori, but motivates us to modify OPF such that the corresponding
SOCP is exact under C1. The modified OPF problem will be discussed in Section IV.
A. Statement of the condition
We start with introducing the notations that will be used in the statement of the condition. One can ignore the
`
terms in (1a) and (1c) to obtain the
Linear DistFlow Model
[21], [33]
S
ij
=
s
i
+
∑
h
:
h
→
i
S
hi
,
∀
(
i,j
)
∈E
;
v
i
−
v
j
= 2Re( ̄
z
ij
S
ij
)
,
∀
(
i,j
)
∈E
.
Let
(
ˆ
S,
ˆ
v
)
denote the solution of the Linear DistFlow model, then
ˆ
S
ij
(
s
) =
∑
h
:
i
∈P
h
s
h
,
∀
(
i,j
)
∈E
;
ˆ
v
i
(
s
) :=
v
0
+ 2
∑
(
j,k
)
∈P
i
Re
(
̄
z
jk
ˆ
S
jk
(
s
)
)
,
∀
i
∈N
as in Fig. 2. Physically,
ˆ
S
ij
(
s
)
denote the sum of power injections
s
h
towards bus 0 that go through line
(
i,j
)
.
Note that
(
ˆ
S
(
s
)
,
ˆ
v
(
s
))
is affine in
s
, and equals
(
S,v
)
if and only if line loss
z
ij
`
ij
is 0 for
(
i,j
)
∈ E
. For two
complex numbers
a,b
∈
C
, let
a
≤
b
denote
Re(
a
)
≤
Re(
b
)
and
Im(
a
)
≤
Im(
b
)
. For two vectors
a,b
of the same
dimension,
a
≤
b
denotes componentwise inequality. Define
<
,
>
, and
≥
similarly.
December 2, 2013
DRAFT
7
i
j
0
k
2Re( ̄
z
jk
ˆ
S
jk
(
s
))
ˆ
S
ij
(
s
)
{
h
:
i
2
P
h
}
v
0
ˆ
v
i
ˆ
S
ij
=
sum of
s
in shaded region
ˆ
v
i
=
v
0
+
sumoftermsoverdashedpath
Fig. 2. Illustration of
ˆ
S
ij
and
ˆ
v
i
. The shaded region is downstream of bus
i
, and contains the buses
{
h
:
i
∈P
h
}
. Quantity
ˆ
S
ij
(
s
)
is defined
to be the sum of bus injections
s
in the shaded region. The dashed lines constitute the path
P
i
from bus
i
to bus 0. Quantity
ˆ
v
i
(
s
)
is defined
as
v
0
plus the terms
2Re( ̄
z
jk
ˆ
S
jk
(
s
))
over the dashed path.
Lemma 1.
If
(
s,S,v,`,s
0
)
satisfies
(1a)
–
(1c)
and
`
≥
0
componentwise, then
S
≤
ˆ
S
(
s
)
and
v
≤
ˆ
v
(
s
)
.
Lemma 1 implies that
ˆ
v
(
s
)
and
ˆ
S
(
s
)
provide upper bounds on
v
and
S
. The lemma is proved in Appendix A.
Let
ˆ
P
(
s
)
and
ˆ
Q
(
s
)
denote the real and imaginary part of
ˆ
S
(
s
)
respectively. Then
ˆ
P
ij
(
s
=
p
+
i
q
) =
ˆ
P
ij
(
p
) =
∑
h
:
i
∈P
h
p
h
,
(
i,j
)
∈E
;
ˆ
Q
ij
(
s
=
p
+
i
q
) =
ˆ
Q
ij
(
q
) =
∑
h
:
i
∈P
h
q
h
,
(
i,j
)
∈E
.
Assume that there exists
p
i
and
q
i
such that
S
i
⊆{
s
∈
C
|
Re(
s
)
≤
p
i
,
Im(
s
)
≤
q
i
}
for
i
∈N
+
as in Fig. 3, i.e.,
Re(
s
i
)
and
Im(
s
i
)
are upper bounded by
p
i
and
q
i
respectively. Note that we do
not
Re
Im
p
i
q
i
0
S
i
Fig. 3. We assume that
S
i
lies in the left bottom corner of
(
p
i
,
q
i
)
, but do not assume that
S
i
is convex or connected.
assume
S
i
to be convex or connected. Define
a
+
:= max
{
a,
0
}
for
a
∈
R
, let
I
:= diag(1
,
1)
denote the
2
×
2
identity matrix, and define
u
i
:=
u
ij
:=
r
ij
x
ij
, A
i
:=
A
ij
:=
I
−
2
v
i
r
ij
x
ij
(
ˆ
P
+
ij
(
p
)
ˆ
Q
+
ij
(
q
)
)
December 2, 2013
DRAFT
8
for
(
i,j
)
∈E
. Since
(
i,j
1
)
∈E
and
(
i,j
2
)
∈E
implies
j
1
=
j
2
,
A
i
and
u
i
are well-defined for
i
∈N
+
.
Further, let
L
:=
{
l
∈ N |
@
k
∈ N
such that
k
→
l
}
denote the collection of leaf buses in the network. For a
leaf bus
l
∈L
, let
n
l
+ 1
denote the number of buses on path
P
l
, and suppose
P
l
=
{
l
n
l
→
l
n
l
−
1
→
...
→
l
1
→
l
0
}
with
l
n
l
=
l
and
l
0
= 0
as in Fig. 4. Let
L
l
1
l
2
l
n
l