of 29
1
Quadratically constrained quadratic programs
on acyclic graphs with application to power
flow
Subhonmesh Bose,
Student Member, IEEE,
Dennice F. Gayme,
Member, IEEE,
K. Mani Chandy,
Fellow, IEEE,
and Steven H. Low,
Fellow, IEEE
Abstract
This paper proves that non-convex quadratically constrained quadratic programs can be solved
in polynomial time when their underlying graph is acyclic, provided the constraints satisfy a certain
technical condition. When this condition is not satisfied, we propose a heuristic to obtain a feasible
point. We demonstrate this approach on optimal power flow problems over radial networks.
Index Terms
Optimal power flow, distribution circuits, radial networks, energy storage, SDP relaxation, minimum
semidefinite rank.
I. I
NTRODUCTION
A quadratically constrained quadratic program (QCQP) is an optimization problem in which
the objective function and the constraints are quadratic. In general, QCQPs are non-convex, and
therefore lack computationally efficient solution methods. Many engineering problems including
S. Bose is with the Department of Electrical Engineering; S. H. Low and K. M. Chandy are with the Department of
Computing and Mathematical Sciences, all at the California Institute of Technology, Pasadena, CA 91125. D. F. Gayme is
with the Department of Mechanical Engineering at the Johns Hopkins University, Baltimore, MD 21218
{
boses, mani,
slow
}
@caltech.edu, dennice@jhu.edu
This work was supported by NSF through NetSE grant CNS 0911041, Southern California Edison, Cisco, and the Okawa
Foundation.
January 1, 2013
DRAFT
arXiv:1203.5599v2 [math.OC] 30 Dec 2012
2
optimal power flow (OPF) can be represented as QCQPs with complex variables. The contribution
of this paper is to expand the class of non-convex QCQPs for which globally optimal solutions
can be guaranteed.
There is a large literature on optimal or approximate algorithms for QCQPs. One such method
employs a convex semidefinite program that is a rank relaxation of the given QCQP. This is
commonly referred to as semidefinite relaxation (SDR). Such semidefinite programs are solvable
in polynomial time using interior-point methods [1]–[3]. In some instances, an optimal solution
of the original QCQP can be recovered from an optimal solution of its SDR. In other cases, SDR
provides a way to approximate the solution of a QCQP. Thus, SDR provides a computationally
tractable way to approach QCQPs [4], [5]. For example, SDR has been applied to a variety of
engineering problems such as MIMO antenna beam-forming [6]–[9], sensor network localization
[10], principal component analysis [11] and stability analysis [12]. SDR has also been extensively
used in systems and control theory applications [13], [14]. Several authors have investigated exact
relaxations, e.g., [15], [16], while others have applied SDR-based approximation techniques to
NP-hard combinatorial problems and non-convex QCQPs, e.g., [17]–[19]. The accuracy of these
approximations has also been extensively studied, e.g., [20]–[22].
In this paper, we prove a sufficient condition under which QCQPs with underlying acyclic
graph structures admit an efficient polynomial time solution using its SDR. We then apply
our result to the optimal power flow (OPF) problem on radial networks. OPF is generally
a non-convex, NP-hard problem that seeks to minimize some cost function, such as power
loss, generation cost and/or user utilities, subject to engineering constraints. Since the original
formulation of Carpentier in 1962 [23], various solution techniques have been used for this
problem; we refer the reader to [24]–[28] for some surveys. OPF can be cast as a QCQP. The
authors in [29], [30] propose to solve its SDR as an approximation. The authors in [31], instead,
propose to solve its (convex) Lagrangian dual and provide a sufficient condition under which
an optimal solution of the OPF can be recovered from a dual optimal solution. For IEEE test
systems and other randomly generated circuits, these approaches have been shown to solve OPF
optimally. Recently, OPF over radial networks has been of considerable interest. A checkable
sufficient condition has been proved in [32]–[34] where an optimal solution of OPF can be
recovered from an optimal solution of its SDR. This paper extends the previously known class
of OPF problems that can be solved efficiently.
January 1, 2013
DRAFT
3
The paper is organized as follows. In Section II, we prove a sufficient condition for a non-
convex QCQP over acyclic graphs to be solvable in polynomial time. In Section III, we apply this
result to characterize a class of OPF problems over radial networks that can be solved efficiently.
In Section IV we describe a heuristic method to obtain feasible solutions for QCQPs that do not
meet these conditions and thus their optimum solution cannot be directly recovered by solving its
SDR. We further apply this technique for the OPF problem and demonstrate through simulations
that we can always find a near-optimal feasible point for OPF. We conclude in Section V.
II. QCQP’
S AND SEMIDEFINITE RELAXATION
Consider the following QCQP with complex variable
x
C
n
.
Primal problem
P
:
minimize
x
C
n
x
H
Cx
subject to:
x
H
C
k
x
b
k
, k
∈K
.
where
x
H
denotes the conjugate transpose of
x
,
C
is either an
n
×
n
complex positive definite
matrix (denoted as
C

0
) or a positive semidefinite matrix (denoted as
C

0
),
K
is a finite
index set,
C
k
is an
n
×
n
complex Hermitian matrix and
b
k
is a scalar for each
k
∈K
.
If the matrices
C
k
,
k
∈ K
are positive semidefinite, then problem
P
is a convex program
and can be solved in polynomial time [35], [36]. If, however, these matrices are not necessarily
positive semidefinite,
P
is non-convex and NP-hard in general. The main result of this paper is
the identification of a class of QCQPs that can be solved in polynomial time even though the
matrices
C
k
,
k
∈ K
are not necessarily positive semidefinite. This result is applied in the next
section to the optimal power flow problem on radial electric networks.
We begin with some notation. Let
[
n
] :=
{
1
,
2
,...,n
}
and for any matrix
H
, let
H
ij
represent
the element corresponding to the
i
th
row and the
j
th
column. Define a function
G
from QCQP
problems to undirected graphs as follows. For a QCQP problem
P
, the undirected graph
G
(
P
)
has vertex set
[
n
]
and the edge set defined as follows:
(
i,j
)
is an edge in
G
(
P
)
⇐⇒
(
i
6
=
j
)
and
(
C
ij
6
= 0
or
[
C
k
]
ij
6
= 0
for some
k
∈K
)
(1)
Since the matrices
C
and
C
k
are Hermitian, the edges of the graph are undirected. Also,
G
(
P
)
has no self-loops from a vertex to itself. We restrict attention to QCQP problems
P
for which
the graph
G
(
P
)
is a tree, i.e., it is connected and acyclic.
January 1, 2013
DRAFT
4
For any vector of real numbers
a
, let
a

0
denote that all elements of
a
are strictly positive.
For any set of complex numbers
U
=
{
u
1
,...,u
r
}
, the
relative interior of the convex hull
[36]
of the set is defined as:
{
a
1
u
1
+
a
2
u
2
+
...a
r
u
r
C
|
a

0
and
r
`
=1
a
`
= 1
}
.
(2)
We restrict our attention to QCQP problems for which the origin of the complex plane does
not belong to the relative interior of the convex hull of the set
{
C
ij
,
[
C
k
]
ij
,k
∈K}
for any edge
(
i,j
)
in
G
(
P
)
. For any edge
(
i,j
)
in
G
(
P
)
, consider the points
C
ij
and
[
C
k
]
ij
,k
∈ K
on the
complex plane. The convex hull of these points is either a single point, a line segment, or a
convex polytope. The condition states that (a) if the hull is a single point, then that point is not
the origin, (b) if the hull is a line segment, then the origin is either an extreme point of the line
segment or the origin does not lie on the line segment, and (c) if the hull is a convex polytope
then the origin is either outside or on the boundary of this polytope. This is illustrated in Figure
1.
We also limit the discussion to QCQPs for which the set of feasible solutions is bounded and
has a strictly feasible point, i.e., there exists
x
C
n
such that
x
H
C
k
x < b
k
for all
k
∈K
.
To summarize, consider QCQPs that satisfy the following.
Condition 1:
(a)
G
(
P
)
is connected and acyclic.
(b) For any edge
(
i,j
)
in
G
(
P
)
, the origin is not in the relative interior of the convex hull of
{
C
ij
,
[
C
k
]
ij
,k
∈K}
.
(c) The set of feasible solutions of
P
is bounded and has a strictly feasible point.
The main result of the paper is the following theorem and its application.
Theorem 1:
All QCQPs
P
that satisfy condition 1 can be solved in polynomial time.
For a continuous optimization problem, we say it can be
solved in polynomial time
if given
any
ζ >
0
, there is an algorithm that finds a feasible solution to the optimization problem
with an objective value within
ζ
of the theoretical optimum in polynomial time [5], [35], [36].
For QCQPs
P
that satisfy condition 1, Theorem 1 says that we can construct such a point in
polynomial time.
To solve
P
, we use its convex relaxation that can be solved in polynomial time. The relaxation
is said to be
exact
, if there exists an optimal solution of the relaxation that can be mapped to an
optimal solution of
P
. An exact (convex) relaxation by itself does not however guarantee that
P
January 1, 2013
DRAFT
5
(a) Origin does
not
belong to the relative interior of the convex hull of these points.
(b) Origin lies in the relative interior of the convex hull of these points.
Fig. 1: Convex hull of
{
C
ij
,
[
C
k
]
ij
,k
∈K}
in condition 1(b).
January 1, 2013
DRAFT
6
can be solved in polynomial time. This is the case when the set of optimizers of the relaxation
contains solutions that cannot be mapped to a feasible point in
P
and there may or may not be
a polynomial time algorithm to find a correct optimum among that set of optimizers.
1
Theorem
1 asserts that when condition 1 holds, not only the convex relaxation of
P
is exact, but it can
also be solved in polynomial time. See Remark 1 at the end of this section for more details.
In the remainder of this section, we prove Theorem 1 for the case where
C
is positive definite.
The proof for the positive semidefinite case is presented in the appendix. Our proof requires the
following result on Hermitian matrices, that is presented here and proved in the appendix.
Lemma 2:
If
H
1

0
and
H
2

0
are two
n
×
n
matrices,
tr(
H
1
H
2
)
ρ
min
[
H
1
]
ρ
max
[
H
2
]
.
where
ρ
min
[
H
]
and
ρ
max
[
H
]
respectively denote the minimum and maximum eigenvalues of any
Hermitian matrix
H
.
A. Proof of Theorem 1 for
C

0
:
For
C

0
, we prove the result more generally by relaxing the condition that the feasible
region of
P
is bounded. Consider the following semidefinite program
RP
where
W
is an
n
×
n
complex positive semidefinite matrix.
Relaxed Problem
RP
:
minimize
W

0
tr(
CW
)
subject to:
tr (
C
k
W
)
b
k
, k
∈K
.
(3)
RP
is a convex relaxation of
P
[5], [36]. Define
p
and
r
as the optimum values of the objective
functions for problems
P
and
RP
respectively.
Lemma 3:
p
,
r
are finite and
p
r
. If
W
solves
RP
optimally and rank
W
1
, then
p
=
r
and problem
P
has an exact SDR.
Proof:
The objective functions of
P
and
RP
are nonnegative and hence
p
and
r
are
finite. Given any feasible solution
x
of
P
,
W
:=
xx
H
is a feasible solution of
RP
. Hence
RP
1
If
every
optimal solution of the relaxation can be mapped to a solution of
P
, then clearly
P
can be solved in polynomial
time. This is sufficient but not a necessary condition for a polynomial time solution.
January 1, 2013
DRAFT
7
is feasible and
p
r
. If rank
W
= 0
, then
W
= 0
, and an optimal solution to
P
is
x
= 0
,
and therefore
r
=
p
. If rank
W
= 1
then
W
has a unique decomposition
W
=
x
x
H
, where
r
= tr(
CW
) =
x
H
Cx
=
p
.
Next, we show that there exists a finite
W
that solves
RP
optimally and has rank
W
1
.
Let the Lagrange multipliers for the inequalities in (3) be
λ
k
0
for each
k
∈ K
. Then the
Lagrangian dual of
RP
is
Dual problem
DP
:
maximize
λ
0
k
∈K
λ
k
b
k
subject to
C
+
k
∈K
λ
k
C
k

0
.
For convenience, we introduce the
n
×
n
matrix
A
(
λ
)
defined as:
A
(
λ
) :=
C
+
k
∈K
λ
k
C
k
,
(4)
Define a function
F
from Hermitian matrices to undirected graphs as follows. For any
n
×
n
Hermitian matrix
H
, the graph
F
(
H
)
on the vertex set
[
n
]
satisfies
(
i,j
)
is an edge in
F
(
H
)
⇐⇒
i
6
=
j
and
H
ij
6
= 0
.
(5)
From the definitions of
F
,
G
and
A
(
λ
)
, it follows that for any
λ
,
F
(
A
(
λ
))
is a subgraph of
G
(
P
)
. For some values of
λ
however, edge
(
i,j
)
may exist in
G
(
P
)
but not in
F
(
A
(
λ
))
; in this
case
F
(
A
(
λ
))
is acyclic but may not be connected, and hence it may be a forest of two or more
disconnected trees rather than a single connected tree that spans all vertices in the graph. Now,
we present a lemma about the connectedness of the graph
F
(
A
(
λ
))
.
Lemma 4:
For all
λ

0
,
F
(
A
(
λ
))
is connected.
Proof:
Consider any edge
(
i,j
)
in
G
(
P
)
. From condition 1, the origin is not in the relative
interior of the convex hull of
{
C
ij
,
[
C
k
]
ij
,k
∈K}
. Using (4), we have
[
A
(
λ
)]
ij
6
= 0
and hence
(
i,j
)
is an edge of
F
(
A
(
λ
))
. Thus
F
(
A
(
λ
))
is identical to
G
(
P
)
which is a tree that spans all
the vertices of the graph.
Next we characterize the relationship between the optimal points of
RP
and
DP
. Let
d
denote the optimal value of the objective function of
DP
.
January 1, 2013
DRAFT
8
Lemma 5:
r
=
d
and
RP/DP
has a finite primal dual optimal point
(
W
)
.
Proof:
To prove this, we first show that
DP
is strictly feasible. At
λ
= 0
,
ρ
min
[
A
(
λ
)] =
ρ
min
[
C
]
>
0
. For a sufficiently small
λ

0
,
ρ
min
[
A
(
λ
)]
>
0
and hence
A
(
λ
)

0
. This implies
λ
is a strictly feasible point of
DP
. Also since
P
is assumed to be strictly feasible,
RP
is
strictly feasible and it has a finite optimum
r
. The rest follows from Slater’s condition [36].
For convenience, define
A
:=
A
(
λ
)
. Now we turn our attention to the graph of
A
, i.e.,
F
(
A
)
to further analyze the primal dual optimum point
(
W
)
of
RP/DP
.
Lemma 6:
If
F
(
A
)
is connected then rank
W
1
.
Proof:
We observe that rank
A
n
1
. This follows from a result in the literature [37], [38,
Theorem 3.4] and [39, Corollary 3.9] that states that for any
n
×
n
positive semidefinite matrix
H
where the associated graph
F
(
H
)
is a connected acyclic graph (i.e., a tree), rank
H
n
1
.
Next we show that rank
W
1
. The complementary slackness condition for optimality of
(
W
)
implies
tr
(
A
W
) = 0
.
Let
W
=
i
ρ
i
w
i
w
H
i
be the spectral decomposition of
W
. Then,
tr
(
A
W
) =
i
ρ
i
w
H
i
A
w
i
= 0
.
Since
A

0
, the eigenvectors
w
i
of
W
corresponding to nonzero eigenvalues
ρ
i
are all in the
null space of
A
. The rank of
A
is at least
n
1
and hence its null space has dimension at
most 1, from which it follows that rank
W
1
.
F
(
A
)
can be connected in one of two ways: (a) the origin of the complex plane lies strictly
outside the convex hull of the set of points
{
C
ij
,
[
C
k
]
ij
6
= 0
,k
∈K}
for all edges
(
i,j
)
in
G
(
P
)
,
or (b)
λ

0
(from lemma 4). In both cases, lemma 6 guarantees that rank
W
1
.
If the origin lies on the boundary of the convex hull however, then
F
(
A
)
may not be connected
when
λ
is not element-wise strictly positive and therefore rank
W
1
may not hold. In that
case, we cannot obtain an optimum solution of
P
from the optimum solution of
RP
. We deal
with this case where
F
(
A
)
is disconnected by using a perturbation [40], [41] of
RP/DP
so
that
F
(
A
)
is connected in the perturbed problem. Then we recover an optimal solution
W
for
RP
such that rank
W
1
from the perturbed problem.
January 1, 2013
DRAFT
9
Define the perturbed problems for parameter
ε >
0
:
Perturbed relaxed problem
RP
ε
:
minimize
W

0
tr(
CW
)
ε
k
∈K
[
b
k
tr (
C
k
W
)]
subject to:
tr (
C
k
W
)
b
k
, k
∈K
.
Perturbed dual problem
DP
ε
:
maximize
λ
k
∈K
λ
k
b
k
subject to
A
(
λ
)

0
, λ
k
ε, k
∈K
.
For any variable
z
in the original problem, let
z
ε
denote the corresponding variable in the
perturbed problem with perturbation parameter
ε
.
Lemma 7:
There exists a
ε
0
>
0
, such that for all
ε
in
(0
0
)
:
1)
r
ε
=
d
ε
and
RP
ε
/DP
ε
has a finite primal dual optimal point
(
W
ε
ε
)
.
2)
F
(
A
ε
)
is connected and rank
W
ε
1
.
Proof:
We choose
ε
0
as follows. For
ε >
0
, observe that
A
(
ε
1
) =
C
+
ε
k
∈K
C
k
,
where
1
is a vector of all ones of appropriate size. Then
ρ
min
[
A
(
ε
1
)]
is a continuous function
of
ε
that has the value
ρ
min
[
C
]
>
0
at
ε
= 0
. Choose
ε
0
sufficiently small such that
ρ
min
[
A
(
ε
1
)]
is strictly bounded away from 0, i.e.,
min
ε
[0
0
]
ρ
min
[
A
(
ε
1
)]
>
0
.
Consider any
ε
in
(0
0
)
. The feasible sets of
RP
and
RP
ε
are identical. Since
A
(
ε
1
)

0
and
W

0
for a feasible point
W
of
RP
(and
RP
ε
),
tr(
CW
)
ε
k
∈K
[
b
k
tr (
C
k
W
)] = tr [
A
(
ε
1
)
W
]
ε
k
∈K
b
k
≥−
ε
0
k
∈K
b
k
and hence
r
ε
is finite.
RP
ε
/DP
ε
are strictly feasible and
r
ε
is bounded below. The first part of
lemma 7 then follows from Slater’s condition [36].
To prove the second part of lemma 7, note that
λ
ε
1

0
. Lemmas 4 and 6 applied to
RP
ε
proves the claim.
January 1, 2013
DRAFT
10
We have shown that for all
ε
in a nonempty interval
(0
0
)
, the optimal solution
W
ε
of
RP
ε
has rank at most 1. Now we analyze the behavior of
W
ε
as
ε
converges to zero. Let
{
ε
`
}
`
=1
be a
decreasing sequence such that
ε
`
0
as
`
→∞
. Consider the sequence of matrices
{
W
ε
`
}
`
=1
;
every matrix in this sequence has rank at most 1. In the next lemma we show that this sequence
has a convergent subsequence and the limit of this subsequence solves
RP
optimally.
Lemma 8:
{
W
ε
`
}
`
=1
has a convergent subsequence. The limit point
ˆ
W
of this subsequence
solves
RP
optimally and satisfies rank
ˆ
W
1
.
Proof:
Consider any
ε
in
(0
0
)
. We first show that
W
ε
is bounded, independent of
ε
. For
any
W
in the feasible set of
RP
(and
RP
ε
),
tr(
CW
)
ε
k
∈K
[
b
k
tr (
C
k
W
)]
︷︷
0
tr(
CW
)
.
Minimizing both sides over the feasible set of
RP
(and
RP
ε
), we have
r
ε
r
,
(6)
that implies
tr [
A
(
ε
1
)
W
ε
] =
r
ε
+
ε
k
∈K
b
k
r
+
ε
0
k
∈K
b
k
.
(7)
Also, Lemma 2 implies
tr [
A
(
ε
1
)
W
ε
]
ρ
min
[
A
(
ε
1
)]
ρ
max
[
W
ε
]
[
min
ε
[0
0
]
ρ
min
[
A
(
ε
1
)]
]
︷︷
>
0
by construction.
ρ
max
[
W
ε
]
.
(8)
Combining equations (7) and (8), we obtain a bound for
ρ
max
[
W
ε
]
, independent of
ε
:
ρ
max
[
W
ε
]
r
+
ε
0
k
∈K
b
k
min
ε
[0
0
]
ρ
min
[
A
(
ε
1
)]
.
Thus
W
ε
is bounded and rank
W
ε
1
. Since the set of positive semidefinite matrices with
rank at most
1
is closed [42],
W
ε
lies in a compact set and
{
W
ε
`
}
`
=1
has a convergent subse-
quence. Let the limit of this subsequence be
ˆ
W
. Then
ˆ
W
is feasible for
RP
and rank
ˆ
W
1
.
Next, we prove that
r
= tr(
C
ˆ
W
)
and hence
ˆ
W
solves
RP
optimally.
January 1, 2013
DRAFT
11
From (6),
r
ε
= tr(
CW
ε
)
ε
k
∈K
[
b
k
tr (
C
k
W
ε
)]
r
.
(9)
Taking limit over the convergent subsequence of
{
W
ε
`
}
`
=1
, we get
tr(
C
ˆ
W
)
r
. Also,
r
is
the optimum value of
RP
and hence
r
tr(
C
ˆ
W
)
. This completes the proof of lemma 8.
So far we have shown that
RP
has a minimizer
ˆ
W
that satisfies rank
ˆ
W
1
and
p
=
r
,
i.e., SDR of
P
is exact. But it is, in general, hard to guarantee that solving
RP
would yield the
minimum rank optimizer if the set of optimizers of
RP
is non-unique. In that case,
RP
cannot
be directly used to solve
P
in polynomial time. In what follows, we present an algorithm to
solve
P
in polynomial time.
First, solve
RP
in polynomial time to obtain
r
. If the associated optimizer
W
has rank at
most 1, then construct
x
from
W
as in lemma 3. We have then found
x
in polynomial time
that solves
P
optimally. If however rank
W
>
1
, choose
ε
0
as given above and solve
RP
ε
0
in
polynomial time. For any
ε
in
(0
0
)
,
r
ε
= tr(
CW
ε
)
ε
k
∈K
[
b
k
tr(
C
k
W
ε
)]
r
tr(
CW
ε
)
,
(10)
where the first inequality follows from (6) and the second one follows from the fact that
r
is
the optimum value of
RP
. Also, comparing the objective function values of
RP
ε
and
RP
ε
0
at
W
ε
and
W
ε
0
respectively, we have
k
∈K
[
b
k
tr(
C
k
W
ε
)]
k
∈K
[
b
k
tr(
C
k
W
ε
0
)]
.
(11)
Combining (10) and (11), we have
|
r
tr(
CW
ε
)
|≤
ε
k
∈K
[
b
k
tr(
C
k
W
ε
0
)]
.
Given any
ζ >
0
, choose
ε
in
(0
0
)
such that
k
∈K
[
b
k
tr(
C
k
W
ε
0
)]
ζ
. Now solve
RP
ε
in
polynomial time to get
W
ε
that satisfies rank
W
ε
1
and compute
x
ε
from it. Then
x
ε
is a
feasible point of
P
and
p
(
x
ε
)
H
C
(
x
ε
)
p
+
ζ.
Also, we have computed
x
ε
in polynomial time. This completes the proof of Theorem 1 for the
case where
C
is positive definite. We remark that a perturbation by an arbitrary small
ε >
0
January 1, 2013
DRAFT
12
can be represented by treating each perturbed scalar variable as a pair
[
a,a
]
to represent
a
+
εa
when solving
RP
using any standard polynomial time algorithm like the interior-point method
[1]–[3], where the pairs
[
a,a
]
are ordered lexicographically [43].
The proof extending the theorem to the case where
C
is positive semidefinite is given in the
appendix.
Remark 1:
The strict feasibility of
P
in Condition 1 is required to solve
P
in polynomial
time. If we relax that constraint, it can be shown that there still exists a positive semidefinite
matrix
W
that solves
RP
optimally and rank
W
1
, i.e.,
P
has an exact SDR. There might
also be other optimal solutions of
RP
that do not satisfy the rank condition and hence cannot
be mapped to an optimal solution of
P
. Solving for a low-rank optimizer arbitrarily closely in
polynomial time is hard to guarantee and is a direction for future work.
III. O
PTIMAL
P
OWER
F
LOW
: A
N APPLICATION
In this section, we apply the results of Section II to the optimal power flow (OPF) problem.
We start by summarizing some of the recent results on OPF relaxations in Section III-A. In
Section III-B we formulate OPF as a QCQP. In Section III-C we restrict our attention to OPF
over radial networks, which are the networks commonly found in distribution circuits, and use
Theorem 1 to characterize a set of conditions under which OPF can be solved efficiently.
A. Prior work
As previously discussed, OPF can be cast as a QCQP. Various non-linear programming
techniques have been applied to the resulting nonconvex problem, e.g., in [44]–[46]. An SDR
for OPF has been explored in [29], [30] and their simulations indicate that the SDR provides
an exact solution of original OPF for many of the IEEE test systems [47]. The authors in [31],
[48] propose to solve the convex Lagrangian dual of OPF and derive a sufficient condition under
which an optimal solution of OPF can be recovered from an optimal dual solution. Though SDR
recovers a solution to OPF on IEEE test systems, it does not work on all problem instances.
Such limitations have been most recently reported in [49], though the nonconvexity of power
flow solutions have been studied much earlier, e.g., in [33], [50]–[52].
Recently, a series of work has explored a class of problems where such limitations do not
apply due to the network topology. It has been independently reported in [32]–[34] that the SDR
January 1, 2013
DRAFT
13
of OPF is exact for radial networks provided certain conditions on the power flow constraints
are satisfied. A different approach to OPF has been explored using the branch flow model,
first introduced in [53], [54]. While [55] studies a linear approximation of this model, various
relaxations based on second-order cone programming (SOCP) have been proposed in [56]–[59].
Authors in [57]–[59] prove that this relaxation is exact for radial networks when there are no
upper bounds on loads, or when there are no upper bounds on voltage magnitudes.
Motivated by the results in [57], a more general branch flow model is introduced in [60]
for the power flow analysis and optimization for both radial and meshed networks. The precise
relationships between the SOCP relaxations and the SDR for the OPF problem has been recently
identified in [61].
B. Problem Formulation
Consider a power system network with
n
nodes (buses). The admittance-to-ground at bus
i
is
y
ii
and the admittance of the line between connected nodes
i
and
j
(denoted by
i
j
) is
y
ij
=
g
ij
i
b
ij
. We assume both
g
ij
>
0
and
b
ij
>
0
, i.e., the lines are resistive and inductive.
Define the corresponding
n
×
n
admittance matrix
Y
as
Y
ij
=
y
ii
+
j
i
y
ij
,
if
i
=
j,
y
ij
,
if
i
6
=
j
and
i
j,
0
otherwise
.
(12)
Remark 2:
Y
is symmetric but not necessarily Hermitian.
The remaining circuit parameters and their relations are defined as follows.
V
and
I
are
n
-dimensional complex voltage and current vectors, where
V
k
,
I
k
denote the
voltage and the injection current at bus
k
[
n
]
respectively. The voltage magnitude at each
bus is bounded as
0
< W
k
≤|
V
k
|
2
W
k
, k
[
n
]
.
S
=
P
+
i
Q
is the
n
-dimensional complex power vector, where
P
and
Q
respectively denote
the real and reactive powers and
S
k
=
P
k
+
i
Q
k
=
V
k
I
H
k
, k
[
n
]
.
(13)
January 1, 2013
DRAFT
14
P
D
k
and
Q
D
k
are the real and reactive power demands at bus
k
[
n
]
, which are assumed to
be fixed and given.
P
G
k
and
Q
G
k
are the real and reactive power generation at bus
k
. They are decision variables
that satisfy the constraints
P
G
k
P
G
k
P
G
k
and
Q
G
k
Q
G
k
Q
G
k
.
Power balance at each bus
k
[
n
]
requires
P
G
k
=
P
D
k
+
P
k
and
Q
G
k
=
Q
D
k
+
Q
k
, which leads
us to define
P
k
:=
P
G
k
P
D
k
,
P
k
:=
P
G
k
P
D
k
Q
k
:=
Q
G
k
Q
D
k
,
Q
k
:=
Q
G
k
Q
D
k
.
The power injections at each bus
k
[
n
]
are then bounded as
P
k
P
k
P
k
, Q
k
Q
k
Q
k
.
The branch power flows and their limits are defined as follows.
S
ij
=
P
ij
+
i
Q
ij
is the sending-end complex power flow from node
i
to node
j
, where
P
ij
and
Q
ij
are the real and reactive power flows respectively. The real power flows are
constrained as
|
P
ij
| ≤
F
ij
where
F
ij
is the line-flow limit between nodes
i
and
j
and
F
ij
=
F
ji
.
L
ij
=
P
ij
+
P
ji
is the power loss over the line between nodes
i
and
j
, satisfying
L
ij
L
ij
where
L
ij
is the thermal line limit and
L
ij
=
L
ji
. Also, observe that since
L
ij
0
, we
have
|
P
ij
|≤
F
ij
,
|
P
ji
|≤
F
ji
if and only if
P
ij
F
ij
,P
ji
F
ji
.
Let
J
k
=
e
k
e
H
k
where
e
k
is the
k
-th canonical basis vector in
C
n
. Define
Y
k
:=
e
k
e
H
k
Y
.
Substituting these expressions into (13) yields
S
k
=
e
H
k
V I
H
e
k
= tr
(
V V
H
(
Y
H
e
k
e
H
k
)
)
=
V
H
Y
H
k
V
=
V
H
(
Y
H
k
+
Y
k
2
)
︷︷
=:Φ
k
V
+
i
V
H
(
Y
H
k
Y
k
2
i
)
︷︷
=:Ψ
k
V
,
(14)
where
Φ
k
and
Ψ
k
are Hermitian matrices. Thus, the two quantities
V
H
Φ
k
V
and
V
H
Ψ
k
V
are
real numbers; moreover
P
k
=
V
H
Φ
k
V, Q
k
=
V
H
Ψ
k
V.
January 1, 2013
DRAFT
15
The real power flow from
i
to
j
can be expressed as a quadratic form as follows.
P
ij
=
Re
{
V
i
(
V
i
V
j
)
H
y
H
ij
}
=
V
H
M
ij
V,
(15)
where
M
ij
is an
n
×
n
Hermitian matrix. Further details of the OPF problem formulation are
provided in the appendix.
The thermal loss of the line connecting buses
i
and
j
is
L
ij
=
L
ji
=
P
ij
+
P
ji
=
V
H
T
ij
V
(16)
where
T
ij
=
T
ji
:=
M
ij
+
M
ji

0
.
For a Hermitian positive semidefinite
n
×
n
matrix
C
, we have
Optimal power flow problem
OPF
:
minimize
V
C
n
V
H
CV
subject to:
P
k
V
H
Φ
k
V
P
k
, k
[
n
]
,
(17a)
Q
k
V
H
Ψ
k
V
Q
k
, k
[
n
]
,
(17b)
W
k
V
H
J
k
V
W
k
, k
[
n
]
,
(17c)
V
H
M
ij
V
F
ij
, i
j,
(17d)
V
H
T
ij
V
L
ij
, i
j,
(17e)
where (17a)–(17e) are respectively constraints on the real and reactive powers, the voltage
magnitudes, the line flows and thermal losses. Note that since
T
ij

0
, (16) implies that
P
ij
+
P
ji
0
. This means that (17d) holds if and only if
|
P
ij
| ≤
F
ij
, i.e., (17d) bounds
the line flows on both ends.
We do not include line-flow constraints that impose an upper bound on the apparent power
P
2
ij
+
Q
2
ij
on each branch
i
j
. These constraints are not quadratic in voltages and hence
beyond the scope of our model.
Remark 3 (Objective Functions):
We consider different optimality criteria by changing
C
as
follows:
Voltages:
C
=
I
n
×
n
(identity matrix) where we aim to minimize
V
2
=
k
|
V
k
|
2
.
January 1, 2013
DRAFT