[PDF] Certified and accurate SDP bounds for the ACOPF problem

View - Download Certified and accurate SDP bounds for the ACOPF problem

Previous PDF

Next PDF

Certified and accurate SDP bounds for the ACOPF

problem

Antoine Oustry

y, Claudia D"Ambrosio, Leo Libertiand Manuel Ruizz

LIX CNRS,´Ecole polytechnique

Institut Polytechnique de Paris, 91128, Palaiseau, France y´Ecole des Ponts, 77455 Marne-La-Vall´ee zR&D department, R´eseau de transport d"´electricit´e, 92073 La D´efense, France Abstract-We propose a new method for improving the bound tightness of the popular semidefinite programming (SDP) relaxation for the ACOPF introduced in [1], [2]. First, we reformulate the ACOPF Lagrangian dual as an unconstrained concave maximization problem with a clique decomposition induced sparse structure. We prove that this new formulation has the same optimal value as the SDP relaxation. We then use the solution of the SDP relaxation as a starting point for a tailored structure-aware bundle method. This post-processing technique significantly improves the tightness of the SDP bounds computed by the state-of-the-art solver MOSEK, as shown by our computational experiments on large-scale instances from PGLib- OPF v21.07. For ten of the tested instances, our post-processing decreases by mor ethan 50% the optimality gap obtained with

MOSEK.

Index Terms-AC Optimal Power Flow, Complex semidefinite programming, Nonsmooth optimization.

I. INTRODUCTION

The ACOPF problem is one of the most fundamental

optimization problems for the management of electric power systems. This is a cost minimization problem in an AC net- work, where the generators should supply electricity to loads under generator and line constraints. Due to the nonconvexity of power flow equations, the ACOPF is a difficult optimization problem both in theory [3] and in practice [4]. Although local optimization solvers are able to find good solutions, obtaining a feasible point with a global optimality certificate is still a challenge for national-scale instances. In this quest for global optimization, convex relaxations are powerful tools to efficiently compute lower bounds on the ACOPF"s value. A review of various relaxation techniques for the ACOPF problem is available in [2]. Among them, semidefinite pro- gramming (SDP) is of strong interest for both theoretical and practical reasons: indeed, the semidefinite relaxation (SDR) is the ACOPF"s Lagrangian bidual [1] and provides tight lower bounds [5]. The main drawback of the standard SDR is that it involves a densenncomplex matrix as a decision variable, wherenis the number of buses. This becomes intractable as soon asnexceeds magnitudesof around 103. To overcome this computational burden, state-of-the-art approaches [6], [7] exploit the sparse structure of the power grid by using a clique decomposition technique. Thanks to a semidefinite completion theorem [8] for matrices with chordal sparsity pattern, it is possible to find an equivalent formulation

for the SDR, with many small semidefinite blocks instead of asingle and largennmatrix. Each of these blocks corresponds

to a maximal clique of the chordal sparsity pattern. This clique-based SDR can be solved with a symmetric interior point (IP) solver [9], [10], with a non-symmetric IP solver [11] or with a first order method like the Alternating Direction Method of Multipliers (ADMM) [12]-[14]. Eltved et al. [6] report the solution of the clique-based ACOPF"s SDR for test cases with up to82;000buses, in a few hours. Despite these advances, the clique-based SDR remains dif- ficult to solve for large-scale instances: numerical instabilities may arise when solving this convex optimization problem. In [5] and [15], the authors report numerical instabilities with the commercial IP solver MOSEK [9], which raises a warning for many tested instances. In [6], the authors report that the well- known academic IP solver SeDuMi fails to solve the clique- based SDR in more than 50% of the test cases; and that the ADMM-based solver CDCS often terminates with sizable dual residuals. Two categories of troubles may arise due to numerical difficulties in solving the SDR. First, they may limit the accuracy of the calculation of the SDR value. Second, obtaining a solution with non-zero primal and/or dual feasibility errors implies that the calculated relaxation value is notcertified[16]. In this case, one obtains anapproximated value of the relaxation without knowing if it is anexactlower bound on the ACOPF"s value. Main contributionsThis paper tackles both aforementioned numerical issues with an original approach. For this purpose, we introduce a new formulation for the Lagrangian dual of the ACOPF, whose value equals the value of the SDR. Our new formulation is a concave maximization problem with the following interesting properties: (a) it is unconstrained (b) the objective function ispartially separable. Based on this formulation, we present how to obtain a certified lower bound from any dual vector, whether feasible or not in theclassical dual SDR. We solve our new formulation with a structure- exploiting polyhedral bundle method. We use this algorithm as apost-processing step, after solving the clique-based SDR with the commercial IP solver MOSEK [9], which is the state- of-the-art solver for ACOPF"s SDR according to [2], [6]. Our numerical experiments on instances from PGLib-OPF v21.07

[17] show that this post-processing considerably improves the22nd Power Systems Computation Conference

PSCC 2022Porto, Portugal - June 27 - July 1, 2022

2 tightness of the dual bounds. For 13 cases, the post-processing increases the certified dual bound by more than0:1%. A more accurate dual bound yields a lo weroptimality g ap : for10 cases, the gap is reduced by more than50%; for5cases among them, the gap is reduced by more than90%.

Mathematical notations:

•x+,x: positive and negative part of the real numberx, •Re(z);Im(z),z?,jzj: Real part, imaginary part, conju- gate and magnitude of complex numberz=Re(z) + iIm(z), •HnCnn: the set of Hermitian matrices of size n, subset ofCnn, the vector space of square complex matrices of sizen, •Hn(S)Hn, forS f1;:::;ng: the set of Hermitian matrices of sizen, whose non-zero coefficients all belong to the principal submatrix associated with indicesk2S, •MH: Hermitian transpose of the matrixM2Cnn, •H(M) :=12 (M+MH)andZ(M) :=12 (MMH), •Tr(M): Trace of the matrixM, •hM;Ni=Tr(MHN): Frobenius product between com- plex matricesM;N2Cnn, •min(H)2R: Minimum eigenvalue of the Hermitian matrixH2Hn, •H0: the matrixHis positive semidefinite (PSD), •Eba: the matrix of the canonical basis ofCnn, associ- ated with the pair of indices(b;a).

II. THEACOPF,THEACOPF"SSDRAND THEIR DUAL

This section presents the context of this work, i.e. the ACOPF problem with current limits, its SDR, and the state- of-the-art approach to solve it, based on clique decomposition.

A. Problem formulation

A power grid is as a network of buses interconnected by lines. It is modelled [18] as an oriented multi-graphN= (B;L)with sizesn=jBjandl=jLj. The orientation of a line is an arbitrary but necessary convention to uniquely define the admittance matrix (see below) modelling this line. A line`2 Lis described by a triplet(b;a;h)s.t.b2 Bis the "'from" bus (denoted byf),a2 Bis the "to" bus (denoted by t) andh2Nis an index, which is non-null in case there are several parallel lines betweenbanda. Electricity generating units are located in several buses in the network. We denote byGbthe set of generators located at busb2 B. The set of all generators isG:=[b2BGb, whose cardinality is denoted bym=jGj. For any generatorg2 G, we denote byb(g)2 B the bus where the generatorgis located. For eachg2 G, the generated powerSg2Cis a decision variable subject to Pg

Re(Sg)P

g;(1) Qg

Im(Sg)Q

g;(2) for parametersPg ;P g;Qg ;Q g2R. For brevity, we define Sg =Pg +iQg ,S g=P g+iQ gand we write (1)- (2) asSg2Sg ;S g

C. The generators" cost functions are

traditionally assumed to depend only on the active powerand to be quadratic convex [18]. Consistently with this latter

assumption and for allg2 G, we definec0g2R,c1g2R andc2g2R+, s.t. the cost associated with active powerp isc0g+c1gp+c2gp2. Since the offsetsc0gplay no role in the optimization, we assume without loss of generality that c

0g= 0, for better readability. However, in the numerical

experiments, we take these offsets into account. We denote by G

1the set of generatorsgwith purely linear cost (c2g= 0),

andG2:=G n G1, which should not be confused with the set G bof generators attached to busb. For each busb2 B, the voltageVb2Cis a decision variable subject to Vb jVbj V b;(3) for parametersVb ;V b2R+. The other parameters related to busbare a shunt admittanceYsb2Cand a loadSloadb= P loadb+iQloadbwithPloadb;Qloadb2R. So as to model the power conservation at each bus, we also need to introduce quantities describing the electrical characteristics of the lines. For each line`= (b;a;h)2 L, we know its (non-symmetric) admittance matrixY`2C22, which follows from a-line model of the line [18]. The coefficients of this matrix are denoted byY`;Yft`;Ytf`;Ytt`. With this notation, we define M b:=YsbEbb+X `2L `=(b;a;h)Y `Ebb+Yft`Eba X `2L `=(a;b;h)Y tt`Ebb+Ytf`Eba; for each busb2 B. Then, the equation modelling the power conservation atb2 Bis X g2GbS g=Sloadb+

Mb;V VH:(4)

Finally, we consider current flow limits on lines. For any line `= (b;a;h)2 L, given a limitI `2R+, we have jY`Vb+Yft`Vaj I `;(5) jYtt`Va+Ytf`Vbj I `:(6) We treat this type of branch flow limits because they are the ones that R ´eseau de Transport d"Electricit´e, the French Trans- mission System Operator, deals with in its daily operations. Nevertheless, our approach could easily be transposed to other types of constraints such as apparent power flow limits. In summary, the ACOPF problem with current flow constraints is the following non-convex optimization problem: min P g2Gc

1gRe(Sg) +c2gRe(Sg)2

s.t. (1)(6)

V2Cn; S2Cm:(OPF)

For any line`= (b;a;h)2 L, we also introduce the matrices N N `t:=jYtt`j2Eaa+Ytt`(Ytf`)?Eba+ (Ytt`)?Ytf`Eab+jYtf`j2Ebb.

Hence, constraints (5) and (6) reads

N`f;V VHI

`2and

N`t;V VHI

`2.22nd Power Systems Computation Conference

PSCC 2022Porto, Portugal - June 27 - July 1, 2022

3

B. The SDR and the clique-based SDR

The SDR, also known as "rank relaxation", is classically derived by replacing the rank-one matrixV VHin (OPF) by a

Hermitian and PSD matrixWof unspecified rank. Hence, theSDR of (OPF) is the following convex optimization problem

min P g2Gc

1gRe(Sg) +c2gRe(Sg)2

s.t.V2 b hEbb;Wi V b28b2 B(SDR)P g2GbS g=Sloadb+hMb;Wi 8b2 B hN`s;Wi I `28(`;s)2 L ff;tg W0

W2Hn; S2Q

g2GSg ;S g C This formulation becomes intractable for large-scale instances [2]. A standard approach to avoid this computational burden

consists in introducing a chordal extension of the undirectedgraph induced byN, and aclique treeTof this chordal

extension [19]. For any nodek2 T, the setBk B is the corresponding clique of the chordal extension, andn kis its cardinality. Choosing an arbitrary rootr2 T, we designate byp(k)2 Tthe parent node of any node k2 T, with the conventionp(r) =r. We define the set J k:=f(b;a)2(Bk\ Bp(k))2:bag. For anyb2 B, we introduce some matricesMbk2Hn(Bk)fork2 T, so as to writeMb=P k2T jb2BkM bk. We underline that the non-zero

coefficients in matrixMbkall belong to the principal submatrixassociated with cliqueBk. For any line`= (b;a;h)2 L, we

definek(`)2 Ts.t.fb;ag Bk. With this notation the clique- based SDR, denoted by(cSDR), reads min P g2Gc

1gRe(Sg) +c2gRe(Sg)2

s.t.V2 b hEbb;Wki V b28k2 T;8b2 BkP g2GbS g=Sloadb+P k2T jb2BkhMbk;Wki 8b2 B N `s;Wk(`)I `28(`;s)2 L ff;tg hEba;Wki= E ba;Wp(k)8k2 T;8(b;a)2 Jk W k08k2 T W k2Hn(Bk)8k2 T S2Q g2GSg ;S g C: The advantage of formulation(cSDR)is that the total number of non-zero coefficients in the matrices(Wk)k2TisP k2Tn2k, whereas the matrix variableWin(SDR)involvesn2non-zero coefficients. If the cliques are of limited size (nkn), then this decomposition is particularly relevant. This is often the case in ACOPF instances, since power grids are known to have low tree-width [2]. SincejT j nby property of chordal graphs, we deduce that for graphs with bounded tree-width ,P k2Tn2kscales inO(n)rather thanO(n2).

Proposition 1.The SDP problems(SDR)and(cSDR)share

the same value. Proof.This follows from the PSD completion theorem in [8], for Hermitian matrices with chordal sparsity pattern.In the following, we will use the integersK1:=P k2Tnk, K 2:=P k2TjJkjandN:=K1+ 2(n+l+K2).C. The SDP dual of the clique-based SDR The dual formulation of(cSDR)includes Linear Matrix Inequalities (LMI) involving a family ofR-linear matrix operatorsAk:RN!Hn(Bk)fork2 T. The operatorAkis defined s.t. for all= (;; ;;;)2RN, A k() :=X b2Bk bkEbb+bH(Mbk) +i bZ(Mbk) X (`;s)2Lff;tg `sN`s+X (b;a)2Jk bakH(Eba) +ibakZ(Eba) 0 X d2Cjp(d)=kX (b;a)2Jd badH(Eba) +ibadZ(Eba)1 A We point out that the Hermitian part and anti-Hermitian part operatorsHandZ, defined in Introduction, appear when

projecting the complex equalities of the primal problem ontheir real and imaginary parts. Having introduced the operators

A kfork2 T, the dual of(cSDR), which we denote by (dualcSDR), then reads max P k2T; b2BkV2 bbk V b2 bk+P b2BPloadbb+Qloadb b P g2GPg yg P gy g+Qg zg Q gz g P g2G2(c1g+y gyg b(g))24c2gP `2LI `2(f`+t`) s.t.Ak(;; ;;;)08k2 Ty gyg =b(g)c1g8g2 G1z gzg b(g)8g2 G (y;y;z;z)2R4m+ (;)2R2K1+ ;;;)2R2(n+l+K2):

III. NEW FORMULATION FOR THE DUALACOPF

This section introduces the central element of our approach, i.e. a new formulation for the dual problem of the ACOPF.

A. Some concave functions of interest

In order to reformulate(dualcSDR)as an unconstrained problem, we introduce some basic functions that are terms in the objective function of(dualcSDR)or penalizations of the constraints: for each generatorg2 G1, we introduce the concave functionspg;qgs.t. for allx2R, p g(x) :=Pg (xc1g)P g(xc1g)+; q g(x) :=Qg xQ gx+; for each generatorg2 G2, we introduce the concavefunctionspg;qgs.t. for allx2R, p g(x) :=8 :Pg (xc1gc2gPg )ifxc1g2c2gPg (xc1g)24c2gifxc1g2[ 2c2gPg ;2c2gP g]; P g(xc1gc2gP g)ifxc1g2c2gP g; q g(x) :=Qg xQ gx+;22nd Power Systems Computation Conference

PSCC 2022Porto, Portugal - June 27 - July 1, 2022

4 for each busb2 B, we define the concave functions v b;pb;qbs.t. for allx2R, v b(x) :=V2 bxV b2x+; p b(x) :=Ploadbx+X g2Gbp g(x); q b(x) :=Qloadbx+X g2Gbq g(x); for each line`2 L, we define the functionh`s.t. for all x2R,h`(x) :=I `2x+. Finally, we introduce for eachk2 Tthe concave multivariate functionfk, s.t. for all= (;; ;;;)2RN, f k() := minfkmin(Ak());0g;quotesdbs_dbs24.pdfusesText_30

[PDF] certification officielle au format PDF

[PDF] Certification OHSAS 18001 - Support Technique

[PDF] CERTIFICATION OHSAS 18001 : 2007

[PDF] Certification PHP

[PDF] certification pmp - Logo Tenstep Tunisia - Gestion De Projet

[PDF] Certification pour le participant pratique libre et pratique acrobatique - Anciens Et Réunions

[PDF] Certification professionnelle de téléphonie d`entreprise en IUT

[PDF] Certification professionnelle d`employé familial

[PDF] Certification Qualité Aéronautique - De L'Automobile Et Des Véhicules

[PDF] Certification Qualité ISO 9001

[PDF] Certification qualité ISO 9001 (version 2008) - France

[PDF] CERTIFICATION RESPONSABLE DE DEVELOPPEMENT

[PDF] Certification sécurité - formation auditeur interne OHSAS 18001 - France

[PDF] Certification selon la norme ISO 13485 - Agrément

[PDF] Certification SH - Fédération Française d`Haltérophilie - France