Convexity/Nonconvexity Certificates for Power Flow Analysis

Abstract

Optimal Power Flow problem is considered as minimization of quadratic performance function subject to linear and quadratic equality/inequality constraints, AC power flow equations specify the feasibility domain. Similar quadratic problems arise in discrete optimization, uncertainty analysis, physical applications. In general they are nonconvex, nevertheless, demonstrate hidden convexity structure. We investigate the “image convexity” property. That is, we consider the image of the space of variables under quadratic map defined by power flow equations (the feasibility domain). If the image is convex, then original optimization problem has nice properties, for instance, it admits zero duality gap and convex optimization tools can be applied. There are several classes of quadratic maps representing the image convexity. We aim to discover similar structure and to obtain convexity or nonconvexity certificates for the individual quadratic transformation. We also provide the numerical algorithms exploiting convex relaxation of quadratic mappings for checking convexity. We address such problems as membership oracle and boundary oracle for the quadratic image. Finally the results are illustrated through some examples of 3-bus systems, namely, we detect nonconvexity of them.

1 Introduction

Various formulations of the Optimal Power Flow problem (OPF) can be found in recent publications [1,2,3]; numerous references are given in the survey [4]. From mathematical point of view most of them (if transformed into real space) can be described as optimization problems with quadratic (or partially linear) objective and constraints. Thus OPF can be considered in the framework of quadratic programming with quadratic constraints. The same class of optimization problems arises in discrete optimization, uncertainty analysis, various physical applications. It is well known that such problems are typically nonconvex and NP-hard. However the special quadratic structure often exhibits so called “hidden convexity” properties, see, e.g. [5, 6]. On the other hand quadratic problems admit efficient techniques of convex relaxation, see [7, 8]; for OPF problems convex relaxation was used in [1, 3]. In what follows we treat OPF as particular case of quadratic optimization. Moreover we proceed from optimization problems to more general setting of images of quadratic maps.

In Sect. 2 we formulate the problem of convexity of quadratic transformations and refer to known results for particular classes of quadratic functions. Power Flow equations do not fit directly to any of the known classes, thus our approach is different — we try to check convexity/nonconvexity of an individual quadratic map. Such certificates of convexity/nonconvexity will be provided in Sect. 3; we also develop efficient algorithms to obtain the certificates. The algorithms exploit convex relaxation technique and so called “boundary oracle” for convex domains. Section 4 contains results on numerical simulation. Conclusions and directions for the future work can be found in final Sect. 5.

2 Convexity of Quadratic Transformations

We consider AC power flow model. The network is characterized by complex admittance matrix

$$Y \in \mathbb {C}^{(\mathcal {N}-1)\times (\mathcal {N}-1)}, $$

where $\mathcal {N}$ is the total number of buses (including slack bus with fixed voltage magnitude and phase). Power injections defined by Kirchhoff’s laws can be written through matrix Y and complex voltages $V_i$:

$$s_i = V_i (YV)_i^*, \quad i = 1, \dots , \mathcal {N}-1.$$

Typical OPF problem is to minimize linear or quadratic cost c(V) subject to quadratic constraints $\underline{s_i} \le s_i \le \overline{s_i}$. We treat all $V\in \mathbb {C}^{\mathcal {N}-1}$ feasible while the constraints are stated in the space of quadratic image of V. Introducing real vector $x = [\text {Re}(V)^T,~ \text {Im}(V)^T]^T$ active and reactive powers are real-valued quadratic functions of x. Further we deal with quadratic transformations in the general setting.

We consider multidimensional quadratic mapping $f: \mathbb {R}^n \rightarrow \mathbb {R}^m$ of the form

$$\begin{aligned} f(x)&= (f_1(x), f_2(x), \dots ,f_m(x))^T \\ f_i(x)&= (A_i x, x) + 2(b_i, x) , \quad i = 1,\dots , m \le n, \end{aligned}$$

then

$$ E = \{f(x): x \in \mathbb {R}^n \} $$

is the image of the space of variables x under this quadratic map. We do not assume that matrices $A_i$ are sign-definite; nevertheless E sometimes occur to be convex (“hidden convexity” property). Let us mention some known results of this sort.

• For $m=2$ and $b_i \equiv 0$ E is convex. This is the pioneering result by Dines [9]. For $m=2$, $b_i \ne 0$ and $c_1 A_1 + c_2 A_2 \succ 0$ (the matrix combination is positive definite for some c) E is convex as well [10].

• For $m=3$ E is convex if there exists a positive-definite linear combination of matrices $A_1, A_2, A_3$ and $b_i\equiv 0$. This is proved in [11] and in [10].

• If $b_i\equiv 0$ and matrices $A_i$ commute, then E is convex [12].

• If $A_i$ have positive off-diagonal entries, then “positive part of E” is convex (i.e. $E+R^m_{+}$ is convex) [13].

Consider the image of a ball $F = \{f(x): ||x||\le \rho \}.$

• For $m=2$ and $b_i\equiv 0$ F is convex [14].

• If matrix B with columns $b_i$ is nonsingular and $\rho$ is small enough, then F is convex for all $m, n\ge 2$ (“small ball” theorem [15]).

There are some other classes of quadratic transformations with convex images, however typically E (or F) is nonconvex; numerous examples will be provided later.

3 Certificates of Convexity/Nonconvexity

We remind some known facts on convex relaxations for quadratic optimization and on convex hull for quadratic image.

The idea of convex relaxations for quadratic problems goes back to [16]; recent results and references can be found in [7, 8]. Similar ideas and technique give the convex hull of the image set E, see also [17].

Notation

For symmetric matrices $\langle X,Y\rangle$ $=$ trace(XY), and $X\succeq 0$ denotes nonnegative definite matrix X.

Theorem 1

The convex hull for the feasibility set E is

$$ G = \text {conv}(E) = \{ \mathcal {H}(X): X\succeq 0, X_{n+1, n+1} = 1\}, $$

where $X = X^T \in \mathbb {R}^{(n+1)\times (n+1)}$,

$\mathcal {H}(X) = (\langle {H}_1,X\rangle , \langle {H}_2,X\rangle , \dots , \langle {H}_m,X\rangle )^T$

$H_{i} = \left( \begin{array}{cc} A_i &{} b_i \\ b_i^T &{} 0 \\ \end{array} \right) .$

Hence we can provide simple sufficient conditions for membership oracle, i.e. checking if a particular point $y\in \mathbb {R}^m$ is feasible (belongs to E). Indeed, it is necessary to have $y\in G$, that is to solve corresponding linear matrix inequality (LMI) [18]. Alternatively, introduce the variable $c\in \mathbb {R}^m$ and construct matrix $A = \sum c_i A_i$, vector $b= \sum c_i b_i$ and block matrix $H(c) = \left( \begin{array}{cc} A &{} b \\ b^T &{} -(c,y) \\ \end{array} \right)$, then the sufficient condition for $y \not \in G$ has the form:

Theorem 2

If there exists c such that for a specified y

$$H(c)\succ 0,$$

then y is not feasible.

Indeed if the LMI is solvable, there exists the separating hyperplane, defined by its normal c that strictly separates y and $G= conv(E)$, hence y does not belong to E. Now we can proceed to a nonconvexity certificate.

Theorem 3

Let $m \ge 3$, $n \ge 3$, $b_i \ne 0$, and for some $c = (c_1, c_2, \dots , c_m)^T$, the matrix $A = \sum c_i A_i \succeq 0$ has a simple zero eigenvalue $A e = 0$, and for $b = \sum c_i b_i$ we have $(b, e) = 0$. Denote $d = -A^{+}b$, $x^{\alpha } = \alpha e+d$, $f^{\alpha } = f(x^{\alpha }) = f^0 +f^1 \alpha +f^2\alpha ^2$. If $|(f^1, f^2)| < \Vert f^1\Vert \cdot \Vert f^2\Vert$, then E is nonconvex.

Geometrically the condition implies that the linear function (c, f) attains its minimum on E at points $f^{\alpha }$ only. But parabola $f^{\alpha }$ is nonconvex, thus the supporting hyperplane touches E on a nonconvex set.

Now the main problem is to find c (if exists) which satisfies Theorem 1 and hence discovers nonconvexity of the feasible set. For this purpose let us construct so called boundary oracle for G. For given $y^0 \in E$ and the arbitrary direction $d \in \mathbb {R}^m$ the following Semidefinite Program (SDP) [18] with variables $t\in \mathbb {R}$, $X = X^T \in \mathbb {R}^{(n+1)\times (n+1)}$ specifies the boundary point $y^0 + td$ of the convex hull:

$$\begin{aligned} \max&~t \\ \mathcal {H}(X)&= y^0 + td \nonumber \\ X&\succeq 0 \nonumber \\ X_{n+1, n+1}&= 1. \nonumber \end{aligned}$$

(1)

If we obtain rank $(X) = 1$ for the solution of (1) we claim that the obtained boundary point is on the boundary of E. Otherwise, the boundary point of the convex hull does not belong to E.

On the other hand the dual problem to (1) gives us normal vector c for the boundary point:

$$\begin{aligned} \min&~\gamma + (c, y^0) \\ (c,d)&= -1 \nonumber \\ H&= \left( \begin{array}{cc} \sum c_i A_i &{} \sum c_i b_i \\ \sum c_i b_i^T &{} \gamma \\ \end{array} \right) \succeq 0 \nonumber \end{aligned}$$

(2)

This is SDP problem with variables $c,\gamma$.

Equipped with boundary oracle technique (which provides both a boundary point of G and the normal vector c in this point) we are able to generate vectors c to identify nonconvexity as in Theorem 1. Thus we arrive to

Algorithm

• 1. Take arbitrary $x^0\in \mathbb {R}^n$, calculate $y^0=f(x^0)$ and fix some N.

• 2. Generate N random directions $d^i$ on the unit sphere in $\mathbb {R}^m$.

• 3. For every random direction $d^i$ solve SDP (2). If the obtained c satisfies Theorem 1, we identifyed nonconvexity.

At the first glance, simpler approach can be applied. Take $c\in \mathbb {R}^m$ and minimize (c, y) on G (given by lemma 1) if such minimum exists. If $A = \sum c_iA_i\succ 0$ the minimum is unique and obtained at rank-1 matrix $xx^T$, $x = A^{-1}b, b=\sum c_ib_i$, and x gives a boundary point of the feasibilty set E. However to identify nonconvexity we should find c such that A is singular. The probability of this event is zero if we sample c randomly. In our approach (when we generate directions d) the probability of finding a boundary point on a “flat” part of the boundary of G (which correspond to nonconvex E) is positive. In simulation results nonconvexity was identified in all examples, where it has been recognized by other methods.

To conclude it is the strong support of the convexity assumption if our algorithm does not meet nonconvexity after large number of iterations N for various $y^0$.

4 Numerical Results

In this section we apply the proposed routine for several test maps. The first one is artificially constructed while the others describe power flow feasibility region for 3-bus networks. Starting form a specified feasible $y^0$ and $N=10^4$ we run the algorithm to obtain vector c such that the supporting hyperplane (c, y) touches the image y(x) in more than one point and thus certifies its nonconvexity. We distinguish nonconvexities discovered by different vectors c and examine the portion of random directions d resulted in every c. The results are summarized in Table 1.

Table 1 Numerical results for discovering nonconvexity of test mappings

Artificial system We start with the artificially constructed quadratic mapping $\mathbb {R}^3 \rightarrow \mathbb {R}^3$ with

$$\begin{aligned} A_1&= \left( \begin{array}{ccc} 1 &{} 1 &{} 1 \\ 1 &{} 2 &{} 0 \\ 1 &{} 0 &{} 2 \\ \end{array} \right) ,&A_2&= \left( \begin{array}{ccc} 3 &{} -1 &{} 0 \\ -1 &{} 0 &{} -1 \\ 0 &{} -1 &{} 1 \\ \end{array} \right) ,&A_3&= I \\ b_1&= \left( \begin{array}{ccc} 1 &{} 1 &{} 1 \\ \end{array} \right) ^T,&b_2&= \left( \begin{array}{ccc} 1 &{} 0 &{} -1 \\ \end{array} \right) ^T,&b_3&= \left( \begin{array}{ccc} 0 &{} 0 &{} 0 \\ \end{array} \right) ^T. \end{aligned}$$

Note that $A_1$ is positive semidefinite thus $c^1 = \left( 1, 0, 0 \right) ^T$ specifies the supporting hyperplane (c, y) touching the image in more than one point. For this map we obtain two other critical $c^2 = \left( 1, 0.5, -1 \right) ^T$ and $c^3 = \left( 1, 4.75, 1.38 \right) ^T$. For $y^0 = \left( 0, 1, 1 \right) ^T$ the portion for every c is given in Table 1. We analytically justify that there is no other c specifying nonconvexity for this map and plot several 2-D sections of the image in $\mathbb {R}^3$ (Fig. 1). For fixed $0 \le y_3 \le 1/3$ the section appears to be convex and for $y_3 = 4$ we visualize all three nonconvexities.

Fig. 1

Two sections of the feasibility domain: first we fix $y_3 = 1/3$ and obtain convex section, then for $y_3 = 4$ the section is nonconvex

Constant power loads [19] This example is borrowed form [19], where feasible points of E are addressed as equilibria of system with constant power loads. The map of interest has the form:

$$\begin{aligned} P_1(x)&= x_1^2 - 0.5 x_1 x_2 + x_1 x_3 - 1.5 x_1 \\ P_2(x)&= x_2^2 - 0.5 x_1 x_2 - x_2 x_3 + 0.5 x_2 \\ P_3(x)&= x_3^2 - 2 \epsilon x_3( x_1 + x_2) - x_3, \quad \epsilon = 0.01. \end{aligned}$$

For $P^0 = \left( 0.5, 0.5, 0.25 \right) ^T$ we obtain a single $c = (1, 2.9021, 0.7329)^T$ identifying nonconvexity. It means that the supporting parabola

$$ f^{\alpha } = \left( \begin{array}{r} -0.5442 \\ 0.0022 \\ -0.0339 \\ \end{array} \right) + \alpha \left( \begin{array}{r} 0.5043 \\ 0.0400 \\ -0.8463 \\ \end{array} \right) + \alpha ^2 \left( \begin{array}{r} -0.0022 \\ -0.1991 \\ 0.7912 \\ \end{array} \right) $$

provides boundary points for the image P(x), $x\in \mathbb {R}^3$ but the convex combination of two boundary points $\lambda f^{\alpha _1} + (1- \lambda )f^{\alpha _2}$ is infeasible for $0<\alpha < 1$, $f^{\alpha _1} \ne f^{\alpha _2}$.

3-bus [20] Consider tree unbalanced 3-bus system (1 slack, 2 PQ-buses) with the admittance matrix

$$ Y = \left( \begin{array}{ccc} -1 &{} 1 &{} 0 \\ 1 &{} -2-i &{} 1+i \\ 0 &{} 1+i &{} -1-i \\ \end{array} \right) . $$

The feasibility region in the space of $P_2$, $Q_2$, $P_3$, $Q_3$ is known to be nonconvex [20]. Here $P_i$ and $Q_i$ denote active and reactive power at the i-th bus, $y = \left( P_2, Q_2, P_3, Q_3 \right) ^T$. For $y^0 = \left( 0, 0, 1, 1 \right) ^T$ our numerical routing obtains the single c generating nonconvexity for approximately $6\%$ of random directions.

3-bus [21] This example of 3-bus cycle network with slack, PV and PQ-bus is borrowed from [21] (Fig. 2).

Fig. 2

Three-bus system

Power flow equations take the form

$$\begin{aligned} P_1&= x^T \left( \begin{array}{cccc} 3.7 &{} -0.6 &{} 0 &{} -0.8 \\ -0.6 &{} 0 &{} 0.8 &{} 0 \\ 0 &{} 0.8 &{} 3.7 &{} -0.6 \\ -0.8 &{} 0 &{} -0.6 &{} 0 \\ \end{array} \right) x + \\&+ 2 (( -1.25, 0, 1.25, 0)^T, x),\\ V_1&= x_1^2 + x_3^2, \\ P_2&=x^T \left( \begin{array}{cccc} 0 &{} -0.6 &{} 0 &{} 0.8 \\ -0.6 &{} 3.6 &{} -0.8 &{} 0 \\ 0 &{} -0.8 &{} 0 &{} -0.6 \\ 0.8 &{} 0 &{} -0.6 &{} 3.6 \\ \end{array} \right) x + \\&+ 2 (( 0, -1.2, 0, 1.6)^T, x),\\ Q_2&=x^T \left( \begin{array}{cccc} 0 &{} -0.8 &{} 0 &{} -0.6 \\ -0.8 &{} 4.8 &{} 0.6 &{} 0 \\ 0 &{} 0.6 &{} 0 &{} -0.8 \\ -0.6 &{} 0 &{} -0.8 &{} 4.8 \\ \end{array} \right) x + \\&+ 2 (( 0, -1.6, 0, -1.2)^T, x). \end{aligned}$$

We remind that $x = (\text {Re} V_1,~ \text {Re} V_2,~ \text {Im} V_1,~ \text {Im} V_2)^T$ and $V_3 = 1$ for slack bus. Starting at the given operation regime $P_1 = 2$, $V_1^2 = 1.21$, $P_2 = -0.7$, $Q_2 = -0.3$ we obtain at least two vectors c identifying nonconvexity but it requires more computational effort than in previous examples. Although our routine is capable to catch nonconvexity with probability one we are not sure that obtained vectors describe all the nonconvexities for this system.

The example may look artificial since the line resistances are as high as the reactances. We run our algorithm for the five times larger line reactances to model transmission grid and still discover nonconvexity of the image.

Remark

We do not propose any routine to solve power flow equation, and we do not pretend to compete with any power flow solvers, neither DC equations nor iterative methods. Our method is focused on the certification and numerical description of nonconvexities of the image that is the reason for inexactness of convex relaxation for OPF.

5 Conclusions and Future Work

The paper addresses power flow analysis in the framework of quadratic transformations geometry. We provide some conditions which guarantee convexity of a quadratic image and numerical tools to identify nonconvexity. Simulation confirms that the technique works for low-dimensional examples. We plan to apply the analysis for medium-dimensional and large-dimensional problems in future. For instance IEEE-14-bus test is one of the first candidates.

The key question is how to deal if nonconvexity is identfied. There are some promising ideas for this case, for instance, based on [22] cutting plane approach can be introduced to specify convex parts of the feasibility region. The proposed algorithm could be potentially improved by finding appropriate $y^0$, incorporating other algorithms for boundary walk, efficient algorithms for solving arising SDP. All the issues mentioned above establish the future research plan.