<figure><img src="image_1.png" /></figure>

HAL
open science

# Application of the moment-SOS approach to global optimization of the OPF problem

Cédric Josz, Jean Maeght, Patrick Panciatici, Jean Charles Gilbert

<figure><img src="image_2.png" /></figure>

## To cite this version:

Cédric Josz, Jean Maeght, Patrick Panciatici, Jean Charles Gilbert. Application of the moment-SOS approach to global optimization of the OPF problem. IEEE Transactions on Power Systems, 2014, 30 (1), pp.8. 10.1109/TPWRS.2014.2320819. [hal-00906483v2](https://hal-00906483v2)

HAL Id: hal-00906483

https://inria.hal.science/hal-00906483v2

Submitted on 26 Nov 2013

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
informatics mathematics
Inria

Application of the
Moment-SOS Approach
to Global Optimization of
the OPF Problem

C. JOSZ, J. MAEGHT, P. PANCIATICI, J. Ch. GILBERT

RESEARCH
REPORT

Nº 8397

18 novembre 2013

Project-Team Pompapi
<figure><img src="image_4.png" /></figure>
<figure><img src="image_5.png" /></figure>

Application of the Moment–SOS Approach to
Global Optimization of the OPF Problem

C. JOSZ†‡, J. MAEGHT†, P. PANCIATICI†, J. Ch. GILBERT‡

Project-Team Pomdapi

Research Report n° 8397 — 18 novembre 2013 — 18 pages

**Abstract:** Finding a global solution to the optimal power flow (OPF) problem is difficult due to its nonconvexity. A convex relaxation in the form of semidefinite programming (SDP) has attracted much attention lately as it yields a global solution in several practical cases. However, it does not in all cases, and such cases have been documented in recent publications. This paper presents another SDP method known as the moment-sos (sum of squares) approach, which generates a sequence that converges towards a global solution to the OPF problem at the cost of higher runtime. Our finding is that in the small examples where the previously studied SDP method fails, this approach finds the global solution. The higher cost in runtime is due to an increase in the matrix size of the SDP problem, which can vary from one instance to another. Numerical experiment shows that the size is very often a quadratic function of the number of buses in the network, whereas it is a linear function of the number of buses in the case of the previously studied SDP method.

**Key-words:** Global optimization, moment/sum-of-squares approach, optimal power flow, polynomial optimization, semidefinite programming.

RESEARCH CENTRE
PARIS - ROCQUENCOURT

Domaine de Voluceau, - Rocquencourt
B.P. 105 - 78153 Le Chesnay Cedex

<footnote>† French transmission system operator Réseau de Transport d'Electricité (RTE), 9, rue de la Porte de Buc, BP 561, F-78000 Versailles, France. E-mails: firstname.lastname@rte-france.com.</footnote>

<footnote>‡ INRIA Paris-Rocquencourt, BP 105, F-78153 Le Chesnay, France. E-mails: Cedric.Josz@inria.fr, Jean-Charles.Gilbert@inria.fr.</footnote>
# Application de la Méthode des Moments-SOS à l'Optimisation Globale des Flux d'Énergie dans un Réseau de Transport d'Électricité

**Résumé** : La détermination de la solution globale du problème d'optimisation des flux d'énergie (OFE) dans un réseau de transport d'électricité est difficile à cause de la non-convexité du problème. Une relaxation convexe de celui-ci, utilisant l'optimisation semi-définie positive (SDP), a attiré l'attention ces dernières années, parce qu'elle permet de calculer l'optimum global dans un certain nombre de situations pratiques intéressantes. Cependant, cette relaxation n'est pas toujours exacte et des cas d'échec ont été décrits dans des publications récentes.

Cet article présente une autre méthode de relaxation SDP, connue sous le nom d'approche des moments-sos (sum-of-squares), qui génère une suite de relaxations SDP dont les valeurs optimales doivent théoriquement converger vers celle du problème d'OFE original, au prix d'un temps de calcul croissant. Les résultats numériques présentés dans cet article montrent en réalité que sur les quelques réseaux avec peu de nœuds considérés, sur lesquels la relaxation de rang échoue, l'approche des moments-sos permet de trouver l'optimum global très rapidement. L'accroissement du temps de calcul est dû à l'augmentation de la dimension des matrices intervenant dans les relaxations SDP générées, laquelle est liée à l'ordre de la relaxation. Les tests numériques montrent qu'une dimension de matrice de l'ordre du carré du nombre de nœuds du réseau est souvent suffisante pour obtenir l'optimum global, tandis qu'avec la relaxation de rang, qui est alors inexacte, la dimension des matrices est égale au nombre de nœuds du réseau.

**Mots-clés** : Méthode des moments-sos, optimisation des flux d'énergie, optimisation globale, optimisation polynomiale, optimisation semi-définie positive, réseau de transport d'électricité.
# 1 Introduction

The optimal power flow (OPF) gives its name to a problem pertaining to power systems that was first introduced by Carpentier in 1962 [10]. It seeks to determine a steady state operating point of an alternating current (AC) power network that is optimal under some criteria such as generating costs. The problem can be cast as a nonlinear optimization problem, which is NP-hard, as was shown in [22]. So far, the various methods [15, 26] that have been investigated to solve the OPF can only guarantee local optimality, due to the nonconvexity of the problem. Recent progress suggests that it may be possible to design a method, based on semidefinite programming (SDP), that yields global optimality rapidly.

SDP is a subfield of convex conic optimization [35]. It deals with problems whose structure resembles that of a linear optimization problem, but where the variable that is being solved for is a positive semidefinite matrix. An SDP problem has a convex feasible set whose definition is sufficiently general to model a large variety of convex problems. Furthermore, it can be solved by efficient techniques, notably the interior point methods, which are able to find a solution of a given precision in polynomial time. These properties make the SDP modelling adapted to many applications [3].

The first attempt to use SDP to solve the OPF problem was made by Bai et al. [2] in 2008. In [22], Lavaei and Low show that the OPF can be written as an SDP problem, with an additional constraint imposing that the rank of the matrix variable must not exceed 1. They discard the rank constraint, as it is done in Shor's relaxation [30], a well-known procedure which applies to quadratically constrained quadratic problems (see [34, 25] and the references therein). They also accept quartic terms that appear in some formulations of the OPF, transforming them by Schur's complement. Their finding is that for all IEEE benchmark networks, namely the 9, 14, 30, 57, 118, and 300-bus systems, the rank constraint is satisfied if a small resistance is added in the lines of the network that have zero resistance. Such a modification to the network is acceptable because in reality, resistance is never equal to zero.

There are cases when the rank constraint is not satisfied and a global solution can thus not be found. Lesieutre et al. [23] illustrate this with a practical 3-bus cyclic network. Gopalakrishnan et al. [13] find yet more examples by modifying the IEEE benchmark networks. Bukhsh et al. [8] provide a 2-bus and a 5-bus example. In addition, they document the local solutions to the OPF in many of the above-mentioned examples where the rank constraint is not satisfied [9].

Several papers propose ways of handling cases when the rank constraint is not satisfied. Gopalakrishnan et al. [13] propose a branch and reduce algorithm. It is based on the fact that the rank relaxation gives a lower bound of the optimal value of the OPF. But according to the authors, using the classical Lagrangian dual to evaluate a lower bound is about as efficient. Sojoudi and Lavaei [31] prove that if one could add controllable phase-shifting transformers to every loop in the network and if the objective is an increasing function of generated active power, then the rank constraint is satisfied. Though numerical experiments confirm this [12], such a modification to the network is not realistic, as opposed to the one mentioned earlier.

Cases where the rank constraint holds have been identified. Authors of [7, 36, 32] prove that the rank constraint is satisfied if the graph of the network is acyclic and if load over-satisfaction is allowed. This is typical of distribution networks but it is not true of
transmission networks.

This paper examines the applicability of the moment-sos (sum of squares) approach to the OPF. This approach [18, 27, 19] aims at finding global solutions to polynomial optimization problems, of which the OPF is a particular instance. The approach can be viewed as an extension of the SDP method of [22]. Indeed, it proposes a sequence of SDP relaxations whose first element is the rank relaxation in many cases. The subsequent relaxations of the sequence become more and more accurate. When the rank relaxation fails, it is therefore natural to see whether the second order relaxation provides the global minimum, then the third, and so on.

The limit to this approach is that the complexity of the relaxations rapidly increases. The matrix size of the SDP relaxation of order $d$ is roughly equal to the number of buses in the network to the power $d$. Surprisingly, in the 2, 3, and 5-bus systems found in [23, 8] where the rank relaxation fails, the second order relaxation nearly always finds the global solution.

This paper is organized as follows. Section 2 presents a formulation of the OPF problem and shows that it can be viewed as a polynomial optimization problem. The moment-sos approach which aims at solving such problems is described in section 3. In section 4, numerical results show that this approach successfully finds the global solution to the 2, 3, and 5-bus systems mentioned earlier. Conclusions are given in section 5.

# 2 OPF as a polynomial optimization problem

We first present a classical formulation of the OPF with quadratic objective, Kirchoff's laws, Ohm's law, power balance equations, and operational constraints. It allows for ideal phase-shifting transformers that have a fixed ratio. Next we show how the OPF can be cast as a polynomial optimization problem.

## 2.1 Classical formulation of the OPF

Let $j$ denote the imaginary unit and let $|z|$ and $z^H$ respectively denote the modulus and the conjugate of a complex number $z$.

Consider an AC electricity transmission network defined by a set of buses $\mathcal{N} = \{1, \dots, n\}$ of which a subset $\mathcal{G} \subset \mathcal{N}$ is connected to generators. Let $s_k^{\text{gen}} = p_k^{\text{gen}} + jq_k^{\text{gen}} \in \mathbb{C}$ denote generated power at bus $k \in \mathcal{G}$. All buses are connected to a load (i.e., power demand). Let $s_k^{\text{dem}} = p_k^{\text{dem}} + jq_k^{\text{dem}} \in \mathbb{C}$ denote power demand at bus $k \in \mathcal{N}$. Let $v_k \in \mathbb{C}$ denote voltage at bus $k \in \mathcal{N}$ and $i_k \in \mathbb{C}$ denote current injected into the network at bus $k \in \mathcal{N}$. The convention used for current means that $v_k i_k^H$ is the power injected into the network at bus $k \in \mathcal{N}$. This means that $v_k i_k^H = -s_k^{\text{dem}}$ at bus $k \in \mathcal{N} \setminus \mathcal{G}$ and $v_k i_k^H = s_k^{\text{gen}} - s_k^{\text{dem}}$ at bus $k \in \mathcal{G}$.

The network connects buses to one another through a set of branches $\mathcal{L} \subset \mathcal{N} \times \mathcal{N}$. Let $\mathcal{N}(l)$ denote the set of buses connected to bus $l \in \mathcal{N}$ by a branch in $\mathcal{L}$. If there is a branch connecting buses $l \in \mathcal{N}$ and $m \in \mathcal{N}$, then $(l, m) \in \mathcal{L}$ and $(m, l) \in \mathcal{L}$. A branch between two buses is described in figure 1. In this figure, $y_{lm} \in \mathbb{C}$ denotes the mutual admittance between buses $(l, m) \in \mathcal{L}$ ($y_{ml} = y_{lm}$ for all $(l, m) \in \mathcal{L}$); $y_{lm}^{\text{gr}} \in \mathbb{C}$ denotes the admittance-to-ground at end $l$ of line $(l, m) \in \mathcal{L}$; $i_{lm} \in \mathbb{C}$ denotes current injected in line
$(l, m) \in \mathcal{L}$ at bus $l$; and $\rho_{lm} \in \mathbb{C}$ denotes the ratio of the ideal phase-shifting transformer at end $l$ of line $(l, m) \in \mathcal{L}$ ($\rho_{lm} = 1$ if there is no transformer, the ratio is never equal to zero). For a reference on modelling of an ideal phase-shifting transformer, see [16]. Two ideal transformers appear in figure 1 even though only one or none exist per branch in a transmission network. This allows one to describe a branch using (3).

<figure><img src="image_6.png" /><figcaption>Figure 1: Branch connecting buses $l$ and $m$</figcaption></figure>

The objective of the OPF is a second order polynomial objective function of generated active power at each generator. Let $c_{k0}, c_{k1}, c_{k2} \in \mathbb{R}$ denote the coefficients of the polynomial at bus $k \in \mathcal{G}$ as can be seen in (1). These can be used to model the cost of active generation. They can be of any value, positive or negative, so they can also be used to model minimum deviation from a given generation plan at each generator. Let $p_k^{\text{plan}}$ denote an active generation plan at bus $k \in \mathcal{G}$. One may impose $c_{k0} = (p_k^{\text{plan}})^2$, $c_{k1} = -2p_k^{\text{plan}}$, and $c_{k2} = 1$ to achieve this.

**OPF:**

$$ \min \sum_{k \in \mathcal{G}} c_{k2}(p_k^{\text{gen}})^2 + c_{k1}p_k^{\text{gen}} + c_{k0}, \quad (1) $$

over the variables $(i_k)_{k \in \mathcal{N}}$, $(i_{lm})_{(l,m) \in \mathcal{L}}$, $(p_k^{\text{gen}})_{k \in \mathcal{N}}$, $(q_k^{\text{gen}})_{k \in \mathcal{N}}$ and $(v_k)_{k \in \mathcal{N}}$ subject to

$$ \forall l \in \mathcal{N}, \quad i_l = \sum_{m \in \mathcal{N}(l)} i_{lm}, \quad (2) $$

$$ \forall (l, m) \in \mathcal{L}, \quad \rho_{lm}^{\text{H}} i_{lm} = y_{lm}^{\text{gr}} \frac{v_l}{\rho_{lm}} + y_{lm} \left( \frac{v_l}{\rho_{lm}} - \frac{v_m}{\rho_{ml}} \right), \quad (3) $$

$$ \forall k \in \mathcal{N} \setminus \mathcal{G}, \quad v_k i_k^{\text{H}} = -p_k^{\text{dem}} - j q_k^{\text{dem}}, \quad (4) $$

$$ \forall k \in \mathcal{G}, \quad v_k i_k^{\text{H}} = p_k^{\text{gen}} - p_k^{\text{dem}} + j(q_k^{\text{gen}} - q_k^{\text{dem}}), \quad (5) $$

$$ \forall k \in \mathcal{N}, \quad p_k^{\text{min}} \le p_k^{\text{gen}} \le p_k^{\text{max}}, \quad (6) $$

$$ \forall k \in \mathcal{N}, \quad q_k^{\text{min}} \le q_k^{\text{gen}} \le q_k^{\text{max}}, \quad (7) $$

$$ \forall k \in \mathcal{N}, \quad v_k^{\text{min}} \le |v_k| \le v_k^{\text{max}}, \quad (8) $$

$$ \forall (l, m) \in \mathcal{L}, \quad |v_l - v_m| \le v_{lm}^{\text{max}}, \quad (9) $$

$$ \forall (l, m) \in \mathcal{L}, \quad |i_{lm}| \le i_{lm}^{\text{max}}, \quad (10) $$

$$ \forall (l, m) \in \mathcal{L}, \quad |\text{Re}(v_l i_{lm}^{\text{H}})| \le p_{lm}^{\text{max}}, \quad (11) $$

$$ \forall (l, m) \in \mathcal{L}, \quad |v_l i_{lm}^{\text{H}}| \le s_{lm}^{\text{max}}. \quad (12) $$

Here are a few explanations for the constraints: (2) corresponds to Kirchoff's first law; (3) corresponds to Kirchoff's first law and Ohm's law; (4) and (5) correspond to power balance equations; (6) corresponds to bounds on active generation; (7) corresponds
to bounds on reactive generation; (8) corresponds to bounds on voltage amplitude; (9) corresponds to bounds on voltage difference; (10) corresponds to bounds on current flow; (11) corresponds to bounds on active power flow; and (12) corresponds to bounds on apparent power flow.

Since the ratios of the transformers are considered fixed, (3) implies that current injected at one end of a line is a linear function of the voltages at both ends of the line. Together with (2), this implies that there exists a complex matrix $Y$ such that $i = Yv$. This so called admittance matrix is defined by

$$ Y_{lm} = \begin{cases} \sum_{k \in \mathcal{N} \setminus \{l\}} \frac{y_{lk} + y_{lk}^{gr}}{|\rho_{lk}|^2} & \text{if } l = m, \\ -\frac{y_{lm}}{\rho_{ml} \rho_{lm}^{H}} & \text{if } (l, m) \in \mathcal{L}, \\ 0 & \text{otherwise.} \end{cases} \quad (13) $$

## 2.2 Polynomial optimization formulation of the OPF

In order to obtain a polynomial formulation of the OPF, we proceed in 3 steps. First, we write a formulation in complex numbers. Second, we use it to write a formulation in real numbers. Third, we use the real formulation to write a polynomial formulation.

### 2.2.1 Formulation of the OPF in complex numbers

Let $\mathbf{a}^H$ and $\mathbf{A}^H$ denote the conjugate transpose of a complex vector $\mathbf{a}$ and of a complex matrix $\mathbf{A}$ respectively. It can be deduced from [31] that there exist finite sets $\mathcal{I}$ and $\mathcal{J}$, Hermitian matrices $(A_k)_{k \in \mathcal{G}}$ of size $n$, complex matrices $(B_i)_{i \in \mathcal{I}}$ and $(C_i)_{i \in \mathcal{J}}$ of size $n$, and complex numbers $(b_i)_{i \in \mathcal{I}}$ and $(c_i)_{i \in \mathcal{J}}$ such that the OPF can be written as

$$ \min_{\mathbf{v} \in \mathbb{C}^n} \sum_{k \in \mathcal{G}} c_k 2 (\mathbf{v}^H A_k \mathbf{v})^2 + c_{k1} \mathbf{v}^H A_k \mathbf{v} + c_{k0}, \quad (14) $$

subject to

$$ \forall i \in \mathcal{I}, \quad \mathbf{v}^H B_i \mathbf{v} \le b_i, \quad (15) $$

$$ \forall i \in \mathcal{J}, \quad |\mathbf{v}^H C_i \mathbf{v}| \le c_i. \quad (16) $$

Constraints (16) correspond to bounds on apparent power flow (12). Constraints (15) correspond to all other constraints.

### 2.2.2 Formulation of the OPF in real numbers

Let $\mathbf{x} \in \mathbb{R}^{2n}$ denote $[\mathrm{Re}(\mathbf{v})^\mathrm{T} \ \mathrm{Im}(\mathbf{v})^\mathrm{T}]^\mathrm{T}$ as is done in [22]. In order to transform the complex formulation of the OPF (14)-(16) into a real number formulation, observe that $\mathbf{v}^H \mathbf{M} \mathbf{v} = (\mathbf{x}^\mathrm{T} \mathbf{M}^{\mathrm{re}} \mathbf{x}) + j(\mathbf{x}^\mathrm{T} \mathbf{M}^{\mathrm{im}} \mathbf{x})$, where the superscript $^\mathrm{T}$ denotes transposition,

$$ M^{\mathrm{re}} := \begin{bmatrix} \mathrm{Re}(M) & -\mathrm{Im}(M) \\ \mathrm{Im}(M) & \mathrm{Re}(M) \end{bmatrix}, \quad \text{and} $$

$$ M^{\mathrm{im}} := \begin{bmatrix} \mathrm{Im}(M) & \mathrm{Re}(M) \\ -\mathrm{Re}(M) & \mathrm{Im}(M) \end{bmatrix}. $$
Then (14)-(16) becomes

$$ \min_{\mathbf{x} \in \mathbb{R}^{2n}} \sum_{k \in \mathcal{G}} c_{k2}(\mathbf{x}^{\top} A_k^{\text{re}} \mathbf{x})^2 + c_{k1}\mathbf{x}^{\top} A_k^{\text{re}} \mathbf{x} + c_{k0}, \quad (17) $$

subject to

$$ \forall i \in \mathcal{I}, \quad \mathbf{x}^{\top} B_i^{\text{re}} \mathbf{x} \le \text{Re}(b_i), \quad (18) $$

$$ \forall i \in \mathcal{I}, \quad \mathbf{x}^{\top} B_i^{\text{im}} \mathbf{x} \le \text{Im}(b_i), \quad (19) $$

$$ \forall i \in \mathcal{J}, \quad (\mathbf{x}^{\top} C_i^{\text{re}} \mathbf{x})^2 + (\mathbf{x}^{\top} C_i^{\text{im}} \mathbf{x})^2 \le c_i^2. \quad (20) $$

### 2.2.3 Formulation of the OPF as polynomial optimization problem

We recall that a polynomial is a function $p: \mathbf{x} \in \mathbb{R}^n \mapsto \sum_{\alpha \in \mathcal{A}} p_{\alpha} \mathbf{x}^{\alpha}$, where $\mathcal{A} \subset \mathbb{N}^n$ is a finite set of integer multi-indices, the coefficients $p_{\alpha}$ are real numbers, and $\mathbf{x}^{\alpha}$ is the monomial $x_1^{\alpha_1} \cdots x_n^{\alpha_n}$. Its degree, denoted deg $p$, is the largest $|\alpha| = \sum_{i=1}^n \alpha_i$ associated with a nonzero $p_{\alpha}$.

The formulation of the OPF in real numbers (17)-(20) is said to be a polynomial optimization problem since the functions that define it are polynomials. Indeed, the objective (17) is a polynomial of $\mathbf{x} \in \mathbb{R}^{2n}$ of degree 4, the constraints (18)-(19) are polynomials of $\mathbf{x}$ of degree 2, and the constraints (20) are polynomials of $\mathbf{x}$ of degree 4.

Formulation (17)-(20) will however not be used below because it has infinitely many global solutions. Indeed, formulation (14)-(16) from which it derives is invariant under the change of variables $\mathbf{v} \to \mathbf{v} e^{j\theta}$ where $\theta \in \mathbb{R}$. This invariance property transfers to (17)-(20). An optimization problem with non isolated solutions is generally more difficult to solve than one with a unique solution [5]. This feature manifests itself in some properties of the moment-sos approach described in section 3. For this reason, we choose to arbitrarily set the voltage phase at bus n to zero. Bearing in mind that $v_n^{\min} \ge 0$, this can be done by replacing voltage constraint (21) at bus n by (22):

$$ (v_n^{\min})^2 \le x_n^2 + x_{2n}^2 \le (v_n^{\max})^2, \quad (21) $$

$$ x_{2n} = 0 \quad \text{and} \quad v_n^{\min} \le x_n \le v_n^{\max}. \quad (22) $$

In light of (22), a polynomial optimization problem where there are $2n-1$ variables instead of $2n$ variables can be formulated. More precisely, the OPF (1)-(12) can be cast as the following polynomial optimization problem

**PolyOPF:**

$$ \min_{\mathbf{x} \in \mathbb{R}^{2n-1}} f_0(\mathbf{x}) := \sum_{\alpha} f_{0,\alpha} \mathbf{x}^{\alpha}, \quad (23) $$

subject to

$$ \forall i = 1, \dots, m, \quad f_i(\mathbf{x}) := \sum_{\alpha} f_{i,\alpha} \mathbf{x}^{\alpha} \ge 0, \quad (24) $$

where $m$ is an integer, $f_{i,\alpha}$ denotes the real coefficients of the polynomial functions $f_i$, and summations take place over $\mathbb{N}^{2n-1}$. The summations are nevertheless finite because only a finite number of coefficients are nonzero.
# 3 Moment-sos approach

We first review some theoretical aspects of the moment-sos approach (a nice short account can be found in [1], and more in [20, 4]). Next, we present a set of relaxations of PolyOPF obtained by this method and illustrate it on a simple example. Finally, we emphasize the relationship between the moment-sos approach and the rank relaxation of [22].

## 3.1 Foundation of the moment approach

The moment-sos approach has been designed to find global solutions to polynomial optimization problems. It is grounded on deep results from real algebraic geometry. The term *moment-sos* derives from the fact that the approach has two dual aspects: the moment and the sum of squares approaches. Both approaches are dual of one another in the sense of Lagrangian duality [29]. Below, we focus on the moment approach because it leads to SDP problems that have a close link with the previously studied SDP method in [22].

Let $\mathbf{K}$ be a subset of $\mathbb{R}^{2n-1}$. The moment approach rests on the surprising (though easy to prove) fact that the problem $\min\{f(\mathbf{x}): \mathbf{x} \in \mathbf{K}\}$ is equivalent to the convex optimization problem

$$ \min_{\mu \text{ positive measure on } \mathbf{K}} \int_{\int d\mu=1} f_0 d\mu. \qquad (25) $$

Although the latter problem has a simple structure, it cannot be solved directly, since its unknown $\mu$ is an infinite dimensional object. Nevertheless, the realized transformation suggests that the initial difficult global optimization problem can be structurally simplified by judiciously expressing it on a space of larger dimension. The moment-sos approach goes along this way by introducing a hierarchy of more and more accurate approximations of problem (25), hence (23)-(24), defined on spaces of larger and larger dimension.

When $f_0$ is a polynomial and $\mathbf{K} := \{x \in \mathbb{R}^{2n-1}: f_i(x) \ge 0, \text{ for } i = 1, \dots, m\}$ is defined by polynomials $f_i$ like in PolyOPF, it becomes natural to approximate the measure $\mu$ by a finite number of its moments. The *moment of $\mu$*, associated with $\alpha \in \mathbb{N}^{2n-1}$, is the real number $y_\alpha := \int x^\alpha d\mu$. Then, when $f_0$ is the polynomial in (23), the objective of (25) becomes $\int f_0 d\mu = \int (\sum_\alpha f_{0,\alpha} x^\alpha) d\mu = \sum_\alpha f_{0,\alpha} \int x^\alpha d\mu = \sum_\alpha f_{0,\alpha} y_\alpha$, whose linearity in the new unknown $y$ is transparent. The constraint $\int d\mu = 1$ is also readily transformed into $y_0 = 1$. In contrast, expressing which are the vectors $y$ that are moments of a positive measure $\mu$ on $\mathbf{K}$ (the other constraint in (25)) is a much more difficult task; this is known as the *moment problem* and it is still not completely understood in the multivariate case, despite more than a century of work [28]. It is that constraint that is approximated in the moment-sos approach.

## 3.2 Hierarchy of semidefinite relaxations

Lasserre [19] proposes a sequence of relaxations for any polynomial optimization problem like PolyOPF that grow better in accuracy and bigger in size when the order $d$ of the relaxation increases. Here and below, $d$ is an integer larger than or equal to each $v_i := \lceil(\deg f_i)/2\rceil$ for all $i = 0, \dots, m$ (we have denote by $\cdot$] the ceiling operator).
Let $Z \succcurlyeq 0$ denote that $Z$ is a symmetric positive semidefinite matrix. Define $\mathbb{N}_q^p := \{\alpha \in \mathbb{N}^p : |\alpha| \le q\}$, whose cardinality is $|\mathbb{N}_q^p| = \binom{p+q}{q} := (p+q)!(p!q)$, and denote by $(z_{\alpha,\beta})_{\alpha,\beta \in \mathbb{N}_q^p}$ a matrix indexed by the elements of $\mathbb{N}_q^p$.

**Relaxation of order d:**

$$ \min_{(y_\alpha)_{\alpha \in \mathbb{N}_{2d}^{2n-1}}} \sum_{\alpha} f_{0,\alpha} y_\alpha, \qquad (26) $$

subject to

$$ y_0 = 1, \qquad (27) $$

$$ (y_{\alpha+\beta})_{\alpha, \beta \in \mathbb{N}_d^{2n-1}} \succcurlyeq 0, \qquad (28) $$

$$ \forall i = 1, \dots, m, \quad \sum_{\gamma} f_{i,\gamma} (y_{\alpha+\beta+\gamma})_{\alpha, \beta \in \mathbb{N}_{d-v_i}^{2n-1}} \succcurlyeq 0. \qquad (29) $$

We have already discussed the origin of (26)-(27) in the above SDP problem, while (28)-(29) are necessary conditions to ensure that $y$ is formed of moments of some positive measure on $\mathbf{K}$. When $d$ increases, these problems form a *hierarchy of semidefinite relaxations*, called that way because the objective (26) is not affected and the feasible set is reduced. These properties show that the optimal value of problem (26)-(29) increases with $d$ and remains bounded by the optimal value of (23)-(24).

For the method to give better results, a ball constraint $||x||^2 \le M$ must be added according to the technical assumption 1.1 in [1]. For the OPF problem, this can be done easily by setting $M$ to $\sum_{k \in \mathcal{N}} (v_k^{\max})^2$ using (8) and (22), without modifying the problem. The following two properties hold in this case [1, theorem 1.12]:

1. the optimal values of the hierarchy of semidefinite relaxations increasingly converge toward the optimal value of PolyOPF,

2. let $y^d$ denote a global solution to the relaxation of order $d$ and $(e^i)_{1 \le i \le 2n-1}$ denotes the canonical basis of $\mathbb{N}^{2n-1}$; if PolyOPF has a unique global solution, then $(y_{e^i}^d)_{1 \le i \le 2n-1}$ converges towards the global solution to PolyOPF as $d$ tends to $+\infty$.

The largest matrix size of the moment relaxation appears in (27) and has the value $|\mathbb{N}_d^{2n-1}| = \binom{2n-1+d}{d}$, where $n$ is the number of buses. For a fixed $d$, matrix size is therefore equal to $O(n^d)$. This makes high order relaxations too large to compute with currently available SDP software packages. Consequently, the success of the moment-sos approach relies wholly upon its ability to find a global solution with a low order relaxation, for which there is no guarantee. Note that the global solution is found by a finite order relaxation under conditions that include the convexity of the problem [21] (not the case of PolyOPF though) or the positive definiteness of the Hessian of the Lagrangian at the saddle points of the Lagrangian [11] (open question in the case of PolyOPF).

## 3.3 Example on a 2-bus network

Consider the general OPF problem presented in section 2.1 on a 2-bus network. We will focus only on one constraint among many and write its contribution to the first couple of relaxations of the hierarchy described in section 3.2.
For clarity of presentation, assume there is no apparent power flow constraint and the objective in (1) is a linear function of active power. As was remarked in section 2.2.3, the degree of the objective and the degree of the constraints of PolyOPF are thus equal to 2. The hierarchy of semidefinite relaxations is hence defined for all orders $d \ge 1$.

Notice that since there are $n = 2$ buses, the vector variable in PolyOPF can be written as $\mathbf{x} = [x_1 \ x_2 \ x_3]$. For clarity of presentation, assume that $v_2^{\min} = 0$. Thus, one of the constraints of (22) is $x_2 \ge 0$. Based on (29), the expressions of this constraint in the first and second order relaxations of the hierarchy are (30) and (31) respectively:

$$y_{010} \ge 0, \qquad (30)$$

$$\begin{bmatrix} y_{010} & y_{110} & y_{020} & y_{011} \\ y_{110} & y_{210} & y_{120} & y_{111} \\ y_{020} & y_{120} & y_{030} & y_{021} \\ y_{011} & y_{111} & y_{021} & y_{012} \end{bmatrix} \ge 0. \qquad (31)$$

For higher orders, the size of the matrix corresponding to the constraint grows: 10, 20, 35, etc. Nevertheless, it is the matrix in (28) that determines the size of the relaxation of order $d$ as its size is greater than matrix size in (29).

According to section 3.2, vector $[y_{100} \ y_{010} \ y_{001}]$ appears in all the relaxations of the hierarchy. When optimality is reached in the relaxations, this vector converges towards the global solution $[x_1^{\text{opt}} \ x_2^{\text{opt}} \ x_3^{\text{opt}}]$ to PolyOPF, provided it is unique (Theorem 1.12 in [1]). Notice that in (31), terms appear that correspond to monomials that do not exist in PolyOPF. Typically, $y_{012}$ corresponds to the monomial $x_2x_3^2$ of degree 3 which is not in PolyOPF because we have restricted the degree of the polynomials to be equal to 2.

## 3.4 Moment-sos relaxations and rank relaxation

When the polynomials $f_i$ defining PolyOPF are quadratic, the first order ($d = 1$) relaxation (26)-(29) is equivalent to Shor's relaxation [17]. To make the link with the rank relaxation of [22], consider now the case when the $f_i$'s are quadratic and homogeneous like in [22], that is $f_i(\mathbf{x}) = \mathbf{x}^T A_i \mathbf{x}$ for all $i = 0, \dots, m$, with symmetric matrices $A_i$. Then introducing the vector $\mathbf{s}$ and the matrix $Y$ defined by $\mathbf{s}_i = y_{e^i}$ and $Y_{kl} = y_{e^k+e^l}$, and tr the trace operator, the first order relaxation reads

$$\min_{(\mathbf{s}, Y)} \mathrm{tr}(A_0 Y), \qquad (32)$$

subject to

$$\begin{bmatrix} 1 & \mathbf{s}^T \\ \mathbf{s} & Y \end{bmatrix} \ge 0 \quad \text{and} \quad \mathrm{tr}(A_i Y) \ge 0 \quad (\forall i = 1, \dots, m). \qquad (33)$$

Using Schur's complement, the positive semidefiniteness condition in (33) is equivalent to $Y - \mathbf{s}\mathbf{s}^T \ge 0$. Since $\mathbf{s}$ does not intervene elsewhere in (32)-(33), it can be eliminated and the constraints of the problem can be replaced by

$$Y \ge 0 \quad \text{and} \quad \mathrm{tr}(A_i Y) \ge 0 \quad (\forall i = 1, \dots, m). \qquad (34)$$

The pair made of (32) and (34) is the rank relaxation of [22].

Here is an example of application to the OPF of the above observation: the first order moment relaxation is equivalent to the rank relaxation of [22] if the following conditions hold
1. the objective of the OPF (1) is an affine function of active power,

2. there are no constraints on apparent power flow,

3. (21) is not replaced by (22) to keep the constraints quadratic.

# 4 Numerical results

We present numerical results for the moment-sos approach applied to instances of the OPF for which the rank relaxation method of [22] fails to find the global solution. We focus on the WB2 2-bus system, LMBM3 3-bus system, and the WB5 5-bus system that are described in [8]. Note that LMBM3 is also found in [23]. For each of the three systems, the authors of [8] modify a bound in the data and specify a range for which the rank relaxation fails. We consider 10 values uniformly distributed in the range in order to verify that the rank relaxation fails and to assess the moment-sos approach. We proceed in accordance with the discussion of section 3.2 by adding the redundant ball constraint. Surprisingly, the second order relaxation whose greatest matrix size is equal to $(2n+1)n$ nearly always finds the global solution.

The materials used are:

* Data of WB2, LMBM3, WB5 systems available online [9],

* Intel(R) Xeon(TM) MP CPU 2.70 GHz 7.00 Go RAM,

* MATLAB version 7.7 2008b,

* MATLAB-package MATPOWER version 3.2 [37],

* SeDuMi 1.02 [33] with tolerance parameter pars.eps set to $10^{-12}$ for all computations,

* MATLAB-based toolbox "YALMIP" [24] to compute Optimization 4 (Dual OPF) in [22] that yields the solution to the rank relaxation,

* MATLAB-package GloptiPoly version 3.6.1 [14] to compute solutions to a hierarchy of SDP relaxations (26)-(29).

The same precision is used as in the solutions of the test archives [9]. In other words, results are precise up to $10^{-2}$ p.u. for voltage phase, $10^{-2}$ degree for angles, $10^{-2}$ MW for active power, $10^{-2}$ MVA for reactive power, and cent per hour for costs. Computation time is several seconds.

GloptiPoly can guarantee that it has found a global solution to a polynomial optimization problem, up to a given precision. This is certainly the case when it finds a feasible point $x$ giving to the objective a value sufficiently close to the optimal value of the relaxation.

## 4.1 2-bus network: WB2

Authors of [8] observe that in the WB2 2-bus system of figure 2, the rank constraint is not satisfied in the rank relaxation method of [22] when 0.976 p.u. $< v_2^{\max} < 1.035$ p.u. In table 1, the first column is made up of 10 points in that range that are uniformly distributed. The second column contains the lowest order of the relaxations that yield a global solution. The optimal value of the relaxation of that order is written in the third column. The fourth
column contains the optimal value of the rank relaxation (it is put between parentheses when the relaxation is inexact).

<figure><img src="image_7.png" /><figcaption>Figure 2: WB2 2-bus system</figcaption></figure>

<table><caption>Table 1: Order of hierarchy needed to reach global solution to WB2 when rank relaxation fails</caption><thead><tr><th>v<sub>2</sub><sup>max</sup><br>(p.u.)</th><th>relax.<br>order</th><th>optimal<br>value ($/h)</th><th>rank relax.<br>value ($/h)</th></tr></thead><tbody><tr><td>0.976</td><td>2</td><td>905.76</td><td>905.76</td></tr><tr><td>0.983</td><td>2</td><td>905.73</td><td>(903.12)</td></tr><tr><td>0.989</td><td>2</td><td>905.73</td><td>(900.84)</td></tr><tr><td>0.996</td><td>2</td><td>905.73</td><td>(898.17)</td></tr><tr><td>1.002</td><td>2</td><td>905.73</td><td>(895.86)</td></tr><tr><td>1.009</td><td>2</td><td>905.73</td><td>(893.16)</td></tr><tr><td>1.015</td><td>2</td><td>905.73</td><td>(890.82)</td></tr><tr><td>1.022</td><td>3</td><td>905.73</td><td>(888.08)</td></tr><tr><td>1.028</td><td>3</td><td>905.73</td><td>(885.71)</td></tr><tr><td>1.035</td><td>2</td><td>882.97</td><td>882.97</td></tr></tbody></table>

The hierarchy of SDP relaxations is defined for $d \ge 1$ because the objective is an affine function and there are no apparent flow constraints. Let's explain how it works in the case where $v_2^{\max} = 1.022$ p.u. The optimal value of the first order relaxation is 861.51 $/h$, that of the second order relaxation is 901.38 $/h$, and that of the third is 905.73 $/h$. This is coherent with point 1 of the discussion of section 3.2 that claims that the optimal values increase with $d$. Computing higher orders is not necessary because GloptiPoly numerically proves global optimality for the third order.

Notice that for $v_2^{\max} = 1.022$ p.u. the value of the rank relaxation found in table 1 (888.08 $/h$) is different from the value of the first order relaxation (861.51 $/h$). If we run GloptiPoly with (21) instead of (22), the optimal value of the first order relaxation is equal 888.08 $/h$ as expected according to section 3.4.

For $v_2^{\max} = 0.976$ p.u. and $v_2^{\max} = 1.035$ p.u. (see the first and last rows of table 1), the rank constraint is satisfied in the rank relaxation method so its optimal value is equal to the one of the successful moment-sos method. In between those values, the rank constraint is not satisfied since the optimal value is less than the optimal value of the OPF. Notice the correlation between the results of table 1 and the upper half of figure 8 in [8]. Indeed, the figure shows the optimal value of the OPF is constant whereas the optimal value of the rank relaxation decreases in a linear fashion when 0.976 p.u. $< v_2^{\max} < 1.035$ p.u.

Surprisingly and encouragingly, according to the second column of table 1, the second order moment-sos relaxation finds the global solution in 8 out of 10 times, and the third
order relaxation always find the global solution.

*Remark:* The fact that the rank constraint is not satisfied for the WB2 2-bus system of [8] seems in contradiction with the results of papers [7, 36, 32]. Indeed, the authors of the papers state that the rank is less than or equal to 1 if the graph of the network is acyclic and if load over-satisfaction is allowed. However, load over-satisfaction is not allowed in this network. For example, for $v_2^{\max} = 1.022$ p.u., adding 1 MW of load induces the optimal value to go down from 905.73 $/h$ to 890.19 $/h$. One of the sufficient conditions in [6] for the rank is less than or equal to 1 relies on the existence of a strictly feasible point. It is not the case here because equality constraints must be enforced in the power balance equation.

## 4.2 3-bus network: LMBM3

We observe that in the LMBM3 3-bus system of figure 3, the rank constraint is not satisfied in the rank relaxation method of [22] when 28.35 MVA $\le s_{23}^{\max} = s_{32}^{\max} < 53.60$ MVA. Below 28.35 MVA, no solutions can be found by the OPF solver runopf in MATPOWER nor by the hierarchy of SDP relaxations. At 53.60 MVA, the rank constraint is satisfied in the rank relaxation method so its optimal value is equal to the optimal value of the OPF found by the second order relaxation; see to the last row of table 2.

<figure><img src="image_8.png" /><figcaption>Figure 3: LMBM3 3-bus system</figcaption></figure>
<table><caption>Table 2: Order of hierarchy needed to reach global solution to LMBM3 when rank relaxation fails</caption><thead><tr><th>s<sub>23</sub><sup>max</sup> = s<sub>32</sub><sup>max</sup><br>(MVA)</th><th>relax.<br>order</th><th>optimal<br>value ($/h)</th><th>rank relax.<br>value ($/h)</th></tr></thead><tbody><tr><td>28.35</td><td>2</td><td>10294.88</td><td>(6307.97)</td></tr><tr><td>31.16</td><td>2</td><td>8179.99</td><td>(6206.78)</td></tr><tr><td>33.96</td><td>2</td><td>7414.94</td><td>(6119.71)</td></tr><tr><td>36.77</td><td>2</td><td>6895.19</td><td>(6045.33)</td></tr><tr><td>39.57</td><td>2</td><td>6516.17</td><td>(5979.38)</td></tr><tr><td>42.38</td><td>2</td><td>6233.31</td><td>(5919.12)</td></tr><tr><td>45.18</td><td>2</td><td>6027.07</td><td>(5866.68)</td></tr><tr><td>47.99</td><td>2</td><td>5882.67</td><td>(5819.02)</td></tr><tr><td>50.79</td><td>2</td><td>5792.02</td><td>(5779.34)</td></tr><tr><td>53.60</td><td>2</td><td>5745.04</td><td>5745.04</td></tr></tbody></table>

The objective of the OPF is a quadratic function of active power so the hierarchy of SDP relaxations is defined for $d \ge 2$. Again, it is surprising that the second order moment-sos relaxation always finds the global solution to the LMBM3 system, as can be seen in the second column of table 2.

Authors of [22] make the assumption that the objective of the OPF is an increasing function of generated active power. The moment-sos approach does not require such an assumption. For example, when $s_{23}^{\max} = s_{32}^{\max} = 50$ MVA, active generation at bus 1 is equal to 148.07 MW and active generation at bus 2 is equal to 170.01 MW using the increasing cost function of [23, 9]. Suppose we choose a different objective which aims at reducing deviation from a given active generation plan at each generator. Say that this plan is $p_1^{\text{plan}} = 170$ MW at bus 1 and $p_2^{\text{plan}} = 150$ MW at bus 2. The objective function is equal to $(p_1^{\text{gen}} - p_1^{\text{plan}})^2 + (p_2^{\text{gen}} - p_2^{\text{plan}})^2$. It is not an increasing function of $p_1^{\text{gen}}$ and $p_2^{\text{gen}}$. The second order relaxation yields a global solution in which active generation at bus 1 is equal to 169.21 MW and active generation at bus 2 is equal to 149.19 MW.

## 4.3 5-bus network: WB5

Authors of [8] observe that in the WB5 5-bus system of figure 4, the rank constraint is not satisfied in the rank relaxation method of [22] when $q_5^{\min} > -30.80$ MVAR. Above 61.81 MVAR, no solutions can be found by the OPF solver runopf in MATPOWER. At $-30.80$ MVAR, the rank constraint is satisfied in the rank relaxation method so its optimal value is equal to the optimal value of the OPF found by the second order moment-sos relaxation; see the first row of table 3. As for the 9 values considered greater than $-30.80$ MVAR, the rank constraint is not satisfied since the optimal value is not equal to the optimal value of the OPF. Notice that the objective of the OPF is a linear function of active power and there are bounds on apparent flow so the hierarchy of SDP relaxations is defined for $d \ge 1$.
<figure><img src="image_9.png" /><figcaption>Figure 4: WB5 5-bus system</figcaption></figure>

<table><caption>Table 3: Order of hierarchy needed to reach global solution to WB5 when rank relaxation fails</caption><thead><tr><th>q<sub>5</sub><sup>min</sup><br>(MVA)</th><th>relax.<br>order</th><th>optimal<br>value ($/h)</th><th>rank relax.<br>value ($/h)</th></tr></thead><tbody><tr><td>-30.80</td><td>2</td><td>945.83</td><td>945.83</td></tr><tr><td>-20.51</td><td>2</td><td>1146.48</td><td>(954.82)</td></tr><tr><td>-10.22</td><td>2</td><td>1209.11</td><td>(963.83)</td></tr><tr><td>00.07</td><td>2</td><td>1267.79</td><td>(972.85)</td></tr><tr><td>10.36</td><td>2</td><td>1323.86</td><td>(981.89)</td></tr><tr><td>20.65</td><td>2</td><td>1377.97</td><td>(990.95)</td></tr><tr><td>30.94</td><td>2</td><td>1430.54</td><td>(1005.13)</td></tr><tr><td>41.23</td><td>2</td><td>1481.81</td><td>(1033.07)</td></tr><tr><td>51.52</td><td>2</td><td>1531.97</td><td>(1070.39)</td></tr><tr><td>61.81</td><td>-</td><td>-</td><td>(1114.90)</td></tr></tbody></table>

When $q_5^{\min} = 61.81$ MVAR, the hierarchy of SDP relaxations is unable to find a feasible point, hence the empty slots in the last row of table 3. Apart from that value, the second order moment-sos relaxation again always finds the global solution according to the second column of 3.

# 5 Conclusion

This paper examines the application of the moment-sos (sum of squares) approach to the global optimization of the optimal power flow (OPF) problem. The result of this paper is that the OPF can be successfully convexified in the case of several small networks where a previously known SDP method fails. The SDP problems considered in this paper can be viewed as extensions of the previously used rank relaxation. It is guaranteed to be more accurate than the previous one but requires more runtime. Directions for future research include using sparsity techniques to reduce computational effort and identifying the OPF problems for which a low order relaxation is exact.
Acknowledgment

Many thanks to Stéphane Fliscounakis for fruitful discussions on the optimal power flow problem and to Javad Lavaei for sharing his MATLAB codes with us.

References

[1] M. F. Anjos, J. B. Lasserre (2012). Introduction to semidefinite, conic and polynomial optimization. In M. F. Anjos, J. B. Lasserre (editors), *Handbook on Semidefinite, Conic and Polynomial Optimization*, volume 166 of *International Series in Operations Research & Management Science*. Springer. 8, 9, 10

[2] X. Bai, H. Wei, K. Fujisawa, Y. Wang (2008). Semidefinite programming for optimal power flow problems. *International Journal of Electrical Power & Energy Systems*, 30(6-7), 383-392. [doi]. 3

[3] A. Ben-Tal, A. Nemirovski (2001). *Lectures on Modern Convex Optimization – Analysis, Algorithms, and Engineering Applications*. MPS-SIAM Series on Optimization 2. SIAM. 3

[4] G. Blekherman, P. A. Parrilo, R. R. Thomas (2013). *Semidefinite Optimization and Convex Algebraic Geometry*. MOS-SIAM Series on Optimization. SIAM and MPS, Philadelphia. [doi]. 8

[5] J.F. Bonnans, J.Ch. Gilbert, C. Lemaréchal, C. Sagastizábal (2006). *Numerical Optimization – Theoretical and Practical Aspects* (second edition). Universitext. Springer Verlag, Berlin. [authors] [editor]. 7

[6] S. Bose, D. F. Gayme, K. M. Chandy, S. H. Low (2012). Quadratically constrained quadratic programs on acyclic graphs with application to power. Submitted to *IEEE Transactions on Power Systems*. 13

[7] S. Bose, D. F. Gayme, S. H. Low, K. M. Chandy (2011). Optimal power flow over tree networks. In *Proc. 49th Annual Allerton Conference on Communication, Control, and Computing*. 3, 13

[8] W. A. Bukhsh, A. Grothey, K. I. McKinnon, P. A. Trodden (2013, August). Local solutions of the optimal power flow problem. Submitted to *IEEE Transactions on Power Systems*. 3, 4, 11, 12, 13, 14

[9] W. A. Bukhsh, A. Grothey, K. I. McKinnon, P. A. Trodden (2013). Test case archive of optimal power flow (OPF) problem with local optima. Available online: http://www.maths.ed.ac.uk/optenergy/LocalOpt/. 3, 11, 14

[10] M. J. Carpentier (1962). Contribution à l'étude du dispatching économique. *Bulletin de la Société Française des Électriciens*, 8, 431-447. 3

[11] E. de Klerk, M. Laurent (2011). On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems. *SIAM Journal on Optimization*, 21(3), 824-832. [doi]. 9

[12] M. Farivar, S. Low (2013). A survey of the optimal power flow literature. *IEEE Transactions on Power Systems*, 28(3), 2565-2572. 3

[13] A. Gopalakrishnan, A. U. Raghunathan, D. Nikovski, L. T. Biegler (2012). Global optimization of optimal power flow using a branch & bound algorithm. In *Proc. 50th Annual Allerton Conference on Communication, Control, and Computing*. 3
[14] D. Henrion, J. B. Lasserre, J. Löfberg (2009). GloptiPoly 3: moments, optimization and semidefinite programming. *Optimization Methods and Software*, 24, 761–779. 11

[15] M. Huneault, F. D. Galiana (1991). A survey of the optimal power flow literature. *IEEE Transactions on Power Systems*, 6(2), 762–770. 3

[16] P. Kundur (1994). AC transmission. In *Power System Stability and Control*, pages 245–249. McGraw-Hill, Inc. 5

[17] J. B. Lasserre. Convergent LMI relaxations for nonconvex quadratic programs. Graduate seminar at MIT, fall 2001. Available online: http://www.mit.edu/6.454/www_fall_2001/cmcaram/lasserre_1.pdf. 10

[18] J. B. Lasserre (2000). Optimisation globale et théorie des moments. *C. R. Acad. Sci. Paris, Série I*, 331, 929–934. 4

[19] J. B. Lasserre (2001). Global optimization with polynomials and the problem of moments. *SIAM Journal on Optimization*, 11, 796–817. [doi]. 4, 8

[20] J. B. Lasserre (2010). *Moments Positive Polynomials and Their Applications*. Imperial College Press Optimization Series 1. Imperial College Press. 8

[21] J.B. Lasserre (2008). Convexity in semialgebraic geometry and polynomial optimization. *SIAM Journal on Optimization*, 19, 1995–2014. [doi]. 9

[22] J. Lavaei, S. H. Low (2012). Zero duality gap in optimal power flow problem. *IEEE Transactions on Power Systems*, 27(1), 92–107. 3, 4, 6, 8, 10, 11, 13, 14

[23] B. C. Lesieutre, D. K. Molzahn, A. R. Borden, Ch. L. DeMarco (2011). Examining the limits of the application of semidefinite programming to power flow problems. In *Proc. 49th Annual Allerton Conference on Communication, Control, and Computing*, pages 28–30. 3, 4, 11, 14

[24] J. Löfberg (2004). YALMIP: A toolbox for modeling and optimization in Matlab. In *IEEE International Symposium on Computer Aided Control Systems Design*, pages 284–289. 11

[25] Z.-Q. Luo, W.-K. Ma, A. M.-C. So, Y. Ye, S. Zhang (2010). Semidefinite relaxation of quadratic optimization problems. *IEEE Signal Processing Magazine*, 27, 20–34. [doi]. 3

[26] K. S. Pandya, S. K. Joshi (2008). A survey of optimal power flow methods. *Journal of Theoretical of Applied Information Technology*, 4(5), 450–458. 3

[27] P. A. Parrilo (2000, May). *Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization*. PhD Thesis, California Institute of Technology. 4

[28] M. Putinar, K. Schmüdgen (2008). Multivariate determinateness. *Indiana University Mathematics Journal*, 57, 2931–2968. 8

[29] R. T. Rockafellar (1974). *Conjugate Duality and Optimization*. Regional Conference Series in Applied Mathematics 16. SIAM, Philadelphia, PA, USA. 8

[30] N. Z. Shor (1987). Quadratic optimization problems. *Soviet Journal of Computer and System Sciences*, 25, 1–11. 3

[31] S. Sojoudi, J. Lavaei (2012). Network topologies guaranteeing zero duality gap for optimal power flow problem. Submitted to *IEEE Transactions on Power Systems*. 3, 6

[32] S. Sojoudi, J. Lavaei (2012). Physics of power networks makes hard optimization problems easy to solve. In *IEEE Power & Energy Society (PES) General Meeting*. 3, 13

[33] J. F. Sturm (1999). Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones. *Optimization Methods and Software*, 11, 625–653. 11
[34] J. F. Sturm, S. Zhang (2003). On cones of nonnegative quadratic functions. *Mathematics of Operations Research*, 28, 246–267. [doi]. 3

[35] H. Wolkowicz, R. Saigal, L. Vandenberghe (editors) (2000). *Handbook of Semidefinite Programming – Theory, Algorithms, and Applications*. Kluwer Academic Publishers. 3

[36] B. Zhang, D. Tse (2011). Geometry of feasible injection region of power networks. In *Proc. 50th Annual Allerton Conference on Communication, Control, and Computing*. 3, 13

[37] R. Zimmerman, C. Murillo-Sánchez, R. Thomas (2011). MATPOWER: Steady-state operations, planning, and analysis tools for power systems research and education. *IEEE Transactions on Power Systems*, 99, 1–8. 11
informatics mathematics
Inria

RESEARCH CENTRE
PARIS - ROCQUENCOURT

Domaine de Voluceau, - Rocquencourt
B.P. 105 - 78153 Le Chesnay Cedex

Publisher
Inria
Domaine de Voluceau - Rocquencourt
BP 105 - 78153 Le Chesnay Cedex
inria.fr

ISSN 0249-6399