Examining the Limits of the Application of

Semidefinite Programming to Power Flow Problems

Bernard C. Lesieutre, Daniel K. Molzahn, Alex R. Borden, and Christopher L. DeMarco
Electrical and Computer Engineering Department
University of Wisconsin-Madison
Madison, WI 53706, USA
Email: lesieutre@wisc.edu, molzahn@wisc.edu, borden@wisc.edu, demarco@engr.wisc.edu

Abstract—The application of semidefinite programming (SDP) While this approach is promising, the relaxation inherent
to power system problems has recently attracted substantial in the SDP formulation may yield solutions that are not
research interest. Specifically, a recent SDP formulation offers physically meaningful. However, with their success on a
a convex relaxation to the well-known, typically nonconvex
“optimal power flow” (OPF) problem. This new formulation was significant number of standard IEEE test cases, Lavaei and
demonstrated to yield zero duality gap for several standard power Low claim in [7] that their SDP formulation will satisfy a
systems test cases, thereby ensuring a globally optimal OPF condition ensuring zero duality gap between the primal and
solution in each. The first goal of the work here is to investigate dual objective functions for most practical OPF problems.
this SDP algorithm for the OPF, and show by example that it can We explore a counterexample to this assertion: a three-
fail to give a physically meaningful solution (i.e., it has a non-
zero duality gap) in some scenarios of practical interest. The bus system with a constraint on the magnitude of complex
remainder of this paper investigates a SDP approach utilizing power flow (“apparent power”) on a transmission line. This
modified objective and constraints to compute all solutions example represents a power system with parameters in realistic
of the nonlinear power flow equations. Several variants are ranges, operated with a commonly imposed constraint. The
described. Results suggest SDP’s promise as an efficient algorithm SDP formulation finds a physically meaningful solution when
for identifying large numbers of solutions to the power flow
equations. the line-flow limit is reasonably large, but fails when a stricter
line-flow limit is enforced. The latter case has a non-zero
I. I NTRODUCTION duality gap.
The optimal power flow (OPF) problem seeks decision Directing attention to constraint equations within the OPF,
variable values to yield an optimal operating point for an the power flow equations govern the relationships between
electric power system in terms of a specified objective and voltages and active and reactive power injections in a power
subject to a wide range of engineering limits on active and system. Solutions to the power flow equations correspond to
reactive power generation, bus voltage magnitudes, transmis- the equilibrium points of the underlying differential equations
sion line and transformer flows, and possibly network stability that govern power system dynamic behavior; it is well known
constraints. Total generation cost is the typical objective; other that large numbers of such solutions can exist [8]. Locating
objectives, such as loss minimization, may be considered. multiple solutions to the power flow equations, particularly
The nonconvexity of the OPF problem has made solution those exhibiting low-voltage magnitude, is important to power
techniques an ongoing topic of research since the problem was system stability assessment [9], [10], [11], [12].
first introduced in 1962 by Carpentier [1]. Nonconvexity in One very direct approach to finding multiple power flow
typical OPF formulations enters largely through the nonlinear solutions simply initializes a Newton-Raphson iteration [13]
power flow equations representing physical constraints on the over a range of carefully selected candidate initial conditions.
electric grid [2]. The long literature reflects a wide range of In another approach, Salam et al. [14] applied the homotopy
proposed solution techniques including successive quadratic method of Chow et al. [15] to the power flow problem. This
programs, Lagrangian relaxation, genetic algorithms, particle method can reliably find all solutions [14] but has a com-
swarm optimization, and interior point methods [3], [4]. putational complexity that grows exponentially with system
Recent research has pursued the application of semidefinite size. Ma and Thorp developed a continuation power flow
programming (SDP) to the OPF problem [5], [6], [7]. SDP algorithm that is computationally tractable for large systems
formulations create a convex relaxation of the OPF problem; [16]. However, while the original work claimed a guarantee
the global solution of the relaxed problem can be found in that the algorithm would find all solutions, a recent critique
polynomial time. If the relaxed problem can then be guaran- of this paper revealed a flaw in the associated proof [17], and
teed to display a zero duality gap, the solution of the relaxed we have subsequently constructed a counterexample. Thus one
problem must be the global optimum of the original OPF. may fairly characterize the state of the art as lacking a tractable
None of the prior methods offer such a means to guarantee algorithm to compute all solutions to the power flow solutions.
global optimum, and hence the SDP formulation has attracted We investigate a SDP formulation of the power flow
significant interest. problem in the context of five-bus and seven-bus example
 n
systems whose modest dimension allow for identification of X
PGk − PDk =Vdk (Gik Vdi − Bik Vqi )
all solutions via [14]. We attempt to replicate these solutions
i=1
using two variants of the SDP approach to the OPF: one n
X
modifying constraints, the other modifying the objective. The + Vqk (Bik Vdi + Gik Vqi ) (2f)
constraint modification proved wholly unsuccessful. Objective i=1
modification had varying success, as described in more detail n
X
below. QGk − QDk =Vdk (−Bik Vdi − Gik Vqi )
This paper is organized as follows. In Section II, we i=1
n
present the OPF problem in both its classical form and the X
+ Vqk (Gik Vdi − Bik Vqi ) (2g)
SDP form. In Section III, we discuss cases where the SDP
i=1
formulation of the OPF problem fails to provide physically
meaningful results. This includes an example using a three-bus Note that this formulation limits the apparent power flow
system where the SDP formulation fails with a strict line-flow measured at each end of a given line, recognizing that active
constraint. In Section IV, we discuss techniques for finding and reactive line losses can cause these quantities to differ.
multiple solutions to the power flow problem using the SDP
formulation. B. Semidefinite Programming Formulation of the Optimal
Power Flow Problem
II. T HE O PTIMAL P OWER F LOW P ROBLEM
This section describes the formulation of the OPF problem
We first present the OPF problem as it is classically formu- as adopted from the SDP algorithm of [7]. Let ek denote
lated. Specifically, this formulation is in terms of rectangular the k th standard basis vector in Rn . Define the matrix Yk =
voltage coordinates, active and reactive power generation, and ek eTk Y, where the superscript T indicates
the transpose opera-
apparent power line-flow limits. See [18] for a review of tor. Define the matrix Ylm = j blm T T
2 + ylm el el − (ylm ) el em ,
the power flow equations in rectangular voltage coordinates. where blm is the total shunt susceptance and ylm is the series
−1
As noted above, this classical OPF formulation is generally admittance of the line (see Figure 1, ylm = (Rlm + jXlm ) ).
nonconvex. We then review the SDP formulation of [7].
Rlm jXlm
A. Classical Formulation of the Optimal Power Flow Problem
Consider an n-bus power system, where N = {1, 2, . . . , n}
represents the set of all buses, G represents the set of generator
buses, and L represents the set of all lines. Let PDk + jQDk j blm
2 j blm
2
represent the active and reactive load demand at each bus
k ∈ N . Let Vk = Vdk + jVqk represent the voltage phasors in
rectangular coordinates at each bus k ∈ N . Let PGk + jQGk
Fig. 1. Transmission Line Π Circuit Model
represent the generation at generator buses k ∈ G. Let Slm
represent the apparent power flow on the line (l, m) ∈ L.
Superscripts “max” and “min” denote specified upper and Matrices employed in the SDP algorithm are given as
lower limits. Let Y = G + jB denote the network admittance
matrix.
"
#
1 Re Yk + YkT Im YkT − Yk


Define a quadratic objective function associated with each Yk = (3)
2 Im Yk − YkT Re Yk + YkT



generator k ∈ G, typically representing a dollar/hour variable "
#
1 Im Yk + YkT Re Yk − YkT


operating cost.
Ȳk = − (4)
2 Re YkT − Yk Im Yk + YkT



2
fk (PGk ) = ck2 PGk + ck1 PGk + ck0 (1) " #
ek eTk 0
Mk = (5)
The classical OPF problem can then be written as 0 ek eTk
"
#
T T


1 Re Ylm + Ylm Im Ylm − Ylm
X Ylm = T

T

(6)
min fk (PGk ) (2a) 2 Im Ylm − Ylm Re Ylm + Ylm
k∈G "
T

T

#
1 Im Ylm + Ylm Re Ylm − Ylm
subject to Ȳlm = − (7)
T T



min max 2 Re Ylm − Ylm Im Ylm + Ylm
PGk ≤ PGk ≤ PGk ∀k ∈ G (2b)
Qmin max
Gk ≤ QGk ≤ QGk ∀k ∈ G (2c) Define vectors of Lagrange multipliers associated with

2 2 lower inequality bounds (2b), (2c), and (2d) as λk , γ k , and
2
Vkmin ≤ Vdk 2
+ Vqk ≤ (Vkmax ) ∀k ∈ N (2d)
max
µk , and those associated with upper bounds as λ̄k , γ̄k , and
|Slm | ≤ Slm ∀ (l, m) ∈ L (2e) µ̄k , respectively.
 Define 3 × 3 symmetric matrices to represent generalized III. D ISCUSSION ON THE S EMIDEFINITE P ROGRAMMING
Lagrange multipliers for the line-flow limits (2e): Hlm , with F ORMULATION ’ S A BILITY TO P ROVIDE P HYSICALLY
Hik
lm the (i, k) element of Hlm . M EANINGFUL R ESULTS
Define 2 × 2 symmetric matrices to represent generalized It is important to note that the SDP formulation above
Lagrange multipliers for the quadratic cost functions (2a): Rk , does not enforce the two-dimensional nullspace for A nor the
with Rik
k the (i, k) element of Rk . corresponding rank one condition on W. If the nullspace of A
Define aggregate multipliers λk , γk , and µk for all k ∈ N . has dimension greater than two at the dual problem’s solution,
the duality gap is non-zero and W does not yield a solution
( √ to the primal OPF problem of interest. In [7] the authors
λ̄k − λk + ck1 + 2 ck2 R12
k if k ∈ G
λk = (8) argue that “practical systems operating at normal conditions”
λ̄k − λk otherwise will display this zero duality gap based on their experience
γk = γ̄k − γ k (9) with a number of IEEE test systems. However, in general,
µk = µ̄k − µk (10) the SDP formulation of the dual problem offers three possible
outcomes: a solution that meets conditions for zero duality
Finally, define a scalar real-valued function h and matrix- gap, and hence yields a globally optimal solution to the OPF
valued function A. problem; a solution to the relaxed SDP formulation with a
higher rank W (hence physically meaningless as a solution to
Xn the original OPF problem); the SDP formulation may have no
h= λk Pkmin − λ̄k Pkmax + λk PDk + γ k Qmin
k
k∈N
feasible solution.
 2  We begin by discussing a class of solution that [7] discounts
−γ̄k Qmax
k + γk QDk + µk Vkmin − µ̄k (Vkmax )2 (11) as being abnormal, and for which they argue one may not
X X n o expect a zero duality gap: that of negative Lagrange multipliers
ck0 − R22 max 2
) H11 22 33


+ k − (Slm lm + Hlm + Hlm associated with active power balance constraints.
k∈G (l,m)∈L
A. Duality Gap in the Case of Negative LMPs
X The Lagrange multipliers λk for the active power constraints
A= λk Yk + γk Ȳk + µk Mk
given in (2f) and (8) are, in the terminology of power markets,
k∈N
X  locational marginal prices (LMP). These are commonly com-
2H12 13

+ lm Ylm + 2Hlm Ȳlm (12) puted and updated many times daily in wholesale electricity
(l,m)∈L markets in the U.S. Simple intuition regarding unconstrained
The SDP formulation of the dual OPF problem may then markets might lead one to believe an OPF solution with
be written as: negative λk , (i.e., consumers at some locations are paid to
consume) could be considered “abnormal” and excluded from
consideration. The authors of [7] do so, stating that their SDP
max h (13a) formulation is not guaranteed to yield a solution with zero
subject to duality gap under these conditions. However, power system
markets operate at conditions with negative LMPs with some
A0 (13b)
regularity. Binding line-flow constraints can cause negative
Hlm  0 ∀ (l, m) ∈ L (13c) LMPs. In systems with binding line-flow constraints, it is
Rk  0, R11
=1
k ∀k ∈ G (13d) possible that increasing the power delivered to certain buses
λk ≥ 0, λ̄k ≥ 0, γ k ≥ 0, γ̄k ≥ 0, µk ≥ 0, µ̄k ≥ 0 (13e) may relieve congestion elsewhere in the system. Reducing
transmission congestion allows for greater output from cheaper
where  0 indicates the corresponding matrix is positive generators, thus reducing overall system costs. Negative LMPs
semidefinite. This formulation is Optimization 4 in [7]. will occur at buses where increasing power consumption leads
The matrix W is the generalized Lagrange multiplier of to decreased overall system costs.
constraint (13b). If the matrix function A evaluated at the The MidwestISO, which operates one the largest wholesale
dual problem’s optimal solution has two zero eigenvalues, [7] power markets in the U.S., displays a color-coded contour map
demonstrates that a unique rank one W can be obtained, and of LMPs throughout its system on its publicly accessible web-
the duality gap is zero. The optimal voltages in rectangular site [19], updating the LMP values at 5-minute intervals. This
coordinates can be extracted from the rank one W. Expressing market saw periods of negative LMPs many times throughout
the rank one matrix as an outer product, W = xxT , one has the summer 2011 period; a sample June 2011 LMP contour is
shown in Figure 2. In this example, 32 of the 190 commercial
 T pricing nodes in the MidwestISO market displayed negative
x = Vd1 · · · Vdn Vq1 · · · Vqn (14)
LMPs, with the most negative being a price of $-112 per
yielding the globally optimal solution to the primal OPF MWh at a node in the Hoosier Energy control area. Inability
problem. to reliably compute OPF solutions for situations that yield
 PG1+ j Q G1 PG2+ j Q G2
negative LMPs appears to be a practical limitation of the SDP 110. MW 110. MW
formulation. + j 40. MVAR + j 40. MVAR

1 2

95 MW
+ j 50. MVAR
0 + j Q G3

Fig. 3. Three-Bus Example System

Fig. 2. Negative LMPs (Lagrange Multipliers) in the MidwestISO Market From Bus To Bus R X b
[19] 1 3 0.065 0.620 0.450
3 2 0.025 0.750 0.700
1 2 0.042 0.900 0.300
B. Duality Gap in the Case of Strict Line-Flow Constraints
TABLE II
Here we provide a new computational example to demon- T HREE -B US S YSTEM N ETWORK D ATA
strate that the SDP formulation of the OPF problem may
also fail to produce physically meaningful solutions in the
presence of line-flow constraints. The SDP formulation of
the OPF problem was solved using YALMIP version 3 [20] have no flow limits). The SDP formulation yields a physi-
and SeDuMi version 1.3 [21] for a simple three-bus example. cally meaningful result, as evidenced by the two-dimensional
For comparison purposes, the classical formulation of the nullspace of A, that matches the solution of the classical
OPF problem was solved using an interior point method formulation. The solution is shown in Tables III and IV,
implemented in MATPOWER version 4.0 [4]. and aggregated Lagrange multipliers (LMPs) for active and
The three-bus power system for our example is depicted in reactive power obtained from (8) and (9) are given in Table V.
Figure 3, where the numeric values indicate the PDk + jQDk
load demands in MW and MVAR. This example uses a 100 Bus 1 Bus 2 Bus 3
|V | 1.069 1.028 1.001
MVA base. The active and reactive power outputs of generators δ (degrees) 0 9.916 -13.561
1 and 2 have large, nonbinding limits. The “generator”at bus Pg (MW) 131.09 185.93 0
3 is a synchronous condenser (i.e. it produces only reactive Qg (MVAR) 17.02 -3.50 0.06
power). The reactive power limits for generator 3 are large TABLE III
enough to be nonbinding. The quadratic generator cost curves S OLUTION TO 3-B US S YSTEM WITH L INE -F LOW L IMIT OF 60 MVA
(C LASSICAL AND SDP F ORMULATIONS )
for generators 1 and 2 are given in Table I for power generation
in MWh, where c2 is the coefficient of the squared term, c1 is
the coefficient of the linear term, and c0 is a constant. There is
no cost associated with generator 3 since it produces no active From Bus To Bus From MVA To MVA
power. The network data are given in Table II. Line shunt 1 3 43.90 47.47
susceptances are specified for the entire line (see Figure 1 for 3 2 60.00 60.00
1 2 22.72 28.69
the Π model circuit representation). The voltage magnitudes
at all buses are constrained to the range 1.1 to 0.9. All values TABLE IV
L INE -F LOW D ATA FOR 3-B US S YSTEM WITH L INE -F LOW L IMIT OF 60
are given in per unit. MVA (C LASSICAL AND SDP F ORMULATIONS )

Generator c2 c1 c0
1 $0.11 per (MWh)2 $5 per MWh $0
2 $0.085 per (MWh)2 $1.2 per MWh $0
Bus 1 Bus 2 Bus 3
TABLE I λ ($/MWh) 33.84 32.81 35.96
T HREE -B US S YSTEM G ENERATOR C OST D ATA γ ($/MVAR-hour) 0 0 0
TABLE V
A GGREGATED L AGRANGE M ULTIPLIERS FOR 3-B US S YSTEM WITH
First consider a line-flow limit of 60 MVA enforced on both L INE -F LOW L IMIT OF 60 MVA
ends of the line between bus 2 and bus 3 (all other lines
 The optimal objective values for both the SDP and classical lower bounds that of the classical formulation, as expected.
formulations are $5707.07 per hour. While space limitations preclude full system descriptions,
Now reduce the line-flow limit to 50 MVA while leaving larger examples also showed these same properties, in which
the other parameters unchanged. The solution to the SDP for- the SDP algorithm yielded an A matrix of rank greater than
mulation yields an A matrix with four-dimensional nullspace. two, and hence failed to provide a meaningful OPF solution.
The solution therefore has a non-zero duality gap and is no Again, the problematic solution cases appeared as sufficiently
longer physically meaningful. However, the classical formu- strict line-flow limits were imposed.
lation solved via an interior point method in MATPOWER In cases for which the SDP formulation fails to provide a
does yield a (at least locally optimal) solution as shown in zero duality gap, one may conjecture that there remains useful
Tables VI and VII. Aggregated Lagrange multipliers (prices) information to be garnered, particularly in cases for which
for active and reactive power obtained using MATPOWER W is close to a rank one matrix. As a pragmatic heuristic,
are given in Table VIII. The aggregated Lagrange multipliers the binding constraints for the (nonphysical) solution to the
at the nonphysical SDP solution are given in Table IX. Note SDP formulation might be assumed to be the same as those
that all aggregated Lagrange multipliers in both the classical for the actual optimal solution. For an n-bus system with 2n
and SDP formulations are non-negative, and the active power binding constraints, the values of all unknown variables are
balance Lagrange multipliers λ are strictly positive. The du- fully determined, and, with a sufficiently close initial guess,
ality gap/loss-of-physically-meaningful SDP solution cannot, could be computed via standard Newton-Raphson. In cases for
therefore, be attributed to negative Lagrange multipliers. which the binding constraints do not yield a fully determined
system, the dimension of the feasible space is still significantly
Bus 1 Bus 2 Bus 3 reduced, and the closest rank one approximation to W could
|V | 1.100 0.926 0.900
δ (degrees) 0 7.259 -17.267 be employed to yield an initial guess to an alternative OPF
Pg (MW) 148.07 170.01 0 algorithm.
Qg (MVAR) 54.70 -8.79 -4.84
IV. T HE P OWER F LOW P ROBLEM
TABLE VI
S OLUTION TO 3-B US S YSTEM WITH L INE -F LOW L IMIT OF 50 MVA We first review the power flow problem in rectangular
(C LASSICAL F ORMULATION ) coordinates. As noted previously, in practice, individual solu-
tions are easily computed via Newton methods; the challenge
lies in attempting to identify all solutions. To this end, we
demonstrate how the power flow problem can be formulated
From Bus To Bus From MVA To MVA
1 3 52.29 60.28 as an OPF problem through suitable choice of the constraints
3 2 50.00 50.00 and objective function. The SDP formulation of this problem is
1 2 14.02 33.33 adapted to the goal of finding multiple solutions to the power
TABLE VII flow equations.
L INE -F LOW D ATA FOR 3-B US S YSTEM WITH L INE -F LOW L IMIT OF 50
MVA (C LASSICAL F ORMULATION ) A. The Power Flow Equations in Rectangular Coordinates
The power flow equations relate the active and reactive
power injected at each bus to the voltage phasor at each bus.
Bus 1 Bus 2 Bus 3
The variables associated with each bus k are the net active
λ ($/MWh) 37.57 30.10 45.54 power injection (Pk = PGk − PDk ), the net reactive power in-
γ ($/MVAR-hour) 0 0 0 jection (Qk = QGk − QDk ), and the voltage Vk = Vdk + jVqk .
TABLE VIII The power flow equations are shown in (2f) and (2g). The
A GGREGATED L AGRANGE M ULTIPLIERS FOR 3-B US S YSTEM WITH voltage magnitude equation is
L INE -F LOW L IMIT OF 50 MVA (C LASSICAL F ORMULATION )
2 2 2
|Vk | = Vdk + Vqk (15)
See [18] for a review of the power flow equations in rectan-
Bus 1 Bus 2 Bus 3 gular voltage coordinates.
λ ($/MWh) 35.78 31.62 40.83
γ ($/MVAR-hour) 0 0 0
While (2f), (2g), and (15) must all be satisfied at all buses,
only two equations are directly enforced at each bus when
TABLE IX
A GGREGATED L AGRANGE M ULTIPLIERS FOR 3-B US S YSTEM WITH solving the power flow problem. To identify the class of
L INE -F LOW L IMIT OF 50 MVA (SDP F ORMULATION ) constraints imposed at each, buses in the power flow problem
are classified as one of three ”types”: PQ (bus indices denoted
by PQ), PV (bus indices denoted by PV), and slack (bus
The optimal objective value for the SDP formulation is index denoted by S). PQ buses enforce the active and reactive
$5789.87 per hour, whereas the optimal objective value to power equations (2f) and (2g). PV buses enforce the active
the classical formulation is $5812.60 per hour. Thus, the power and voltage magnitude equations (2f) and (15). Finally,
objective function value at the relaxed solution of the SDP a single slack bus enforces specified values of Vdk and Vqk .
B. The Power Flow Equations Formulated as an OPF Problem 0.45 + j 0.15 0.4 + j 0.05
By “tightening” inequality constraints that appear in the V = 1.06
OPF problem (in the limit, upper and lower limits equal), it 0 deg 5 2 3
is clear that one can recover the equalities for the power flow
0.08 + j 0.24 0.01 + j 0.03
problem as a subset of the standard constraints of the OPF
problem. In particular, for sufficiently small ǫ > 0, one may
0.06 + j 0.18
impose OPF constraints:
0.02 + j 0.06 0.08 + j 0.24
0.06 + j 0.18

Pk − PDk − ǫ ≤ PGk ≤ Pk − PDk + ǫ ∀k ∈ {PQ, PV} (16a)

Qk − QDk − ǫ ≤ QGk ≤ Qk − QDk + ǫ ∀k ∈ PQ (16b) 0.04 + j 0.12
2 2 2 2 1 4
|Vk | − ǫ ≤ Vdk + Vqk ≤ |Vk | + ǫ ∀k ∈ {PV, S} (16c)

As will be described below, by suitable choice of objective

function, one may seek to “steer” the OPF towards different 0.2 + j 0.1 0.6 + j 0.1
power flow solutions. However, it is useful to first consider P = 0.4
general properties of the respective feasible spaces for the |V| = 1.0
power flow problem, the classical OPF problem, and the SDP
formulation of the OPF problem. The feasible space of the Fig. 4. Five-Bus Example System
power flow problem is made up of discrete points at the
solutions to the power flow equations. The feasible space of Solution
1 2 3 4 5
the classical OPF problem is more difficult to characterize. V1 1.0000 1.0000 1.0000 1.0000 1.0000
It is generally nonconvex and may not be connected [2]. By V2 0.9805 0.5012 0.3770 0.7933 0.0626
appropriately setting the constraints, the OPF formulation of V3 0.9771 0.5879 0.4108 0.7403 0.2160
V4 0.9662 0.8317 0.0666 0.0580 0.6982
the power flow problem shrinks the feasible space to emulate V5 1.0600 1.0600 1.0600 1.0600 1.0600
a discrete set of points. The SDP formulation of the OPF δ1 -2.0675 -138.9679 -128.5864 -12.1469 -126.6253
problem is connected and convex. However, the rank relax- δ2 -4.5358 -129.8511 -116.8370 -12.6793 -159.5293
δ3 -4.8535 -134.8640 -124.1731 -13.8795 -144.7963
ation of this formulation increases the feasible space to include δ4 -5.6925 -141.6605 -185.7340 -71.5017 -133.4401
nonphysically meaningful solutions. The rank relaxation also δ5 0.0000 0.0000 0.0000 0.0000 0.0000
increases the feasible space of the power flow problem from Solution
6 7 8 9 10
a set of discrete points to a continuous space. This may result V1 1.0000 1.0000 1.0000 1.0000 1.0000
in nonphysically meaningful solutions to the SDP formulation V2 0.1972 0.0563 0.0342 0.1968 0.0884
of the power flow problem. V3 0.0301 0.0496 0.1846 0.0369 0.1658
V4 0.6289 0.6327 0.6865 0.0814 0.0756
C. Finding Multiple Solutions to the Power Flow Equations V5 1.0600 1.0600 1.0600 1.0600 1.0600
δ1 -16.5040 -18.0976 -16.9090 -22.5210 -119.8826
We discuss two different approaches using SDP to find mul- δ2 -26.0422 -61.1266 -69.0465 -30.6818 -141.8399
tiple solutions to the power flow equations. The first approach δ3 -81.8652 -80.6706 -37.7869 -85.9455 -144.7567
δ4 -23.4519 -25.4435 -23.8729 -79.4189 -178.4992
involves modifying the constraints of the SDP formulation. δ5 0.0000 0.0000 0.0000 0.0000 0.0000
The second approach involves modifying the objective func-
TABLE X
tion. T HE T EN S OLUTIONS FOR THE F IVE -B US S YSTEM
1) Example Systems: The five-bus and seven-bus systems
shown in Figures 4 and 5 were used to test both approaches.
Load, generation and voltage magnitudes in Figures 4 and
5 are given in per unit. Network values in Figures 4 and 5 non-zero duality gap and failed to yield a meaningful solution
are given as R + jX in per unit. The complete set of power to the power flow.
flow solutions for these systems have been calculated using a Additionally, we attempted to constrain the voltage mag-
homotopy method [14], and are summarized in Table X and nitudes at PQ buses to be below the base solution results.
Table XI. This approach also failed; imposing such voltage constraints
2) Modifying the Constraints: We first seek to differentiate yielded only nonphysical results (i.e., non-zero duality gap).
among possible solutions by imposing an inequality constraint 3) Modifying the Objective Function: An alternate formu-
on slack bus active power. The solution having least power lation examined selected slack bus active power generation
generated by the slack bus corresponds to the solution with as an objective to be maximized. The solution with highest
lowest losses. This base solution is reliably found with no losses for the five-bus system, solution 3 in Table X, was
inequality constraint. Imposing a minimum slack bus power obtained via SDP in this way. Other examples, including the
constraint greater than the slack bus power in the base so- seven-bus system, identified only nonphysical solutions with
lution forces the OPF to another solution with higher losses. this objective function.
However, in all such cases examined, the SDP solution had Next considered was an objective function based on bus
 0.076 + j 0.016 0.478 + j 0.039 -0.9 - j 0.3 Solution c1 c2 c3 c4 c5
V = 1.0 1 0 -1 -1 -1 0
0 deg 7 6 2 1 2 0 1 -1 0 0
4 0 0 0 1 0
0.054 + j 0.223 0.013 + j 0.042 0.082 + j 0.192 6 0 0 1 0 0
7 0 1 1 0 0
0.057 + j 0.174 8 0 1 0 0 0
0.067 + j 0.171
0.019 + j 0.059 9 0 0 1 1 0
0.058 + j 0.176
3 0 0.65 -0.70 0.90 0
5 0 0.70 -0.10 -0.15 0
0.024 + j 0.100 0.024 + j 0.100
10 0 0.45 -0.25 0.50 0
5 4 3
TABLE XII
C OMBINATIONS OF W EIGHTS c AND C ORRESPONDING S OLUTIONS FOR
0.183 + j 0.127 0.135 + j 0.058 0.942 + j 0.190 F IVE -B US S YSTEM

Fig. 5. Seven-Bus Example System

Solution c1 c2 c3 c4 c5 c6 c7
Solution 1 -1 -1 -1 -1 -1 -1 0
1 2 3 4 2 0 0 1 0 0 0 0
V1 1.0758 0.7312 0.2880 0.3435 3 1 0 0 0 0 0 0
V2 0.9635 0.5876 0.5415 0.4332 4 0.30 -0.20 0.35 0.45 -0.40 0.05 0
V3 0.9041 0.1745 0.5430 0.2497
TABLE XIII
V4 0.9278 0.4122 0.6458 0.4359
C OMBINATIONS OF W EIGHTS c AND C ORRESPONDING S OLUTIONS FOR
V5 0.9638 0.7229 0.7750 0.6879
S EVEN -B US S YSTEM
V6 0.9675 0.6638 0.6402 0.5496
V7 1.0000 1.0000 1.0000 1.0000
δ1 5.2859 14.9576 101.8188 88.3361
δ2 -2.9342 -5.2212 -6.2931 -6.8346
δ3 -8.4439 -52.6775 -19.8095 -44.2797
δ4 -5.7500 -14.2056 -11.2462 -16.1362 computed, appropriately scaled, and set as the initial condition
δ5 -2.4463 -3.2056 -3.8617 -3.9193 for a Newton-Raphson power flow solver. With this approach,
δ6 -2.5918 -4.3031 -5.0158 -5.3138 some, but not all, of the nonphysical solutions obtained from
δ7 0.0000 0.0000 0.0000 0.0000
the SDP formulation for the five-bus and seven-bus systems
TABLE XI converged to power flow solutions.
T HE F OUR S OLUTIONS FOR THE S EVEN -B US S YSTEM

V. C ONCLUSION
This paper has investigated existing and new applications
voltage magnitudes, in the form
of the semidefinite programming formulation of the optimal
n power flow problem. We have discussed two practical system
2
X
min cT |V | = min ci trace (Mi W) (17) conditions where the SDP formulation of the OPF problem
i=1 may fail to give physically meaningful results. The first was
where c is a vector of weights; i.e. the objective function already identified in the discussion of [7], but was not rec-
in (17) is a weighted sum squares of voltage magnitudes. ognized as a commonly occurring practical system condition:
Appropriate choices of the weights in c favored solutions with that of negative bus LMPs. In a new result, this work has
low voltages at selected buses. also provided a numerical optimal power flow example to
This method identified all of the ten solutions in the five- demonstrate that a non-zero duality gap may arise in SDP
bus system, as summarized in Table XII, and all of the formulation as a line-flow inequality constraint is progressively
four solutions in the seven-bus system, as summarized in “tightened.” Under these conditions, the SDP fails to provide
Table XIII. Solutions above the line in Tables XII and XIII a physically meaningful solution to the original OPF problem
were found using heuristically determined weights c. Similar of interest.
heuristically determined weights were identified that were To explore possible extensions of the SDP formulation in
expected to find the remaining solutions (3, 5, and 10 for the traditionally intractable power system computations, we next
five-bus system and 4 in the seven-bus system); however, the addressed the problem of locating all possible solutions to the
SDP formulation for these heuristically determined weights power flow. To identify different power flow solutions, families
gave nonphysical results. Alternatively, testing a variety of of OPF problems were formulated by modifying the OPF con-
randomly generated weights yielded the combinations below straints and objective function. In the test cases examined, the
the line in Tables XII and XIII that found the remaining modified objective approach was successful in finding all of
solutions. the power flow solutions. Although not all objective functions
As noted previously, solutions with non-zero duality gap yielded physically meaningful solutions, objective functions
in which W has rank greater than one can be used to capable of finding all solutions were identified. As a heuristic
estimate approximate, candidate solutions. As a heuristic, the enhancement to the method, nonphysical solutions obtained
eigenvector associated with the largest eigenvalue of W was from the SDP formulation were used to construct approximate
solutions that then initialized a traditional Newton-Raphson [6] J. Lavaei and S. Low, “Convexification of Optimal Power Flow Prob-
power flow solver. lem,” in 48th Annual Allerton Conference on Communication, Control,
and Computing (Allerton), 2010, October 2010, pp. 223 –232.
The examples examined in this paper demonstrate that the [7] ——, “Zero Duality Gap in Optimal Power Flow Problem,” To appear
SDP formulation in its present development is not capable of in IEEE Transactions on Power Systems, 2011, available at https://www.
reliably solving the OPF problem in several practical operating cds.caltech.edu/∼ lavaei/TPS 1.pdf.
[8] A. Klos and A. Kerner, “The Non-Uniqueness of Load Flow Solution,”
conditions of interest. Initial attempts at adapting the SDP OPF Proc. PSCC-5, p. 3.1/8, Cambridge, 1975.
approach to compute all possible power flow solutions showed [9] H.-D. Chiang, F. Wu, and P. Varaiya, “Foundations of Direct Methods
promise in test cases, but did not give physically meaningful for Power System Transient Stability Analysis,” IEEE Transactions on
Circuits and Systems, vol. 34, no. 2, pp. 160 – 173, February 1987.
results for all objective functions and constraints. Clearly, the [10] M. Ribbens-Pavella and F. Evans, “Direct Methods for Studying Dy-
use of relaxation-based SDP methods in otherwise nonconvex namics of Large-Scale Electric Power Systems-A Survey,” Automatica,
power system problems has significant potential, but in its vol. 21, no. 1, pp. 1 – 21, 1985.
[11] V. Venikov, V. Stroev, V. Idelchick, and V. Tarasov, “Estimation of Elec-
present development does not yet reliably solve the full range trical Power System Steady-State Stability in Load Flow Calculations,”
of practical problems of interest. IEEE Transactions on Power Apparatus and Systems, vol. 94, no. 3, pp.
1034 – 1041, May 1975.
ACKNOWLEDGMENT [12] Y. Tamura, H. Mori, and S. Iwamoto, “Relationship Between Voltage In-
stability and Multiple Load Flow Solutions in Electric Power Systems,”
The authors acknowledge support of this work by U.S. IEEE Transactions on Power Apparatus and Systems, vol. PAS-102,
Department of Energy under award #DE-SC0002319, as well no. 5, pp. 1115 –1125, May 1983.
as by the National Science Foundation under IUCRC award [13] J. Glover, M. Sarma, and T. Overbye, Power System Analysis and
Design. Thompson Learning, 2008.
#0968833. Daniel Molzahn would like to acknowledge the [14] F. Salam, L. Ni, S. Guo, and X. Sun, “Parallel Processing for the
support of the NSF Graduate Research Fellowship. The au- Load Flow of Power Systems: The Approach and Applications,” in
thors would also like to thank Dr. Hongbo Dong and Mr. Proceedings of the 28th IEEE Conference on Decision and Control,
1989, December 1989, pp. 2173 –2178 vol.3.
Taedong Kim for their insightful comments and assistance in [15] S. Chow, J. Mallet-Paret, and J. Yorke, “Finding Zeros of Maps:
validating the results presented in this paper. Homotopy Methods that are Constructive With Probability One,” Math.
Comp, vol. 32, no. 143, pp. 887–899, 1978.
R EFERENCES [16] W. Ma and S. Thorp, “An Efficient Algorithm to Locate All the Load
Flow Solutions,” IEEE Transactions on Power Systems, vol. 8, no. 3, p.
[1] J. Carpentier, “Contribution to the Economic Dispatch Problem,” Bull. 1077, 1993.
Soc. Franc. Elect, vol. 8, no. 3, pp. 431–447, 1962. [17] H. Chen, “Cascaded Stalling of Induction Motors in Fault-Induced
[2] B. Lesieutre and I. Hiskens, “Convexity of the Set of Feasible Injections Delayed Voltage Recovery (FIDVR),” Masters Thesis, University
and Revenue Adequacy in FTR Markets,” IEEE Transactions on Power of Wisconsin-Madison, Department of Electrical and Computer
Systems, vol. 20, no. 4, pp. 1790 – 1798, November 2005. Engineering, 2011. [Online]. Available: http://minds.wisconsin.edu/
[3] Z. Qiu, G. Deconinck, and R. Belmans, “A Literature Survey of Optimal handle/1793/53749
Power Flow Problems in the Electricity Market Context,” in Power [18] R. Klump and T. Overbye, “A New Method for Finding Low-Voltage
Systems Conference and Exposition, 2009. PSCE ’09. IEEE/PES, March Power Flow Solutions,” in Power Engineering Society Summer Meeting,
2009, pp. 1–6. 2000. IEEE, 2000.
[4] R. Zimmerman, C. Murillo-Sánchez, and R. Thomas, “MATPOWER: [19] MidwestISO, “LMP Contour Map from 2:40 PM, June 22, 2011,” http:
Steady-State Operations, Planning, and Analysis Tools for Power Sys- //www.midwestmarket.org/page/LMP+Contour+Map+%28EOR%29.
tems Research and Education,” IEEE Transactions on Power Systems, [20] J. Lofberg, “YALMIP: A Toolbox for Modeling and Optimization in
no. 99, pp. 1–8, 2011. MATLAB,” in Computer Aided Control Systems Design, 2004 IEEE
[5] X. Bai, H. Wei, K. Fujisawa, and Y. Wang, “Semidefinite Programming International Symposium on. IEEE, 2004, pp. 284–289.
for Optimal Power Flow Problems,” International Journal of Electrical [21] J. Sturm, “Using SeDuMi 1.02, A MATLAB Toolbox for Optimization
Power & Energy Systems, vol. 30, no. 6-7, pp. 383–392, 2008. Over Symmetric Cones,” Optimization Methods and Software, vol. 11,
no. 1, pp. 625–653, 1999.