A spatial branchandcut method for nonconvex QCQP

Authors: Chen Chen Alper Atamtürk Shmuel S Oren

Publish Date: 2016/12/10

Volume: 165, Issue: 2, Pages: 549-577

PDF Link

Abstract

We develop a spatial branchandcut approach for nonconvex quadratically constrained quadratic programs with bounded complex variables CQCQP Linear valid inequalities are added at each node of the search tree to strengthen semidefinite programming relaxations of CQCQP These valid inequalities are derived from the convex hull description of a nonconvex set of 2 times 2 positive semidefinite Hermitian matrices subject to a rankone constraint We propose branching rules based on an alternative to the rankone constraint that allows for local measurement of constraint violation Closedform bound tightening procedures are used to reduce the domain of the problem We apply the algorithm to solve the alternating current optimal power flow problem with complex variables as well as the boxconstrained quadratic programming problem with real variablesThe authors would like to thank Dr Richard P O’Neill of the Federal Energy Regulatory Commission for the initial impetus to study conic relaxations of ACOPF and for helpful comments in early drafts of the paper This research has been supported in part by Federal Energy Regulatory Commission and by Grant FA95501010168 from the Office of Assistant Secretary Defense for Research and Engineering Chen Chen was supported in part by a NSERC PGSD fellowshipSparse positive semidefinite decomposition of a Hermitian matrix Xin mathbb HNtimes N yields a set of index sets C where X csucceq 0 forall cin C iff Xsucceq 0 Note that bigcap forall c in C c = 1ldots N A property of sparse decomposition is that C can be represented with an acyclic graph where each node is an element c of C and an edge between two nodes indicates that at least one index is shared between the corresponding index sets this is known as a clique tree 21 23 The clique tree of a chordal graph can be constructed in time and space linear with respect to the number of edges 14 A matrix can be completed for a certain property if there exist values for the entries not specified by the clique tree such that the fully specified matrix can attain the propertyIf X=xx then text rank Xle 1 Xsucceq 0 and so one direction is obvious Now consider the other direction suppose that X c succeq 0 text rank X cle 1 forall c in C We will use a constructive proof ie we shall construct an x so that xx c = X c forall c in CLet us consider the clique tree corresponding to the chordal graph formed by C Label a terminal node c 1 Since X c 1 has rank one and is positive semidefinite we have that X c 1 = lambda 1c 1 d 1c 1d 1c 1 and so we can set x c 1= sqrtlambda 1c 1d 1c 1 for any normalized principal eigenvector d 1c 1 Now denote a neighbouring node c 2 and consider its corresponding index set with some normalized principal eigenvector d 2c 2 By clique tree property X c 1 and X c 2 share at least one entry say X mm so d 1c 1 m=d 2c 2 m Since eigenvectors of the eigenbasis are only unique up to rotation by complex phase d 2 can be rotated to form hatd 2 so that d 1c 1 m=hatd 2c 2 m ie rotating the eigenvector so that one entry attains a specific angle Then we can set x c 2 = sqrtlambda 1c 2hatd 2 where x mm the shared entry of x c 1x c 2 retains the same value The remaining elements of x can be found by proceeding through neighbours in the same manner with the acyclic property ensuring that each element of x is set once square This relies on a generalization of the fact that in ACOPF and in load flow the bus angles of any solution can be scaled up or down by constants From the proposition it immediately follows that in the alternative rank condition only the 2times 2 principal minors related to the submatrices X c need to be considered and so valid inequalities 3a and 3b can be applied in a sparse fashionVariables and data The decision variables used in LACOPF are nodal powers P+jQ in mathbb Cn a Hermitian decision matrix representing the outer product of nodal voltages W+imath T in mathbb Hntimes n and power to and from buses respectively across branches P f+jQ fP t+jQ t in mathbb Ck All other parameters are fixed data convex costs c 0 in mathbb R c 1 in mathbb RNc 2 in mathbb R +N load D P+jD Q in mathbb Cn admittance matrices Y in mathbb Cntimes n Y fY t in mathbb Cktimes n voltage magnitude limits Vmin Vmax in mathbb Rn phase angle limits theta min theta max in mathbb Rk generator limits Pmin +jQmin Pmax +jQmax in mathbb Cn and line limits Smax in mathbb R ++n Y=G+jB is the bus admittance matrix and Y f=G f+jB fY t=G t+jB t are branch admittances corresponding to ‘from’ and ‘to’ nodes respectively Admittance is composed of conductance G and susceptance B For a branch r from m to n the r m entry of C f in mathbb Rktimes n and the r n entry of C t in mathbb Rktimes n are 1 all unconnected entries in those matrices are 0 50Objective and constraints The objective is to minimize the cost of real power generation where P+PD is the net generation of real nodal power Constraints 16b and 16c are the power flow equations relating nodal power to nodal voltage Constraints 16d and 16e model demand and generation limits Constraint 16f bounds voltage magnitudes Constraint 16g bounds phase angle differences between buses Constraints 16h to 16k are the branch power flow equations Constraints 16l and 16m constrain apparent power across lines We will also consider other types of line limits but omit them here for brevity Constraints 16n and 16o ensure that W+imath T can represent the outer product of nodal voltages 31SDP relaxation In LACOPF only the rank constraint 16o is nonconvex and dropping it gives a convex relaxation RACOPF This primal relaxation approach was first applied to ACOPF by Bai et al 6 and the conic dual formulation was first considered by Lavaei and Low 31 Note that in ACOPF the bounds L ijU ij ine j are specified as angle bounds in polar coordinates ie L ij=tan theta min ijU ij=tan theta max ij

Keywords: